## Integer Programming |

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. 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:

$\underset{x}{\mathrm{min}}\mathrm{}\left\{f{}^{T}x\right\}$

Subject to the constraints:

$Ax\le b$ | (inequality constraint) |

${A}_{\mathrm{eq}}x={b}_{\mathrm{eq}}$ | (equality constraint) |

$\mathrm{lb}\le x\le \mathrm{ub}$ | (bound constraint) |

${x}_{i}\mathrm{are\; integers}$ | (integer constraint) |

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:

**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.

For more information on integer programming, see Optimization Toolbox™.

- Getting Started with Integer Programming in MATLAB (Code example)
- Traveling Salesman Problem (Code example)
- Supply Chain Optimization (Code example)
- Solve Sudoku Puzzles (Code example)
- Modeling a Problem for Linear Programming 8:51 (Video)
- Setting Up and Solving a Linear Programming Problem 10:47 (Video)

- intlinprog function in Optimization Toolbox (Documentation)
- Mixed-Integer Linear Programming Algorithms (Documentation)
- Tuning Integer Linear Programming (Documentation)

*See also*: *Optimization Toolbox*, *Global Optimization Toolbox*, *linear programming*, *quadratic programming*, *nonlinear programming*, *portfolio optimization*, *investment management*, *energy trading*