# Tag Info

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

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

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

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

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

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

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

### 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 ...
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 ...
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/...
Accepted

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

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

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

### 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$ ...
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 ...
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 (...
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 ...
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 ...

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

### 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 ...
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 ...
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 ...
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)$ ...