Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What are some ways to deal with dependent constraints in integer programming?

For example, suppose I want to maximize $x+3y+2z$ subject to (i) $x+y<=3$ and (ii) if $y+z>=2$ then $x+z<=6$.

Are there any theories/algorithms on this type of integer programming?

share|improve this question
    
you can try to divide it to two IP problem, and it looks like the first one with the only constraint $x+y\leq 3$ will be unbounded, because $z$ is unrestricted. The second one will be with all three constraints and it looks like appropriate IP problem. –  com Feb 23 '12 at 18:53
    
I do not get it. How does your suggestion deal with the dependency in the 2nd constraint, i.e. if y+z>=2 then x+z<=6? –  pegausbupt Feb 23 '12 at 20:36
add comment

1 Answer

up vote 1 down vote accepted

You can model certain logical constraints like "if-then" statements using binary inequalities.

For your problem, you could introduce the binary variable $w$, which can only take on values of $0$ or $1$.

Then your "if $y+z \geq 2$ then $x+z \leq 6$" constraint can be implemented as the following:

$$ \begin{align} y + z - 1 &\leq M(1 - w), \\ x + z - 6 &\leq Mw, \end{align} $$ where $M$ is some sufficiently large constant.

Why does this work? If $y+z \geq 2$, then the first constraint forces the value of $w$ to be $0$, which causes the second inequality to be equivalent to $x + z \leq 6$. On the other hand, if $y+z \leq 1$, then the first constraint doesn't force anything about the value of $w$, which means that second constraint allows $x+z \leq 6$ or $x + z \geq 7$. (I'm assuming that all variables are integers, since you mentioned that you're doing integer programming.)

For more on linear and integer programming models with logical constraints, see Section 3.3 of Rader's Deterministic Operations Research. Other texts on linear and integer programming sometimes discuss modeling with logical constraints as well.

share|improve this answer
    
Thanks,Mike! This is exactly what I am looking for. –  pegausbupt Feb 24 '12 at 17:45
    
@pegausbupt: I'm glad it was helpful! –  Mike Spivey Feb 25 '12 at 4:06
add comment

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.