×

zbMATH — the first resource for mathematics

A hybrid approach of bundle and Benders applied large mixed linear integer problem. (English) Zbl 1271.90049
Summary: Consider a large mixed integer linear problem where structure of the constraint matrix is sparse, with independent blocks, and coupling constraints and variables. There is one of the groups of constraints to make difficult the application of Benders scheme decomposition. In this work, we propose the following algorithm; a Lagrangian relaxation is made on the mentioned set of constraints; we presented a process heuristic for the calculation of the multiplier through the resolution of the dual problem, structured starting from the bundle methods. According to the methodology proposed, for each iteration of the algorithm, we propose Benders decomposition where quotas are provided for the value function and \(\varepsilon\)-subgradient.
Reviewer: Reviewer (Berlin)

MSC:
90C05 Linear programming
90C11 Mixed integer programming
Software:
CPLEX; MINTO; NOA
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] P. R. Pinheiro, Uma Metodologia de Feixe e Benders Aplicada a um Problema Linear Inteiro de Grande Porte [Tese de Doutorado], Universidade Federal do Rio de Janeiro, 1998.
[2] H. M. Salkin and K. Mathur, Foundations of Integer Programming, North-Holland, 1989. · Zbl 0683.90042
[3] ILOG, “ILOG CPLEX 10.0 Users Manual,” United States of America, 2006.
[4] G. L. Nemhauser, M. W. P. Savelsbergh, and G. C. Sigismondi, “MINTO, a mixed INTeger optimizer,” Operations Research Letters, vol. 15, no. 1, pp. 47-58, 1994. · Zbl 0806.90095 · doi:10.1016/0167-6377(94)90013-2
[5] E. Kwork and Y. Lee, “Parallelism in mixed integer programming,” in Proceedings of the International Symposium on Mathematical Programming, Ann Arbor, Mich, USA, 1994.
[6] M. Help and R. M. Karp, “The traveling salesman problem and minimum spanning trees,” Operations Research, vol. 18, pp. 1138-11162, 1970. · Zbl 0226.90047 · doi:10.1287/opre.18.6.1138
[7] M. Held and R. M. Karp, “The traveling-salesman problem and minimum spanning trees: part II,” Mathematical Programming, vol. 1, no. 1, pp. 6-25, 1971. · Zbl 0232.90038 · doi:10.1007/BF01584070
[8] A. M. Geoffrion, “Lagrangian relaxation for integer programming,” Mathematical Programming Study, vol. 2, pp. 82-114, 1974. · Zbl 0395.90056
[9] M. L. Fisher, “The lagrangian relaxation method for solving integer programming problems,” Management Science, vol. 27, no. 1, pp. 1-18, 1981. · Zbl 0466.90054 · doi:10.1287/mnsc.27.1.1
[10] L. G. Khachian, “A polynomial algorithm for linear programming,” Soviet Mathematics Doklady, vol. 20, pp. 191-194, 1979. · Zbl 0409.90079
[11] D. Bertsimas and J. B. Orlin, “A technique for speeding up the solution of the Lagrangean dual,” Mathematical Programming, vol. 63, no. 1-3, pp. 23-45, 1994. · Zbl 0806.90081 · doi:10.1007/BF01582057
[12] K. Aardal and T. Larsson, “A benders decomposition based heuristic for the hierarchical production planning problem,” European Journal of Operational Research, vol. 45, no. 1, pp. 4-14, 1990. · Zbl 0692.90057 · doi:10.1016/0377-2217(90)90151-Z
[13] K. Holmberg, “Mean value cross decomposition applied to integer programming problems,” European Journal of Operational Research, vol. 97, no. 1, pp. 124-138, 1997. · Zbl 0923.90119 · doi:10.1016/S0377-2217(96)00139-7
[14] K. Holmberg and J. Ling, “A Lagrangean heuristic for the facility location problem with staircase costs,” European Journal of Operational Research, vol. 97, no. 1, pp. 63-74, 1997. · Zbl 0923.90104 · doi:10.1016/S0377-2217(96)00058-6
[15] J. F. Benders, “Partitioning procedures for solving mixed-variables programming problems,” Numerische Mathematik, vol. 4, no. 1, pp. 238-252, 1962. · Zbl 0109.38302 · doi:10.1007/BF01386316 · eudml:131533
[16] K. Aardal and A. Ari, “On the resemblance between the Kornai-Liptak and cross decomposition techniques for block-angular linear programs,” European Journal of Operational Research, vol. 46, no. 3, pp. 393-398, 1990. · Zbl 0703.90061 · doi:10.1016/0377-2217(90)90015-4
[17] G. Côté and M. A. Laughton, “Large-scale mixed integer programming: benders-type heuristics,” European Journal of Operational Research, vol. 16, no. 3, pp. 327-333, 1984. · Zbl 0532.90077 · doi:10.1016/0377-2217(84)90287-X
[18] M. L. Fisher and R. A. Jaikumar, “Decomposition algorithm for large scale vehicle routing,” Working Paper 78-11-05, Department of Decision Sciences, University of Pennsylvania.
[19] H. H. Hoc, “Topological optimization of networks: a non-linear mixed integer model employing generalized benders decomposition,” IEEE Transactions on Automatic Control, vol. 27, no. 1, pp. 164-169, 1982. · Zbl 0472.90068 · doi:10.1109/TAC.1982.1102873
[20] G. G. Paula Jr. and N. Maculan, “A p-median location algorithm based on the convex lagrangean relation of the benders master problem,” in Proceedings of the International Symposium on Mathematical Programming, Tokyo, Japan, 1988.
[21] K. Rana and R. G. Vickson, “A model and solution algorithm for optimal routing of a time-chartered containership,” Transportation Science, vol. 22, no. 2, pp. 83-95, 1988. · Zbl 0642.90053 · doi:10.1287/trsc.22.2.83
[22] M. Held, P. Wolfe, and H. P. Crowder, “Validation of subgradient optimization,” Mathematical Programming, vol. 6, no. 1, pp. 62-88, 1974. · Zbl 0284.90057 · doi:10.1007/BF01580223
[23] B. T. Poljak, “A general method of solving extremum problems,” Soviet Mathematics, vol. 8, pp. 593-597, 1967. · Zbl 0177.15102
[24] B. T. Polyak, “Minimization of unsmooth functionals,” USSR Computational Mathematics and Mathematical Physics, vol. 9, no. 3, pp. 14-29, 1969. · Zbl 0229.65056 · doi:10.1016/0041-5553(69)90061-5
[25] N. Z. Shor, Minimization Methods for Non-Differentiable Functions, 1985. · Zbl 0561.90058
[26] J. A. Ferland and M. Florian, “A sub-optimal algorithm to solve a large scale 0-1 programming problem,” in Survey of Mathematical Programming, A. Prekopa, Ed., pp. 461-469, North-Holland, Amsterdam, 1979. · Zbl 0433.90050
[27] K. Holmberg, “On using approximations of the Benders master problem,” European Journal of Operational Research, vol. 77, no. 1, pp. 111-125, 1994. · Zbl 0810.90096 · doi:10.1016/0377-2217(94)90032-9
[28] M. Minoux, “Subgradient optimization and benders decomposition for large scale programming,” in Mathematical Programming, R. W. Cottle, M. L. Kelmanson, and B. Korte, Eds., 1984. · Zbl 0531.90067
[29] M. Minoux, Mathematical Programming, Theory and Algorithms, John Wiley and Sons, 1986. · Zbl 0602.90090
[30] D. McDaniel and M. Devine, “A modified benders’ partitioning algorithm for mixed integer programming,” Management Science, vol. 24, pp. 312-319, 1977. · Zbl 0371.90102 · doi:10.1287/mnsc.24.3.312
[31] T. J. Van Roy, “Cross decomposition for mixed integer programming,” Mathematical Programming, vol. 25, no. 1, pp. 46-63, 1983. · Zbl 0505.90057 · doi:10.1007/BF02591718
[32] T. J. Van Roy, “A cross decomposition algorithm for capacited facility location,” Operations Research, vol. 34, no. 1, pp. 145-163, 1986. · Zbl 0594.90022 · doi:10.1287/opre.34.1.145
[33] G. B. Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, NJ, USA, 1963. · Zbl 0108.33103
[34] G. B. Dantzig and P. Wolfe, “Decomposition principle for linear programs,” Operations Research, vol. 8, pp. 101-111, 1960. · Zbl 0093.32806 · doi:10.1287/opre.8.1.101
[35] A. M. Geoffrion, “Generalized Benders Decomposition,” Journal of Optimization Theory and Applications, vol. 10, no. 4, pp. 237-260, 1972. · Zbl 0229.90024 · doi:10.1007/BF00934810
[36] K. Holmberg, “On the convergence of cross decomposition,” Mathematical Programming, vol. 47, no. 1-3, pp. 269-296, 1990. · Zbl 0715.90078 · doi:10.1007/BF01580863
[37] K. Holmberg, “Generalized cross decomposition applied to nonlinear integer programming problems: duality gaps and convexi-fication in parts,” Optimization, vol. 23, pp. 341-3356, 1992. · Zbl 0817.90070 · doi:10.1080/02331939208843769
[38] K. Holmberg, “Cross decomposition applied to integer programming problems: duality gaps and convexification in parts,” Operations Research, vol. 42, no. 4, pp. 657-668, 1994. · Zbl 0864.90095 · doi:10.1287/opre.42.4.657
[39] K. Holmberg, “Solving the staircase cost facility location problem with decomposition and piecewise linearization,” European Journal of Operational Research, vol. 75, no. 1, pp. 41-61, 1994. · Zbl 0809.90093 · doi:10.1016/0377-2217(94)90184-8
[40] K. Homberg, Decomposition in large scale mathematical programming [Ph.D. dissertation], Institute of Technology, Linköping, Sweden, 1985.
[41] J. Kornai and T. Liptak, “Two-level planning,” Econometrica, vol. 33, pp. 141-191, 1965. · Zbl 0127.36703 · doi:10.2307/1911892
[42] K. Holmberg, “A convergence proof for linear mean value cross decomposition,” ZOR Zeitschrift fü Operations Research Methods and Models of Operations Research, vol. 39, no. 2, pp. 157-186, 1994. · Zbl 0799.90089 · doi:10.1007/BF01415580
[43] C. Y. Lee, “A cross decomposition algorithm for a multiproduct-multitype facility location problem,” Computers and Operations Research, vol. 20, no. 5, pp. 527-540, 1993. · Zbl 0774.90054 · doi:10.1016/0305-0548(93)90016-C
[44] K. Holmberg, “Linear mean value cross decomposition: a generalization of the Kornai-Liptak method,” European Journal of Operational Research, vol. 62, no. 1, pp. 55-73, 1992. · Zbl 0770.90041 · doi:10.1016/0377-2217(92)90177-B
[45] K. Holmberg, “Primal and dual decomposition as organizational design: price and/or resource directive decomposition,” Tecnical Report LiTH-MAT-R-94-04, Linköping Institute of Technology, Linköping, Sweden.
[46] S. Kim, S. C. Cho, and B. S. Um, “A simplified cross decomposition algorithm for multiple right hand choice linear programming,” Journal of the Operations Research Society of Japan, vol. 32, no. 4, pp. 441-449, 1989. · Zbl 0691.90055
[47] K. Holmberg and K. O. Jörnsten, “Cross decomposition applied to the stochastic transportation problem,” European Journal of Operational Research, vol. 17, no. 3, pp. 361-368, 1984. · Zbl 0547.90078 · doi:10.1016/0377-2217(84)90131-0
[48] B. Pchénitchny and Y. Daniline, Methodes Numériques dans les Problèmes d’Extrémum, Mir, Moscow, Russia, 1977. · Zbl 0389.65027
[49] C. Lemaréchal, “An extension of davidon methods to non differentiable problems,” Mathematical Programming Study, vol. 3, pp. 95-109, 1975. · Zbl 0358.90051
[50] P. Wolfe, “A method of conjugate subgradient for minimizing nondifferentiable functions,” in Nondifferentiable Optimization, Mathematical Programming Study 3, M. L. Balinski and P. Wolfe, Eds., pp. 145-1173, 1975. · Zbl 0369.90093
[51] R. T. Wong, Accelerating benders decomposition for network design [Ph.D. thesis], Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1978.
[52] C. Lemaréchal, “Nondifferenciable optimization, sub-gradient and \epsilon -subgradient methods,” Lecture Notes in Economics and Mathematical Systems, vol. 117, pp. 191-1199, 1976. · Zbl 0358.90066
[53] K. C. Kiwiel, Methods of Descend for Nondifferentiable Optimization, vol. 1133 of Lecture Notes in Mathematics, 1985. · Zbl 0561.90059 · doi:10.1007/BFb0074500
[54] K. C. Kiwiel, “A method for solving certain quadratic programming problems arising in nonsmooth optimization,” IMA Journal of Numerical Analysis, vol. 6, no. 2, pp. 137-152, 1986. · Zbl 0603.65041 · doi:10.1093/imanum/6.2.137
[55] K. C. Kiwiel and A. Stachurski, NOA-A Fortran Package of Nondifferentiable Optimization Algorithms, vol. 6, Systems Research Institute, Polish Academy of Sciences, Newelska, Poland, 1988.
[56] E. W. Cheney and A. A. Goldstein, “Newton’s method for convex programming and Tchebycheff approximation,” Numerische Mathematik, vol. 1, no. 1, pp. 253-268, 1959. · Zbl 0113.10703 · doi:10.1007/BF01386389 · eudml:131435
[57] J. E. Kelley, “The cutting plane method for solving convex problems,” SIAM Journal, vol. 8, pp. 703-712, 1960. · Zbl 0098.12104 · doi:10.1137/0108053
[58] K. C. Kiwiel, “Approximations in proximal bundle methods and decomposition of convex programs,” Journal of Optimization Theory and Applications, vol. 84, no. 3, pp. 529-548, 1995. · Zbl 0824.90110 · doi:10.1007/BF02191984
[59] H. Schramm, Eine Kombination von Bundle-und Trust-Region-Verfahren zur Lösung Nichtdifferenzierbarer Optimierungs Probleme, Helf 30, Bayreuther Mathematische Schriften, Bayreuth, Germany, 1989. · Zbl 0683.90069
[60] H. Schramm and J. Zowe, “A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results,” SIAM Journal on Optimization, vol. 2, no. 1, pp. 121-152, 1992. · Zbl 0761.90090 · doi:10.1137/0802008
[61] K. C. Kiwiel, “Proximity control in bundle methods for convex nondifferentiable minimization,” Mathematical Programming, vol. 46, no. 1-3, pp. 105-122, 1990. · Zbl 0697.90060 · doi:10.1007/BF01585731
[62] C. Lemaréchal and C. Sagastizábal, “Application of bundle methods to the unit-commitment problem,” Rapport Tecnique 0184, Institu Recherche d’Informatique et d’Automatique, Le Chesnay, 1995. · Zbl 1055.90572
[63] L. Qi and X. Chen, “A preconditioning proximal Newton method for nondifferentiable convex optimization,” Mathematical Programming B, vol. 76, no. 3, pp. 411-429, 1997. · Zbl 0871.90065 · doi:10.1007/BF02614391
[64] M. M. Mäkelä and P. Neittaanmäki, Nonsmooth Optimization, World Scientific, 1992. · Zbl 0757.49017
[65] D. Medhi, Decomposition of structured large scale optimization problems and parallel optimization [Ph.D. thesis], University of Wisconsin, 1987.
[66] SIAG/OPT Views-and-News, “A Forum for the SIAM Activity Group on Optimization,” Larry Nazareth Editor, 4, 1994.
[67] C. Lemaréchal, “Interview with Claude Lemaréchal,” Optima, 1996.
[68] C. Lemaréchal, “Lagrangian decomposition and nonsmooth optimization: bundle algorithm, prox iteration, augmented la-grangian,” in Nonsmooth Optimization: Methods and Applications, F. Giannessi, Ed., pp. 201-216, Gordon and Breach, Philadelphia, Pa, USA, 1992. · Zbl 1050.90553
[69] J. B. Hiriart-Urruty and C. Lemarechal, Convex Analysis and Minimization Algorithms, vol. 1-2, 1993. · Zbl 0795.49001
[70] L. Armijo, “Minimization of function having continuous parcial derivatives,” Pacific Journal of Mathematics, vol. 16, pp. 1-3, 1966. · Zbl 0202.46105 · doi:10.2140/pjm.1966.16.1
[71] P. R. Pinheiro, A. L. V. Coelho, A. B. De Aguiar, and T. O. Bonates, “On the concept of density control and its application to a hybrid optimization framework: investigation into cutting problems,” Computers and Industrial Engineering, vol. 61, no. 3, pp. 463-472, 2011. · doi:10.1016/j.cie.2011.03.013
[72] P. R. Pinheiro, A. L. V. Coelho, A. B. de Aguiar, and A. de Meneses Sobreira Neto, “Towards aid by generate and solve methodology: application in the problem of coverage and connectivity in wireless sensor networks,” International Journal of Distributed Sensor Networks, vol. 2012, Article ID 790459, 11 pages, 2012. · doi:10.1155/2012/790459
[73] N. Nepomuceno, P. Pinheiro, and A. L. V. Coelho, “Tackling the container loading problem: a hybrid approach based on integer linear programming and genetic algorithms,” Lecture Notes in Computer Science, vol. 4446, pp. 154-165, 2007.
[74] R. D. Saraiva, N. V. Nepomuceno, and P. R. Pinheiro, “The generate-and-solve framework revisited: generating by simulated annealing,” Lecture Notes in Computer Science, vol. 7832, pp. 262-273, 2013.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.