| Τύπος: |
Διάλεξη |
| Ημ/νία Έναρξης: |
7/10/2009 |
| Ημ/νία Λήξης: |
|
| Ώρα Έναρξης: |
13:00 |
| Ώρα Λήξης: |
|
| Ομιλητής: |
Δρ. Γεώργιος Κ.Δ. Σαχαρίδης, Senior Research Associate , Center for Advanced Infrastructure and Transportation (CAIT), Department of Civil and Environmental Engineering, Rutgers - The State University of New Jersey, ΗΠΑ |
| Τίτλος: |
Speeding-up Benders decomposition method |
| Περιγραφή: |
Benders decomposition technique (Benders, 1962) is based on the idea of exploiting decomposable structure present in the formulation of a given problem so that its solution can be converted into the solution of several smaller sub-problems. One is the slave problem which is obtained by fixing a number of decision variables of the initial problem to a feasible value and the second one is the restricted master problem which is expected to provide the optimal solution after the addition of a number of cuts. The cuts are deduced from the resolution of the slave problem in each iteration of the algorithm. In each iteration, cuts are appended to restricted master problem which is solved again to optimality. Benders method is an algorithm that has been applied successfully to a variety of applications and different fields of mathematical programming as for example stochastic programming, global optimization, hierarchical optimization etc. In some cases the straightforward application of the classical Benders algorithm does not lead to fast convergence. Over the years various techniques have been proposed to speed-up the classical Benders decomposition algorithm. The work presented in the literature has mainly focused on either reducing the number of iterations of the algorithm or on restricting the solution space of the decomposed problems. This work presents two new strategies for the speeding-up of the Benders algorithm which are applied to two case studies in order to evaluate their efficiency. These strategies referred to as: covering cut bundle (CCB) generation [saharidis et al. 2009] and maximum feasible sub-system (MFS) cut generation [Saharidis and Ierapetritou 2009]. Both strategies implement in a novel way the multiple constraints generation idea. The CCB and MFS generation are applied to mixed integer problems arising from two types of applications the scheduling of crude oil [Saharidis, 2006] and the scheduling problem for multi-product, multi-purpose batch plants [Ierapetritou and Floudas, 1998]. In both cases CCB and MFS significantly decrease the number of iterations of the Benders method leading to improved resolution times. |
| Χώρος: |
Αμφιθέατρο |
| Link1: |
|
| Link2: |
|
| Photo1: |
|
| Photo2: |
|
| Photo3: |
|
Επιστροφή
|
