What Is Integer Programming?

Integer programming is minimizing or maximizing a function subject to equality, inequality, and integer constraints. Integer constraints restrict some or all of the variables in the optimization problem to take on only integer values. This enables accurate modeling of problems involving discrete quantities (such as shares of a stock or cells in a battery) or yes-or-no decisions. When there are integer constraints on only some of the variables, the problem is called a mixed-integer program (MIP). Example integer programming problems include portfolio optimization in finance, optimal dispatch of generating units (unit commitment) in energy production, design optimization in engineering, and scheduling and routing in transportation and supply chain applications.

Mixed-Integer Nonlinear Programming (MINLP)

The most general form of integer programming is called a mixed-integer nonlinear program.  

MINLP is the mathematical problem of finding a vector \(x\) that minimizes the function:

\[\min_x f(x)\]

Subject to the constraints:

\[\begin{eqnarray}g(x) \leq 0 & \quad & \text{(inequality constraint)} \\h(x) = 0 & \quad & \text{(equality constraint)} \\ x_i \in \mathbb{Z} & \quad & \text{(integer constraint)} \end{eqnarray}\]

Mixed-Integer Linear Programming (MILP)

Many integer programming problems can be formulated with only linear objectives and constraints. In this case, the integer program is called a mixed-integer linear program and is written as:

\[\min_{x} \left\{f^{\mathsf{T}}x\right\}\]

Subject to the constraints:

\[\begin{eqnarray}Ax \leq b & \quad & \text{(inequality constraint)} \\A_{eq}x = b_{eq} & \quad & \text{(equality constraint)} \\lb \leq x \leq ub & \quad & \text{(bound constraint)} \\ x_i \in \mathbb{Z} & \quad & \text{(integer constraint)} \end{eqnarray}\]

Solving Mixed-Integer Linear Programs in MATLAB

Integer programming algorithms can be implemented in software such as MATLAB^®. Solving MILPs typically requires using a combination of techniques to narrow the solution space, find integer-feasible solutions, and discard portions of the solution space that do not contain better integer-feasible solutions. Common techniques for integer programming include:

• Cutting planes: Add additional constraints to the problem that reduce the search space.
• Heuristics: Search for integer-feasible solutions.
• Branch and bound: Systematically search for the optimal solution. The algorithm solves linear programming relaxations with restricted ranges of possible values of the integer variables.

The MILP solver in Optimization Toolbox™ implements these techniques.

Solving Mixed-Integer Nonlinear Programs in MATLAB

Some MINLPs can be solved by adapting these integer programming techniques to nonlinear functions or by linearizing the nonlinear functions and solving a sequence of MILPs. When the nonlinear functions can only be evaluated at integral points, other techniques are needed. Two algorithms applicable to these types of integer programs are implemented in Global Optimization Toolbox.

• Genetic algorithms: Mimic a natural selection process that repeatedly modifies a population of individual solutions that are restricted to integral values.
• Surrogate optimization: Automatically build a surrogate model of the problem that can be relaxed and is then solved by adaptations of MILP techniques to MINLP.

For more information on integer programming, see Optimization Toolbox and Global Optimization Toolbox.