Benders decomposition: solving binary master problems by enumeration. (English) Zbl 1408.90203

Summary: We develop a variant of Benders decomposition for mixed-integer programming that solves each master problem by explicit enumeration. By storing the master problem’s current objective-function value for each potential solution, computational effort remains essentially constant across iterations. Using both serial and parallel processing, tests against competing methods show computational speedups that exceed two orders of magnitude.


90C11 Mixed integer programming
90B80 Discrete location and assignment
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut


Full Text: DOI


[1] Alguacil, N.; Conejo, A. J., Multiperiod optimal power flow using benders decomposition, IEEE Trans. Power Syst., 15, 1, 196-201, (2000)
[2] Bai, L.; Rubin, P. A., Combinatorial benders cuts for the minimum tollbooth problem, Oper. Res., 57, 6, 1510-1522, (2009)
[3] Benders, J. F., Partitioning procedures for solving mixed-variables programming problems, Numer. Math., 4, 1, 238-252, (1962)
[4] Birge, J. R.; Louveaux, F. V., A multicut algorithm for two-stage stochastic linear programs, European J. Oper. Res., 34, 3, 384-392, (1988)
[5] Brown, G.; Carlyle, M.; Salmerón, J.; Wood, K., Defending critical infrastructure, Interfaces, 36, 6, 530-544, (2006)
[6] Canto, S. P., Application of benders’ decomposition to power plant preventive maintenance scheduling, European J. Oper. Res., 184, 2, 759-777, (2008)
[7] Codato, G.; Fischetti, M., Combinatorial benders’ cuts for mixed-integer linear programming, Oper. Res., 54, 4, 756-766, (2006)
[8] Crowder, H.; Johnson, E.; Padberg, M., Solving large-scale zero-one linear programming problems, Oper. Res., 31, 5, 803-834, (1983)
[9] Fortz, B.; Poss, M., An improved benders decomposition applied to a multi-layer network design problem, Oper. Res. Lett., 37, 5, 359-364, (2009)
[10] Geoffrion, A. M., Generalized benders decomposition, J. Optim. Theory Appl., 10, 4, 237-260, (1972)
[11] Geoffrion, A. M.; Graves, G. W., Multicommodity distribution system design by benders decomposition, Manage. Sci., 20, 5, 822-844, (1974)
[12] Horowitz, E.; Sahni, S., Fundamentals of computer algorithms, (1978), Computer Science Press, Inc. Rockville, MD
[13] IBM ILOG CPLEX optimization studio, getting started with CPLEX, v12.4, (2011), IBM Corp.
[14] IBM ILOG CPLEX optimization studio, CPLEX user’s manual, v12.6, (2013), IBM Corp.
[15] Israeli, E.; Wood, R. K., Shortest-path network interdiction, Networks, 40, 2, 97-111, (2002)
[16] Magnanti, T. L.; Wong, R. T., Accelerating benders decomposition: algorithmic enhancement and model selection criteria, Oper. Res., 29, 3, 464-484, (1981)
[17] Naoum-Sawaya, J.; Elhedhli, S., An interior-point benders based branch-and-cut algorithm for mixed integer programs, Ann. Oper. Res., 210, 1, 33-55, (2013)
[18] Nemhauser, G.; Wolsey, L., Integer and combinatorial optimization, (1999), Wiley-Interscience New York
[19] OpenMP Architecture Review Board, OpenMP Application Program Interface, Version 4.0, 2013. URL: http://www.openmp.org/mp-documents/OpenMP4.0.0.pdf.
[20] Salmeron, J.; Wood, R. K., The value of recovery transformers in protecting an electric transmission grid against attack, IEEE Trans. Power Syst., 30, 5, 2396-2403, (2015)
[21] Salmeron, J.; Wood, K.; Baldick, R., Worst-case interdiction analysis of large-scale electric power grids, IEEE Trans. Power Syst., 24, 1, 96-104, (2009)
[22] S.M. Sanchez, R.K. Wood, The “BEST” algorithm for solving stochastic mixed integer programs, in: Proc. 2006 Winter Sim. Conf., Monterey, CA, 2006, pp. 765-773.
[23] Santoso, T.; Ahmed, S.; Goetschalckx, M.; Shapiro, A., A stochastic programming approach for supply chain network design under uncertainty, European J. Oper. Res., 167, 1, 96-115, (2005)
[24] Sarin, S. C.; West-Hansen, J., The long-term mine production scheduling problem, IIE Trans., 37, 2, 109-121, (2005)
[25] Sridhar, V.; Park, J. S., Benders-and-cut algorithm for fixed-charge capacitated network design problem, European J. Oper. Res., 125, 3, 622-632, (2000)
[26] Tarvin, D. A., Benders decomposition: an integer-programming extension with further computational enhancements, (2014), Colorado School of Mines Golden, CO, (Ph.D. thesis)
[27] Van Slyke, R. M.; Wets, R., L-shaped linear programs with applications to optimal control and stochastic programming, SIAM J. Appl. Math., 17, 4, 638-663, (1969)
[28] Wets, R. J.-B., Stochastic programs with fixed recourse: the equivalent deterministic program, SIAM Rev., 16, 3, 309-339, (1974)
[29] Xu, Y.; Ralphs, T. K.; Ladányi, L.; Saltzman, M. J., Computational experience with a software framework for parallel integer programming, INFORMS J. Comput., 21, 3, 383-397, (2009)
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.