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. Exploiting structure of chance constrained programs via submodularity
 
research article

Exploiting structure of chance constrained programs via submodularity

Frick, Damian
•
Sessa, Pier Giuseppe
•
Wood, Tony A.
Show more
July 2019
Automatica

We introduce a novel approach to reduce the computational effort of solving convex chance constrained programs through the scenario approach. Instead of reducing the number of required scenarios, we directly minimize the computational cost of the scenario program. We exploit the problem structure by efficiently partitioning the constraint function and considering a multiple chance constrained program that gives the same probabilistic guarantees as the original single chance constrained problem. We formulate the problem of finding the optimal partition, a partition achieving the lowest computational cost, as an optimization problem with nonlinear objective and combinatorial constraints. By using submodularity of the support rank of a set of constraints, we propose a polynomial-time algorithm to find suboptimal solutions to this partitioning problem and we give approximation guarantees for special classes of cost metrics. We illustrate that the resulting computational cost savings can be arbitrarily large and demonstrate our approach on a case study from production planning.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.automatica.2019.03.027
Author(s)
Frick, Damian
Sessa, Pier Giuseppe
Wood, Tony A.
Kamgarpour, Maryam  
Date Issued

2019-07

Published in
Automatica
Volume

105

Start page

89

End page

95

Editorial or Peer reviewed

REVIEWED

Written at

OTHER

EPFL units
SYCAMORE  
Available on Infoscience
December 1, 2021
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/183321
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