Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/16478
Title: A dynamic programming approach for a class of robust optimization problems
Author: Agra, Agostinho
Santos, Márcio Costa
Nace, Dritan
Poss, Michael
Keywords: Robust optimization
Budgeted uncertainty
Dynamic programming
Row-andcolumn generation
FPTAS
Issue Date: Sep-2016
Publisher: Society for Industrial and Applied Mathematics
Abstract: Common approaches to solving a robust optimization problem decompose the problem into a master problem (MP) and adversarial problems (APs). The MP contains the original robust constraints, written, however, only for nite numbers of scenarios. Additional scenarios are generated on the y by solving the APs. We consider in this work the budgeted uncertainty polytope from Bertsimas and Sim, widely used in the literature, and propose new dynamic programming algorithms to solve the APs that are based on the maximum number of deviations allowed and on the size of the deviations. Our algorithms can be applied to robust constraints that occur in various applications such as lot-sizing, the traveling salesman problem with time windows, scheduling problems, and inventory routing problems, among many others. We show how the simple version of the algorithms leads to a fully polynomial time approximation scheme when the deterministic problem is convex. We assess numerically our approach on a lot-sizing problem, showing a comparison with the classical mixed integer linear programming reformulation of the AP.
Peer review: yes
URI: http://hdl.handle.net/10773/16478
DOI: 10.1137/15M1007070
ISSN: 1052-6234
Appears in Collections:CIDMA - Artigos
OGTCG - Artigos

Files in This Item:
File Description SizeFormat 
M100707.pdfDocumento principal486.16 kBAdobe PDFView/Open


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.