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) ...
- 8,462
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 ...
- 281k
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 ...
- 8,462
6
votes
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,126
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 $...
- 29.8k
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 ...
- 281k
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 ...
- 2,368
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 ...
- 8,462
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 ...
- 281k
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 ...
- 719
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 ...
- 281k
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 ...
- 151
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.♦
- 169k
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 ...
- 416
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 ...
- 416
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 ...
- 281k
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.♦
- 169k
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 ...
- 281k
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 ...
- 2,552
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 ...
- 281k
4
votes
Accepted
Complexity of linear programming
There exist polynomial time algorithms for solving linear programs. These include the ellipsoid algorithm and interior-point methods. See Wikipedia.
- 281k
4
votes
Complexity of linear programming
It's because there are other algorithms (like interior point methods) which run in polynomial time for solving the problem. Even with that being said, it is perfectly possible that the simplex method ...
- 23k
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, ...
- 495
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 ...
- 29.8k
4
votes
Accepted
Learn a system of linear inequalities given solutions
I suspect that you can just compute the convex hull of the set of feasible points and, for each edge of the hull, write down the equation of the semi-plane that includes all feasible points and such ...
- 29.8k
4
votes
Accepted
How to get the highest score in this game?
Let $a_i$, $b_i$, $c_i$ be the maximum number of points that you can get by picking A[i], B[i], C[i] in the last round.
Obviously $a_1 = A[1]$, $b_1 = B[1]$, $c_1 = C[1]$.
And equally obvious is that $...
- 32.6k
4
votes
Prove that a quadratically-constrained linear program (QCLP) is NP-Complete
You can force a variable $x_i$ to be binary introducing a new variable $y_i$ and adding the quadratic constraint $y_i^2 = 1$ (forcing $y_i$ to be either $1$ or $-1$) and the linear constraint $2 x_i = ...
- 29.8k
4
votes
Accepted
Are integer linear *feasibility* problems NP-hard?
Feasibility of integer linear programming (ILP) is also NP-hard.
(Why? See https://cs.stackexchange.com/a/29916/755, Is 0-1 integer linear programming NP-hard when $c^T$ is the all-ones vector?, ...
D.W.♦
- 169k
4
votes
Assignment problem, but minimise the greatest individual cost, rather than the aggregate cost
The property described is sometimes known as "min max fairness" (alternatively/equivalently "minimax", "max-min", etc...), see for example [1], [2], [3]. For assignment ...
- 2,350
Only top scored, non community-wiki answers of a minimum length are eligible