3. Mixed Integer Linear Optimization#
A peculiar feature of the linear optimization problems that we have seen so far was that the decision variables can take any real value provided that all the constraints are satisfied. However, there are many situations in which it makes sense to restrict the feasible set 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 where certain constraints are to hold only if another constraint holds – for example, the amount of power generated in a coal plant taking at least its minimum value only if the generator is turned on. None of these two examples can be formulated using linear constraints alone. For such and many other situations, it is often possible that the problem can still be modeled as an LP, yet with an extra restriction that some variables need to take integer values only.
A mixed-integer linear optimization (MILO) is an LP problem in which some variables are constrained to be integers. Formally, it 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\}\).
In this chapter, there is a number of examples with companion AMPL implementation that explore various modeling and implementation aspects of MILO:
A basic MILO example modeling the BIM production with perturbed data
Go to the next chapter about network optimization.