# Tag Info

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,469

### 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 ...
• 22.5k
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 ...
• 162k
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 ...
• 8,303

### 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 ...
• 162k

### 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 ...
• 162k
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 ...
• 162k

### 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 ...
• 485
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 ...
• 278k
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 ...
• 162k

### 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,797
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$, ...
• 162k
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.6k

### 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

### 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 ...

### Is 0-1 integer linear programming with only equality constraints NP-Hard?

Consider the Maximum Independent Set problem ($\mathcal{NP}$-hard): given a graph $G=(V,E)$, find the maximum independent set in $G$, i.e., the subset of vertices $I \subseteq V$ such that every two ...
• 1,096
Accepted

• 29.5k
Accepted

### Why is it useful to transform 0-1 integer programming problem into SAT problem?

One important thing to know about ILP and 3SAT is that, often, on problem instances that arise on practice, they can be solved faster than a worst-case analysis would indicate. As such, worst-case ...
• 162k
The problems is equivalent to the closest vector problem (CVP). This is because $Ax=b, x\in \mathbb{Z}^n$ is a lattice. And the quadratic $\frac{1}{2} x^\top Q x + c^\top x$ can be written as \$\frac{1}...