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 ...
- 6,063
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 ...
- 13.1k
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-...
- 13.1k
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 ...
- 2,305
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 ...
- 1,702
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 ...
- 6,063
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.
...
- 606
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 ...
- 3,459
13
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 ...
- 2,013
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.
...
- 5,909
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 ...
- 801
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 ...
- 211
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 ...
- 11.9k
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/...
- 516
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 ...
- 1,548
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-...
- 2,495
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,...
- 6,352
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 ...
- 13.1k
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$ ...
- 2,705
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 ...
- 3,396
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 (...
- 13.1k
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 ...
- 3,635
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 ...
- 12.9k
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 ...
- 1,482
8
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 ...
- 1,549
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 ...
- 3,396
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 ...
- 11.9k
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 ...
- 30.4k
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 ...
- 3,459
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)$ ...
- 3,975
Only top scored, non community-wiki answers of a minimum length are eligible