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

Authors

  • Hadi Mohammadi Department of Mathematics and Computer, Amirkabir University of Technology, Tehran
  • Esmaile Khorram Department of Mathematics and Computer, Amirkabir University of Technology, Tehran

DOI:

https://doi.org/10.26713/cma.v10i3.1116

Keywords:

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

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.

Downloads

Download data is not yet available.

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.

Downloads

Published

30-09-2019
CITATION

How to Cite

Mohammadi, H., & Khorram, E. (2019). A New Combination of Lagrangean Relaxation, Dantzig-Wolfe Decomposition and Benders Decomposition Methods for Exact Solution of the Mixed Integer Programming Problems. Communications in Mathematics and Applications, 10(3), 495–508. https://doi.org/10.26713/cma.v10i3.1116

Issue

Vol. 10 No. 3 (2019)

Section

Research Article

License

Creative Commons Licence 4.0 by  

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a CCAL that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.