Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
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. –  fedja May 31 '13 at 13:20
    
@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. –  Brendan McKay May 31 '13 at 14:25
    
I edited the problem, hope it is clearer now. –  Gecko May 31 '13 at 15:18
    
there is a typo in the title; should be "encoding" instead of "enconding" –  Manfred Weis Nov 10 '13 at 17:08

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer
    
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). –  Manfred Weis Nov 10 '13 at 17:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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