# Tag Info

21

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 are asking whether P-vs-NP is contained within OR (although the body of your question does not). I would not say that P-vs-NP is contained within OR; rather, it ...

19

The ellipsoid method is polynomial for the same reason that you cannot fold a piece of paper 103 times: exponential growth! Because the formal proof is already in Khachiyan (1980), I will try to give a more informal and intuitive explanation. Please forgive my simplifications for the sake of clarity. Consider a linear program. That is, we want to minimize a ...

16

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-academic) O.R. people are not necessarily fixated on it. In some circles, NP Hard is essentially considered to mean unsolvable. However, there are several ...

14

Feels like you are asking two things, tractability of convex problems and convexity of integer problems. A first order approximation is that convex programs are tractable, .i.e., most problems you can think of as a layman in the field that are convex, are (probably) tractable to solve. That's why you would be told that in an introductory course on convex ...

14

For an introduction to complexity theory, see this answer. A problem is NP-complete if it is both in NP and it is NP-hard. Only decision problems are in NP. Hence, if one considers MILP as a decision or feasibility problem, it is correct to say that MILP is NP-complete as well as NP-hard. Maximization and minimization problems are not decision problems (...

13

This is an answer to the original question before it was edited (Can a problem move from NP to P). No, if a problem is NP-complete then it is not solvable in polynomial time unless P=NP, which has not been proven yet. Furthermore, if there were any NP-hard problem which would be solvable in polynomial time then (by reduction) it could be used to solve any ...

13

There is no theoretically efficient method, unless P=NP. The Hamiltonian Path Problem is the problem of determining whether there exists a path in an undirected or directed graph that visits each vertex exactly once. This problem is NP-complete (see link). If you could determine the longest path efficiently, you could do so for every starting point and ...

13

Deciding if a given solution to a mixed integer linear program is optimal is coNP-complete. When the answer is “no, it is not optimal” there is an efficiently verifiable witness—a better solution. Minor caveat: This answer assumes that there is a better solution that is efficiently verifiable (which necessitates that it can be represented with a ...

13

First of all, I would say that "fast solvable in practice" is possible also when your remaining problem still is NP-hard. But since you ask specifically for polytime solvability, there are some cases. Most well-known is probably "TU-ness" of your matrix. When you solve a MIP $$\min\{c^tx \mid Ax\geq b, x\in Z^n\times Q^q\}$$ then you will obtain an integer ...

11

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 is a quintessential example of a question belonging to the TCS (theoretical computer science) field. As others have pointed out, a solution of the P vs NP ...

10

Mathematically, mixed-integer programs (MIPs) are non-convex, for the very reason you stated: the set $x \in \{0,1\}$ is inherently non-convex. In fact, for a convex optimization problem (e.g. linear programming), you can find the solution in polynomial time using interior-point methods. The reason the optimization community is going against the pure "...

9

LP can be solved in polynomial time (both in theory and in practice by primal-dual interior-point methods.) MILP is NP-Hard, so it can't be solved in polynomial time unless P=NP. However, MILP can certainly be solved in exponential time by branch and bound.

9

I have used a GAP as a subproblem in a previous project where the aim was to solve the single source capacitated facility location problem. I tried several things in order to speed up the computations, and found that the most effective approach was to use exact knapsack separation from the capacity constraints. That is, I basically solved the dual of the "...

9

Another approach is to include both an exact algorithm (e.g., MIP solver) and a very fast heuristic. If the exact algorithm times out, you can compare its best solution with the solution from the heuristic and return the best one. The advantage of this approach is that the heuristic can be tailored to your specific problem, and therefore might have a better ...

9

If you have enough memory to use the non-limited memory version of BFGS, then, subject to the caveat below that not all BFGS (or LBFGS) implementations are equal, use that in preference to LBFGS (Limited Memory version of BFGS). I.e., a high quality LBFGS implementation may still perform better than a lower quality implementation of BFGS. Not all BFGS ...

9

As observed by Kevin Dalmeijer, you cannot expect an efficient method unless $\sf{P=NP}$. Since you're asking explicitly for dynamic programming: define $C(s,t,V)$ as the longest path from $s$ to $t$ without visiting the vertices in $V$. Values $C$ satisfy \begin{align*} C(s,t,V)= \begin{cases} \max\limits_{u\in N^{-}(t)\setminus V} C(s,u,V\cup\{t\})...

9

This is where decomposition algorithms (specifically Dantzig-Wolfe can be quite useful). My thesis work and subsequent OSS in COIN provides APIs to do this kind of thing: https://projects.coin-or.org/Dip The basic idea is that the oracle is the graph implementation while the side constraints are modeled as the master constraints in the decomposition ...

8

The simple answer is that for large scale problems (1m+ rows and columns) we would use interior point instead of dual simplex. The main challenge is not really the solving algorithm, since interior point has polynomial complexity for LP, it's the implementation challenges, i.e., manipulating matrices that take up massive memory (and sometimes need to be ...

8

As other answers have already noted, this problem is NP-hard. That, however, is not the end of the story. The longest path problem has some positive algorithmic results in the context of parametrized algorithms. The main idea is that even though the problem may be NP-hard in general, we can consider a parameter of the input $k$ and try to develop ...

8

Finding a minimum-cardinality MIS for a linear program is an NP-hard problem in general, see Edoardo Amaldi, Marc E. Pfetsch, and Leslie E. Trotter Jr. On the maximum feasible subsystem problem, IISs and IIS-hypergraphs. Mathematical Programming, 95(3):533–554, 2003. For this reason, commercial solvers such as CPLEX use heuristics to identify small IIS which ...

8

In DP Bertsekas Network Optimization (that can be downloaded for free) there's an exercise at Page 104 (Finding an initial price vector) where you can find a method for solving shortest paths in dynamic graphs. Basically, it resorts to using the price vectors from the first iteration to warm start the method at the second. Many years ago I implemented that ...

8

If variable fixings can be derived automatically (e.g. you specified a constraint saying $2x_1=4$ and maybe another saying $x_1+x_2=1$), those variables will be fixed at known values. A smaller problem will then be solved, and we will restore the values for the fixed variables when we report the solution (e.g. in this case $x_1=2$ and $x_2=-1$). The cost of ...

7

I think there is three angles to attack this problem. A complete solution will probably feature each one of them Large set of (hard) test cases: If you are worried about the hard instances, then I would create a large set of test cases which you can update anytime you find a new one that was difficult. These can be integrated into the build pipeline of your ...

7

You could try to solve it as a min cost flow problem. NetworkX is a package for graph algorithms and has algorithms for this implemented. It can easily be installed via pip install networkx. An minimal working example is given at the bottom of this link: https://networkx.github.io/documentation/networkx-2.4/reference/algorithms/generated/networkx....

7

In general ILP solvers are not as efficient in solving the Maximum Matching problem. A comparison of efficient matching algorithm implementations, as well as an ILP formulation for the Maximum Cardinality Matching Problem and the Minimum Weight perfect matching problem can be found in Figures 5 and 6 of this paper: Dimitrios Michail, Joris Kinable, Barak ...

6

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 context of OR. The basics Before you can even properly understand what "$\mathsf{P}=\mathsf{NP}$" or "$\mathsf{P}\neq \mathsf{NP}$" means, you need to know what ...

6

In the full-dimensional case, I think you can consider $\varepsilon\geq 0$ as an extra continuous variable in order to get your poly-size certificate. Let $$Q=\{(x,\varepsilon)\,:\,Ax+e\varepsilon\leq b, 0\leq\varepsilon\leq1\}.$$ If there is a mixed-integer point in the interior of $P$ then there exists a mixed-integer point of poly-size in $Q$ with \$\...

5

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, software, curricula, legislation, and other forms of code are hard to prove correct without actually executing them to see what happens. The execution may be ...

5

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 which are essentially OR problems, then you can say P = NP. But, the P vs. NP issue is not strictly “under” OR because there are other fields which are ...

5

I think the spanning tree polytope also falls under this category. Computing the minimum spanning tree is easy. However, we would require all the sub-tour elimination constraints (which is exponential in number of vertices) to represent the spanning tree polytope in 0-1 variables as a LP. EDIT: From the comments below, one can find a reference for a ...

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