Optimization Online


Polynomial Approximations for Continuous Linear Programs

Dimitra Bampou (dimitra.bampou04***at***imperial.ac.uk)
Daniel Kuhn (dkuhn***at***imperial.ac.uk)

Abstract: Continuous linear programs have attracted considerable interest due to their potential for modelling manufacturing, scheduling and routing problems. While efficient simplex-type algorithms have been developed for separated continuous linear programs, crude time discretization remains the method of choice for solving general (non-separated) problem instances. In this paper we propose a more generic approximation scheme for non-separated continuous linear programs, where we approximate the functional decision variables (policies) by polynomial and piecewise polynomial decision rules. This restriction results in an upper bound on the original problem, which can be computed efficiently by solving a tractable semidefinite program. To estimate the approximation error, we also compute a lower bound by solving a dual continuous linear program in (piecewise) polynomial decision rules. We establish the convergence of the primal and dual approximations under Slater-type constraint qualifications. We also highlight the potential of our method for optimizing large-scale multiclass queueing systems and dynamic Leontief models.

Keywords: Continuous linear programming, polynomial decision rules, conic programming, multiclass queueing networks, dynamic Leontief model

Category 1: Infinite Dimensional Optimization

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Working paper, Department of Computing, Imperial College London, January 2011

Download: [PDF]

Entry Submitted: 01/31/2011
Entry Accepted: 01/31/2011
Entry Last Modified: 04/05/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society