# What are the algorithms for integer programming in which constraints are dependent?

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?

-
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

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.

-
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