# 6. Mixed integer optimization¶

## 6.1. Introduction¶

In the previous chapters we have considered different classes of convex problems with continuous variables. In this chapter we consider a much wider range of problems by allowing integer variables. In particular, we consider conic and convex quadratic optimization problems where some of the variables are constrained to be integer valued. In principle, this allows us to model a vastly larger range of problems, but in practice we may not able to solve the resulting integer optimization problems within a reasonable amount of time.

## 6.2. Integer modeling¶

In this section we consider different building blocks for integer optimization, which we think of as building blocks for general integer problems.

### 6.2.1. Implication of positivity¶

Often we have a real-valued variable \(x\in \R\) satisfying \(0 \leq x < M\) for a known upper bound \(M\), and we wish to model the implication

where \(z\in \{0,1\}\) is an *indicator variable*. Since \(0 \leq x <M\) we can rewrite (1) as a linear inequality

where \(z\in\{0,1\}\). From the characterization (2) we see that that (1) is equivalent to

which is the well-known property of *contraposition*. In Sec. 6.3 we discuss such standard boolean expressions in more details.

Assume that production of a specific item \(i\) has a production cost of \(u_i\) per unit produced with an additional fixed charge of \(w_i\) if we produce item \(i\), i.e., a discontinuous production cost

shown in Fig. 6.1. If we let \(M\) denote an upper bound on the quantities we can produce, we get an alternative expression for the production cost,

where \(z_i\) is a binary variable indicating whether item \(i\) is produced or not. We can then minimize the total production cost under an affine constraint \(Ax=b\) as

which is a linear mixed-integer optimization problem. Note that by minimizing the production cost, we rule out the possibility that \(z_i=1\) and \(x_i=0\).

On the other hand, suppose \(x\) satisfies \(0<m \leq x\) for a known lower bound \(m\). We can then model the implication

(which is the reverse implication of (1)) as a linear inequality

where \(z\in\{0,1\}\).

### 6.2.2. Semi-continuous variables¶

We can also model *semi-continuity* of a variable \(x\in \R^n\),

where \(0<a\leq b\) using a double inequality

where \(z\in \{0,1\}\).

### 6.2.3. Constraint satisfaction¶

Suppose we have an upper bound \(M\) on the affine expression \(a^T x - b\) where \(x\in \R^n\). We can then model the implication \((z=1) \to (a^Tx \leq b)\) as

where \(z\in\{0,1\}\), i.e., \(z\) indicates whether or not the constraint \(a^T x \leq b\) is satisfied. To model the reverse implication \((a^Tx\leq b)\to (z=1)\) we equivalently consider the contraposition \((z=0)\to (a^Tx > b)\), which we can rewrite as

where \(m<a^T x - b\) is a lower bound. In practice, we relax the strict inequality using a small amount of slack, i.e.,

Collectively, we thus model \((a^Tx \leq b) \leftrightarrow (z=1)\) as

In a similar fashion, we can model \((z=1)\to (a^T x \geq b)\) as

and \((z=0)\to (a^T x < b)\) as

so we model \((z=1)\leftrightarrow (a^T x \geq b)\) as

using the alower bound \(m<a^Tx - b\) and upper bound \(M>a^Tx - b\). We can combine (9) and (9) to model indication of equality constraints \(a^Tx = b\). To that end, we note that \((z=1)\to (a^T x = b)\) is equivalent to both (7) and (10), i.e.,

On the other hand, \((z=0)\to (a^T x \neq b)\) (or equivalently \((z=0) \to (a^Tx > b) \lor (a^Tx < b)\)) can be written using (8) and (11) as

where \(z_1 + z_2 - z \leq 1\) is equivalent to \((z=0)\to (z_1=0)\lor (z_2=0)\).

### 6.2.4. Disjunctive constraints¶

With disjunctive constraints we require that at least one out of a set of constraints is satisfied. For example, we may require that

