Fetching the paper…
Reading the bibliography…
In this paper, we surveyed the existing literature studying different approaches and algorithms for the four critical components in the general branch and bound (B&B) algorithm, namely, branching variable selection, node selection, node pruning, and cutting-plane selection.
A. H. Land and A. G. Doig, “An automatic method for solving discrete programming problems,” in Econometrica , 1960, vol. 28, no. 3, pp. 497–520
1960
Earlier work this paper cites.
R. Gomory, “An algorithm for the mixed integer problem,” Rand Corporation , 1960
1960
Earlier work this paper cites.
R. J. Dakin, “A tree-search algorithm for mixed integer programming problems,” The computer journal , vol. 8, no. 3, pp. 250–255, 1965
1965
Earlier work this paper cites.
P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE transactions on Systems Science and Cybernetics , vol. 4, no. 2, pp. 100–107, 1968
1968
Earlier work this paper cites.
M. Bénichou, J.-M. Gauthier, P. Girodet, G. Hentges, G. Ribière, and O. Vincent, “Experiments in mixed-integer linear programming,” Mathematical Programming , vol. 1, no. 1, pp. 76–94, 1971
1971
Earlier work this paper cites.
V. Chvátal, “Edmonds polytopes and a hierarchy of combinatorial problems,” Discrete Mathematics , vol. 4, no. 4, pp. 305–337, 1973
1973
Earlier work this paper cites.
J. Forrest, J. Hirst, and J. A. Tomlin, “Practical solution of large mixed integer programming problems with umpire,” Management Science , vol. 20, no. 5, pp. 736–773, 1974
1974
Earlier work this paper cites.
W. H. Kohler and K. Steiglitz, “Characterization and theoretical comparison of branch-and-bound algorithms for permutation problems,” Journal of the ACM (JACM) , vol. 21, no. 1, pp. 140–156, 1974
1974
Earlier work this paper cites.
T. Ibaraki, “The power of dominance relations in branch-and-bound algorithms,” Journal of the ACM (JACM) , vol. 24, no. 2, pp. 264–279, 1977
1977
Earlier work this paper cites.
P. G. Falk, “Experiments in mixed integer linear programming in a manufacturing system,” Omega , vol. 8, no. 4, pp. 473–484, 1980
1980
Earlier work this paper cites.
H. Crowder, E. L. Johnson, and M. Padberg, “Solving large-scale zero-one linear programming problems,” Operations Research , vol. 31, no. 5, pp. 803–834, 1983
1983
Earlier work this paper cites.
F. A. Al-Khayyal and J. E. Falk, “Jointly constrained biconvex programming,” Mathematics of Operations Research , vol. 8, no. 2, pp. 273–286, 1983
1983
Earlier work this paper cites.
M. W. Padberg, T. J. Van Roy, and L. A. Wolsey, “Valid linear inequalities for fixed charge problems,” Operations Research , vol. 33, no. 4, pp. 842–861, 1985. [Online]. Available: https://doi.org/10.1287/opre.33.4.842
1985
Earlier work this paper cites.
T. J. Van Roy and L. A. Wolsey, “Valid inequalities for mixed 0-1 programs,” Discrete Applied Mathematics , vol. 14, no. 2, pp. 199–213, 1986. [Online]. Available: https://www.sciencedirect.com/science/article/pii/0166218X86900612
1986
Earlier work this paper cites.
F. Glover, “Future paths for integer programming and links to artificial intelligence,” Computers & operations research , vol. 13, no. 5, pp. 533–549, 1986
1986
Earlier work this paper cites.
F. Glover and H. J. Greenberg, “New approaches for heuristic search: A bilateral linkage with artificial intelligence,” European Journal of Operational Research , vol. 39, no. 2, pp. 119–130, 1989
1989
Earlier work this paper cites.
G. L. Nemhauser and L. A. Wolsey, “A recursive procedure to generate all cuts for 0–1 mixed integer programs,” Mathematical Programming , vol. 46, no. 1-3, pp. 379–390, 1990
1990
Earlier work this paper cites.
W. Cook, R. Kannan, and A. Schrijver, “Chvátal closures for mixed integer programming problems,” Mathematical Programming , vol. 47, no. 1-3, pp. 155–174, 1990
1990
Earlier work this paper cites.
M. Padberg and G. Rinaldi, “A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems,” SIAM Review , vol. 33, no. 1, pp. 60–100, 1991. [Online]. Available: https://doi.org/10.1137/1033004
1991
Earlier work this paper cites.
L. Lovász and A. Schrijver, “Cones of matrices and set-functions and 0–1 optimization,” Siam J Opt , vol. 1, no. 2, pp. 166–190, 1991
1991
Earlier work this paper cites.
E. Balas, S. Ceria, and G. Cornuéjols, “A lift-and-project cutting plane algorithm for mixed 0–1 programs,” Mathematical Programming , vol. 58, no. 1-3, pp. 295–324, 1993
1993
Earlier work this paper cites.
M. W. Savelsbergh, “Preprocessing and probing techniques for mixed integer programming problems,” ORSA Journal on Computing , vol. 6, no. 4, pp. 445–454, 1994
1994
Earlier work this paper cites.
R. Bixby and W. Cook, “Finding cuts in the tsp (a preliminary report),” Surgery , vol. 89, no. 12, 1995
1995
Earlier work this paper cites.
K. Aardal, Y. Pochet, and L. A. Wolsey, “Capacitated facility location: valid inequalities and facets,” Mathematics of Operations Research , vol. 20, no. 3, pp. 562–582, 1995
1995
Earlier work this paper cites.
E. Balas, S. Ceria, and G. Cornuéjols, “Mixed 0-1 programming by lift-and-project in a branch-and-cut framework,” Management Science , vol. 42, no. 9, pp. 1229–1246, 1996. [Online]. Available: https://doi.org/10.1287/mnsc.42.9.1229
1996
Earlier work this paper cites.
H. Marchand, “A polyhedral study of the mixed knapsack set and its use to solve mixed integer programs,” Ph.D. dissertation, UCL-Université Catholique de Louvain, 1998
1998
Earlier work this paper cites.
J. Clausen, “Branch and bound algorithms-principles and examples,” Department of Computer Science, University of Copenhagen , pp. 1–30, 1999
1999
Earlier work this paper cites.
A. Martin, “Integer programs with block structure,” 1999
1999
Earlier work this paper cites.
J. T. Linderoth and M. W. P. Savelsbergh, “A computational study of search strategies for mixed integer programming,” INFORMS Journal on Computing , vol. 11, no. 2, pp. 173–187, 1999. [Online]. Available: https://doi.org/10.1287/ijoc.11.2.173
1999
Earlier work this paper cites.
J. T. Linderoth and M. W. Savelsbergh, “A computational study of search strategies for mixed integer programming,” INFORMS Journal on Computing , vol. 11, no. 2, pp. 173–187, 1999
1999
Earlier work this paper cites.
R. L. van de Leensel, C. Van Hoesel, and J. Van de Klundert, “Lifting valid inequalities for the precedence constrained knapsack problem,” Mathematical programming , vol. 86, no. 1, pp. 161–185, 1999
1999
Earlier work this paper cites.
E. Demeulemeester, W. Herroelen et al. , “The discrete time/resource trade-off problem in project networks: a branch-and-bound approach,” IIE transactions , vol. 32, no. 11, pp. 1059–1069, 2000
2000
Earlier work this paper cites.
A. Atamtürk, G. L. Nemhauser, and M. W. Savelsbergh, “Conflict graphs in solving integer programming problems,” European Journal of Operational Research , vol. 121, no. 1, pp. 40–55, 2000
2000
Earlier work this paper cites.
E. Balas, S. Ceria, M. Dawande, F. Margot, and G. Pataki, “Octane: A new heuristic for pure 0–1 programs,” Operations Research , vol. 49, no. 2, pp. 207–225, 2001
2001
Earlier work this paper cites.
H. Marchand and L. A. Wolsey, “Aggregation and mixed integer rounding to solve mips,” Operations research , vol. 49, no. 3, pp. 363–371, 2001
2001
Earlier work this paper cites.
S. Arora, B. Bollobás, and L. Lovász, “Proving integrality gaps without knowing the linear program,” in The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. IEEE, 2002, pp. 313–322
2002
Earlier work this paper cites.
F. Margot, “Pruning by isomorphism in branch-and-cut,” Mathematical Programming , vol. 94, no. 1, pp. 71–90, 2002
2002
Earlier work this paper cites.
H. Marchand, A. Martin, R. Weismantel, and L. Wolsey, “Cutting planes in integer and mixed integer programming,” Discrete Applied Mathematics , vol. 123, no. 1-3, pp. 397–446, 2002
2002
Earlier work this paper cites.
M. Fischetti and A. Lodi, “Local branching,” Mathematical programming , vol. 98, no. 1, pp. 23–47, 2003
2003
Earlier work this paper cites.
——, “Exploiting orbits in symmetric ilp,” Mathematical Programming , vol. 98, no. 1, pp. 3–21, 2003
2003
Cited alongside, same era.
T. Achterberg, T. Koch, and A. Martin, “Branching rules revisited,” Operations Research Letters , vol. 33, no. 1, pp. 42–54, 2005. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0167637704000501
2005
Cited alongside, same era.
M. Fischetti, F. Glover, and A. Lodi, “The feasibility pump,” Mathematical Programming , vol. 104, no. 1, pp. 91–104, 2005
2005
Cited alongside, same era.
E. Danna, E. Rothberg, and C. Le Pape, “Exploring relaxation induced neighborhoods to improve mip solutions,” Mathematical Programming , vol. 102, no. 1, pp. 71–90, 2005
2005
Cited alongside, same era.
A. Atamtuerk, “Cover and pack inequalities for (mixed) integer programming,” Annals of Operations Research , vol. 139, no. 1, pp. 21–38, 2005
I. Goodfellow, Y. Bengio, A. Courville, and Y. Bengio, Deep learning . MIT press Cambridge, 2016, vol. 1, no. 2
2016
Later among the works it cites.
A. Marcos Alvarez, L. Wehenkel, and Q. Louveaux, “Online learning for strong branching approximation in branch-and-bound,” 2016
2016
Later among the works it cites.
E. Khalil, P. Le Bodic, L. Song, G. Nemhauser, and B. Dilkina, “Learning to branch in mixed integer programming,” Proceedings of the AAAI Conference on Artificial Intelligence , vol. 30, no. 1, Feb. 2016. [Online]. Available: https://ojs.aaai.org/index.php/AAAI/article/view/10080
2016
Later among the works it cites.
G. Di Liberto, S. Kadioglu, K. Leo, and Y. Malitsky, “Dash: Dynamic approach for switching heuristics,” European Journal of Operational Research , vol. 248, no. 3, pp. 943–953, 2016
2016
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2005
Cited alongside, same era.
T. Berthold, “Primal heuristics for mixed integer programs,” 2006
2006
Cited alongside, same era.
C. M. Bishop, Pattern recognition and machine learning . springer, 2006
2006
Cited alongside, same era.
P. Geurts, D. Ernst, and L. Wehenkel, “Extremely randomized trees,” Machine learning , vol. 63, no. 1, pp. 3–42, 2006
2006
Cited alongside, same era.
T. Achterberg, “Constraint integer programming,” 2007
2007
Cited alongside, same era.
E. Rothberg, “An evolutionary algorithm for polishing mixed integer programming solutions,” INFORMS Journal on Computing , vol. 19, no. 4, pp. 534–541, 2007
2007
Cited alongside, same era.
A. Nahapetyan and P. M. Pardalos, “A bilinear relaxation based algorithm for concave piecewise linear network flow problems,” Journal of Industrial & Management Optimization , vol. 3, no. 1, p. 71, 2007
2007
Cited alongside, same era.
P. Bonami, G. Cornuéjols, S. Dash, M. Fischetti, and A. Lodi, “Projected chvátal–gomory cuts for mixed integer linear programs,” Mathematical Programming , vol. 113, no. 2, pp. 241–257, 2008
2008
Cited alongside, same era.
2017
Later among the works it cites.
A. Lodi and G. Zarpellon, “On learning and branching: a survey,” Top , vol. 25, no. 2, pp. 207–236, 2017
2017
Later among the works it cites.
C. Ansótegui, J. Pon, M. Sellmann, and K. Tierney, “Reactive dialectic search portfolios for maxsat,” in Proceedings of the AAAI Conference on Artificial Intelligence , vol. 31, no. 1, 2017
2017
Later among the works it cites.
D. Karapetyan, A. P. Punnen, and A. J. Parkes, “Markov chain methods for the bipartite boolean quadratic programming problem,” European Journal of Operational Research , vol. 260, no. 2, pp. 494–506, 2017
2017
Later among the works it cites.
E. B. Khalil, B. Dilkina, G. L. Nemhauser, S. Ahmed, and Y. Shao, “Learning to run heuristics in tree search.” in IJCAI , 2017, pp. 659–666
2017
Later among the works it cites.
——, “A computational study of primal heuristics inside an mi (nl) p solver,” Journal of Global Optimization , vol. 70, no. 1, pp. 189–206, 2018
2018
Later among the works it cites.
S. S. Dey and M. Molinaro, “Theoretical challenges towards cutting-plane selection,” Mathematical Programming , vol. 170, no. 1, pp. 1–30, 2018
2018
Later among the works it cites.
R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction . MIT press, 2018
2018
Later among the works it cites.
M.-F. Balcan, T. Dick, T. Sandholm, and E. Vitercik, “Learning to branch,” in Proceedings of the 35th International Conference on Machine Learning , ser. Proceedings of Machine Learning Research, J. Dy and A. Krause, Eds., vol. 80. PMLR, 10–15 Jul 2018, pp. 344–353. [Online]. Available: http://proceedings.mlr.press/v80/balcan18a.html
2018
Later among the works it cites.
A. Gleixner, M. Bastubbe, L. Eifler, T. Gally, G. Gamrath, R. L. Gottwald, G. Hendel, C. Hojny, T. Koch, M. Lübbecke, S. J. Maher, M. Miltenberger, B. Müller, M. Pfetsch, C. Puchert, D. Rehfeldt, F. Schlösser, C. Schubert, F. Serrano, Y. Shinano, J. M. Viernickel, M. Walter, F. Wegscheider, J. T. Witt, and J. Witzig, “The scip optimization suite 6.0,” ZIB, Takustr. 7, 14195 Berlin, Tech. Rep. 18-26, 2018
2018
Later among the works it cites.
2018
Later among the works it cites.
G. Hendel, “Adaptive large neighborhood search for mixed integer programming,” 2018
2018
Later among the works it cites.
R. Baltean-Lugojan, P. Bonami, R. Misener, and A. Tramontani, “Selecting cutting planes for quadratic semidefinite outer-approximation via trained neural networks,” Technical Report, CPLEX Optimization, IBM, Tech. Rep., 2018
2018
Later among the works it cites.
2019
Later among the works it cites.
2019
Later among the works it cites.
Y. Shen, Y. Shi, J. Zhang, and K. B. Letaief, “Lorm: Learning to optimize for resource management in wireless networks with few training samples,” IEEE Transactions on Wireless Communications , vol. 19, no. 1, pp. 665–679, 2019
2019
Later among the works it cites.
M. Lee, G. Yu, and G. Y. Li, “Learning to branch: Accelerating resource allocation in wireless networks,” IEEE Transactions on Vehicular Technology , vol. 69, no. 1, pp. 958–970, 2019
2019
Later among the works it cites.
G. Zarpellon, J. Jo, A. Lodi, and Y. Bengio, “Parameterizing branch-and-bound search trees to learn branching policies,” 2020
2020
Later among the works it cites.
2020
Later among the works it cites.
2020
Later among the works it cites.
G. Gamrath, D. Anderson, K. Bestuzheva, W.-K. Chen, L. Eifler, M. Gasse, P. Gemander, A. Gleixner, L. Gottwald, K. Halbig et al. , “The scip optimization suite 7.0,” 2020
2020
Later among the works it cites.
H. Sun, W. Chen, H. Li, and L. Song, “Improving learning to branch via reinforcement learning,” in Learning Meets Combinatorial Algorithms at NeurIPS2020 , 2020. [Online]. Available: https://openreview.net/forum?id=z4D7-PTxTb
2020
Later among the works it cites.
M. Etheve, Z. Alès, C. Bissuel, O. Juan, and S. Kedad-Sidhoum, “Reinforcement learning for variable selection in a branch and bound algorithm,” in Integration of Constraint Programming, Artificial Intelligence, and Operations Research , E. Hebrard and N. Musliu, Eds. Cham: Springer International Publishing, 2020, pp. 176–185
2020
Later among the works it cites.
A. Hottung, S. Tanaka, and K. Tierney, “Deep learning assisted heuristic tree search for the container pre-marshalling problem,” Computers & Operations Research , vol. 113, p. 104781, 2020
2020
Later among the works it cites.
R. Addanki, V. Nair, and M. Alizadeh, “Neural large neighborhood search,” in Learning Meets Combinatorial Algorithms NeurIPS Workshop , 2020
2020
Later among the works it cites.
2020
Later among the works it cites.
Á. S. Xavier, F. Qiu, and S. Ahmed, “Learning to solve large-scale security-constrained unit commitment problems,” INFORMS Journal on Computing , 2020
2020
Later among the works it cites.
J.-Y. Ding, C. Zhang, L. Shen, S. Li, B. Wang, Y. Xu, and L. Song, “Accelerating primal solution findings for mixed integer programs based on solution prediction,” in Proceedings of the AAAI Conference on Artificial Intelligence , vol. 34, no. 02, 2020, pp. 1452–1459
2020
Later among the works it cites.
G. Aglin, S. Nijssen, and P. Schaus, “Learning optimal decision trees using caching branch-and-bound search,” in Proceedings of the AAAI Conference on Artificial Intelligence , vol. 34, no. 04, 2020, pp. 3146–3153
2020
Later among the works it cites.
Y. Tang, S. Agrawal, and Y. Faenza, “Reinforcement learning for integer programming: Learning to cut,” in Proceedings of the 37th International Conference on Machine Learning , ser. Proceedings of Machine Learning Research, H. D. III and A. Singh, Eds., vol. 119. PMLR, 13–18 Jul 2020, pp. 9367–9376. [Online]. Available: http://proceedings.mlr.press/v119/tang20a.html
2020
Later among the works it cites.
K. Yilmaz and N. Yorke-Smith, “A study of learning search approximation in mixed integer branch and bound: Node selection in scip,” AI , vol. 2, no. 2, pp. 150–178, 2021
2021
Closest in time.
2021
Closest in time.
S. S. Dey, A. M. Kazachkov, A. Lodi, and G. Munoz, “Cutting plane generation through sparse principal component analysis,” URL http://www. optimization-online. org/DB_HTML/2021/02/8259. html , 2021
2021
Closest in time.
K.-W. Chang, A. Krishnamurthy, A. Agarwal, H. Daume, and J. Langford, “Learning to search better than your teacher,” in International Conference on Machine Learning . PMLR, 2015, pp. 2058–2066
2066
Closest in time.