Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond

• URL: http://arxiv.org/abs/2106.04033v1
• Date: Tue, 8 Jun 2021 00:57:59 GMT
• Title: Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond
• Authors: Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, Ellen Vitercik
• Abstract summary: State-of-the-art solvers integrate a myriad of cutting-plane techniques to speed up the underlying tree-search algorithm. We prove the first guarantees for learning high-performing cut-selection policies tailored to the instance distribution.
• Score: 98.92725321081994
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cutting-plane methods have enabled remarkable successes in integer programming over the last few decades. State-of-the-art solvers integrate a myriad of cutting-plane techniques to speed up the underlying tree-search algorithm used to find optimal solutions. In this paper we prove the first guarantees for learning high-performing cut-selection policies tailored to the instance distribution at hand using samples. We first bound the sample complexity of learning cutting planes from the canonical family of Chv\'atal-Gomory cuts. Our bounds handle any number of waves of any number of cuts and are fine tuned to the magnitudes of the constraint coefficients. Next, we prove sample complexity bounds for more sophisticated cut selection policies that use a combination of scoring rules to choose from a family of cuts. Finally, beyond the realm of cutting planes for integer programming, we develop a general abstraction of tree search that captures key components such as node selection and variable selection. For this abstraction, we bound the sample complexity of learning a good policy for building the search tree.

Related papers

• Learning Cut Generating Functions for Integer Programming [1.1510009152620668]
  The branch-and-cut algorithm is the method of choice to solve large scale integer programming problems. Recent advances have employed a data-driven approach to select optimal cutting planes from a parameterized family. We show that the selected CGF can outperform the GMI cuts for certain distributions.
  arXiv  Detail & Related papers  (2024-05-22T20:56:34Z)
• Learning bounded-degree polytrees with known skeleton [15.137372516678143]
  We establish finite-sample guarantees for efficient proper learning of bounded-degree polytrees. We provide an efficient algorithm which learns $d$-polytrees in time and sample complexity for any bounded $d$ when the underlying undirected graph is known.
  arXiv  Detail & Related papers  (2023-10-10T06:03:51Z)
• TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
  Branch-and-Bound is a convenient approach to solving optimization tasks in the form of Mixed Linear Programs. The efficiency of the solver depends on the branchning used to select a variable for splitting. We propose a reinforcement learning method that can efficiently learn the branching.
  arXiv  Detail & Related papers  (2023-06-09T14:01:26Z)
• Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts [88.94020638263467]
  The incorporation of cutting planes within the branch-and-bound algorithm, known as branch-and-cut, forms the backbone of modern integer programming solvers. We conduct a novel structural analysis of branch-and-cut that pins down how every step of the algorithm is affected by changes in the parameters defining the cutting planes added to the input integer program. Our main application of this analysis is to derive sample complexity guarantees for using machine learning to determine which cutting planes to apply during branch-and-cut.
  arXiv  Detail & Related papers  (2022-04-15T03:32:40Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  We propose a frequent itemset-driven search approach, which integrates the concept of frequent itemset mining in data mining into the well-known memetic search framework. It iteratively employs the frequent itemset recombination operator to generate promising offspring solution based on itemsets that frequently occur in high-quality solutions. In particular, it discovers 29 new upper bounds and matches 18 previous best-known bounds.
  arXiv  Detail & Related papers  (2022-01-18T11:16:40Z)
• Improved Learning Bounds for Branch-and-Cut [98.92725321081994]
  Branch-and-cut is the most widely used algorithm for solving integer programs. An increasingly popular approach is to use machine learning to tune these parameters. In this paper, we prove sample guarantees for this procedure.
  arXiv  Detail & Related papers  (2021-11-18T04:07:29Z)
• Learning to Select Cuts for Efficient Mixed-Integer Programming [46.60355046375608]
  We propose a data-driven and generalizable cut selection approach, named Cut Ranking, in the settings of multiple instance learning. Cut Ranking has been deployed in an industrial solver for large-scale MIPs. It has achieved the average speedup ratio of 12.42% over the production solver without any accuracy loss of solution.
  arXiv  Detail & Related papers  (2021-05-28T07:48:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.