PARAMETRIC PROGRAMMING

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

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