Integer programming algorithms minimize or maximize a linear 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 yes-or-no decisions. When there are integer constraints on only some of the variables, the problem is called a mixed-integer linear program. Example integer programming problems include portfolio optimization in finance, optimal dispatch of generating units (unit commitment) in energy production, and scheduling and routing in operations research.
Integer programming requires finding a vector \(x\) that minimizes the function:
\[\min_{x} \left\{f^{\mathsf{T}}x\right\}\]
Subject to the contraints:
\[\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 such problems 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 include:
For more information on integer programming, see Optimization Toolbox™.
Traveling Salesman Problem - Example
Supply Chain Optimization - Example
Solve Sudoku Puzzles - Example
Mathematical Modeling with Optimization, Part 1 (8:51) - Video
Mathematical Modeling with Optimization, Part 2 (10:46) - Video
Optimal Dispatch of Power Generators - Example
Operations, Logistics and Supply Chain Management - MathWorks Consulting
See also: Optimization Toolbox, Global Optimization Toolbox, linear programming, quadratic programming, nonlinear programming, portfolio optimization, investment management, energy trading, prescriptive analytics