Modeling tips & tricks

1. Binary variables#

This method is used when we can precisely determine the possible values of a variable. For instance, given an integer variable $x \in \mathbb{Z}$ with the condition $0 \leq x \leq 9$, we can decompose the variable $x$ into 9 binary variables $x_i$ ($0 \leq i \leq 9$) to satisfy

$$x_i = \begin{cases} 1 & \text{ if } x\text{ is equal to } i \\ 0 & \text{ otherwise } \end{cases}$$

Why do we need to decompose a variable into multiple variables? What is the benefit? The answer is, suppose we have not only one variable $x$ as above but also another variable $y \in \mathbb{Z}$ with the condition $0 \leq y \leq 9$. Then, it would be very difficult to linearize the condition $x \neq y$ if we use these two variables. On the other hand, if we decompose both $x$ and $y$ into binary variables, this condition can be easily modeled as follows: $x_i + y_i \leq 1, \forall 0 \leq i \leq 9$.

2. Modeling nonlinear constraints geometrically#

This method is applicable when we can find a convex hull containing only points that satisfy the desired constraint. For instance, to linearize the condition $x = y \Leftrightarrow z = 1$ where $x, y, z$ are binary variables. We observe that the feasible points are $(1, 1, 1), (0, 0, 1), (1, 0, 0), (0, 1, 0)$. Geometrically representing these points in three-dimensional space, we obtain the tetrahedron $ABCD$ shown below

The points within the tetrahedron $ABCD$ are precisely those that satisfy the given condition. The equations defining this tetrahedron are the exact constraints needed to linearize the original condition, specifically, the following conditions

$$\begin{cases} x + y - z \geq 1 \\ y + z - x \geq 1 \\ z + x - y \geq 1 \\ x + y = z \geq 1 \\ \end{cases}$$

A few notes:

• Use this method when we can determine all points satisfying the original constraint
• There must exist a convex set that contains all and only the points satisfying the constraint
• The above convex set should be easily representable by other linear constraints
• From this point forward, I will use the term geometric method to describe this technique. (This name is entirely my own creation, and I haven't consulted any references. It might not be the correct terminology. If you know the proper term for this method, please let me know so I can correct it.)

3. Modeling nonlinear “$A$ or $B$” constraints#

The typical form of these constraints is:

$$\left[ \begin{array}{ll} f(x) & \geq A \\ g(x) & \geq B \end{array} \right .$$

A common approach to linearize this type of constraint is to introduce an additional binary variable that corresponds to the two cases of the original constraint and then try to reformulate the original condition so that they are not contradictory. For example, consider linearizing the following constraint with $x, y \geq 0$

$$\begin{cases} \left[ \begin{array}{ll} 2x + y \geq 5 \\ x + 2y \geq 5 \end{array} \right .\\ x, y \geq 0 \end{cases}$$

Create binary variable $z$ satisfying

$$z = \begin{cases} 1 & \text{if } 2x + y \geq 5 \\ 0 & \text{if } x + 2y \geq 5 \\ \end{cases}$$

Then the original condition can be reformulated as follows

$$\begin{cases} 2x + y \geq Az \\ x + 2y \geq A - A(1-z)\\ x, y \geq 0 \end{cases}$$

Note: This method is quite difficult to apply and requires case-by-case analysis to find an appropriate linearization.

4. Conclusion#

We have discussed 3 common modeling techniques. Additional methods can be found in MOSEK Modeling Cookbook.

Happy modeling!