Parametric programming

From Glossary

Jump to: navigation, search

Solving a family of mathematical programs over a parameter space. For example, consider the family of linear programs:

\min \left \{ cx: Ax = b + td, x \ge 0 \right \},

where t is a (scalar) parameter and d is a specified direction vector. Starting with LaTeX: t=0, the LP is solved, then an optimal basis is found (if possible) that remains optimal as LaTeX: t is increased. The max value of LaTeX: t is determined; if this is finite, the basis changes to a new optimal basis (for the max LaTeX: t value) such that LaTeX: t can be further increased, if possible. This is continued until either LaTeX: t cannot be increased any further or a basis is found that remains optimal on the interval, LaTeX: \textstyle [t_k, \infty), where LaTeX: \textstyle 0 < t_1 < t_2 < \dots < t_k are the break points of the optimal objective value as a function of the parameter.

Personal tools