Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
More than 10 years ago, there was during an INFORMS annual meeting a session dedicated to “Great Unsolved Problems in O.R.” (you can find a small report of that session on this webpage).
Which are nowadays the most important open problems in O.R. that will have a strong impact on other research fields?
EDIT 13/07/2019: so far the answers are mainly theoretically oriented. Anyone can suggest more computational unsolved/open problems?
Two open problems in linear optimization (which is considered more or less a 'solved' subfield by many):
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.
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.
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:
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.
Here is a list of unsolved (open) problems by R. Weber. The most fascinating ones in my opinion are the following.
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.
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.
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.
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
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
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.
