22
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,\qquad y_1\leq x_2\,,$$
it can be written using the single range constraint
$$0 \leq x_1 + x_2-2y_1 \leq 1\,.$$
Similarly, for logical OR:
$$0 \leq 2y_1 - x_1 - x_2 ...
11
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 an integer $w$, determine whether there is a solution to $Ax = b$ with Hamming weight at most $w$.
You can reduce this problem to your problem. The system $Ax = ...
10
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$ of at most $r$ vertices from $V$ such that every edge in $E$ is incident on at least one vertex in $U$. (Equivalently: Is it possible to kill every edge in $G$ ...
9
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 $(-4,0)$ are both solutions while $(0,0)$ is not. It is also not closed, which is another reason why you cannot use it in a linear program (change $>$ to $\...
8
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 section >= minimum to handle abs(X) >= minimum. Here is another one with more tricks: http://orinanobworld.blogspot.de/2012/07/modeling-absolute-values.html
There ...
8
"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 algorithm, the general case for which discovered by Alexander Barvinok in 1994. It appears that all modern algorithms are broadly based on this method. Barvinok &...
8
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 find an approximate solution as well (find the best solution they can within the time constraints). There are no hard-and-fast rules.
Of course, ILP is NP-hard, ...
7
It's the same was 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) \leq k$?
You see that the former immediately solves the latter, and you can solve the former by using the latter with binary search over the set of ...
7
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 problem by a reduction to the assignment problem, i.e., to computing a maximum weight matching in a weighted bipartite graph.
Suppose we have a bipartite graph ...
7
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 continuous variable. If we restrict $x$ to be integer valued, then the second constraint can be simplified to:
$$
y-101\delta \le x \le -y+101 (1-\delta)
$$
7
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 integer lattice $\mathbb Z^n$. For example, if $n=100$, one has $2^{100} \approx 10^{30}$ possible ways of rounding.
Of course, one can round all entries of an $n$...
6
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 variant.
This implies that #4 is NP-complete as well, as #3 is a special case of #4.
Now for the strong result: Your problem #1 is NP-complete. The proof of ...
6
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 indicates that negated literals aren't allowed (you can't have $x_1 - x_3 = 1$ or $x_1 - x_4 \ge 1$).
Thus, in the special case where you have only type-2 ...
6
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 single problem as any single problem can be solved in $O(1)$!
That said, there is a notable class of ILP's that is known to be polynomial time solvable. This ...
5
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. Verifying the solution just involves plugging into the equations and checking that all equations hold. Finding the solution requires a bit more work (e.g., ...
5
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 of $k$ in an instance in which the optimal integer solution has value $V$ but the LP has a solution of value at most $V/k$. This shows that any rounding ...
5
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 give you a solution.
However, there are multiple caveats:
First, this isn't always possible. Sometimes there are both constraints that place lower limits and ...
5
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 through the steps of the proof of the theorem (which can be found in any textbook) and you'll obtain a valid reduction from 0-1 ILP to SAT.
5
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$, then the $M(1-y)$ term disappears; if $y=0$, then $M(1-y)$ becomes something huge and the inequality is automatically satisfied). The latter encodes the ...
5
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 boolean logic operations in zero-one integer linear programming (ILP) for many more boolean conditions and how to express them as linear inequalities.
5
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 here), but strong duality does not hold, so I doubt it can be used along the lines you suggest.
5
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 integer linear program has a feasible solution, then it has a feasible solution whose length (in bits) is at most a polynomial in the length (in bits) of the ...
5
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 the XCSP competition.
5
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 competitions for subsets (PB, SAT, max-SAT) and for constraint programming, as you and other answers pointed out. You can find many competitions (DIMACS ...
4
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)
determine whether it is possible to complete the given partial matrix $\mathrm A$ with values in $\{0,1\}$ such that the resulting completed matrix ...
4
I have a method for you that will help you find valid solutions (matrices) for many possible values of $m,n$. However, it is not a complete answer to your question. It can try to find a matrix for a particular value of $m,n$, but it might fail, and if it fails, you've learned nothing; my method cannot prove that no such matrix exists.
The method is based ...
4
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 Mathematics 123.1 (2002): 5-74.
In particular, Section 2.1 discusses integer programming in bounded dimension, and presents algorithms due to different authors. ...
4
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 size (but not length) linear in the number of variables.
In variant 1, we do not want to introduce additional variables. Essentially, we want to add clauses ...
4
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 says that $x_1\leqslant x_2$.
And if $y=0$ then you will be left with
$$A\leqslant x_1-x_2\leqslant M,$$ which says that $x_1>x_2$ (since $0<A<M$).
Only top voted, non community-wiki answers of a minimum length are eligible