3. Mixed Integer Linear Optimization#
The particular feature of linear optimization problems is that as long as the decision variables satisfy all the constraints, they can take any value. However, there are many situations in which it makes sense to restrict the solution space in a way that cannot be expressed using linear (in-)equality constraints. For example, some numbers might need to be integers, such as the number of people to be assigned to a task. Another situation is when certain constraints need to hold only if another constraint holds. For example, the amount of power generated by a power plant need to be not smaller than a certain minimum threshold only if that generator is turned on. Neither of these two examples can be expressed using only linear constraints, as we have seen up to this point. In these cases, it is often still possible to formulate the problem as a LO problem, although some extra restrictions may be needed on certain variables, requiring them to take on integer values only. We will refer to this type of LO problem in which some variables are constrained to be integers as mixed-integer linear optimization (MILO) problems.
Formally, a MILO problem is defined as
where \(\mathcal{I} \subseteq \{1,\dots,n\}\) is the subset of indices identifying the variables that take integer values. The remaining variables are tacitly assumed to be real variables, that is \(x_i \in \mathbb{R}\) for \(i \not\in\mathcal{I}\). Of course, if the decision variables are required to be nonnegative, we could use the set \(\mathbb{N}\) instead of \(\mathbb{Z}\). A special case of integer variables are binary variables, which can take only values in \(\mathbb{B}=\{0,1\}\).
This chapter includes several examples with companion Pyomo implementation that explore various modeling and implementation aspects of MILO:
Go to the next chapter about network optimization.