toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
Details
   print
  Records Links
Author Ramirez-Pico, C.; Ljubic, I.; Moreno, E. doi  openurl
  Title Benders Adaptive-Cuts Method for Two-Stage Stochastic Programs Type
  Year (down) 2023 Publication Transportation Science Abbreviated Journal Transp. Sci.  
  Volume Early Access Issue Pages  
  Keywords two-stage stochastic programming; Benders decomposition; network flow; conditional value-at-risk; facility location  
  Abstract Benders decomposition is one of the most applied methods to solve two-stage stochastic problems (TSSP) with a large number of scenarios. The main idea behind the Benders decomposition is to solve a large problem by replacing the values of the second stage subproblems with individual variables and progressively forcing those variables to reach the optimal value of the subproblems, dynamically inserting additional valid constraints, known as Benders cuts. Most traditional implementations add a cut for each scenario (multicut) or a single cut that includes all scenarios. In this paper, we present a novel Benders adaptive-cuts method, where the Benders cuts are aggregated according to a partition of the scenarios, which is dynamically refined using the linear program-dual information of the subproblems. This scenario aggregation/disaggregation is based on the Generalized Adaptive Partitioning Method (GAPM), which has been successfully applied to TSSPs. We formalize this hybridization of Benders decomposition and the GAPM by providing sufficient conditions under which an optimal solution of the deterministic equivalent can be obtained in a finite number of iterations. Our new method can be interpreted as a compromise between the Benders single-cuts and multicuts methods, drawing on the advantages of both sides, by rendering the initial iterations faster (as for the single-cuts Benders) and ensuring the overall faster convergence (as for the multicuts Benders). Computational experiments on three TSSPs [the Stochastic Electricity Planning, Stochastic Multi Commodity Flow, and conditional value-at-risk (CVaR) Facility Location] validate these statements, showing that the new method outperforms the other implementations of Benders methods, as well as other standard methods for solving TSSPs, in particular when the number of scenarios is very large. Moreover, our study demonstrates that the method is not only effective for the risk-neutral decision makers, but also that it can be used in combination with the risk-averse CVaR objective.  
  Address  
  Corporate Author Thesis  
  Publisher Place of Publication Editor  
  Language Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0041-1655 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:001011928100001 Approved  
  Call Number UAI @ alexi.delcanto @ Serial 1814  
Permanent link to this record
 

 
Author Ljubic, I.; Moreno, E. pdf  doi
openurl 
  Title Outer approximation and submodular cuts for maximum capture facility location problems with random utilities Type
  Year (down) 2018 Publication European Journal Of Operational Research Abbreviated Journal Eur. J. Oper. Res.  
  Volume 266 Issue 1 Pages 46-56  
  Keywords Combinatorial optimization; Branch-and-cut; Maximum capture; Random utility model; Competitive facility location  
  Abstract We consider a family of competitive facility location problems in which a “newcomer” company enters the market and has to decide where to locate a set of new facilities so as to maximize its market share. The multinomial logit model is used to estimate the captured customer demand. We propose a first branch-and-cut approach for this family of difficult mixed-integer non-linear problems. Our approach combines two types of cutting planes that exploit particular properties of the objective function: the first one are the outer-approximation cuts and the second one are the submodular cuts. The approach is computationally evaluated on three datasets from the recent literature. The obtained results show that our new branch-and-cut drastically outperforms state-of-the-art exact approaches, both in terms of the computing times, and in terms of the number of instances solved to optimality. (C) 2017 Elsevier B.V. All rights reserved.  
  Address [Ljubic, Ivana] ESSEC Business Sch, 3 Av Bernard Hirsch,BP 50105, F-95021 Cergy Pontoise, France, Email: ivana.ljubic@essec.edu;  
  Corporate Author Thesis  
  Publisher Elsevier Science Bv Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0377-2217 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000423646500005 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 815  
Permanent link to this record
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: