O.R中尚未解決的重大問題


42

10多年前,在INFORMS年度會議期間,舉行了一場專門討論" 未解決的重大問題"的會議。"(您可以在this webpage上找到該會話的小報告)。

當今是O.R.中最重要的未解決問題。會對其他研究領域產生重大影響?

編輯13/07/2019 :到目前為止,答案主要是理論上的。任何人都可以提出更多計算性未解決/未解決的問題

25

Two open problems in linear optimization (which is considered more or less a 'solved' subfield by many):

  1. Is there a pivoting strategy for the Simplex algorithm guaranteeing to find an optimal vertex in a polynomial number of steps?

This is related to the Hirsch conjecture. The diameter of a polytope is a theoretical lower bound on the Simplex iterations necessary.

The average number of iterations appears to have been proven to be polynomial, and there are various pivoting strategies with expected polynomial number of iterations, but the worst case for all strategies still appears to be exponential.

  1. Can convergence in less than $\sqrt n$ steps be guaranteed for any interior point method for linear programming?

It can be proved that interior point methods converge in $O(\sqrt n \ln \frac{1}{\epsilon})$ iterations (see for example Gondzio 2012). In practice they are observed to converge faster (in the order of around $O(\ln (n+m))$ iterations. But (to the best of my knowledge) no better bound has been proven so far.


14

Problem #9 in the list of Smale's Problems states:

The linear programming problem: Find a strongly-polynomial time algorithm which for given matrix $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$ decides whether there exists $x \in \mathbb{R}^n$ with $Ax \ge b$.

If interested in other (not-necessarily OR but in related fields), you can check the following pages too:


9

Here is a list of unsolved (open) problems by R. Weber. The most fascinating ones in my opinion are the following.

  • Search for a moving target in discrete time

The discrete-time version of this problem is still unsolved. There have been partial solutions, but no solution for all possible values of the model parameters.

  • Non-preemptive release of stochastic jobs to uniform machines

I make the conjecture that an optimal policy has the property that whenever it assigns a job to an available processor, it makes the assignment to the fastest available processor. Moreover, there exist thresholds, one for each state of the processors and decreasing in the state (seen as a boolean vector, in which busy and idle processors are indicated by 1 and 0, respectively), such that an optimal policy is to assign a job to an available processor if, and only if, the number of jobs in the buffer exceeds the relevant threshold for the present state of the processors.


12

In inventory theory, I would argue that the most significant unsolved question is:

What is the optimal inventory policy for a multi-echelon inventory system with at least one distribution node?

A "distribution node" is a node that has at least 2 successors. For serial systems (in which every node has at most one successor and at most one predecessor) and for assembly systems (in which every node has at most one successor), it is well known that a base-stock policy is optimal. But for systems with distribution nodes (which could include one-warehouse multiple-retailer systems, general distribution systems, general tree systems, etc.), the optimal policy is unknown. The primary complication is that in addition to deciding when and how much to order, we also have to decide how to allocate inventory to the successor nodes when the current inventory is insufficient to meet their combined demand.

A related question is:

In a multi-echelon inventory system with at least one distribution node, if we assume each node follows a base-stock ordering policy and a first-come, first-served allocation policy (whether or not such policies are actually optimal), how can we efficiently optimize the base-stock levels at all nodes?

This one turns out to be hard, too.


7

The following books on approximation algorithms each have a chapter dedicated to open problems:

1) Chapter 17 of The Design of Approximation Algorithms by Williamson and Shmoys (freely available)

2) Chapter 30 of Approximation Algorithms by Vazirani


7

Even though the following problem is usually not listed as a typical OR-problem, its solution might (depending on how the solution looks like) have a HUGE effect on OR algorithms. I am speaking of nothing less but the P vs. NP-problem, which is one of the most important open problems in all of mathematics (and computer science). It is also listed as one of the Millenium Problems and its solution would bring the person to solve it $1,000,000 from the Clay Mathematics Institute.

The problem ask whether the two formal classes P and NP are the same or not, i.e. whether P=NP or P$\not =$NP. While the inclusion P$\subseteq$NP is rather trivial, the other inclusion is not. In fact, it is widely believed nowadays that P$\not=$NP is true (c.f. the latest P =? NP Poll).

If, however, it would turn out that P=NP, then this would have a tremendous effect on OR because this would imply that all those NP-complete problems which people from OR like to deal with (TSP, Graph Coloring, Integer Programming in general...) would allow polynomial-time solution algorithms.

If the solution were P$\not =$NP then this would not have such a big effect on OR as P=NP. Yet, for people working in OR it would nevertheless be interesting to know the final solution to the P vs. NP question.


8

I personally like the 4/3 conjecture for Metric or Euclidean TSP: http://himtp.or.uni-bonn.de/index.php/The_4/3-Conjecture_for_Eulidean_TSP


6

Personally, I feel that solving bilevel MILPs and non-convex quadratic problems is not yet practically possible.

While there is some literature on bilevel MIPLPs (e.g. Fischetti, Matteo, et al. "A new general-purpose algorithm for mixed-integer bilevel linear programs."), this work has not yet arrived in robust (commercial) off-the-shelf solvers. But these bilevel problems have many practical applications, quoting from the same paper:

Bilevel optimization problems are very challenging optimization models arising in many important practical contexts, including pricing mechanisms in the energy sector, airline and telecommunication industry, transportation networks, optimal expansion of gas networks, critical infrastructure defense, and machine learning.

For the relevance and discussion of nonconvex QP, this OR answer is very insightful.