To that end, let \(M>a_j^T x - b_j,\:\forall j\) be a collective upper bound. Then we can model

as

where \(z_j\in \{0,1\}\) are binary variables. To characterize the reverse implication \((a_1^T x \leq b_1) \lor (a_2^T x \leq b_2) \lor \cdots \lor (a_k^T x \leq b_k)\to (z=1)\) we consider the contrapositive

which we can write as

for a lower bound \(m<a_j^T x - b_j, \: \forall j\).

### 6.2.5. Pack constraints¶

For a *pack constraint* we require that at most one of the constraints are satisfied. Considering (13) we can formulate this as

### 6.2.6. Partition constraints¶

For a *partition constraint* we require that exactly one of the constraints are satisfied. Considering (13) we can formulate this as

### 6.2.7. Continuous piecewise-linear functions¶

Consider the continuous univariate piecewise-linear *non-convex* function \(f:[\alpha_1,\alpha_5] \mapsto \R\) shown in Fig. 6.2. At the interval \([\alpha_j,\alpha_{j+1}]\), \(j=1,2,3,4\) we can describe the function as

for some \(\lambda_j,\lambda_{j+1}\geq 0\) with \(\lambda_j+\lambda_{j+1}=1\). If we add a constraint that only two (adjacent) variables \(\lambda_{j}, \lambda_{j+1}\) can be nonzero we can characterize \(f(x)\) over the entire interval \([\alpha_1,\alpha_5]\) as a convex combination,

The condition that only two adjacent variables can be nonzero is sometimes called an SOS2 constraint. If we introduce indicator variables \(z_i\) for each pair of adjacent variables \((\lambda_i,\lambda_{i+1})\), we can model it as

which satisfies \((z_j=1)\to \lambda_i=0, i\neq\{j,j+1\}\). Collectively, we can then model the epigraph \(f(x)\leq t\) as

for a piecewise-linear function \(f(x)\) with \(n\) terms. This approach is often called the *lambda-method*.

For the function in Fig. 6.2 we can reduce the number of integer variables by using a *Gray encoding*

of the intervals \([\alpha_j,\alpha_{j+1}]\) and an indicator variable \(y\in \{0,1\}^2\) to represent the four different values of Gray code. We can then describe the constraints on \(\lambda\) using only two indicator variables,

which leads to a more efficient characterization of the epigraph \(f(x)\leq t\),

The lambda-method can also be used to model multivariate continuous piecewise-linear non-convex functions, specified on a set of polyhedra \(P_k\). For example, for the function shown in Fig. 6.3 we can model the epigraph \(f(x)\leq t\) as

Note, for example, that \(z_2=1\) implies that \(\lambda_2=\lambda_5=\lambda_6=0\) and \(x=\lambda_1 v_1 + \lambda_3 v_3 + \lambda_4 v_4\).

For this function we can also reduce the number of indicator variables using a Gray encoding of decision variables for the different polyhedra. If we use a decision variable \(y\in\{0,1\}^2\) with a Gray encoding

we have

which gives the characterization of the epigraph

For multidimensional piecewise linear functions, a reduction of the number of binary decision variables is only possible when the polyhedral regions have a special topology, for example a “Union Jack” arrangement as shown in Fig. 6.3. We refer to the recent survey [VAN10] for further references and comparisons between different mixed-integer formulations for piecewise linear functions.

### 6.2.8. Lower semicontinuous piecewise-linear functions¶

The ideas in Sec. 6.2.7 can be applied to *lower semicontinuous* piecewise-linear functions as well. For example, consider the function shown in Fig. 6.4. If we denote the one-sided limits by \(f_{-}(c):=\lim_{x\uparrow c}f(x)\) and \(f_{+}(c):=\lim_{x\downarrow c}f(x)\), respectively, the one-sided limits, then we can describe the epigraph \(f(x)\leq t\) for the function in Fig. 6.4 as

