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

10

Easy answer: 64 GB With 24 threads (is this already including hyperthreads? Maybe not, so we are actually talking about 48 threads...) you'll have about 2 and a half GB for every thread - that's not very much if you really want to make good use of those threads. So going for 32 GB is definitely the wrong move and you'll most likely regret this choice. AFAIK, ...

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

8

This is a variant of the minimum $k$-cut problem. The node set is $\mathbb{X}$, the edge weights are $1-d(x,y)$, and $k=S$. Also related to the wedding planner problem, where $\mathbb{X}$ is the set of guests, $S$ is the number of tables, and $H$ is the maximum number of guests per table. Here, $d(x,y)$ measures whether $x$ and $y$ dislike each other. See ...

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

7

The prototypical graph search algorithm Dijkstra's algorithm for finding the shortest paths between nodes in a graph which works for unbounded non-negative weights has a time complexity for $O(|V|^2)$ where $|V|$ is the number of nodes/vertices in a graph which is in $P$. There are special cases where further knowledge (such as heuristics) or the graph ...

7

In academic publications (where the point is to present a model and possibly computational scheme to solve an actual problem) I typically do not bother to count the constraints. First, the reader can do it themselves from the algebraic formulation. Second, the reader is more interested in whether "realistic" instances of problem are solvable with &...

7

Here are my notes about the various discrete optimization methods. Combinatorial branch-and-bound Manual implementation Provides a bound Works well when the bound is good Rarely used nowadays Mixed-Integer (Non)-Linear Programming Model-and-run, very good commercial solvers Provides a bound Works well when the (N)LP relaxation (possibly with cuts) is ...

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