Great Unsolved Problems in O.R

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?

• Please correct me if I'm wrong, but won't "unsolved" problems be more from a computational/tractability POV as opposed to "not being solvable or yet to be solved"? That is, theoretically you can have a model for the most complex OR problems with many variables and a healthy dose of uncertainty constraints added to the mix. The "unsolvability" would arise primarily through computational constraints, no? As a result unsolvable problems in OR == computationally intractable problems => studies in approximations for lower bounds. What may I be missing?
– PhD
Jul 9 '19 at 18:19
• I've taken the world "unsolved" from the title of the INFORMS session.Then, I am asking about "open problems" in a broad sense. I like the answer by Michael below, but I will be equally happy to see more "computational" oriented answers. Jul 9 '19 at 18:28
• I think the hardest part of your question is that you ask for open problems that "will have a strong impact on other research fields". There are plenty of intriguing open problems and conjectures, but it is often hard to argue that resolving them will really have an impact on other fields. Jul 10 '19 at 9:58

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.

• Thanks Michael for your reply. Before of accepting your answer, I will wait to see if anyone else will show up with other open problems. Jul 9 '19 at 17:19
• Yes, I really hoped more answers would come up to your question, but it's only been a few hours Jul 9 '19 at 17:34
• Hey Michael, I think that the latest results shared by Laura Sanita during MIP2019 prove that the answer to the first question you listed is unfortunately false. Check this slide twitter.com/timoberthold/status/1151127202924302336 Jul 19 '19 at 0:48
• Interesting, but no: From what I understand this only rules out the possibility of a "perfect" pivoting rule with minimum number of steps. We don't need the minimum number of iterations, or even within a constant factor of the minimum. Polynomial pivoting rules are not exluded by this result. Jul 19 '19 at 16:45

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.

• 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.

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

• Can you say briefly what the conjecture is? Jul 21 '19 at 12:45

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

2) Chapter 30 of Approximation Algorithms by Vazirani