Optimization Toolbox 5.0

Linear Programming

Linear programming problems consist of a linear expression for the objective function and linear equality and inequality constraints. Optimization Toolbox includes three algorithms used to solve this type of problem: interior point, active-set, and simplex.

The interior point algorithm is based on a primal-dual predictor-corrector algorithm used for solving linear programming problems. Interior point is especially useful for large-scale problems that have structure or can be defined using sparse matrices.

The active-set algorithm minimizes the objective at each iteration over the active set (a subset of the constraints that are locally active) until it reaches a solution.

The simplex algorithm is a systematic procedure for generating and testing candidate vertex solutions to a linear program. The simplex algorithm is the most widely used algorithm for linear programming.

Linear programming used in the design of a plant for generating steam and electrical power.

Binary Integer Programming

Binary integer programming problems involve minimizing a linear objective function subject to linear equality and inequality constraints. Each variable in the optimal solution must be either a 0 or a 1.

Optimization Toolbox solves these problems using a branch-and-bound algorithm that:

• Searches for a feasible binary integer solution
• Updates the best binary point found as the search tree grows
• Verifies that no better solution is possible by solving a series of linear programming relaxation problems

Binary integer programming used to solve an investment problem.