A new algorithm for state-constrained separated continuous linear programs. (English) Zbl 0921.49023

Luo, Xiaodong; Bertsimas, Dimitris

SIAM J. Control Optimization 37, No. 1, 177-210 (1999).

A continuous linear program is considered, with two state functions \(u(.)\) and \(y(.)\), a constraint \[ \int^t_0 Gu(s)ds+ Ey(t)=a(t) \] with \(a(.)\) piecewise linear, and separate pointwise linear inequalities for \(u(.)\) and \(y(.)\), with piecewise constant right sides. This class (SCSCLP) of problems is stated to give important models for manufacturing and communication systems. A strong duality theorem is proved. An algorithm is proposed to solve SCSCLP, requiring computing KKT points for a number of nonconvex quadratic programming subproblems with polyhedral constraints. Convergence and termination are proved; zero duality gap follows from the algorithm. A numerical application is included, with up to 250 continuous variables, showing the effectiveness of the algorithm.

Reviewer: B.D.Craven (Parkville)

MSC:

90C05	Linear programming
49M37	Numerical methods based on nonlinear programming
90C34	Semi-infinite programming
49N15	Duality theory (optimization)

Keywords:

continuous linear programming; strong duality; semi-infinite linear programming; nonlinear programming; jobshop scheduling problems