22
votes
Express boolean logic operations in zero-one integer linear programming (ILP)
The logical AND relation can be modeled in one range constraint
instead of three constraints (as in the other solution).
So instead of the three constraints
$$y_1\geq x_1+x_2−1,\qquad y_1\leq x_1,\...
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.
- 273k
10
votes
Linear programming with absolute values
All constraints in a linear program are convex (if $x,y$ satisfy the constraints, then $tx+(1-t)y$ also does for all $0 \leq t \leq 1$). The constraint $|a|+b > 3$ is not convex, since $(4,0)$ and $...
- 273k
9
votes
Why can't we round results of linear programming to get integer programming?
In $\mathbb R$, one can simply round down or round up to obtain an element of $\mathbb Z$. Only two choices!
However, in $\mathbb R^n$, one has $2^n$ ways of rounding to obtain an element of the ...
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 ...
- 19.9k
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 ...
- 273k
8
votes
Accepted
Linear programming with absolute values
I've found out a very interesting document that answers my question: http://lpsolve.sourceforge.net/5.5/absolute.htm It's about integer programming and it covers all possible cases I think. See ...
- 301
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 ...
- 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 ...
- 273k
7
votes
Accepted
Cast to boolean, for integer linear programming
I think I can do it with one extra binary variable $\delta \in \{0,1\}$:
$$
-100y \le x \le 100 y
$$
$$
0.001y-100.001\delta \le x \le -0.001y+100.001 (1-\delta)
$$
Update
This assumes $x$ is a ...
- 271
7
votes
Accepted
Why can't we round results of linear programming to get integer programming?
If there are only constraints that place a lower bound on the number of trucks, but no constraints that place an upper limit on the number of trucks, then of course you can round up. That will still ...
D.W.♦
- 150k
6
votes
Accepted
Complexity of solving LP with a non-linear growth in variables/constraints
The running time of algorithms for linear programming depends not only on the number of variables but also, unsurprisingly, on the number of constraints. This is hidden in the parameter $L$ which is ...
- 273k
6
votes
Accepted
Unfeasible linear program becomes feasible if a variable is removed
There is (unless $P=NP$) no polynomial time algorithm for this problem, since the problem is $NP$-hard by reduction from Subset Sum. If you set $l_i=u_i$ then the problem is to determine if there is a ...
- 13.1k
6
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 ...
- 7,268
5
votes
Accepted
Are some Integer programming formulations completely useless for relaxation?
Yes, some IP formulations are less useful than others. The technique used to show that an LP relaxation can only be so good is showing integrality gaps. For a minimization problem, an integrality gap ...
- 273k
5
votes
Can you generate random linear programming problems?
Sure, of course you can create random linear programming problems. Why not?
Yes, in general, you can usually verify the solution to a linear programming problem faster than you can find the solution....
D.W.♦
- 150k
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: ...
- 854
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.♦
- 150k
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 ...
- 81k
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 ...
- 273k
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,144
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 ...
- 273k
4
votes
Accepted
Time complexity of linear program?
Answering your first question, whether you can tighten the analysis depends on the function $T$. If $T$ is constant, for example, then the analysis is tight; if $T$ is a polynomial, then the analysis ...
- 273k
4
votes
Accepted
Modeling $(x > 0 \wedge y > 0) \Leftrightarrow z > 0$ in a linear program: impossible?
A linear program consists of a finite collection of inequalities of the form $\sum_i a_ix_i \leq b_i$. Each such inequality defines a closed convex set, and so their intersection defines a closed ...
- 273k
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
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 ...
- 497
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 ...
- 273k
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.♦
- 150k
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 ...
- 366
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 ...
- 366
Only top scored, non community-wiki answers of a minimum length are eligible