Optimization Toolbox

Linear Programming

Engineers and scientists use mathematical modeling to describe the behavior of systems under study. System requirements, when defined mathematically as constraints on the decision variables input into the mathematical system model, form a mathematical program. This mathematical program, or optimization problem description, can then be solved using optimization techniques. Linear programming is one class of mathematical programs where the objective and constraints consist of linear relationships.

Mathematical Modeling with Optimization, Part 1 8:51
Transform a problem description into a mathematical program that can be solved using optimization, using a steam and electric power plant example.

Mathematical Modeling with Optimization, Part 2 10:47
Solve a linear program using Optimization Toolbox solvers, using a steam and electric power plant example.

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:

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