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,\...
user avatar
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 ...
user avatar
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 $...
user avatar
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$ ...
user avatar
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 ...
user avatar
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)...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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....
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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$, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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)...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible