國立虎尾科技大學 |

On High-Performance Benders-Decomposition-Based Exact Methods With Application to Mixed-Integer and Stochastic Problems.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	On High-Performance Benders-Decomposition-Based Exact Methods With Application to Mixed-Integer and Stochastic Problems./
Author:	Rahmaniani, Ragheb.
Description:	1 online resource (219 pages)
Notes:	Source: Dissertation Abstracts International, Volume: 76-11C.
Contained By:	Dissertation Abstracts International76-11C.
Subject:	Industrial engineering. -
Online resource:	click for full text (PQDT)

On High-Performance Benders-Decomposition-Based Exact Methods With Application to Mixed-Integer and Stochastic Problems.
Rahmaniani, Ragheb.

On High-Performance Benders-Decomposition-Based Exact Methods With Application to Mixed-Integer and Stochastic Problems. - 1 online resource (219 pages)

Source: Dissertation Abstracts International, Volume: 76-11C.

Thesis (Ph.D.)--Ecole Polytechnique, Montreal (Canada), 2018.

Includes bibliographical references

Stochastic integer programming (SIP) combines the difficulty of uncertainty and non-convexity, and constitutes a class of extremely challenging problems to solve. Efficiently solving SIP problems is of high importance due to their vast applicability. Therefore, the primary focus of this dissertation is on solution methods for SIPs. We consider two-stage SIPs and present several enhanced decomposition algorithms for solving them. Our main goal is to develop new decomposition schemes and several acceleration techniques to enhance the classical decomposition methods, which can lead to efficiently solving various SIP problems to optimality.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2018

Mode of access: World Wide Web

Subjects--Topical Terms:

679492
Industrial engineering.
Index Terms--Genre/Form:

554714
Electronic books.

On High-Performance Benders-Decomposition-Based Exact Methods With Application to Mixed-Integer and Stochastic Problems.
LDR:04754ntm a2200361Ki 4500 001 917477
005 20181012133446.5
006 m o u
007 cr mn||||a|a||
008 190606s2018 xx obm 000 0 eng d
035 $a (MiAaPQ)AAI10957160
035 $a (MiAaPQ)EPMontreal3008
035 $a AAI10957160
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Rahmaniani, Ragheb. $3 1191534
245 1 0 $a On High-Performance Benders-Decomposition-Based Exact Methods With Application to Mixed-Integer and Stochastic Problems.
264 0 $c 2018
300 $a 1 online resource (219 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertation Abstracts International, Volume: 76-11C.
500 $a Advisers: Michel Gendreau; Teodor G. Crainic; Walter Rei.
502 $a Thesis (Ph.D.)--Ecole Polytechnique, Montreal (Canada), 2018.
504 $a Includes bibliographical references
520 $a Stochastic integer programming (SIP) combines the difficulty of uncertainty and non-convexity, and constitutes a class of extremely challenging problems to solve. Efficiently solving SIP problems is of high importance due to their vast applicability. Therefore, the primary focus of this dissertation is on solution methods for SIPs. We consider two-stage SIPs and present several enhanced decomposition algorithms for solving them. Our main goal is to develop new decomposition schemes and several acceleration techniques to enhance the classical decomposition methods, which can lead to efficiently solving various SIP problems to optimality.
520 $a In the first essay of this dissertation, we present a state-of-the-art survey of the Benders decomposition algorithm. We provide a taxonomy of the algorithmic enhancements and the acceleration strategies of this algorithm to synthesize the literature, and to identify shortcomings, trends and potential research directions. In addition, we discuss the use of Benders decomposition to develop efficient (meta-)heuristics, describe the limitations of the classical algorithm, and present extensions enabling its application to a broader range of problems.
520 $a Next, we develop various techniques to overcome some of the main shortfalls of the Benders decomposition algorithm. We propose the use of cutting planes, partial decomposition, heuristics, stronger cuts, and warm-start strategies to alleviate the numerical challenges arising from instabilities, primal inefficiencies, weak optimality/feasibility cuts, and weak linear relaxation. We test the proposed strategies with benchmark instances from stochastic network design problems. Numerical experiments illustrate the computational efficiency of the proposed techniques.
520 $a In the third essay of this dissertation, we propose a new and high-performance decomposition approach, called Benders dual decomposition method. The development of this method is based on a specific reformulation of the Benders subproblems, where local copies of the master variables are introduced and then priced out into the objective function. We show that the proposed method significantly alleviates the primal and dual shortfalls of the Benders decomposition method and it is closely related to the Lagrangian dual decomposition method. Computational results on various SIP problems show the superiority of this method compared to the classical decomposition methods as well as CPLEX 12.7.
520 $a Finally, we study parallelization of the Benders decomposition method. The available parallel variants of this method implement a rigid synchronization among the master and slave processors. Thus, it suffers from significant load imbalance when applied to the SIP problems. This is mainly due to having a hard mixed-integer master problem that can take hours to be optimized. We thus propose an asynchronous parallel Benders method in a branchand- cut framework. However, relaxing the synchronization requirements entails convergence and various efficiency problems which we address them by introducing several acceleration techniques and search strategies. In particular, we propose the use of artificial subproblems, cut generation, cut aggregation, cut management, and cut propagation. The results indicate that our algorithm reaches higher speedup rates compared to the conventional synchronized methods and it is several orders of magnitude faster than CPLEX 12.7.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2018
538 $a Mode of access: World Wide Web
650 4 $a Industrial engineering. $3 679492
655 7 $a Electronic books. $2 local $3 554714
690 $a 0546
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a Ecole Polytechnique, Montreal (Canada). $3 845478
773 0 $t Dissertation Abstracts International $g 76-11C.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10957160 $z click for full text (PQDT)