where we a different decision variable for the intervals \([\alpha_1,\alpha_2)\), \([\alpha_2,\alpha_2]\), and \((\alpha_2,\alpha_3]\). As a special case this gives us an alternative characterization of fixed charge models considered in Sec. 6.2.1.

## 6.3. Boolean primitives¶

In the previous sections we used a binary decision variables to indicate whether or not a real valued affine expression was positive. In general, we can express a multitude of boolean expressions as linear inequality constraints involving integer variables. The basic operators from boolean algebra are *complement*, *conjunction* and *disjunction*, which are used to construct more complicated boolean expressions. In the following we let \(x\) and \(y\) denote binary variables with values \(\{0,1\}\).

### 6.3.1. Complement¶

Logical complement \(\lnot x\) is defined by the following truth table.

\(x\) | \(\lnot x\) |
---|---|

0 | 1 |

1 | 0 |

Thus in terms of an affine relationship,

### 6.3.2. Conjunction¶

Logical conjunction \((x\land y)\) is defined by the following truth table.

\(x\) | \(y\) | \(x \land y\) |
---|---|---|

0 | 0 | 0 |

1 | 0 | 0 |

0 | 1 | 0 |

1 | 1 | 1 |

Thus \(z = (x \land y)\) is equivalent to

### 6.3.3. Disjunction¶

Logical disjunction \((x\lor y)\) is defined by the following truth table.

\(x\) | \(y\) | \(x \lor y\) |
---|---|---|

0 | 0 | 0 |

1 | 0 | 1 |

0 | 1 | 1 |

1 | 1 | 1 |

Thus \((x \lor y)\) is equivalent to

The following table shows basic properties that are easily verified using the truth tables for complement, conjunction and disjunction.

Associativity | \(x\lor(y\lor z) = (x\lor y)\lor z\) | \(x\land(y\land z) = (x\land y)\land z\) |

Commutativity | \(x\lor y = y \lor x\) | \(x\land y = y\land x\) |

Distributivity | \(x\lor (y \land z) = (x \lor y) \land (x \lor z)\) | \(x\land (y \lor z) = (x \land y) \lor (x \land z)\) |

De Morgan | \(\lnot (x \land y) = \lnot x \lor \lnot y\) | \(\lnot (x \lor y) = \lnot x \land \lnot y\) |

The last row in the table shows the properties called *De Morgan’s laws*, which shows that conjugation and disjunction in a sense are dual operators.

### 6.3.4. Implication¶

Logical implication \((x \to y)\) is defined by the following truth table.

\(x\) | \(y\) | \(x \to y\) |
---|---|---|

0 | 0 | 1 |

1 | 0 | 0 |

0 | 1 | 1 |

1 | 1 | 1 |

It is easy verify that that \((x \to y)\) is equivalent to both \(( \lnot x \lor y)\) and

In terms of indicator variables we have that \(x \to y\) is equivalent to

Consider two real-valued variables \(0\leq u,v \leq M\). We can model complementary \(uv=0\) by introducing two indicator variables \(x\) and \(y\),

or equivalently

We then model \((u=0)\lor(v=0)\) as \((\lnot x \lor \lnot y)\), which can be written as

### 6.3.5. Exclusive disjunction¶

Logical exclusive disjunction \((x \oplus y)\) is defined by the following truth table.

\(x\) | \(y\) | \(x \oplus y\) |
---|---|---|

0 | 0 | 0 |

1 | 0 | 1 |

0 | 1 | 1 |

1 | 1 | 0 |

Thus \(z=x \oplus y\) is equivalent to

It is easy to verify from the truth table that \((x \oplus y)\) is equivalent to \(( x \lor y) \land \lnot (x \land y)\).

## 6.4. Integer optimization¶

A general mixed integer conic optimization problem has the form

where \(\cal C\) is direct product of self-dual cones (discussed in Chaps. 2-4) and \({\cal I}\subseteq \{1, \dots, n\}\) denotes the set of variables that are constrained to be integers.