# Tag Info

## Hot answers tagged linear-programming

Accepted

### Why is Integer Linear Programming in NP?

As you have seen in other sources, the proof that there exists a witness with polynomial size does not exactly fit inside the margin, so to speak. The proof I know of (from the book I mention below) ...
• 8,323
Accepted

### Does linear programming admit a strongly polynomial-time algorithm?

This problem is still open. See for example Wikipedia, which while not a dependable source in general, will probably be updated if a strongly polynomial time algorithm is ever found.
• 278k

### Finding all solutions to an integer linear programming (ILP) problem

"Linear programming" is an optimisation problem. The problem that you are trying to solve is to count lattice points inside a finite convex rational polytope. This problem has a polynomial-time ...
• 22.7k
Accepted

### Some Questions related to Linear programming

Let me answer your questions one by one: The solution of the linear program $\max x$ is $\infty$. This is an example with not finite optimum solution. This is the same as just having no optimum ...
• 278k
Accepted

### Project to nearest point in convex polytope

A quadratic program is an optimization problem where the goal is to minimize $y^T Q y + c^T y$ subject to $A y \leq b$. If $Q$ is positive definite, then this is a convex quadratic program and we can ...
• 126
Accepted

### Why does this not prove $P\neq NP$?

What Fiorini et al. show is the following: The TSP polytope $P_n$ over $n$ points is a polytope in $\binom{n}{2}$ dimensions whose vertices correspond to all Hamiltonian cycles in $K_n$ (the complete ...
• 278k
Accepted

### How to check if a specific ILP problem can be solved in polynomial time or not?

First of all, let me start by making clear that the notion of 'solvable in polynomial time' is something defined on a class of problem instances. It makes no sense to speak of polynomial time for a ...
• 8,323

• 278k

### Why is Integer Linear Programming in NP?

The paper "On the Complexity of Integer Programming" from Papadimitriou has a very compact (2 and a half pages counting from abstract) proof. It only needs the common knowledge about dual ...
• 709

### Why can't we round results of linear programming to get integer programming?

Here is a 2d region where rounding the optimal continuous solution (top right) will always give an invalid integer solution: Here is a 2d region where rounding the optimal continuous solution (green ...
Accepted

### Given 2 sets of n points: minimize sum of traveled distances

As mentioned in the problem statement, this is the Assignment Problem (minimum weight bipartite matching) where it is known that the weights are the Euclidean distances. There have been several ...
• 507
Accepted

### Linear programming restricted to rational coefficients

In order to consider the computational complexity of linear programming, we need a way of encoding an instance of linear programming as a string. In particular, we need to fix an encoding of the ...
• 278k

### Is 0-1 integer linear programming with only equality constraints NP-Hard?

Consider the Maximum Independent Set problem ($\mathcal{NP}$-hard): given a graph $G=(V,E)$, find the maximum independent set in $G$, i.e., the subset of vertices $I \subseteq V$ such that every two ...
• 1,096

### Max flow with priorities

First, build an algorithm to solve the following problem: Given a threshold $t$ and a flow graph $G$, find the solution that maximizes $N_2$, subject to the requirement that $N_1 \ge t$. That ...
• 163k
Accepted

• 278k
Accepted

### Standard ILP Formulation of Travelling salesman problem: Purpose of subtour elimination constraints?

Consider this example: Every vertex has one incoming and one outgoing edge, so it is not prevented by the first two constraints. It is however prevented by the third constraint, as if you take any of ...
• 2,542