2
$\begingroup$

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?

  • 0
    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?2012-02-23

1 Answers 1

3

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.

  • 0
    @pegausbupt: I'm glad it was helpful!2012-02-25