A simplex based algorithm to solve separated continuous linear programs (Q930346)

The author develops a simplex based algorithm to solve separated continuous linear programs (SCLP) of the form \[ \max \int_0^T \left(\left(\gamma' + (T-t) c'\right) u(t) + d'x(t)\right) dt \] \[ \text{s.t. } \int_0^t Gu(s)ds + F x(t) \leq \alpha + at \] \[ Hu(t) \leq b \] \[ x(t), u(t) \geq 0 \quad t \in [0,T]. \] A symmetric dual SCLP* is formulated and weak duality and complementary slackness are shown. By construction, as a result of the algorithm, strong duality is proved under feasibility and boundedness assumptions. Under the same assumptions the existence of solutions to SCLP and SCLP* for all \(0<T<\infty\) is shown. Under a nondegeneracy assumption the solution is proved to be unique. The algorithm is based on the characterization of optimal solutions of SCLP and SCLP* as (finite) sequences of bases which correspond to extreme points of the feasible region. The validity region of a base sequence is shown to be a convex polyhedral cone. This allows the definition of neighboring base sequences (those whose validity regions have boundaries with an intersection containing more than the origin) which describe the iterations of the algorithm. The algorithm solves SCLP/SCLP* by a sequence of SCLP steps analogous to the parametric self dual simplex method for LP. The author first gives a simplified version of the algorithm with some assumption that he later removes in the general and extended versions.