66
Logical AND: Use the linear constraints $y_1 \ge x_1 + x_2 - 1$, $y_1 \le x_1$, $y_1 \le x_2$, $0 \le y_1 \le 1$, where $y_1$ is constrained to be an integer. This enforces the desired relationship. (Pretty neat that you can do it with just linear inequalities, huh?)
Logical OR: Use the linear constraints $y_2 \le x_1 + x_2$, $y_2 \ge x_1$, $y_2 \ge x_2$, ...
19
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+x2−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 ≤...
18
If a problem is NP-Hard it means that there exists a class of instances of that problem whose are NP-Hard.
It is perfectly possible for other specific classes of instances to be solvable in polynomial time.
Consider for example the problem of finding a 3-coloration of a graph. It is a well-known NP-Hard problem. Now imagine that its instances are restricted ...
13
No, special cases can be easier.
Consider this IP, for example, given $a_i \geq 0$ for $i \in [1..n]$:
$\qquad\displaystyle \min \sum_{i=1}^n x_ia_i$
s.t. $\quad\displaystyle\sum_{i=1}^n x_i \geq 1$
and $\ \displaystyle x_i \in \mathbb{N}$ for $i \in [1..n]$.
It finds the minimum among $a_1, \dots, a_n$ (that for which, inevitably, $x_i=1$ in an optimal ...
11
0-1 ILP formulated as:
Does there exist a vector $\mathbf{x}$, subject to constraints:
$$
\left.\begin{array}{rrrrr|rr}
a_{11} x_1 & + &a_{12} x_2 & ... + & a_{1n} x_n\le b_1 \\
a_{21} x_1 & + &a_{22} x_2 & ... + & a_{2n} x_n\le b_2 \\
...\\
a_{m1} x_1 & + &a_{m2} x_2 & ... + & a_{mn} ...
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
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 = ...
8
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
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
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 ...
6
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 ...
6
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
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
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 ...
5
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 ...
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
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$).
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 ...
4
One-in-three 3SAT is NP-complete. Looking at the reduction, it inherits the APX-hardness of 3SAT. You can formulate one-in-three 3SAT as a binary integer program with binary entries, so you problem is APX-hard.
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
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
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 ...
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
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.
4
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
