Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning. (English) Zbl 1387.90010
Summary: The branch-and-bound (B&B) algorithmic framework has been used successfully to find exact solutions for a wide array of optimization problems. B&B uses a tree search strategy to implicitly enumerate all possible solutions to a given problem, applying pruning rules to eliminate regions of the search space that cannot lead to a better solution. There are three algorithmic components in B&B that can be specified by the user to fine-tune the behavior of the algorithm. These components are the search strategy, the branching strategy, and the pruning rules. This survey presents a description of recent research advances in the design of B&B algorithms, particularly with regards to these three components. Moreover, three future research directions are provided in order to motivate further exploration in these areas.
MSC:
| 90-02 | Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90C10 | Integer programming |
| 90C27 | Combinatorial optimization |
Keywords:
branch-and-bound; discrete optimization; integer programming; search strategies; cyclic best first search; surveyReferences:
| [1] | Land, A. H.; Doig, A. G., An automatic method for solving discrete programming problems, Econometrica, 497-520 (1960) · Zbl 0101.37004 |
| [2] | Lawler, E. L.; Wood, D. E., Branch-and-bound methods: A survey, Oper. Res., 14, 699-719 (1966) · Zbl 0143.42501 |
| [3] | Nemhauser, G.; Wolsey, L., Integer and Combinatorial Optimization. Vol. 18 (1988), Wiley: Wiley New York · Zbl 0652.90067 |
| [4] | Bertsimas, D.; Tsitsiklis, J. N., Introduction to Linear Optimization (1997), Athena Scientific |
| [5] | Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity (1998), Courier Dover Publications · Zbl 0944.90066 |
| [6] | Clausen, J., Branch and bound algorithms-principles and examples. Technical Report (1999), Department of Computer Science, University of Copenhagen |
| [7] | Malaguti, E.; Monaci, M.; Toth, P., An exact approach for the vertex coloring problem, Discrete Optim., 8, 174-190 (2011) · Zbl 1244.05092 |
| [8] | Morrison, D. R.; Sewell, E. C.; Jacobson, S. H., An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset, European J. Oper. Res. (2013), in press |
| [9] | Guzelsoy, M.; Nemhauser, G.; Savelsbergh, M., Restrict-and-relax search for 0-1 mixed-integer programs, EURO J. Comput. Optim., 1, 201-218 (2013) · Zbl 1296.90081 |
| [10] | Dechter, R.; Pearl, J., Generalized best-first search strategies and the optimality of \(A^\ast \), J. ACM, 32, 505-536 (1985) · Zbl 0631.68075 |
| [18] | Koch, T.; Achterberg, T.; Andersen, E.; Bastert, O.; Berthold, T.; Bixby, R.; Danna, E.; Gamrath, G.; Gleixner, A.; Heinz, S.; Lodi, A.; Mittelmann, H.; Ralphs, T.; Salvagnin, D.; Steffy, D.; Wolter, K., MIPLIB 2010: Mixed integer programming library version 5, Math. Program. Comput., 3, 103-163 (2011) |
| [20] | Fischetti, M.; Monaci, M., Exploiting erraticism in search, Oper. Res., 62, 114-122 (2014) · Zbl 1291.90148 |
| [21] | Fischetti, M.; Glover, F.; Lodi, A., The feasibility pump, Math. Program. Ser. A, 104, 91-104 (2005) · Zbl 1077.90039 |
| [22] | Bertacco, L.; Fischetti, M.; Lodi, A., A feasibility pump heuristic for general mixed-integer problems, Discrete Optim., 4, 63-76 (2007) · Zbl 1169.90415 |
| [23] | Fischetti, M.; Lodi, A., Local branching, Math. Program., 98, 23-47 (2003) · Zbl 1060.90056 |
| [24] | Danna, E.; Rothberg, E.; Le Pape, C., Exploring relaxation induced neighborhoods to improve MIP solutions, Math. Program., 102, 71-90 (2005) · Zbl 1131.90036 |
| [25] | Danna, E.; Le Pape, C., Branch-and-price heuristics: A case study on the vehicle routing problem with time windows, (Desaulniers, G.; Desrosiers, J.; Solomon, M. M., Column Generation (2005)), 99-129 · Zbl 1246.90036 |
| [26] | French, A. P.; Robinson, A. C.; Wilson, J. M., Using a hybrid genetic-Algorithm/Branch and bound approach to solve feasibility and optimization integer programming problems, J. Heuristics, 7, 551-564 (2001) · Zbl 0987.68615 |
| [27] | Büdenbender, K.; Grünert, T.; Sebastian, H., A hybrid tabu Search/Branch-and-Bound algorithm for the direct flight network design problem, Transportation Sci., 34, 364-380 (2000) · Zbl 1014.90006 |
| [28] | Gendron, B.; Crainic, T. G., Parallel Branch-and-Branch Algorithms: Survey and Synthesis (1994) · Zbl 0824.90096 |
| [29] | Carvajal, R.; Ahmed, S.; Nemhauser, G.; Furman, K.; Goel, V.; Shao, Y., Using diversification, communication and parallelism to solve mixed-integer linear programs, Oper. Res. Lett., 42, 186-189 (2014) · Zbl 1408.90194 |
| [30] | Koch, T.; Ralphs, T.; Shinano, Y., Could we use a million cores to solve an integer program?, Math. Methods Oper. Res., 76, 67-93 (2012) · Zbl 1262.90106 |
| [31] | Ibaraki, T., Theoretical comparisons of search strategies in branch-and-bound algorithms, Int. J. Comput. Inf. Sci., 5, 315-344 (1976) · Zbl 0406.68031 |
| [32] | Golomb, S. W.; Baumert, L. D., Backtrack programming, J. ACM, 12, 516-524 (1965) · Zbl 0139.12305 |
| [33] | Tarjan, R., Depth-first search and linear graph algorithms, SIAM J. Comput., 1, 146-160 (1972) · Zbl 0251.05107 |
| [34] | Atamtürk, A.; Savelsbergh, M. W.P., Integer-programming software systems, Ann. Oper. Res., 140, 67-124 (2005) · Zbl 1091.90046 |
| [36] | Kumar, V., Algorithms for constraint-satisfaction problems: A survey, AI Mag., 13, 32 (1992) |
| [37] | Slate, D. J.; Atkin, L. R., CHESS 4.5—The Northwestern University chess program, (Frey, P. W., Chess Skill in Man and Machine (1983), Springer: Springer New York), 82-118 |
| [38] | Korf, R. E., Depth-first iterative-deepening: An optimal admissible tree search, Artificial Intelligence, 27, 97-109 (1985) · Zbl 0573.68030 |
| [40] | Scholl, A.; Klein, R., Balancing assembly lines effectively—a computational comparison, European J. Oper. Res., 114, 50-58 (1999) · Zbl 0949.90034 |
| [41] | Sewell, E. C.; Jacobson, S. H., A branch, bound, and remember algorithm for the simple assembly line balancing problem, INFORMS J. Comput., 24, 433-442 (2012) · Zbl 1462.90112 |
| [42] | Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2009), MIT Press · Zbl 1187.68679 |
| [43] | Shi, L.; Ólafsson, S., Nested partitions method for global optimization, Oper. Res., 48, 390-407 (2000) · Zbl 1106.90368 |
| [44] | Bixby, R. E.; Fenelon, M.; Gu, Z.; Rothberg, E.; Wunderling, R., MIP: theory and practice—closing the gap, (Powell, M. J.D.; Scholtes, S., System Modelling and Optimization. System Modelling and Optimization, IFIP—The International Federation for Information Processing, vol. 46 (2000), Springer US), 19-49 · Zbl 0986.90025 |
| [45] | Achterberg, T.; Berthold, T.; Koch, T.; Wolter, K., Constraint integer programming: A new approach to integrate CP and MIP, (Perron, L.; Trick, M. A., Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lect. Notes Comput. Sci., vol. 5015 (2008), Springer: Springer Berlin, Heidelberg), 6-20 · Zbl 1142.68504 |
| [46] | Kao, G. K.; Sewell, E. C.; Jacobson, S. H., A branch, bound, and remember algorithm for the \(1 \mid r_i \mid \sum t_i\) scheduling problem, J. Sched., 12, 163-175 (2009) · Zbl 1179.90139 |
| [47] | Choi, S.; Shin, M.; Cha, J., Loss reduction in distribution networks using cyclic best first search, (Gavrilova, M. L.; Gervasi, O.; Kumar, V.; Tan, C. J.K.; Taniar, D.; Laganá, A.; Mun, Y.; Choo, H., Computational Science and Its Applications—ICCSA 2006. Computational Science and Its Applications—ICCSA 2006, Lecture Notes in Computer Science, vol. 3984 (2006), Springer: Springer Berlin, Heidelberg), 312-321 |
| [48] | Morrison, D. R.; Sauppe, J. J.; Sewell, E. C.; Jacobson, S. H., Cyclic best-first search: Using contours to guide branch-and-bound algorithms. Technical Report (2014), University of Illinois, Urbana-Champaign |
| [49] | Dür, M.; Stix, V., Probabilistic subproblem selection in branch-and-bound algorithms, J. Comput. Appl. Math., 182, 67-80 (2005) · Zbl 1078.65050 |
| [50] | Kolesar, P. J., A branch and bound algorithm for the knapsack problem, Manage. Sci., 13, 723-735 (1967) |
| [51] | Mehrotra, A.; Trick, M. A., A column generation approach for graph coloring, INFORMS J. Comput., 8, 344-354 (1996) · Zbl 0884.90144 |
| [52] | Savelsbergh, M., A branch-and-price algorithm for the generalized assignment problem, Oper. Res., 45, 831-841 (1997) · Zbl 0895.90161 |
| [53] | Morrison, D. R.; Sauppe, J. J.; Sewell, E. C.; Jacobson, S. H., A wide branching strategy for the graph coloring problem, INFORMS J. Comput., 26, 704-717 (2014) · Zbl 1304.90211 |
| [54] | Babel, L., A fast algorithm for the maximum weight clique problem, Computing, 52, 31-38 (1994) · Zbl 0791.68127 |
| [55] | Held, S.; Cook, W.; Sewell, E. C., Maximum-weight stable sets and safe lower bounds for graph coloring, Math. Program. Comput., 4, 363-381 (2012) · Zbl 1267.90005 |
| [56] | Beale, E. M.L.; Tomlin, J. A., Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables, (Fifth Annual International Conference on Operational Research (1970), Tavistock Publications), 447-454 |
| [57] | Beale, E. M.L.; Forrest, J. J.H., Global optimization using special ordered sets, Math. Program., 10, 52-69 (1976) · Zbl 0331.90056 |
| [58] | de Farias, I.; Johnson, E.; Nemhauser, G., A generalized assignment problem with special ordered sets: a polyhedral approach, Math. Program., 89, 187-203 (2000) · Zbl 1060.90081 |
| [59] | D’Ambrosio, C.; Lodi, A., Mixed integer nonlinear programming tools: a practical overview, 4OR, 9, 329-349 (2011) · Zbl 1235.90101 |
| [60] | Geoffrion, A. M., An improved implicit enumeration approach for integer programming, Oper. Res., 17, 437-454 (1969) · Zbl 0174.20801 |
| [61] | Achterberg, T.; Koch, T.; Martin, A., Branching rules revisited, Oper. Res. Lett., 33, 42-54 (2005) · Zbl 1076.90037 |
| [62] | Ortega, F.; Wolsey, L. A., A branch-and-cut algorithm for the single-commodity, uncapacitated, fixed-charge network flow problem, Networks, 41, 143-158 (2003) · Zbl 1106.90016 |
| [63] | Benichou, M.; Gauthier, J. M.; Girodet, P.; Hentges, G.; Ribiere, G.; Vincent, O., Experiments in mixed-integer linear programming, Math. Program., 1, 76-94 (1971) · Zbl 0233.90016 |
| [64] | Achterberg, T., Constraint integer programming (2007), (Ph.D. thesis) · Zbl 1430.90427 |
| [65] | Applegate, D.; Bixby, R. E.; Chvátal, V.; Cook, W., Finding cuts in the TSP. Technical Report 95-05 (1995), DIMACS |
| [66] | Reinelt, G., TSPLIB—a traveling salesman problem library, ORSA J. Comput., 3, 376-384 (1991) · Zbl 0775.90293 |
| [67] | Linderoth, J. T.; Savelsbergh, M. W.P., A computational study of search strategies for mixed integer programming, INFORMS J. Comput., 11, 173 (1999) · Zbl 1040.90535 |
| [68] | Pryor, J.; Chinneck, J. W., Faster integer-feasibility in mixed-integer linear programs by branching to force change, Comput. Oper. Res., 38, 1143-1152 (2011) · Zbl 1208.90122 |
| [69] | Fischetti, M.; Monaci, M., Backdoor branching, (Günlük, O.; Woeginger, G. J., Integer Programming and Combinatoral Optimization. Integer Programming and Combinatoral Optimization, Lecture Notes in Computer Science, vol. 6655 (2011), Springer: Springer Berlin, Heidelberg), 183-191 · Zbl 1341.90091 |
| [70] | Gilpin, A.; Sandholm, T., Information-theoretic approaches to branching in search, Discrete Optim., 8, 147-159 (2011) · Zbl 1241.90183 |
| [71] | Karzan, F. K.; Nemhauser, G. L.; Savelsbergh, M. W.P., Information-based branching schemes for binary linear mixed integer problems, Math. Program. Comput., 1, 249-293 (2009) · Zbl 1184.90114 |
| [72] | Vilà, M.; Pereira, J., A branch-and-bound algorithm for assembly line worker assignment and balancing problems, Comput. Oper. Res., 44, 105-114 (2014) · Zbl 1307.90090 |
| [74] | Sherali, H. D.; Tuncbilek, C. H., A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique, J. Global Optim., 2, 101-112 (1992) · Zbl 0787.90088 |
| [75] | Desrosiers, J.; Jans, R.; Adulyasak, Y., Improved column generation algorithms for the job grouping problem. Technical Report G-2013-26 (2013), Les Cahiers du GERAD |
| [76] | Gendron, B.; Khuong, P.; Semet, F., A Lagrangian-Based Branch-and-Bound Algorithm for the Two-Level Uncapacitated Facility Location Problem with Single-Assignment Constraints. Technical Report CIRRELT-2013-21 (2013), CIRRELT |
| [77] | Phan, D. T., Lagrangian duality and branch-and-bound algorithms for optimal power flow, Oper. Res., 60, 275-285 (2012) · Zbl 1251.90308 |
| [78] | Kohler, W. H.; Steiglitz, K., Characterization and theoretical comparison of branch-and-bound algorithms for permutation problems, J. ACM, 21, 140-156 (1974) · Zbl 0279.68035 |
| [79] | Bellman, R., The theory of dynamic programming, Bull. Amer. Math. Soc., 60, 503-515 (1954) · Zbl 0057.12503 |
| [80] | Ibaraki, T., The power of dominance relations in branch-and-bound algorithms, J. ACM, 24, 264-279 (1977) · Zbl 0357.90043 |
| [81] | Sewell, E. C.; Sauppe, J. J.; Morrison, D. R.; Jacobson, S. H.; Kao, G., A BB&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times, J. Global Optim., 54, 791-812 (2012) · Zbl 1258.90043 |
| [82] | Fischetti, M.; Salvagnin, D., Pruning moves, INFORMS J. Comput., 22, 108-119 (2010) · Zbl 1243.90136 |
| [83] | Nazareth, T.; Verma, S.; Bhattacharya, S.; Bagchi, A., The multiple resource constrained project scheduling problem: A breadth-first approach, European J. Oper. Res., 112, 347-366 (1999) · Zbl 0938.90031 |
| [84] | Demeulemeester, E.; Reyck, B. D.; Herroelen, W., The discrete time/resource trade-off problem in project networks: a branch-and-bound approach, IIE Trans., 32, 1059-1069 (2000) |
| [85] | Margot, F., Pruning by isomorphism in branch-and-cut, Math. Program. Ser. B, 94, 71-90 (2002) · Zbl 1023.90088 |
| [86] | Margot, F., Exploiting orbits in symmetric ilp, Math. Program., 98, 3-21 (2003) · Zbl 1082.90070 |
| [87] | Ostrowski, J.; Linderoth, J.; Rossi, F.; Smriglio, S., Orbital branching, Math. Program., 126, 147-178 (2011) · Zbl 1206.90101 |
| [88] | Gomory, R. E., Outline of an algorithm for integer solutions to linear programs, Bull. Amer. Math. Soc., 64, 275-278 (1958) · Zbl 0085.35807 |
| [89] | Padberg, M.; Rinaldi, G., A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Rev., 33, 60-100 (1991) · Zbl 0734.90060 |
| [90] | Balas, E.; Ceria, S.; Cornuéjols, G., Mixed 0-1 programming by lift-and-project in a branch-and-cut framework, Manage. Sci., 42, 1229-1246 (1996) · Zbl 0880.90105 |
| [91] | Cornuéjols, G., Valid inequalities for mixed integer linear programs, Math. Program., 112, 3-44 (2008) · Zbl 1278.90266 |
| [92] | Marchand, H.; Martin, A.; Weismantel, R.; Wolsey, L., Cutting planes in integer and mixed integer programming, Discrete Appl. Math., 123, 397-446 (2002) · Zbl 1130.90370 |
| [93] | Balas, E.; Ceria, S.; Cornuéjols, G.; Natraj, N., Gomory cuts revisited, Oper. Res. Lett., 19, 1-9 (1996) · Zbl 0865.90098 |
| [94] | Chvátal, V., Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Math., 4, 305-337 (1973) · Zbl 0253.05131 |
| [95] | Cook, W.; Kannan, R.; Schrijver, A., Chvátal closures for mixed integer programming problems, Math. Program., 47, 155-174 (1990) · Zbl 0711.90057 |
| [96] | Nemhauser, G.; Wolsey, L., A recursive procedure to generate all cuts for 0-1 mixed integer programs, Math. Program., 46, 379-390 (1990) · Zbl 0735.90049 |
| [97] | Lovász, L.; Schrijver, A., Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optim., 1, 166-190 (1991) · Zbl 0754.90039 |
| [98] | Balas, E.; Ceria, S.; Cornuéjols, G., A lift-and-project cutting plane algorithm for mixed 0-1 programs, Math. Program., 58, 295-324 (1993) · Zbl 0796.90041 |
| [99] | Balas, E.; Perregaard, M., A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer Gomory cuts for 0-1 programming, Math. Program., 94, 221-245 (2003) · Zbl 1030.90068 |
| [100] | Balas, E., Intersection cuts-a new type of cutting planes for integer programming, Oper. Res., 19, 19-39 (1971) · Zbl 0219.90035 |
| [101] | Marchand, H., A polyhedral study of the mixed knapsack set and its use to solve mixed integer programs (1998), Faculté des Sciences Appliquées, Université catholique de Louvain, (Ph.D. thesis) |
| [102] | Atamtürk, A., Cover and pack inequalities for (mixed) integer programming, Ann. Oper. Res., 139, 21-38 (2005) · Zbl 1091.90053 |
| [103] | Padberg, M.; Van Roy, T. J.; Wolsey, L. A., Valid linear inequalities for fixed charge problems, Oper. Res., 33, 842-861 (1985) · Zbl 0579.90072 |
| [104] | Martin, A.; Weismantel, R., Contributions to general mixed integer knapsack problems. Technical Report (1997), Konrad-Zuse-Zentrum für Informationstechnik |
| [105] | Marchand, H.; Wolsey, L., Aggregation and mixed integer rounding to solve MIPs, Oper. Res., 49, 363-371 (2001) · Zbl 1163.90671 |
| [106] | Crowder, H.; Johnson, E.; Padberg, M., Solving large-scale zero-one linear programming problems, Oper. Res., 31, 803-834 (1983) · Zbl 0576.90065 |
| [107] | Balas, E.; Saxena, A., Optimizing over the split closure, Math. Program., 113, 219-240 (2008) · Zbl 1135.90030 |
| [108] | Fischetti, M.; Salvagnin, D., Approximating the split closure, INFORMS J. Comput., 25, 808-819 (2013) |
| [109] | Achterberg, T.; Wunderling, R., Mixed integer programming: Analyzing 12 years of progress, (Jünger, M.; Reinelt, G., Facets of Combinatorial Optimization—Festschrift for Martin Grötschel (2013), Springer), 449-481 · Zbl 1317.90206 |
| [110] | Benders, J. F., Partitioning procedures for solving mixed-variables programming problems, Numer. Math., 4, 238-252 (1962) · Zbl 0109.38302 |
| [111] | Geoffrion, A. M., Generalized benders decomposition, J. Optim. Theory Appl., 10, 237-260 (1972) · Zbl 0229.90024 |
| [112] | Hernández-Pérez, H.; Salazar-González, J., A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery, Discrete Appl. Math., 145, 126-139 (2004) · Zbl 1058.90054 |
| [113] | Jünger, M.; Reinelt, G.; Thienel, S., Practical problem solving with cutting plane algorithms in combinatorial optimization, (Cook, W.; Lovász, L.; Seymour, P., Combinatorial Optimization. Combinatorial Optimization, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 20 (1995)), 111-152 · Zbl 0835.90076 |
| [114] | Mitchell, J. E., Branch-and-cut algorithms for combinatorial optimization problems, (Handbook Appl. Optim. (2002)), 65-77 |
| [115] | Dantzig, G. B.; Wolfe, P., Decomposition principle for linear programs, Oper. Res., 8, 101-111 (1960) · Zbl 0093.32806 |
| [116] | Barnhart, C.; Johnson, E. L.; Nemhauser, G. L.; Savelsbergh, M. W.P.; Vance, P. H., Branch-and-price: Column generation for solving huge integer programs, Oper. Res., 46, 316-329 (1998) · Zbl 0979.90092 |
| [117] | Lübbecke, M. E.; Desrosiers, J., Selected topics in column generation, Oper. Res., 53, 1007-1023 (2005) · Zbl 1165.90578 |
| [118] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W. H. Freeman · Zbl 0411.68039 |
| [119] | Vanderbeck, F., Branching in branch-and-price: a generic scheme, Math. Program., 130, 249-294 (2011) · Zbl 1229.90100 |
| [120] | Gualandi, S.; Malucelli, F., Exact solution of graph coloring problems via constraint programming and column generation, INFORMS J. Comput., 24, 81-100 (2012) · Zbl 1461.05091 |
| [121] | Easton, K.; Nemhauser, G.; Trick, M., Solving the travelling tournament problem: A combined integer programming and constraint programming approach, (Burke, E.; Causmaecker, P. D., Practice and Theory of Automated Timetabling IV. Practice and Theory of Automated Timetabling IV, Lect. Notes Comput. Sci., vol. 2740 (2003), Springer: Springer Berlin, Heidelberg), 100-109 |
| [124] | Fukasawa, R.; Longo, H.; Lysgaard, J.; Aragão, M. P.D.; Reis, M.; Uchoa, E.; Werneck, R. F., Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Math. Program., 106, 491-511 (2006) · Zbl 1094.90050 |
| [125] | Uchoa, E.; Fukasawa, R.; Lysgaard, J.; Pessoa, A.; de Aragão, M. P.; Andrade, D., Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation, Math. Program., 112, 443-472 (2008) · Zbl 1146.90059 |
| [126] | Rossi, F.; Beek, P. V.; Walsh, T., Handbook of Constraint Programming (2006), Elsevier Science · Zbl 1175.90011 |
| [127] | Kim, H.; Hooker, J. N., Solving fixed-charge network flow problems with a hybrid optimization and constraint programming approach, Ann. Oper. Res., 115, 95-124 (2002) · Zbl 1013.90010 |
| [128] | van Beek, P., Backtracking search algorithms, (Rossi, F.; van Beek, P.; Walsh, T., Foundations of Artificial Intelligence. Foundations of Artificial Intelligence, Handbook of Constraint Programming, vol. 2 (2006), Elsevier), 85-134, (Chapter 4) |
| [129] | Gamrath, G.; Koch, T.; Martin, A.; Miltenberger, M.; Weninger, D., Progress in presolving for mixed integer programming. Technical Report 13-48 (2013), Zuse Institute: Zuse Institute Berlin |
| [130] | Marques-Silva, J. P.; Sakallah, K. A., GRASP: A search algorithm for propositional satisfiability, IEEE Trans. Comput., 48, 506-521 (1999) · Zbl 1392.68388 |
| [131] | Caseau, Y.; Laburthe, F., Improving branch and bound for jobshop scheduling with constraint propagation, (Deza, M.; Euler, R.; Manoussakis, I., Combinatorics and Computer Science. Combinatorics and Computer Science, Lecture Notes in Computer Science, vol. 1120 (1996), Springer: Springer Berlin, Heidelberg), 129-149 · Zbl 07876626 |
| [132] | Fahle, T., Simple and fast: Improving a branch-and-bound algorithm for maximum clique, (Möhring, R.; Raman, R., Algorithms—ESA 2002. Algorithms—ESA 2002, Lect. Notes Comput. Sci., vol. 2461 (2002), Springer: Springer Berlin, Heidelberg), 485-498 · Zbl 1019.90517 |
| [133] | Li, C. M.; Manyà, F.; Planes, J., Exploiting unit propagation to compute lower bounds in branch and bound max-SAT solvers, (Beek, P. V., Principles and Practice of Constraint Programming—CP 2005. Principles and Practice of Constraint Programming—CP 2005, Lecture Notes in Computer Science, vol. 3709 (2005), Springer: Springer Berlin, Heidelberg), 403-414 · Zbl 1153.68470 |
| [135] | Achterberg, T., Conflict analysis in mixed integer programming, Discrete Optim., 4, 4-20 (2007) · Zbl 1169.90414 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
