2
$\begingroup$

I have an objective function to be maximized

$obj(x) = \sum_i \gamma_i x_i$ with $x_i \in \mathbb{R}$

With multiple constraints of the form:

$\min_{y \in 0,1} (\sum_{i \in A} \alpha_i x_i + \sum_{i \in B}\beta_i x_i y )= Const$, with $\alpha_i,\beta_i \in {0,1}$ and $A$ and $B$ disjoint

Each of such constraints should probably be reformulated as:

$\sum_{i \in A} \alpha_i x_i \geq Const$

$\sum_{i \in A} \alpha_i x_i + \sum_{i \in B}\beta_i x_i \geq Const$

$\sum_{i \in A} \alpha_i x_i = Const \quad OR \quad \sum_{i \in A} \alpha_i x_i + \sum_{i \in B}\beta_i x_i = Const $

But I am not sure on how to encode this OR condition as a linear constraint.

Any ideas?

EDITS:

Made clear that there are multiple of such constraints between, up to 20.

Reformulated the problem more precisely

$\endgroup$
4
  • 1
    $\begingroup$ Either $x_0=Const$ and $x_0+\dots\ge Const$, or all $x_0+\dots=Const$ and $x_0\ge Const$. So you just solve 2 standard LP problems instead of one. That is if the constant is the same. If not, split according to the value of Const: $x_0$ can be just one of them, if any. $\endgroup$
    – fedja
    May 31, 2013 at 13:20
  • $\begingroup$ @fedja: I expect there are many constraints of that form, not just one. Gecko, please clarify. We don't want to split it into an exponential number of LPs. $\endgroup$ May 31, 2013 at 14:25
  • $\begingroup$ I edited the problem, hope it is clearer now. $\endgroup$
    – Gecko
    May 31, 2013 at 15:18
  • $\begingroup$ there is a typo in the title; should be "encoding" instead of "enconding" $\endgroup$ Nov 10, 2013 at 17:08

2 Answers 2

1
$\begingroup$

Your constraint

$\sum_{i \in A} \alpha_i x_i = Const \quad OR \quad \sum_{i \in A} \alpha_i x_i + \sum_{i \in B}\beta_i x_i = Const $

is equivalent to

$\sum_{i \in A} \alpha_i x_i \le Const + M y$

$\sum_{i \in A} \alpha_i x_i \ge Const - M y$

$ \sum_{i \in A} \alpha_i x_i + \sum_{i \in B}\beta_i x_i \le Const + M (1-y)$

$ \sum_{i \in A} \alpha_i x_i + \sum_{i \in B}\beta_i x_i \ge Const - M (1-y)$

where $y\in\{0,1\}$ and $M$ is a really large ("large enough") positive constant.

$\endgroup$
0
$\begingroup$

The essential problem is how to express the $\beta_i x_i y$ via linear constraints; as $\beta_i$ and $y \in {0,1}$ that is equivalent to expressing $\eta_i := \beta_i \wedge y$ via linear constraints, which is possible in the following way:

$\eta_i \le \beta_i$
$\eta_i \le y$
$0 \le \eta_i$
$\beta_i+y-1 \le \eta_i$

now replace all occurences of $\beta_i x_i y$ with $\eta_i x_i$ and add the above constraints;
The rest should pose no further difficulties.

The general way of modeling Boolean operations via linear constraints is to take the faces of the simplex that is the convex hull of the 3D vectors, whose $x$ and $y$ coordinates correspond to the values of the variables and whose $z$ coordinate coresponds to the result of the operation.
The upper faces are upper bounds and the lower faces are the lower bounds.

$\endgroup$
1
  • $\begingroup$ A good online overview of LP encoding of various constraints can be found by searching for "Linear Programming Tricks" and "Integer Programming Tricks" ( this is meant as a pointer for visitors of MO that were attracted by the general formulation of the posed problem). $\endgroup$ Nov 10, 2013 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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