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,\...
11
votes
Accepted
Is weighted XOR-SAT NP-hard?
A classical result of Berlekamp, McEliece, and van Tilborg shows that the following problem, maximum likelihood decoding, is NP-complete: given a matrix $A$ and a vector $b$ over $\mathbb{F}_2$, and ...
- 274k
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 $...
- 274k
10
votes
Accepted
How to partition a set into a given number of disjoint subsets subject to some conditions?
This problem is NP-hard by reduction from Vertex Cover.
In the Vertex Cover problem, we are given a graph $G = (V, E)$ and a number $r$, and our task is to determine whether there is some subset $U$ ...
- 5,354
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 ...
- 20.2k
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
Are there practical methods for solving ILP?
Some ILPs can be solved rapidly (to an exact solution) in practice; some cannot. Usually when we are talking about solving an ILP, we are looking for an exact solution, though some ILP solvers can ...
D.W.♦
- 152k
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.♦
- 152k
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 ...
- 7,568
6
votes
Reducing Zero-One Integer Linear Programming problem to SAT
The existence of such a reduction follows immediately from the Cook-Levin theorem, which guarantees that you can reduce any problem in NP to SAT and describes explicitly one way to do it. Just work ...
D.W.♦
- 152k
6
votes
Does integer programming $\in$ NP imply $NP=CoNP$?
The decision problem version of integer linear programming is known to be in NP. In particular, determining whether an integer linear program has a feasible solution is in NP. It is known that if an ...
D.W.♦
- 152k
6
votes
Accepted
Efficient algorithm for simple constraint satisfaction problem
There is unlikely to be any efficient algorithm.
Your first class of constraints are monotone exactly-1 CNF clauses. Your second class of constraints are monotone CNF clauses. The monotone part ...
D.W.♦
- 152k
6
votes
Are there competitions for integer programming?
There are no competitions targeting general integer programming or mixed integer programming, but there are (or were) benchmarks, such as the MIPLIB (linear) and the MINLPLIB (nonlinear).
There are ...
- 465
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 ...
- 274k
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.♦
- 152k
5
votes
Accepted
Boolean variable true iff equation is satisfied in ILP
You can do this by introducing the two inequalities
$$x_1 \le x_2 + M (1-y)$$
and
$$x_1 > x_2 - M y.$$
The former encodes the requirement $y=1 \implies x_1 \le x_2$ (you can see that if $y=1$, ...
D.W.♦
- 152k
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.♦
- 152k
5
votes
Accepted
Does integer programming $\in$ NP imply $NP=CoNP$?
The notion of duality suggested by the discrete Farkas lemma found in Lasserre's paper does not correspond to an integer program. There is a notion of duality for integer programs (see for example ...
- 274k
5
votes
Accepted
Are there competitions for integer programming?
There are competitions for constraint satisfaction solvers. Some problems there can be readily translated to IP solvers as well. See e.g., MiniZinc challenge which has taken place yearly since 2008 or ...
- 22.4k
4
votes
Accepted
Fastest known complexity for combinatorial ILP algorithm?
From what I can tell by searching, the definite survey seems to be:
Aardal, Karen, Robert Weismantel, and Laurence A. Wolsey. "Non-standard approaches to integer programming." Discrete Applied ...
- 22.4k
4
votes
How to reduce the low-rank matrix completion problem to integer programming?
Simplifying the problem:
Given
a positive integer $r$
positive integers $m, n \geq 2$
a partial binary matrix $\mathrm A \in \{*, 0,1\}^{m \times n}$ (where $*$ denotes an unknown entry)...
4
votes
Poly-time reduction from ILP to SAT?
It is some sort of necro-answer to already answered and accepted question, but I want to note, that there is really easier way.
Consider you have one of inequalities like this:
$5*x_1 + 2*x_2 + 3*...
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
Reducing Zero-One Integer Linear Programming problem to SAT
There are two variants to perform the encoding. I am assuming that you want the SAT instance in Conjunctive Normal form, as otherwise your ROBDD can be mapped pretty directly to a Boolean formula of ...
- 2,692
4
votes
Boolean variable true iff equation is satisfied in ILP
You could add a constant $0<A<M$ and then you add this constraint:
$$A-y(A+M)\leqslant x_1-x_2\leqslant M(1-y).$$
If $y=1$ then you are left with
$$-M\leqslant x_1-x_2\leqslant 0,$$ which ...
- 693
4
votes
Accepted
Maximizing the boolean combination of given real numbers
Maybe there is something I do not understand in your question, but the way it is formulated it seems that the set of solutions is:
set $b_i=1$ if $x_i > 0$
set $b_i=0$ if $x_i < 0$
all others $...
- 348
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 ...
- 376
Only top scored, non community-wiki answers of a minimum length are eligible