Skip to main content
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$ ...
j_random_hacker's user avatar
9 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 ...
Pseudonym's user avatar
  • 22.5k
9 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.'s user avatar
  • 162k
7 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 ...
Discrete lizard's user avatar
  • 8,303
6 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.'s user avatar
  • 162k
6 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.'s user avatar
  • 162k
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.'s user avatar
  • 162k
6 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 ...
Ggouvine's user avatar
  • 485
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 ...
Yuval Filmus's user avatar
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.'s user avatar
  • 162k
5 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 ...
DCTLib's user avatar
  • 2,797
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.'s user avatar
  • 162k
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 ...
Juho's user avatar
  • 22.6k
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 ...
Ribz's user avatar
  • 693
4 votes

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 ...
Mingwei Samuel's user avatar
4 votes

Poly-time reduction from ILP to SAT?

It is some sort of necro-answer to already answered and accepted question, but I want to note, that there is really easier way. Consider you have one of inequalities like this: $5*x_1 + 2*x_2 + 3*...
Konstantin Vladimirov's user avatar
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 $...
Seb Destercke's user avatar
4 votes

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 ...
Eugene's user avatar
  • 1,096
4 votes
Accepted

Expressing conditional in linear program

If you know the maximum value of $B$ then you can easily express all comparisons as described here: https://blog.adamfurmanek.pl/2015/09/12/ilp-part-4/ In your case you need the following: $0 \le -B ...
user1543037's user avatar
4 votes

Computing overlap of intervals in an integer programming framework

By overlap I understand its length (no its coordinates) since you didn't specify how to handle no overlap case. First you need to know whether $x_1\le y_1$ which is just a comparison. Next, you ...
user1543037's user avatar
4 votes
Accepted

How do you proceed if your milp is not solvable

It's hard to specify one approach because it depends on your needs. From my experience I can suggest the following: Precision Typical solvers report solutions as "optimal" using gap parameters ...
user1543037's user avatar
4 votes

Boolean variable that captures whether an inequality holds

Add the inequalities $$\begin{align*} a_1 x_1 + \dots + a_n x_n &\ge b - M (1-y)\\ a_1 x_1 + \dots + a_n x_n &< b + M y, \end{align*}$$ where $M$ is chosen sufficiently large. Why does ...
D.W.'s user avatar
  • 162k
4 votes

Linear programming over a finite field

Your problem, solving a system of linear equations, can be solved using an ancient algorithm, Gaussian elimination, which works over all fields. Note that linear programming is more general, allowing ...
Yuval Filmus's user avatar
4 votes

Detecting conservation, loss, or gain in a crafting game with items and recipes

Your problem is equivalent to asking whether there is some linear combination of row vectors from your $\mathbb R^{m\times n}$ matrix that has all coefficients positive and sums to a vector in which (...
j_random_hacker's user avatar
4 votes

Expressing a constraint of the form $\max(x_1,x_2) \ge q$ in a linear program

No. If you could do that in linear programming then you could force a variable to have binary values, so you'd be able to solve integer linear programs using LP solvers. Indeed, we can simulate $x \in ...
Steven's user avatar
  • 29.5k
4 votes
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 ...
D.W.'s user avatar
  • 162k
4 votes
Accepted

Approximation algorithms for integer convex quadratic programs over a linear subspace

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}...
Sriram's user avatar
  • 387

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