Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Polynomial Approximations for Continuous Linear Programs
 
Loading...
Thumbnail Image
research article

Polynomial Approximations for Continuous Linear Programs

Bampou, Dimitra
•
Kuhn, Daniel  
2012
SIAM Journal on Optimization

Continuous linear programs have attracted considerable interest due to their potential for modeling 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 (nonseparated) problem instances. In this paper we propose a more generic approximation scheme for nonseparated 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.

  • Details
  • Metrics
Type
research article
DOI
10.1137/110822992
Author(s)
Bampou, Dimitra
•
Kuhn, Daniel  
Date Issued

2012

Published in
SIAM Journal on Optimization
Volume

22

Issue

2

Start page

628

End page

648

Subjects

Continuous linear programming

•

Polynomial decision rules

•

Conic programming

URL

URL

http://epubs.siam.org/doi/abs/10.1137/110822992
Peer reviewed

NON-REVIEWED

Written at

OTHER

EPFL units
RAO  
Available on Infoscience
January 21, 2014
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/100039
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés