A New Combination of Lagrangean Relaxation, Dantzig-Wolfe Decomposition and Benders Decomposition Methods for Exact Solution of the Mixed Integer Programming Problems

Hadi Mohammadi, Esmaile Khorram

Abstract


The combinational technique of cross decomposition is a suitable one for exact solution of the mixed integer programming problems which uses simultaneously the advantages of Lagrangean relaxation, Dantzig-Wolfe decomposition and Benders decomposition methods for Minimization problem that each reinforces one another. The basic idea for this technique is the generation of suitable upper and lower bounds for the optimal value of the original problem at each iteration. In this paper, new cross decomposition algorithm, with the combination of Lagrangean relaxation method (the combination of three concepts of cutting-plane, sub-gradient and trust region), Dantzig-Wolfe decomposition and Benders decomposition methods are used in order to reinforce bounds and to speed up convergence. By increasing the problem scale and regarding the use of the Lagrangean relaxation method in this technique, the lower bound with more strength and efficacy, and by the aid of Dantzig-Wolfe decomposition method more suitable upper bound (if exists) and furthermore less number of iterations for achieving optimal solution is obtained. The convergence of this technique regarding the convergence of Benders decomposition method in finite iteration numbers is guaranteed.


Keywords


Cross decomposition; Benders decomposition; Lagrangean relaxation; Dantzig Wolfe decomposition; Cutting planes; Sub-gradient; Trust region; Column generation

Full Text:

PDF

References


J. F. Benders, Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik 4(1) (1962), 238 – 252, DOI: 10.1007/BF01386316.

E. W. Cheney and A. A. Goldstein, Newton’s method for convex programming and Tchebycheff approximation, Numerische Mathematik 1(1) (1959), 253 – 268, DOI: 10.1007/BF01386389.

M. S. Daskin, Network and Discrete Location: Models, Algorithms, and Applications, John Wiley & Sons, Inc, Chap Appendix H. Longitudes, Latitudes, Demands, and Fixed Cost for SORTCAP.GRT: A 49-Node Problem Defined on the Continental United States (1995).

E. Ogbe and X. Li, A new cross decomposition method for stochastic mixed-integer linear programming, European Journal of Operational Research 256(2) (2017), 487 – 499, DOI: 10.1016/j.ejor.2016.08.005.

M. Fischetti, D. Salvagnin and A. Zanette, A note on the selection of Benders’ cuts, Mathematical Programming 124(1-2) (2010), 175 – 182, DOI: 10.1007/s10107-010-0365-7.

P. Garcia-Herreros, J. Wassick and I. E. Grossmann, Design of Resilient Supply Chains with Risk of Facility Disruptions, Industrial & Engineering Chemistry Research 53 (44) (2014), 17240 – 17251, DOI: 10.1021/ie5004174.

G. B. Dantzig and P. Wolfe, Decomposition principle for linear programs, Operations Research 8(1) (1960), 101 – 111, DOI: 10.1287/opre.8.1.101.

A. M. Geofrion and G. W. Graves, Multicommodity distribution system design by Benders ecomposition, Management Science 20(5) (1974), 822 – 844, DOI: 10.1287/mnsc.20.5.822.

M. Held and R. M. Karp, The traveling salesman problem and minimum spanning trees: Part II, Mathprogramming 16–25 (1971), DOI: 10.1007/BF01584070.

K. Holmberg, On the convergence of cross decomposition, Mathematical Programming 47(2) (1990), 269 – 296, DOI: 10.1007/BF01580863.

D. MacDaneil and M. Devine, A modified bendes partitioning algorithm for mixed integer programming, Management Science 24(3) (1977), 312 – 319, DOI: 10.1287/mnsc.24.3.312.

T. L. Magnanti and R. T. Wong, Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria, Operations Research 29(3) (1981), 464 – 484, DOI: 10.1287/opre.29.3.464.

R. E. Marsten,W.W. Hogan and J.W. Blankenship, The box step method for large-scale optimization, Operations Research 23(3) (1975), 389 – 405, DOI: 10.1287/opre.23.3.389.

S. Mitra, P. Garcia-Herreros and I. E. Grossmann, A Novel Cross-decomposition Multi-cut Scheme for Two-Stage Stochastic Programming, in 24th European Symposium on Computer Aided Process Engineering: Part A and B, June 20 2014, Vol. 33, p. 241, DOI: 10.1016/B978-0-444-63456-6.50041-7.

N. Papadakos, Practical enhancements to the magnanti-wong method, Operations Research Letters 36(4) (2008), 444 – 449, DOI: 10.1016/j.orl.2008.01.005.

C. A. Poojari and J. E. Beasley, Improving Benders decomposition using a genetic algorithm, European Journal of Operational Research 199(1) (2009), 89 – 97, DOI: 10.1016/j.ejor.2008.10.033.

R. Rahmaniani, T. G. Crainic, M. Gendreau and W. Rei, The Benders decomposition algorithm: A literature review, European Journal of Operational Research 259(3) (2017), 801 – 817, DOI: 10.1016/j.ejor.2016.12.005.

W. Rei, J.-F. Cordeau, M. Gendreau and P. Soriano, Accelerating Benders decomposition by local branching, INFORMS Journal on Computing 21(2) (2009), 333 – 345, DOI: 10.1287/ijoc.1080.0296.

G. K. Saharidis and M. G. Ierapetritou, Speed-up Benders decomposition using maximum density cut (MDC) generation, Annals of Operations Research 210(1) (2013), 101 – 123, DOI: 10.1007/s10479-012-1237-8.

G. K. Saharidis and M. G. Ierapetritou, Improving Benders decomposition using maximum feasible subsystem (MFS) cut generation strategy, Computers & Chemical Engineering 34(8) (2010), 1237 – 1245, DOI: 10.1016/j.compchemeng.2009.10.002.

G. K. Saharidis, M. Minoux and M. C. Ierapetritou, Accelerating Benders method using covering cut bundle generation, International Transactions in Operational Research 17(2) (2010), 221 – 237, DOI: 10.1111/j.1475-3995.2009.00706.x.

S. Mouret, I. E. Grossmann and P. Pestiaux, Anew Lagrangean decomposition approach applied to the integration of refinery planning and crude-oil scheduling, Computers and Chemical Engineering 35 (2011), 2750 – 2766, DOI: 10.1016/j.compchemeng.2011.03.026.

L. V. Snyder and M. S. Daskin, Reliability models for facility location: the expected failure cost case, Transportation Science 39(3) (2005), 400 – 416, DOI: 10.1287/trsc.1040.0107.

T.J. Van Roy, Cross decomposition for mixed integer programming, Mathematical Programming 25(1) (1983), 46 – 63, DOI: 10.1007/BF02591718.

G. Zakeri, A. B. Philpott, D. M. Ryan, Inexact cuts in Benders decomposition, SIAM Journal on Optimization 10(3) (2000), 643 – 657, DOI: 10.1137/S1052623497318700.




DOI: http://dx.doi.org/10.26713%2Fcma.v10i3.1116

Refbacks

  • There are currently no refbacks.


eISSN 0975-8607; pISSN 0976-5905