Mixed-Integer Optimization

Mixed-integer optimization deals with problems of the following form:

(1)\[\begin{split}\begin{align} \min_{x} \quad & c^\top x + x^\top D x + c_0 \\ \text{s.t.} \quad & a_{i\cdot}^\top x + x^\top Q^i x \le b_i, \quad i = 1, \ldots, m, \\ & x_j \in \mathbb{Z}, \quad j \in I \subseteq \{ 1, \dotsc, n \}. \end{align}\end{split}\]

Here, \(x\) are the decision variables, while \(c\), \(D\), \(c_0\), \(a_i\), \(Q^i\), and \(b_i\) are given data. Some of the decision variables are required to be integer-valued and are indexed by \(I\).

We say that (1) is an integer problem if \(I = \{ 1, \dotsc, n \}\), i.e., if all variables are required to be integer. It is said to be mixed-integer if \(I \neq \emptyset\). Otherwise, we say that (1) is a continuous problem.

An important class of problems is when \(D = 0\) and \(Q^i = 0\) for all \(i\), i.e., when the objective function and the constraints are linear. In such a case, we say that (1) is a mixed-integer linear problem (MILP), or a linear problem (LP) if all variables are continuous.

The feasible region of an integer problem and its linear relaxation.

Table of Contents

• Modeling a MIP with idol
  • The Environment
  • Models
  • Variables
  • Expressions
  • Constraints
  • Objective Functions
• Solving MIPs
  • The Concept of Optimizer and OptimizerFactory
  • Using an External Solver and Accessing the Solution
  • Getting Access to The Underlying Optimizer
  • Adding User Cuts and Lazy Constraints
  • Creating Your Own Callback
• Branch-and-Bound Algorithm
  • Writing an LP-based Branch-and-Bound [TODO]
• Column Generation and Branch-and-Price Algorithm
  • Solving A Dantzig-Wolfe Reformulation
  • Writing A Branch-and-Price Algorithm
  • Using Strong Branching