6.4 Parametric programming

In parametric programming the data depend on a parameter \(\theta \), for example \(b(\theta ) = b + \theta d\), and the solution is traced for all \(\theta \). By Theorem 6.1.1 the basis stays optimal on an interval of \(\theta \); at its end a basic variable reaches zero, a dual simplex pivot changes the basis, and the next interval begins. The optimal value is linear on each interval and concave overall, with slope \(y^{\mathsf T}d\) on each piece. For \(c(\theta ) = c + \theta d\) the roles are exchanged: primal simplex pivots at the breakpoints, and a convex value function. Figure 5 is the case \(d = e_2\).

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.