Skip to main content
Share Your Experience: Take the 2024 Developer Survey
19 votes
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) ...
Discrete lizard's user avatar
  • 8,248
12 votes
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.
Yuval Filmus's user avatar
9 votes

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 ...
Pseudonym's user avatar
  • 22.2k
9 votes
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 ...
Yuval Filmus's user avatar
8 votes
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 ...
xeqql's user avatar
  • 126
8 votes
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 ...
Yuval Filmus's user avatar
7 votes
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 ...
Discrete lizard's user avatar
  • 8,248
6 votes

Find max total revenue in a directed graph

Your problem can be solved by reducing it to a min-cost max-flow problem where a unit of flow represents one unit of commodity. A negative cost represents a profit. Create a directed graph containing $...
Steven's user avatar
  • 29.5k
5 votes
Accepted

Converting If-else condition to Linear Programming

This can be expressed with just the equation $X=Y$. Since $X,Y$ are zero-or-one variables, the only possible assignments that are consistent with your condition are $X=Y=0$ and $X=Y=1$. See Express ...
D.W.'s user avatar
  • 161k
5 votes
Accepted

Finding a minimal width strip which encloses a set of points in the plane

Take the convex hull of your set of points. Then use "rotating calipers" to find the optimal strip. What is needed here to make this work is a lemma that characterizes a potentially optimal solution: ...
Joseph O'Rourke's user avatar
5 votes

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

What you're proposing isn't "a linear program for TSP", so it doesn't come into the scope of the proof. You've observed that, if $\mathrm{P=NP}$, then TSP can be reduced to polynomial-sized linear ...
David Richerby's user avatar
5 votes
Accepted

Fractional vertex cover number may not be feasible? Very confusing!

The linear program defining the minimum fractional vertex cover always has an optimal solution. The fact that some linear programs are infeasible or unbounded doesn’t mean that every linear program is ...
Yuval Filmus's user avatar
5 votes
Accepted

Reducing linear programming to positive linear programming

You can add a variable $y$ and a linear equality $y=c^Tx+c_0$ for some $c_0$. Then, the original problem is equivalent to maximizing $y$ in the new system. Except for the condition $y\geq 0$. That ...
kne's user avatar
  • 2,254
5 votes
Accepted

How to calculate the dimension of a convex polyhedron?

While there are probably much more efficient approaches, the following method can be used to compute the dimension in polynomial time, and is not too complicated. Implicit inequalities The dimension ...
Discrete lizard's user avatar
  • 8,248
5 votes
Accepted

Prove that a quadratically-constrained linear program (QCLP) is NP-Complete

Given a graph $G$ and a parameter $k$, consider the linear program with a variable $x_v$ for each vertex $v$, and the following constraints: $x_v \leq 1$ for all vertices $v$ $\sum_v x_v \ge k$ $x_u ...
Yuval Filmus's user avatar
5 votes

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 ...
Sudix's user avatar
  • 709
4 votes

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 ...
Mingwei Samuel's user avatar
4 votes
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 ...
tjhighley's user avatar
  • 507
4 votes
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 ...
Yuval Filmus's user avatar
4 votes

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 ...
D.W.'s user avatar
  • 161k
4 votes
Accepted

Expressing conditional in linear program

If you know the maximum value of $B$ then you can easily express all comparisons as described here: https://blog.adamfurmanek.pl/2015/09/12/ilp-part-4/ In your case you need the following: $0 \le -B ...
user1543037's user avatar
4 votes
Accepted

How do you proceed if your milp is not solvable

It's hard to specify one approach because it depends on your needs. From my experience I can suggest the following: Precision Typical solvers report solutions as "optimal" using gap parameters ...
user1543037's user avatar
4 votes
Accepted

Maximum matching using linear programming

This approach is described by Grötschel, Lovász and Schrijver in their paper The ellipsoid method and its consequences in combinatorial optimization, as well as in their book Geometric algorithms and ...
Yuval Filmus's user avatar
4 votes

Boolean variable that captures whether an inequality holds

Add the inequalities $$\begin{align*} a_1 x_1 + \dots + a_n x_n &\ge b - M (1-y)\\ a_1 x_1 + \dots + a_n x_n &< b + M y, \end{align*}$$ where $M$ is chosen sufficiently large. Why does ...
D.W.'s user avatar
  • 161k
4 votes
Accepted

Linear programs with strict inequalities and supremum objectives

Suppose that the supremum of a continuous function $f(x)$ subject to $Ax < b$ is $c$, and assume furthermore that the constraints imply a bound on $\|x\|_\infty$. Thus there is a sequence of ...
Yuval Filmus's user avatar
4 votes
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 ...
Tassle's user avatar
  • 2,522
4 votes

Linear programming over a finite field

Your problem, solving a system of linear equations, can be solved using an ancient algorithm, Gaussian elimination, which works over all fields. Note that linear programming is more general, allowing ...
Yuval Filmus's user avatar
4 votes

Linear Programming Problem - what is feasible size for solution on a PC

For continuous LP, problems with millions of nonzeros are solved routinely. I'd expect problems with 10 millions nonzeros to be solvable, barring numerical issues. You can find some benchmarks here, ...
Ggouvine's user avatar
  • 485
4 votes

Expressing a constraint of the form $\max(x_1,x_2) \ge q$ in a linear program

No. If you could do that in linear programming then you could force a variable to have binary values, so you'd be able to solve integer linear programs using LP solvers. Indeed, we can simulate $x \in ...
Steven's user avatar
  • 29.5k

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