Skip to main content
22 votes
Accepted

Why is the Ellipsoid Method of polynomial complexity?

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 ...
Kevin Dalmeijer'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
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
Accepted

MILP: is it NP-complete or NP-hard?

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 ...
Rolf van Lieshout's user avatar
15 votes

Can an integer optimization problem be convex?

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 ...
Johan Löfberg's user avatar
14 votes

Are there NP hard problems solved in P time?

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

Are there any efficient algorithms to solve the longest path problem in networks with cycles?

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 ...
Kevin Dalmeijer's user avatar
13 votes
Accepted

Complexity of verifying optimality in (mixed) integer programming

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. ...
Austin Buchanan's user avatar
13 votes

Can an integer optimization problem be convex?

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 ...
Richard's user avatar
  • 3,469
13 votes
Accepted

Polynomially solvable cases of zero-one programming

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. ...
Marco Lübbecke's user avatar
11 votes

Complexity of LP and MILP Problems?

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 ...
Brian Borchers's user avatar
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
Accepted

State-of-the-art algorithms for solving linear programs

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 ...
Nikos Kazazakis's user avatar
10 votes
Accepted

Can a generic ILP solver find graph matchings as fast as a specialized algorithm?

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/...
Matthew Galati's user avatar
10 votes
Accepted

RAM requirement for optimization problems

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 ...
mattmilten's user avatar
  • 1,703
10 votes

Optimization Solution Framework

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-...
fontanf's user avatar
  • 2,623
9 votes

Generalized Assignment Problem as the sub-problem

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,...
Sune's user avatar
  • 6,657
9 votes

How do we decide/plan an SLA for an NP-hard optimization process running in production?

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

Are there any efficient algorithms to solve the longest path problem in networks with cycles?

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$ ...
Marcus Ritt's user avatar
  • 2,745
9 votes
Accepted

Computational complexity to compute an IIS

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 ...
Joris Kinable's user avatar
9 votes
Accepted

When is the original BFGS algorithm still better than the Limited-Memory version?

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 (...
Mark L. Stone's user avatar
9 votes
Accepted

Re-calculating shortest path in slightly altered graph

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 ...
Claudio Contardo's user avatar
9 votes
Accepted

Fast algorithm for Transportation Problem in Python?

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 ...
user3680510's user avatar
  • 3,655
9 votes
Accepted

Optimization Solution Framework

You have to keep in mind that MIPs can return the optimal solution, provided enough computation time is given. So if time is not an issue, I would always go for a MIP. Also, MIPs are more flexible in ...
Kuifje's user avatar
  • 13.6k
8 votes

Are there any efficient algorithms to solve the longest path problem in networks with cycles?

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 ...
Discrete lizard's user avatar
8 votes

Can a generic ILP solver find graph matchings as fast as a specialized algorithm?

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 ...
Joris Kinable's user avatar
8 votes
Accepted

Effect of 'unused' variables on the result and runtime of optimization algorithms

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 ...
Nikos Kazazakis's user avatar
8 votes
Accepted

A clustering problem with 0 or 1 distances for minimizing the summation of distances

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 ...
RobPratt's user avatar
  • 33.1k
7 votes

How do we decide/plan an SLA for an NP-hard optimization process running in production?

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 ...
Richard's user avatar
  • 3,469
7 votes
Accepted

Complexity of navigation with google maps

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)$ ...
worldsmithhelper's user avatar

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