Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/31601
Title: | Lagrangian duality for robust problems with decomposable functions: the case of a robust inventory problem |
Author: | Rodrigues, Filipe Agra, Agostinho Requejo, Cristina Delage, Erick |
Keywords: | Lagrangian relaxation Robust optimization Lot-sizing Demand uncertainty Affine approximation Budgeted uncertainty polytope |
Issue Date: | 2021 |
Publisher: | INFORMS |
Abstract: | We consider a class of min-max robust problems in which the functions that need to be “robustified” can be decomposed as the sum of arbitrary functions. This class of problems includes many practical problems, such as the lot-sizing problem under demand uncertainty. By considering a Lagrangian relaxation of the uncertainty set, we derive a tractable approximation, called the dual Lagrangian approach, that we relate with both the classical dualization approximation approach and an exact approach. Moreover, we show that the dual Lagrangian approach coincides with the affine decision rule approximation approach. The dual Lagrangian approach is applied to a lot-sizing problem, in which demands are assumed to be uncertain and to belong to the uncertainty set with a budget constraint for each time period. Using the insights provided by the interpretation of the Lagrangian multipliers as penalties in the proposed approach, two heuristic strategies, a new guided iterated local search heuristic, and a subgradient optimization method are designed to solve more complex lot-sizing problems in which additional practical aspects, such as setup costs, are considered. Computational results show the efficiency of the proposed heuristics that provide a good compromise between the quality of the robust solutions and the running time required in their computation. |
Peer review: | yes |
URI: | http://hdl.handle.net/10773/31601 |
DOI: | 10.1287/ijoc.2020.0978 |
ISSN: | 1091-9856 |
Publisher Version: | https://pubsonline.informs.org/doi/10.1287/ijoc.2020.0978 |
Appears in Collections: | CIDMA - Artigos DMat - Artigos OGTCG - Artigos |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RodriguesAgraRequejoDelage-INFORMS2021-PostPrint.pdf | 598.18 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.