0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is constraint (1)? You mention it, but I don't see a definition of which constraint that refers to. What do you mean by "some of"? Do you mean, if $sel_i < 1$ for all $i$, then you can ignore the inequality constraint; but if there exists at least one index $i$ such that $sel_i=1$, then the inequality constraint must be respected? $\endgroup$ – D.W. Jun 27 '14 at 17:56
  • $\begingroup$ Are the selector variables required to be integers, or can they be arbitrary real numbers? Do you really have only 5 of them? $\endgroup$ – D.W. Jun 27 '14 at 17:58
  • $\begingroup$ Constraint (1) is requirement to 'obj' function's value to be larger then some number (second equation in my question, it has (1) on the right side). You are correct with second part - if all $sel_i < 1$, I can skip inequation completely. Finally, $sel_i$ are strictly integers. In general, I have a lot of selectors ($10^4$) and constraints ($10^3$). But in my question I just keep it simple. $\endgroup$ – CaptainTrunky Jun 27 '14 at 18:20
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ THanks, D.W., your response is very helpful. I've solve my problem with the following set of constraints: $$\sum_i c_i sel_i >= Value * \alpha$$ $$\sum_i c_i sel_i >= VeryHugeNumber * (1 - \alpha)$$ $\alpha$ is integer in range [0 .. 1]. $VeryHugeNumber$ is some constant, which is larger than $Value$. This forces solver to "choose" one of the constraints. $\endgroup$ – CaptainTrunky Jun 28 '14 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.