Branch-and-Bound Algorithms as Polynomial-Time Approximation Schemes

References

• [1] Alvarez AM, Louveaux Q, Wehenkel L (2017) A machine learning-based approximation of strong branching. INFORMS J. Comput. 29(1):185–195.Link, Google Scholar
• [2] Balcan MF, Dick T, Sandholm T, Vitercik E (2018) Learning to branch. Dy J, Krause A, eds. Proc. 35th Internat. Conf. Machine Learn. Proc. Machine Learn. Res., vol. 80 (PMLR, New York), 344–353.Google Scholar
• [3] Bell T, Frieze A (2023) Solving a random asymmetric TSP exactly in quasi-polynomial time w.h.p. Preprint, submitted August 5, https://arxiv.org/abs/2308.02946.Google Scholar
• [4] Bengio Y, Lodi A, Prouvost A (2021) Machine learning for combinatorial optimization: A methodological tour d’horizon. Eur. J. Oper. Res. 290(2):405–421.Crossref, Google Scholar
• [5] Bolusani S, Besançon M, Bestuzheva K, Chmiela A, Dionísio J, Donkiewicz T, van Doornmalen J, et al. (2024) The SCIP Optimization Suite 9.0. Preprint, submitted February 27, https://arxiv.org/abs/2402.17702.Google Scholar
• [6] Borst S, Dadush D, Mikulincer D (2023) Integrality gaps for random integer programs via discrepancy. Bansal N, Nagarajan V, eds. Proc. 2023 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 1692–1733.Google Scholar
• [7] Borst S, Dadush D, Huiberts S, Tiwari S (2023) On the integrality gap of binary integer programs with Gaussian data. Math. Programming 197(2):1221–1263. Crossref, Google Scholar
• [8] Cacchiani V, Iori M, Locatelli A, Martello S (2022) Knapsack problems—An overview of recent advances. Part II: Multiple, multidimensional, and quadratic knapsack problems. Comput. Oper. Res. 143(C):105693. Crossref, Google Scholar
• [9] Chen B, Potts CN, Woeginger GJ (1998) A review of machine scheduling: Complexity, algorithms and approximability. Du DZ, Pardalos PM, eds. Handbook of Combinatorial Optimization, vol. 3 (Springer, Boston), 21–169.Crossref, Google Scholar
• [10] Chvátal V (1980) Hard knapsack problems. Oper. Res. 28(6):1402–1411.Link, Google Scholar
• [11] Dadush D, Tiwari S (2020) On the complexity of branching proofs. Saraf S, ed. 35th Comput. Complexity Conf. (CCC 2020) (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 34:1–34:35.Google Scholar
• [12] Dantzig GB (1957) Discrete variable extremum problems. Oper. Res. 5(2):266–277.Link, Google Scholar
• [13] Dash S (2005) Exponential lower bounds on the lengths of some classes of branch-and-cut proofs. Math. Oper. Res. 30(3):678–700.Link, Google Scholar
• [14] Dechter R, Pearl J (1985) Generalized best-first search strategies and the optimality of A*. J. ACM 32(3):505–536.Crossref, Google Scholar
• [15] Dey SS, Dubey Y, Molinaro M (2023) Lower bounds on the size of general branch-and-bound trees. Math. Programming 198(1):539–559.Crossref, Google Scholar
• [16] Dey SS, Dubey Y, Molinaro M (2023) Branch-and-bound solves random binary IPs in poly(n)-time. Math. Programming 200(1):569–587.Crossref, Google Scholar
• [17] Dey SS, Dubey Y, Molinaro M, Shah P (2024) A theoretical and computational analysis of full strong-branching. Math. Programming 205(1):303–336.Crossref, Google Scholar
• [18] Encz KI, Mastrolilli M, Vercesi E (2025) Branch-and-bound algorithms as polynomial-time approximation schemes. Censor-Hillel K, Grandoni F, Ouaknine J, Puppis G, eds. 52nd Internat. Colloquium Automata Languages Programming (ICALP 2025) (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 73:1–73:19.Google Scholar
• [19] Fishkin AV, Jansen K, Mastrolilli M (2008) Grouping techniques for scheduling problems: Simpler and faster. Algorithmica 51(2):183–199.Crossref, Google Scholar
• [20] Garey MR, Johnson DS (1975) Complexity results for multiprocessor scheduling under resource constraints. SIAM J. Comput. 4(4):397–411.Crossref, Google Scholar
• [21] Greenberg H, Hegerich RL (1970) A branch search algorithm for the knapsack problem. Management Sci. 16(5):327–332.Link, Google Scholar
• [22] Gupta P, Gasse M, Khalil EB, Kumar MP, Lodi A, Bengio Y (2020) Hybrid models for learning to branch. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Proc. 34th Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 18087–18097.Google Scholar
• [23] Hart PE, Nilsson NJ, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Systems Sci. Cybernetics 4(2):100–107.Crossref, Google Scholar
• [24] Horowitz E, Sahni S (1974) Computing partitions with applications to the knapsack problem. J. ACM 21(2):277–292.Crossref, Google Scholar
• [25] Horowitz E, Sahni S (1976) Exact and approximate algorithms for scheduling nonidentical processors. J. ACM 23(2):317–327.Crossref, Google Scholar
• [26] Ibarra OH, Kim CE (1975) Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4):463–468.Crossref, Google Scholar
• [27] Jansen K, Mastrolilli M (2004) Approximation schemes for parallel machine scheduling problems with controllable processing times. Comput. Oper. Res. 31(10):1565–1581.Crossref, Google Scholar
• [28] Khalil E, Le Bodic P, Song L, Nemhauser G, Dilkina B (2016) Learning to branch in mixed integer programming. Proc. AAAI Conf. Artificial Intelligence 30(1):724–731.Google Scholar
• [29] Kohler WH, Steiglitz K (1974) Characterization and theoretical comparison of branch-and-bound algorithms for permutation problems. J. ACM 21(1):140–156.Crossref, Google Scholar
• [30] Kolesar PJ (1967) A branch and bound algorithm for the knapsack problem. Management Sci. 13(9):723–735.Link, Google Scholar
• [31] Lawler EL (1979) Fast approximation algorithms for knapsack problems. Math. Oper. Res. 4(4):339–356.Link, Google Scholar
• [32] Lenstra JK, Shmoys DB, Tardos É (1987) Approximation algorithms for scheduling unrelated parallel machines. 28th Annual Sympos. Foundations Comput. Sci. (IEEE, New York), 217–224.Google Scholar
• [33] Lodi A, Zarpellon G (2017) On learning and branching: A survey. TOP 25(2):207–236. Crossref, Google Scholar
• [34] Margot F (2002) Pruning by isomorphism in branch-and-cut. Math. Programming 94(1):71–90. Crossref, Google Scholar
• [35] Martello S, Toth P (1990) Knapsack Problems: Algorithms and Computer Implementations (John Wiley & Sons, Inc., New York).Google Scholar
• [36] Martello S, Soumis F, Toth P (1997) Exact and approximation algorithms for makespan minimization on unrelated parallel machines. Discrete Appl. Math. 75(2):169–188.Crossref, Google Scholar
• [37] Mastrolilli M (2003) Efficient approximation schemes for scheduling problems with release dates and delivery times. J. Scheduling 6(6):521–531.Crossref, Google Scholar
• [38] Mastrolilli M (2004) Scheduling to minimize max flow time: Off-line and on-line algorithms. Internat. J. Foundations Comput. Sci. 15(2):385–401.Crossref, Google Scholar
• [39] Mastrolilli M (2006) A linear time approximation scheme for the single machine scheduling problem with controllable processing times. J. Algorithms 59(1):37–52.Crossref, Google Scholar
• [40] Mastrolilli M, Hutter M (2006) Hybrid rounding techniques for knapsack problems. Discrete Appl. Math. 154(4):640–649.Crossref, Google Scholar
• [41] Maudet G, Danoy G (2024) Search strategy generation for branch and bound using genetic programming. Preprint, submitted December 12, https://arxiv.org/abs/2412.09444v1.Google Scholar
• [42] Mokotoff E (2001) Parallel machine scheduling problems: A survey. Asia Pacific J. Oper. Res. 18(2):193–242.Google Scholar
• [43] Morrison DR, Jacobson SH, Sauppe JJ, Sewell EC (2016) Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optim. 19:79–102.Crossref, Google Scholar
• [44] Pataki G, Tural MK, Wong EB (2010) Basis reduction and the complexity of branch-and-bound. Charikar M, ed. Proc. 21st Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1254–1261.Google Scholar
• [45] Perron L, Furnon V (2024) OR-tools. Accessed October 30, 2025, https://developers.google.com/optimization/.Google Scholar
• [46] Scavuzzo L, Aardal KI, Lodi A, Yorke-Smith N (2024) Machine learning augmented branch and bound for mixed integer linear programming. Math. Programming 2025 Series B 210(1):1–49.Google Scholar
• [47] van de Velde SL (1993) Duality-based algorithms for scheduling unrelated parallel machines. INFORMS J. Comput. 5(2):192–205.Link, Google Scholar
• [48] Vazirani VV (2001) Approximation Algorithms (Springer, Berlin).Google Scholar