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 ...
- 270k
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 $...
- 270k
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,154
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
What is the decision version of integer programming?
It's the same as for all NP problems; the optimisation problem is
Find a valid solution $s$ that minimises¹ $f(s)$!
and the corresponding decision problem is
Is there a valid solution $s$ with $f(s)...
- 70.9k
8
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 ...
- 18.9k
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.♦
- 141k
7
votes
Find perfect matching whose weight is minimal, in polynomial time
Yes, there is a polynomial-time algorithm for your problem. There's no need to use a LP or ILP; you can solve it directly using combinatorial, graph-based methods. In particular, we can solve your ...
D.W.♦
- 141k
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 ...
- 261
7
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 ...
6
votes
Accepted
Restricted Integer Programming
All four problems are NP-complete.
Let me start by proving two easy results:
Your problem #3 is NP-complete, even when the matrix has only a single row, as explained here: Complexity of a subset sum ...
D.W.♦
- 141k
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.♦
- 141k
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 ...
- 6,978
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.♦
- 141k
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 ...
- 270k
5
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.♦
- 141k
5
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.♦
- 141k
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.♦
- 141k
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.♦
- 141k
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 ...
- 270k
5
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.♦
- 141k
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.1k
5
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 ...
- 435
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
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.1k
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,682
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 ...
- 673
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
Only top scored, non community-wiki answers of a minimum length are eligible