Skip to main content
27 votes

Great Unsolved Problems in O.R

Two open problems in linear optimization (which is considered more or less a 'solved' subfield by many): Is there a pivoting strategy for the Simplex algorithm guaranteeing to find an optimal vertex ...
Michael Feldmeier's user avatar
21 votes
Accepted

Does the problem of P vs NP come under the category of Operational Research?

The short answer is yes, operations researchers care a lot about P vs NP. We deal in algorithms, and the complexity of those algorithms matters a lot to us. The title of your question suggests you ...
LarrySnyder610's user avatar
17 votes

Great Unsolved Problems in O.R

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 \...
EhsanK's user avatar
  • 5,864
16 votes

Does the problem of P vs NP come under the category of Operational Research?

P vs. NP may come "under" the category of Operational Research (O.R.). But unlike theoretical computer science and algorithm analysis, in which P vs. NP may be a be all and end all, practical (non-...
Mark L. Stone's user avatar
16 votes

Great Unsolved Problems in O.R

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 "...
LarrySnyder610's user avatar
12 votes

Great Unsolved Problems in O.R

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 ...
TheSimpliFire's user avatar
  • 5,412
11 votes

Does the problem of P vs NP come under the category of Operational Research?

This goes against the grain of the other answers here, but I do not believe that the P vs NP problem would naturally be categorized as a question in operations research. Instead, I would argue that it ...
pre-kidney's user avatar
10 votes

Great Unsolved Problems in O.R

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 ...
YukiJ's user avatar
  • 2,023
8 votes

Great Unsolved Problems in O.R

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
Jeff Linderoth's user avatar
7 votes

Are there any real-world problems where quadratization helps to solve something that couldn't have been solved without quadratization?

A recent paper by Quantum Computing Inc people is showing experiments on graph partitioning where QUBO approaches lead to better results than the state of the art. Here is the paper: https://arxiv.org/...
Hexaly's user avatar
  • 2,986
7 votes

Great Unsolved Problems in O.R

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) ...
ydubey7's user avatar
  • 579
6 votes

Great Unsolved Problems in O.R

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 ...
Simon's user avatar
  • 1,142
6 votes

Does the problem of P vs NP come under the category of Operational Research?

While other answers have focused on the question whether "P vs. NP" can be considered to be in OR, I will instead look at the parts about this topic that I think are most relevant to study in the ...
Discrete lizard's user avatar
5 votes

Are there any real-world problems where quadratization helps to solve something that couldn't have been solved without quadratization?

Are there any cases where quadratization is an essential component of a state-of-the-art algorithm for a real-world problem? Yes. Quadratization has been used in pseudo-Boolean optimization (...
Rob's user avatar
  • 2,120
5 votes

Does the problem of P vs NP come under the category of Operational Research?

The other answers are good. I'd add that "P vs. NP" spans OR, CS, project management, education, HR, governance, and several other related fields. Procedures, algorithms, project and business plans, ...
stevegt's user avatar
  • 151
5 votes

Does the problem of P vs NP come under the category of Operational Research?

As mentioned by others, OR is definitely involved in the P vs. NP issue. If you can find a polynomial time algorithm to solve the Quadratic Assignment Problem or the TSP which Marco mentioned, both of ...
dxb's user avatar
  • 1,799

Only top scored, non community-wiki answers of a minimum length are eligible