Essec\Faculty\Model\Contribution {#2216
#_index: "academ_contributions"
#_id: "14101"
#_source: array:26 [
"id" => "14101"
"slug" => "benders-adaptive-cuts-method-for-two-stage-stochastic-programs"
"yearMonth" => "2023-09"
"year" => "2023"
"title" => "Benders Adaptive-Cuts Method for Two-Stage Stochastic Programs"
"description" => "RAMIREZ-PICO, C., LJUBIC, I. et MORENO, E. (2023). Benders Adaptive-Cuts Method for Two-Stage Stochastic Programs. <i>Transportation Science</i>, 57(5), pp. 1252-1275."
"authors" => array:3 [
0 => array:3 [
"name" => "LJUBIC Ivana"
"bid" => "B00683004"
"slug" => "ljubic-ivana"
]
1 => array:1 [
"name" => "RAMIREZ-PICO Cristian"
]
2 => array:1 [
"name" => "MORENO Eduardo"
]
]
"ouvrage" => ""
"keywords" => array:5 [
0 => "two-stage stochastic programming"
1 => "benders decomposition"
2 => "network flow"
3 => "conditional value-at-risk"
4 => "facility location"
]
"updatedAt" => "2024-03-18 11:05:54"
"publicationUrl" => "https://pubsonline.informs.org/doi/10.1287/trsc.2022.0073"
"publicationInfo" => array:3 [
"pages" => "1252-1275"
"volume" => "57"
"number" => "5"
]
"type" => array:2 [
"fr" => "Articles"
"en" => "Journal articles"
]
"support_type" => array:2 [
"fr" => "Revue scientifique"
"en" => "Scientific journal"
]
"countries" => array:2 [
"fr" => null
"en" => null
]
"abstract" => array:2 [
"fr" => "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."
"en" => "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."
]
"authors_fields" => array:2 [
"fr" => "Systèmes d'Information, Data Analytics et Opérations"
"en" => "Information Systems, Data Analytics and Operations"
]
"indexedAt" => "2024-12-21T16:21:43.000Z"
"docTitle" => "Benders Adaptive-Cuts Method for Two-Stage Stochastic Programs"
"docSurtitle" => "Journal articles"
"authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>, RAMIREZ-PICO Cristian, MORENO Eduardo"
"docDescription" => "<span class="document-property-authors">LJUBIC Ivana, RAMIREZ-PICO Cristian, MORENO Eduardo</span><br><span class="document-property-authors_fields">Information Systems, Data Analytics and Operations</span> | <span class="document-property-year">2023</span>"
"keywordList" => "<a href="#">two-stage stochastic programming</a>, <a href="#">benders decomposition</a>, <a href="#">network flow</a>, <a href="#">conditional value-at-risk</a>, <a href="#">facility location</a>"
"docPreview" => "<b>Benders Adaptive-Cuts Method for Two-Stage Stochastic Programs</b><br><span>2023-09 | Journal articles </span>"
"docType" => "research"
"publicationLink" => "<a href="https://pubsonline.informs.org/doi/10.1287/trsc.2022.0073" target="_blank">Benders Adaptive-Cuts Method for Two-Stage Stochastic Programs</a>"
]
+lang: "en"
+"_type": "_doc"
+"_score": 8.167604
+"parent": null
}
