Check constraint under some condition in linear programming

Question

I would like to minimize linear pseudo-boolean function

$$\mathrm{obj} = \sum_i c_i \mathrm{sel}_i$$

subject to $$\sum_i c_i sel_i \geq \mathrm{Value} \qquad\qquad(1)$$ where

$c_1,\dots c_5, \mathrm{Value}$ are some constants;

$\mathrm{sel}_1,\dots,\mathrm{sel}_5$ are sort of selector variables, $ 0 \leq \mathrm{sel}_i \leq 1$

Everything is pretty straightforward, but I need to check constraint (1) if and only if some of $\mathrm{sel}_i = 1$. In the other words, if $\mathrm{obj} = 0$, that is OK with me, but if some or all of $\mathrm{sel}_i$ are picked up, I need to check $\mathrm{obj} \geq \mathrm{Value}$. Currently I'm using SAT to solve similar problem, but I prefer to study something else. Maybe I need consider different framework for this task? Any directions will be very useful. Thanks in advance.

Answer 1

This can be solved by case-splitting, depending upon whether any of the $sel_i$ are 1 or not, and then solving each case separately. Each case can then be handled using integer linear programming, so you might like to read about ILP solvers.

There are only two cases. We'll optimize for each, separately. The two cases are:

• Case 1: No selector is $=1$. In this case, $sel_i < 1$ for all $i$, and the linear inequality can be skipped. So the problem is to minimize the objective function subject to the requirement that $sel_i < 1$ for all $i$.

  You could solve this using an integer linear programming solver, but actually that's shooting a fly with a cannon. Since each $sel_i$ is required to be an integer in the range $0 \le sel_i \le 1$, this means you know that $sel_i = 0$ for all $i$. So, this case really covers only one possible assignment to the selectors: the all-zeros assignment. You can simply evaluate the value of the objective function at $sel_i=0$; in particular, this means that the objective function takes on the value $0$. So the value $0$ is always attainable.

• Case 2: At least one selector is $=1$. In this case, there exists at least one index $i$ such that $sel_i = 1$ for all $i$, and the linear inequality cannot be skipped. So now we have some kind of knapsack-like problem: we are looking for a sum of a subset of the $c_i$'s that is as small as possible, subject to the requirement that it be greater than $Value$.

  This could be handled with integer linear programming. Each $sel_i$ is an integer unknown, and you have linear inequalities and want to minimize a linear objective function. Adding the extra constraint $sel_1 + sel_2 + \dots + sel_5 \ge 1$ will ensure that at least one of the selectors is $=1$, as needed for this case. This means that you could just feed the problem to an ILP solver and see what solution it gives you.

  You might be able to find better algorithms, by borrowing techniques used for the subset sum problem or knapsack problem. In fact, it looks like this is a kind of reverse knapsack. If we just negate the constants, then we're looking for a subset of the negated constants whose sum is as large as possible, subject to the constraint that it be $\le Value$. That sounds like a knapsack problem; each negated constant is the weight and value of some object, and $Value$ represents the capacity of the knapsack. The one twist is that now your objects might have negative weight/value.

  Since we're in the special case where weight = value, this is in fact an instance of a subset sum kind of problem. The decision version of youur problem is: given $\alpha$, we want to know whether there is any subset of the constants whose value is in the range $[\alpha,Value]$. If we can solve the decision version, then we can serve your optimization problem by using binary search over $\alpha$.