Assume you have 2 binary variables $b$ and $c$. Suppose you want another binary variable, $a$ to be $\max(b,c)$ always. How would you represent this in the constraints of an integer program or of a mixed integer linear program (assuming it can't be done in an IP)?
EDIT: The following constraints would work for setting $a = \max(b,c)$:
$a \geq b$
$a \geq c$
$a \leq b+c$
This can be verified by both a truth table and by case analysis.
I still haven't understood exactly how the method described below is incorrect.
I have tried the following method (although there are some possible issues in the truth table):
Introduce another binary variable, $z$. Now, put the conditions:
$a \geq b$
$a \geq c$
$a \leq b + z$
$a \leq c + 1 - z$
$b \geq c - z$
Doing case analysis:
- $b = 0, c = 0$: For any $z\in\{0,1 \}$, all the constraints are only true for $a=0$.
- $b = 0, c = 1$: For $z=0$, the 5th constraint isn't satisfied. For $z=1$, all the constraints are true for $a=1$.
- $b = 1, c = 0$: For $z=1$, the 1st and 4th constraints can't be satisfied together. For $z=0$, all the constraints are true for $a=1$.
- $b = 1, c = 1$: For any $z\in\{0,1 \}$, all the constraints are true for $a=1$.
Does this case analysis mean that the set of constraints indeed represents $a=\max(b,c)$? I am unsure because of the following "issues" with the truth table.
- $a=1,b=0,c=1,z=0$: The constraints aren't satisfied => the truth table value is false. However, $a=1,b=0,c=1$ should always be true for $a=\max(b,c)$.
- $a=1,b=1,c=0,z=1$: The constraints aren't satisfied => the truth table value is false. However, $a=1,b=1,c=0$ should always be true for $a=\max(b,c)$.
How should we resolve the "issues" with the case analysis and the truth table?
The version with $z$ is technically correct. The two "solutions" you identify as issues each violate a constraint and thus are excluded from the feasible region. The solver will rule out both.