Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning

Land, 1960, An automatic method for solving discrete programming problems, Econometrica, 497, 10.2307/1910129 Lawler, 1966, Branch-and-bound methods: A survey, Oper. Res., 14, 699, 10.1287/opre.14.4.699 Nemhauser, 1988 Bertsimas, 1997 Papadimitriou, 1998 Clausen, 1999 Malaguti, 2011, An exact approach for the vertex coloring problem, Discrete Optim., 8, 174, 10.1016/j.disopt.2010.07.005 Morrison, 2013, An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset, European J. Oper. Res. Guzelsoy, 2013, Restrict-and-relax search for 0–1 mixed-integer programs, EURO J. Comput. Optim., 1, 201, 10.1007/s13675-013-0007-y Dechter, 1985, Generalized best-first search strategies and the optimality of A∗, J. ACM, 32, 505, 10.1145/3828.3830 IBM Corp., IBM ILOG CPLEX Optimization Studio V12.5, 2014. L. Ladanyi, T. Ralphs, M. Guzelsoy, A. Mahajan, SYMPHONY 5.5.0, 2014. URL: https://projects.coin-or.org/SYMPHONY. Gurobi Optimization, Inc., 2014. Gurobi Optimizer 5.6. LINDO Systems, Inc., 2014. LINDO API 8.0. Konrad-Zuse-Zentrum für Informationstechnik Berlin. SCIP Optimization Suite 3.0.1, 2014. URL: http://scip.zib.de/scip.shtml. Fair Isaac Corporation (FICO), 2014. Xpress Optimization Suite. COIN-OR, 2014. COIN-OR Branch and Cut. https://projects.coin-or.org/Cbc. Koch, 2011, MIPLIB 2010: Mixed integer programming library version 5, Math. Program. Comput., 3, 103, 10.1007/s12532-011-0025-9 E. Danna, Performance variability in mixed integer programming, in: Workshop on Mixed Integer Programming, 2008. Fischetti, 2014, Exploiting erraticism in search, Oper. Res., 62, 114, 10.1287/opre.2013.1231 Fischetti, 2005, The feasibility pump, Math. Program. Ser. A, 104, 91, 10.1007/s10107-004-0570-3 Bertacco, 2007, A feasibility pump heuristic for general mixed-integer problems, Discrete Optim., 4, 63, 10.1016/j.disopt.2006.10.001 Fischetti, 2003, Local branching, Math. Program., 98, 23, 10.1007/s10107-003-0395-5 Danna, 2005, Exploring relaxation induced neighborhoods to improve MIP solutions, Math. Program., 102, 71, 10.1007/s10107-004-0518-7 Danna, 2005, Branch-and-price heuristics: A case study on the vehicle routing problem with time windows, 99 French, 2001, Using a hybrid genetic-Algorithm/Branch and bound approach to solve feasibility and optimization integer programming problems, J. Heuristics, 7, 551, 10.1023/A:1011921025322 Büdenbender, 2000, A hybrid tabu Search/Branch-and-Bound algorithm for the direct flight network design problem, Transportation Sci., 34, 364, 10.1287/trsc.34.4.364.12319 Gendron, 1994 Carvajal, 2014, Using diversification, communication and parallelism to solve mixed-integer linear programs, Oper. Res. Lett., 42, 186, 10.1016/j.orl.2013.12.012 Koch, 2012, Could we use a million cores to solve an integer program?, Math. Methods Oper. Res., 76, 67, 10.1007/s00186-012-0390-9 Ibaraki, 1976, Theoretical comparisons of search strategies in branch-and-bound algorithms, Int. J. Comput. Inf. Sci., 5, 315, 10.1007/BF00998631 Golomb, 1965, Backtrack programming, J. ACM, 12, 516, 10.1145/321296.321300 Tarjan, 1972, Depth-first search and linear graph algorithms, SIAM J. Comput., 1, 146, 10.1137/0201010 Atamtürk, 2005, Integer-programming software systems, Ann. Oper. Res., 140, 67, 10.1007/s10479-005-3968-2 J. Chinneck, Practical optimization: A gentle introduction. 2015. http://www.sce.carleton.ca/faculty/chinneck/po.html. Kumar, 1992, Algorithms for constraint-satisfaction problems: A survey, AI Mag., 13, 32 Slate, 1983, CHESS 4.5—The Northwestern University chess program, 82 Korf, 1985, Depth-first iterative-deepening: An optimal admissible tree search, Artificial Intelligence, 27, 97, 10.1016/0004-3702(85)90084-0 P. Meseguer, Interleaved depth-first search, in: IJCAI, 1997, pp. 1382–1387. Scholl, 1999, Balancing assembly lines effectively—a computational comparison, European J. Oper. Res., 114, 50, 10.1016/S0377-2217(98)00173-8 Sewell, 2012, A branch, bound, and remember algorithm for the simple assembly line balancing problem, INFORMS J. Comput., 24, 433, 10.1287/ijoc.1110.0462 Cormen, 2009 Shi, 2000, Nested partitions method for global optimization, Oper. Res., 48, 390, 10.1287/opre.48.3.390.12436 Bixby, 2000, MIP: theory and practice—closing the gap, vol. 46, 19 Achterberg, 2008, Constraint integer programming: A new approach to integrate CP and MIP, vol. 5015, 6 Kao, 2009, A branch, bound, and remember algorithm for the 1∣ri∣∑ti scheduling problem, J. Sched., 12, 163, 10.1007/s10951-008-0087-3 Choi, 2006, Loss reduction in distribution networks using cyclic best first search, vol. 3984, 312 Morrison, 2014 Dür, 2005, Probabilistic subproblem selection in branch-and-bound algorithms, J. Comput. Appl. Math., 182, 67, 10.1016/j.cam.2004.10.019 Kolesar, 1967, A branch and bound algorithm for the knapsack problem, Manage. Sci., 13, 723, 10.1287/mnsc.13.9.723 Mehrotra, 1996, A column generation approach for graph coloring, INFORMS J. Comput., 8, 344, 10.1287/ijoc.8.4.344 Savelsbergh, 1997, A branch-and-price algorithm for the generalized assignment problem, Oper. Res., 45, 831, 10.1287/opre.45.6.831 Morrison, 2014, A wide branching strategy for the graph coloring problem, INFORMS J. Comput., 26, 704, 10.1287/ijoc.2014.0593 Babel, 1994, A fast algorithm for the maximum weight clique problem, Computing, 52, 31, 10.1007/BF02243394 Held, 2012, Maximum-weight stable sets and safe lower bounds for graph coloring, Math. Program. Comput., 4, 363, 10.1007/s12532-012-0042-3 Beale, 1970, Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables, 447 Beale, 1976, Global optimization using special ordered sets, Math. Program., 10, 52, 10.1007/BF01580653 de Farias, 2000, A generalized assignment problem with special ordered sets: a polyhedral approach, Math. Program., 89, 187, 10.1007/PL00011392 D’Ambrosio, 2011, Mixed integer nonlinear programming tools: a practical overview, 4OR, 9, 329, 10.1007/s10288-011-0181-9 Geoffrion, 1969, An improved implicit enumeration approach for integer programming, Oper. Res., 17, 437, 10.1287/opre.17.3.437 Achterberg, 2005, Branching rules revisited, Oper. Res. Lett., 33, 42, 10.1016/j.orl.2004.04.002 Ortega, 2003, A branch-and-cut algorithm for the single-commodity, uncapacitated, fixed-charge network flow problem, Networks, 41, 143, 10.1002/net.10068 Benichou, 1971, Experiments in mixed-integer linear programming, Math. Program., 1, 76, 10.1007/BF01584074 Achterberg, 2007 Applegate, 1995 Reinelt, 1991, TSPLIB—a traveling salesman problem library, ORSA J. Comput., 3, 376, 10.1287/ijoc.3.4.376 Linderoth, 1999, A computational study of search strategies for mixed integer programming, INFORMS J. Comput., 11, 173, 10.1287/ijoc.11.2.173 Pryor, 2011, Faster integer-feasibility in mixed-integer linear programs by branching to force change, Comput. Oper. Res., 38, 1143, 10.1016/j.cor.2010.10.025 Fischetti, 2011, Backdoor branching, vol. 6655, 183 Gilpin, 2011, Information-theoretic approaches to branching in search, Discrete Optim., 8, 147, 10.1016/j.disopt.2010.07.001 Karzan, 2009, Information-based branching schemes for binary linear mixed integer problems, Math. Program. Comput., 1, 249, 10.1007/s12532-009-0009-1 Vilà, 2014, A branch-and-bound algorithm for assembly line worker assignment and balancing problems, Comput. Oper. Res., 44, 105, 10.1016/j.cor.2013.10.016 S. Arora, B. Bollobas, L. Lovász, Proving integrality gaps without knowing the linear program, in: The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings, 2002, pp. 313–322. Sherali, 1992, A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique, J. Global Optim., 2, 101, 10.1007/BF00121304 Desrosiers, 2013 Gendron, 2013 Phan, 2012, Lagrangian duality and branch-and-bound algorithms for optimal power flow, Oper. Res., 60, 275, 10.1287/opre.1110.1036 Kohler, 1974, Characterization and theoretical comparison of branch-and-bound algorithms for permutation problems, J. ACM, 21, 140, 10.1145/321796.321808 Bellman, 1954, The theory of dynamic programming, Bull. Amer. Math. Soc., 60, 503, 10.1090/S0002-9904-1954-09848-8 Ibaraki, 1977, The power of dominance relations in branch-and-bound algorithms, J. ACM, 24, 264, 10.1145/322003.322010 Sewell, 2012, A BB&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times, J. Global Optim., 54, 791, 10.1007/s10898-011-9793-z Fischetti, 2010, Pruning moves, INFORMS J. Comput., 22, 108, 10.1287/ijoc.1090.0329 Nazareth, 1999, The multiple resource constrained project scheduling problem: A breadth-first approach, European J. Oper. Res., 112, 347, 10.1016/S0377-2217(97)00402-5 Demeulemeester, 2000, The discrete time/resource trade-off problem in project networks: a branch-and-bound approach, IIE Trans., 32, 1059, 10.1080/07408170008967461 Margot, 2002, Pruning by isomorphism in branch-and-cut, Math. Program. Ser. B, 94, 71, 10.1007/s10107-002-0358-2 Margot, 2003, Exploiting orbits in symmetric ilp, Math. Program., 98, 3, 10.1007/s10107-003-0394-6 Ostrowski, 2011, Orbital branching, Math. Program., 126, 147, 10.1007/s10107-009-0273-x Gomory, 1958, Outline of an algorithm for integer solutions to linear programs, Bull. Amer. Math. Soc., 64, 275, 10.1090/S0002-9904-1958-10224-4 Padberg, 1991, A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Rev., 33, 60, 10.1137/1033004 Balas, 1996, Mixed 0–1 programming by lift-and-project in a branch-and-cut framework, Manage. Sci., 42, 1229, 10.1287/mnsc.42.9.1229 Cornuéjols, 2008, Valid inequalities for mixed integer linear programs, Math. Program., 112, 3, 10.1007/s10107-006-0086-0 Marchand, 2002, Cutting planes in integer and mixed integer programming, Discrete Appl. Math., 123, 397, 10.1016/S0166-218X(01)00348-1 Balas, 1996, Gomory cuts revisited, Oper. Res. Lett., 19, 1, 10.1016/0167-6377(96)00007-7 Chvátal, 1973, Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Math., 4, 305, 10.1016/0012-365X(73)90167-2 Cook, 1990, Chvátal closures for mixed integer programming problems, Math. Program., 47, 155, 10.1007/BF01580858 Nemhauser, 1990, A recursive procedure to generate all cuts for 0–1 mixed integer programs, Math. Program., 46, 379, 10.1007/BF01585752 Lovász, 1991, Cones of matrices and set-functions and 0–1 optimization, SIAM J. Optim., 1, 166, 10.1137/0801013 Balas, 1993, A lift-and-project cutting plane algorithm for mixed 0–1 programs, Math. Program., 58, 295, 10.1007/BF01581273 Balas, 2003, A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer Gomory cuts for 0–1 programming, Math. Program., 94, 221, 10.1007/s10107-002-0317-y Balas, 1971, Intersection cuts-a new type of cutting planes for integer programming, Oper. Res., 19, 19, 10.1287/opre.19.1.19 Marchand, 1998 Atamtürk, 2005, Cover and pack inequalities for (mixed) integer programming, Ann. Oper. Res., 139, 21, 10.1007/s10479-005-3442-1 Padberg, 1985, Valid linear inequalities for fixed charge problems, Oper. Res., 33, 842, 10.1287/opre.33.4.842 Martin, 1997 Marchand, 2001, Aggregation and mixed integer rounding to solve MIPs, Oper. Res., 49, 363, 10.1287/opre.49.3.363.11211 Crowder, 1983, Solving large-scale zero–one linear programming problems, Oper. Res., 31, 803, 10.1287/opre.31.5.803 Balas, 2008, Optimizing over the split closure, Math. Program., 113, 219, 10.1007/s10107-006-0049-5 Fischetti, 2013, Approximating the split closure, INFORMS J. Comput., 25, 808, 10.1287/ijoc.1120.0543 Achterberg, 2013, Mixed integer programming: Analyzing 12 years of progress, 449 Benders, 1962, Partitioning procedures for solving mixed-variables programming problems, Numer. Math., 4, 238, 10.1007/BF01386316 Geoffrion, 1972, Generalized benders decomposition, J. Optim. Theory Appl., 10, 237, 10.1007/BF00934810 Hernández-Pérez, 2004, A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery, Discrete Appl. Math., 145, 126, 10.1016/j.dam.2003.09.013 Jünger, 1995, Practical problem solving with cutting plane algorithms in combinatorial optimization, 20, 111 Mitchell, 2002, Branch-and-cut algorithms for combinatorial optimization problems, 65 Dantzig, 1960, Decomposition principle for linear programs, Oper. Res., 8, 101, 10.1287/opre.8.1.101 Barnhart, 1998, Branch-and-price: Column generation for solving huge integer programs, Oper. Res., 46, 316, 10.1287/opre.46.3.316 Lübbecke, 2005, Selected topics in column generation, Oper. Res., 53, 1007, 10.1287/opre.1050.0234 Garey, 1979 Vanderbeck, 2011, Branching in branch-and-price: a generic scheme, Math. Program., 130, 249, 10.1007/s10107-009-0334-1 Gualandi, 2012, Exact solution of graph coloring problems via constraint programming and column generation, INFORMS J. Comput., 24, 81, 10.1287/ijoc.1100.0436 Easton, 2003, Solving the travelling tournament problem: A combined integer programming and constraint programming approach, vol. 2740, 100 D.R. Morrison, E.C. Sewell, S.H. Jacobson, Solving the pricing problem in a generic branch-and-price algorithm using zero-suppressed binary decision diagrams, 2014. arXiv:1401.5820  [cs.DS]. M.P. de Aragão, E. Uchoa, Integer program reformulation for robust branch-and-cut-and-price algorithms, in: Mathematical Program in Rio: a Conference in Honour of Nelson Maculan, 2003, pp. 56–61. Fukasawa, 2006, Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Math. Program., 106, 491, 10.1007/s10107-005-0644-x Uchoa, 2008, Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation, Math. Program., 112, 443, 10.1007/s10107-006-0043-y Rossi, 2006 Kim, 2002, Solving fixed-charge network flow problems with a hybrid optimization and constraint programming approach, Ann. Oper. Res., 115, 95, 10.1023/A:1021145103592 van Beek, 2006, Backtracking search algorithms, vol. 2, 85, 10.1016/S1574-6526(06)80008-8 Gamrath, 2013 Marques-Silva, 1999, GRASP: A search algorithm for propositional satisfiability, IEEE Trans. Comput., 48, 506, 10.1109/12.769433 Caseau, 1996, Improving branch and bound for jobshop scheduling with constraint propagation, vol. 1120, 129 Fahle, 2002, Simple and fast: Improving a branch-and-bound algorithm for maximum clique, vol. 2461, 485 Li, 2005, Exploiting unit propagation to compute lower bounds in branch and bound max-SAT solvers, vol. 3709, 403 T. Sandholm, R. Shields, Nogood learning for mixed integer programming, in: Workshop on Hybrid Methods and Branching Rules in Combinatorial Optimization, Montréal, 2006. Achterberg, 2007, Conflict analysis in mixed integer programming, Discrete Optim., 4, 4, 10.1016/j.disopt.2006.10.006 R.J. Lipton, K. Regan, Branch and bound—why does it work? 2012. URL: http://rjlipton.wordpress.com/2012/12/19/branch-and-bound-why-does-it-work/.