A NEW ALGORITHM FOR STATE-CONSTRAINED SEPARATED CONTINUOUS LINEAR-PROGRAMS

During the last few decades, significant progress has been made in sol ving large-scale finite-dimensional and semi-infinite linear programmi ng problems. In contrast, little progress has been made in solving lin ear programs in infinite-dimensional spaces despite their importance a s models in manufacturing and communication systems. Inspired by the r esearch on separated continuous linear programs, we propose a new clas s of continuous linear programming problems that has a variety of impo rtant applications in communications, manufacturing, and urban traffic control. This class of continuous linear programs contains the separa ted continuous linear programs as a subclass. Using ideas from quadrat ic programming, we propose an efficient algorithm for solving large-sc ale problems in this new class under mild assumptions on the form of t he problem data. We prove algorithmically the absence of a duality gap for this class of problems without any boundedness assumptions on the solution set. We show this class of problems admits piecewise constan t optimal control when the optimal solution exists. We give conditions for the existence of an optimal solution. We also report computationa l results which illustrate that the new algorithm is effective in solv ing large-scale realistic problems (with several hundred continuous va riables) arising in manufacturing systems.