Learning to Branch
Maria-Florina Balcan Travis Dick Tuomas Sandholm Ellen Vitercik




Learning to Branch[Authors' addresses: ]
    Maria-Florina Balcan Travis Dick Tuomas Sandholm Ellen Vitercik
    December 24, 2016
===================================================================




Tree search algorithms, such as branch-and-bound, are the most widely used tools for solving combinatorial and nonconvex problems. For example, they are the foremost method for solving (mixed) integer programs and constraint satisfaction problems. Tree search algorithms recursively partition the search space to find an optimal solution. In order to keep the tree size small, it is crucial to carefully decide, when expanding a tree node, which question (typically variable) to branch on at that node in order to partition the remaining space. Numerous partitioning techniques (e.g., variable selection) have been proposed, but there is no theory describing which technique is optimal. We show how to use machine learning to determine an optimal weighting of any set of partitioning procedures for the instance distribution at hand using samples from the distribution. We provide the first sample complexity guarantees for tree search algorithm configuration. These guarantees bound the number of samples sufficient to ensure that the empirical performance of an algorithm over the samples nearly matches its expected performance on the unknown instance distribution. This thorough theoretical investigation naturally gives rise to our learning algorithm. Via experiments, we show that learning an optimal weighting of partitioning procedures can dramatically reduce tree size, and we prove that this reduction can even be exponential. Through theory and experiments, we show that learning to branch is both practical and hugely beneficial.




§ INTRODUCTION


Many widely-used algorithms are customizable: they have tunable parameters that have an enormous effect on runtime, solution quality, or both. Tuning parameters by hand is notoriously tedious and time-consuming. In this work, we study algorithm configuration via machine learning, where the goal is to design algorithms that learn the optimal parameter setting for the problem instance distribution at hand.

We study configuration of tree search algorithms. These algorithms are the most widely used tools for solving  combinatorial and nonconvex problems throughout artificial intelligence, operations research, and beyond (e.g., <cit.>). For example, branch-and-bound (B&B) algorithms <cit.> solve mixed integer linear programs (MILPs),  and thus have diverse applications, including ones in
machine learning such as MAP estimation <cit.>, object recognition <cit.>, clustering <cit.>, and semi-supervised SVMs <cit.>.

A tree search algorithm systematically partitions the search space to find an optimal solution. The algorithm organizes this partition via a tree: the original problem is at the root and the children of a given node represent the subproblems formed by partitioning the feasible set of the parent node. A branch is pruned if it is infeasible or it cannot produce a better solution than the best one found so far by the algorithm.
Typically the search space is partitioned by adding an additional constraint on some variable.  For example, suppose the feasible set is defined by the constraint Ax⃗≤b⃗, with x⃗∈{0,1}^n. A tree search algorithm might partition this feasible set into two sets, one where A x⃗≤b⃗, x_1 = 0, and x_2, …, x_n ∈{0,1}, and another where A x⃗≤b⃗, x_1 = 1, and x_2, …, x_n ∈{0,1}, in which case the algorithm has branched on x_1.
A crucial question in tree search algorithm design is determining which variable to branch on at each step. An effective variable selection policy can have a tremendous effect on the size of the tree. Currently, there is no known optimal strategy and the vast majority of existing techniques are backed only by empirical comparisons. In the worst-case, finding an approximately optimal branching variable, even at the root of the tree alone, is NP-hard. This is true even in the case of satisfiability, which is a special case of constraint satisfaction and of
MILP <cit.>.

In this work, rather than attempt to characterize a branching strategy that is universally optimal, we show empirically and theoretically that it is possible to learn high-performing branching strategies for a given application domain. We model an application domain as a distribution over problem instances, such as a distribution over scheduling problems that an airline solves on a day-to-day basis. This model is standard throughout the algorithm configuration literature (e.g., <cit.>). The approach has also been used on large-scale problems in industry to configure and select winner determination algorithms for clearing tens of billions of dollars of combinatorial auctions <cit.>. The algorithm designer does not know the underlying distribution over problem instances, but has sample access to the distribution. We show how to use samples from the distribution to learn a variable selection policy that will result in as small a search tree as possible in expectation over the underlying distribution.

Our learning algorithm adaptively partitions the parameter space of the variable selection policy into regions where for any parameter in a given region, the resulting tree sizes across the training set are invariant. The learning algorithm returns the empirically optimal parameter over the training set, and thus performs empirical risk minimization (ERM). We prove that the adaptive nature of our algorithm is necessary: performing ERM over a data-independent discretization of the parameter space can be disastrous. In particular, for any discretization of the parameter space, we provide an infinite family of distributions over MILP instances such that every point in the discretization results in a B&B tree with exponential size in expectation, but there exist infinitely-many parameters outside of the discretized points that result in a tree with constant size with probability 1. A small change in parameters can thus cause a drastic change in the algorithm's behavior. This fact contradicts conventional wisdom. For example, SCIP, the best  open-source MILP solver, sets one of the parameters we investigate to 5/6, regardless of the input MILP's structure. <cit.> wrote that 5/6 was empirically optimal when compared against four other data-independent values. In contrast, our analysis shows that a data-driven approach to parameter tuning can have an enormous benefit.

The sensitivity of tree search algorithms to small changes in their parameters is a key challenge that differentiates our sample complexity analysis from those typically found in machine learning. For many well-understood function classes in machine learning, there is a close connection between the distance in parameter space between two parameter vectors and the distance in function space between the two corresponding functions. Understanding this connection is a necessary prerequisite to analyzing how many significantly different functions there are in the class, and thereby quantifying the class's intrinsic complexity. Intrinsic complexity typically translates to VC dimension, Rademacher complexity, or some other metric which allows us to derive learnability guarantees. Since the tree size of a search algorithm as a function of its parameters does not exhibit this predictable behavior, we must carefully analyze the way in which the parameters influence each step of the procedure in order to derive learning algorithms with strong guarantees.
In doing so, we present the first sample complexity guarantees for automated configuration of tree search algorithms. We provide worst-case bounds proving that a surprisingly small number of samples are sufficient for strong learnability guarantees: the sample complexity bound grows quadratically in the size of the problem instance, despite the complexity of the algorithms we study.

In our experiments section, we show that on many datasets based on real-world NP-hard problems, different parameters can result in B&B trees of vastly different sizes.
Using an optimal parameter for one distribution on problems from a different distribution can lead to a dramatic tree size blowup.
We also provide data-dependent generalization guarantees that allow the algorithm designer to use far fewer samples than in the worst case if the data is well-structured.



 §.§ Related work


Several works have studied the use of machine learning techniques in the context of B&B; for an overview, see the summary by <cit.>.

As in this work, <cit.> study variable selection policies. Their goal is to find a variable selection strategy that mimics the behavior of the classic branching strategy known as strong branching while running faster than strong branching. <cit.> study a similar problem, although in their work, the feature vectors in the training set describe nodes from multiple MILP instances. Neither or these works come with any theoretical guarantees, unlike our work.

Several other works study data-driven variable selection from a purely experimental perspective. <cit.>
devise an algorithm that learns how to dynamically switch
between different branching heuristics along the branching tree. <cit.> propose techniques for choosing problem-specific branching rules based on a partial B&B tree. Ideally, these branching rules will choose variables that will lead to fast fathoming. They do not rely on any techniques from machine learning. In the context of CSP tree search, <cit.> apply existing multi-armed bandit algorithms
to learning variable selection policies during tree search and <cit.> use a bandit approach to select different levels of propagation during search.

Other works have explored the use of machine learning techniques in the context of other aspects of B&B beyond variable selection. For example, <cit.> use machine learning to speed up branch-and-bound, focusing on speeding up the node selection policy. Their work does not provide any learning-theoretic guarantees.
Other works that have studied machine learning techniques for branch-and-bound problems other than variable selection include <cit.>, who also study how to devise node selection policies, <cit.>, who study how to set CPLEX parameters, <cit.>, who study how to detect decomposable model structure, and <cit.>, who study how to determine when to run heuristics.

From a theoretical perspective, <cit.> present a theoretical model for the selection of branching variables. It is based upon an abstraction of MIPs to a simpler setting in which it is possible to analytically evaluate the dual bound improvement of choosing a given variable. Based on this model, they present a new variable selection policy which has strong performance on many MIPLIB instances. Unlike our work, this paper is unrelated to machine learning.

The learning-theoretic model of algorithm configuration that we study in this paper was introduced to the theoretical computer science community by <cit.>. Under this model, an application domain is modeled as a distribution over problem instances and the goal is to PAC-learn an algorithm that is nearly optimal over the distribution. This model was later studied by <cit.> as well.
These papers were purely theoretical. In contrast, we show that the techniques proposed in this paper are practical as well, and provide significant benefit.

We provide a more detailed description of several of these papers in Appendix <ref>.



§ TREE SEARCH


Tree search is a broad family of algorithms with diverse applications. 
To exemplify the specifics of tree search, we present a vast family of NP-hard problems — (mixed) integer linear programs — and describe how tree search finds optimal solutions to problems from this family. Later on in Section <ref>, we provide another example of tree search for constraint satisfaction problems. In Appendix <ref>, we provide a formal, more abstract definition of tree search and generalize our results to this more general algorithm.


 §.§ Mixed integer linear programs


We study mixed integer linear programs (MILPs)
where the objective is to maximize c⃗^⊤x⃗ subject to Ax⃗≤b⃗ and where some of the entries of x⃗ are constrained to be in {0,1}.
Given a MILP Q, we denote an optimal solution to the LP relaxation of Q as x̆⃗̆_Q = (x̆_Q[1], …x̆_Q[n]). Throughout this work, given a vector a⃗, we use the notation a[i] to denote the i^th component of a⃗. We also use the notation c̆_Q to denote the optimal objective value of the LP relaxation of Q. In other words, c̆_Q = c⃗^⊤x̆⃗̆_Q.

[Winner determination]
Suppose there is a set {1, …, m} of items for sale and a set {1, …, n} of buyers. In a combinatorial auction, each buyer i submits bids v_i(b) for any number of bundles b ⊆{1, …, m}. The goal of the winner determination problem is to allocate the goods among the bidders so as to maximize social welfare, which is the sum of the buyers' values for the bundles they are allocated. We can model this problem as a MILP by assigning a binary variable x_i,b for every buyer i and every bundle b they submit a bid v_i(b) on. The variable x_i,b is equal to 1 if and only if buyer i receives the bundle b. Let B_i be the set of all bundles b that buyer i submits a bid on. An allocation is feasible if it allocates no item more than once (∑_i = 1^n ∑_b ∈ B_i, j ∋ b x_i,b≤ 1 for all j ∈{1, …, m}) and if each bidder receives at most one bundle (∑_b ∈ B_i x_i,b≤ 1 for all i ∈{1, …, n}).
Therefore, the MILP is:

    [                            maximize    ∑_i = 1^n ∑_b ∈ B_i v_i(b) x_i,b;                                s.t. ∑_i = 1^n ∑_b ∈ B_i, j ∋ b x_i,b≤ 1                           ∀ j ∈ [m];                                                      ∑_b ∈ B_i x_i,b≤ 1                           ∀ i ∈ [n];                                                             x_i,b∈{0,1}                 ∀ i ∈ [n], b ∈ B_i. ]




  §.§.§ MILP tree search

MILPs are typically solved using a tree search algorithm called branch-and-bound (B&B).
Given a MILP problem instance, B&B relies on two subroutines that efficiently compute upper and lower bounds on the optimal value within a given region of the search space. The lower bound can be found by choosing any feasible point in the region. An upper bound can be found via a linear programming relaxation. The basic idea of B&B is to partition the search space into convex sets and find upper and lower bounds on the optimal solution within each. The algorithm uses these bounds to form global upper and lower bounds, and if these are equal, the algorithm terminates, since the feasible solution corresponding to the global lower bound must be optimal. If the global upper and lower bounds are not equal, the algorithm refines the partition and repeats.

In more detail, suppose we want to use B&B to solve a MILP Q'. B&B iteratively builds a search tree  with the original MILP Q' at the root. In the first iteration,  consists of a single node containing the MILP Q'. At each iteration, B&B uses a node selection policy (which we expand on later) to select a leaf node of the tree , which corresponds to a MILP Q. B&B then uses a variable selection policy (which we expand on in Section <ref>) to choose a variable x_i of the MILP Q to branch on. Specifically, let Q^+_i (resp., Q^-_i) be the MILP Q except with the additional constraint that x_i = 1 (resp., x_i = 0). B&B sets the right (resp., left) child of  in  to be a node containing the MILP Q^+_i (resp., Q^-_i). B&B then tries to “fathom” these leafs: the leaf containing Q^+_i (resp., Q^-_i) is fathomed if:


  * The optimal solution to the LP relaxation of Q^+_i (resp., Q^-_i) satisfies the constraints of the original MILP Q'.

  * The relaxation of Q^+_i (resp., Q^-_i) is infeasible, so Q^+_i (resp., Q^-_i) must be infeasible as well.

  * The objective value of the LP relaxation of Q^+_i (resp., Q^-_i) is smaller than the objective value of the best known feasible solution, so the optimal solution to Q^+_i (resp., Q^-_i) is no better than the best known feasible solution.

B&B terminates when every leaf has been fathomed. It returns the best known feasible solution, which is optimal. See Algorithm <ref> for the pseudocode.


The most common node selection policy is the best bound policy. Given a B&B tree, it selects the unfathomed leaf containing the MILP Q with the maximum LP relaxation objective value. Another common policy is the depth-first policy, which selects the next unfathomed leaf in the tree in depth-first order.



In Figure <ref>, we show the search tree built by B&B given as input the following MILP <cit.>: 
    [                                                      maximize          40x_1 + 60x_2 + 10x_3 + 10x_4 + 3x_5 + 20x_6 + 60x_7;                                                    subject to 40x_1 + 50x_2 + 30x_3 + 10x_4 + 10x_5 + 40 x_6 + 30 x_7 ≤ 100;                                                                                                         x_1, …, x_7 ∈{0,1}. ]
 Each rectangle denotes a node in the B&B tree. Given a node , the top portion of its rectangle displays the optimal solution x̆⃗̆_Q to the LP relaxation of Q, which is the MILP (<ref>) with the additional constraints labeling the edges from the root to . The bottom portion of the rectangle corresponding to Q displays the objective value c̆_Q of the optimal solution to this LP relaxation, i.e., c̆_Q = (40, 60, 10, 10, 3, 20, 60) ·x̆⃗̆_Q. In this example, the node selection policy is the best bound policy and the variable selection policy selects the “most fractional” variable: the variable x_i such that x̆_Q[i] is closest to 1/2, i.e., i = {min{1 - x̆_[i], x̆_[i]}}. 

In Figure <ref>, the algorithm first explores the root. At this point, it has the option of exploring either the left or the right child. Since the optimal objective value of the right child (136) is greater than the optimal objective value of the left child (135), B&B will next explore the pink node (marked 1). Next, B&B can either explore either of the pink node's children or the orange node (marked 2). Since the optimal objective value of the orange node (135) is greater than the optimal objective values of the pink node's children (120), B&B will next explore the orange node. After that B&B can explore either of the orange node's children or either of the pink node's children. The optimal objective value of the green node (marked 3) is higher than the optimal objective values of the orange node's right child (116) and the pink node's children (120), so B&B will next explore the green node. At this point, it finds an integral solution, which satisfies all of the constraints of the original MILP (<ref>). This integral solution has an objective value of 133. Since all of the other leafs have smaller objective values, the algorithm cannot find a better solution by exploring those leafs. Therefore, the algorithm fathoms all of the leafs and terminates.





  §.§.§ Variable selection in MILP tree search


Variable selection policies typically depend on a real-valued score per variable x_i.

Let  be a deterministic function that takes as input a partial search tree , a leaf Q of that tree, and an index i and returns a real value ((, Q, i) ∈). For a leaf Q of a tree , let N_, Q be the set of variables that have not yet been branched on along the path from the root of  to Q. A score-based variable selection policy selects the variable _x_j ∈ N_, Q{(, Q, j)} to branch on at the node Q.


We list several common definitions of the function  below. Recall that for a MILP Q with objective function c⃗·x⃗, we denote an optimal solution to the LP relaxation of Q as x̆⃗̆_Q = (x̆_Q[1], …x̆_Q[n]). We also use the notation c̆_Q to denote the objective value of the optimal solution to the LP relaxation of Q, i.e., c̆_Q = c⃗^⊤x̆⃗̆_Q. Finally, we use the notation Q_i^+ (resp., Q_i^-) to denote the MILP Q with the additional constraint that x_i = 1 (resp., x_i = 0). If Q_i^+ (resp., Q_i^-) is infeasible, then we set c̆_Q - c̆_Q_i^+ (resp., c̆_Q - c̆_Q_i^-) to be some large number greater than ||c⃗||_1.



  
Most fractional. In this case, (, ,i) = min{1 - x̆_[i], x̆_[i]}. The variable that maximizes (, ,i) is the “most fractional” variable, since it is the variable such that x̆_Q[i] is closest to 1/2.



  
Linear scoring rule <cit.>. In this case, (, ,i) = (1 - μ)·max{c̆_Q - c̆_Q_i^+, c̆_Q - c̆_Q_i^-} + μ·min{c̆_Q - c̆_Q_i^+, c̆_Q - c̆_Q_i^-} where μ∈ [0,1] is a user-specified parameter. This parameter balances an “optimistic” and a “pessimistic” approach to branching: An optimistic approach would choose the variable that maximizes max{c̆_Q - c̆_Q_i^+, c̆_Q - c̆_Q_i^-}, which corresponds to μ = 0, and a pessimistic approach would choose the variable that maximizes min{c̆_Q - c̆_Q_i^+, c̆_Q - c̆_Q_i^-}, which corresponds to μ = 1.



  
Product scoring rule <cit.>. In this case, (, ,i) = max{c̆_Q - c̆_Q_i^-, γ}·max{c̆_Q - c̆_Q_i^+, γ} where γ = 10^-6. Comparing c̆_Q - c̆_Q_i^- and c̆_Q - c̆_Q_i^+ to γ allows the algorithm to compare two variables even if c̆_Q - c̆_Q_i^- = 0 or c̆_Q - c̆_Q_i^+ = 0. After all, suppose the scoring rule simply calculated the product (c̆_Q - c̆_Q_i^-)·(c̆_Q - c̆_Q_i^+) without comparing to γ. If c̆_Q - c̆_Q_i^- = 0, then the score equals 0, canceling out the value of c̆_Q - c̆_Q_i^+ and thus losing the information encoded by this difference.



  
Entropic lookahead scoring rule <cit.>. Let 
    e(x) = -x log_2(x) - (1-x)log_2(1-x)    if  x ∈ (0,1)
    
    0    if  x ∈{0,1}.
 Set (, ,i)=-∑_j = 1^n (1 - x̆_[i]) · e (x̆__i^-[j]) + x̆_[i] · e (x̆__i^+[j]).



  
Alternative definitions of the linear and product scoring rules. In practice, it is often too slow to compute the differences c̆_Q - c̆_Q_i^- and c̆_Q - c̆_Q_i^+ for every variable, since it requires solving as many as 2n LPs. A faster option is to partially solve the LP relaxations of Q_i^- and Q_i^+, starting at x̆⃗̆_Q  and running
a small number of simplex iterations. Denoting the new objective values as c̃_Q_i^- and c̃_Q_i^+, we can revise the linear scoring rule to be (, ,i) = (1 - μ)·max{c̆_Q - c̃_Q_i^+, c̆_Q - c̃_Q_i^-} + μ·min{c̆_Q - c̃_Q_i^+, c̆_Q - c̃_Q_i^-} and we can revise the product scoring rule to be (, ,i) = max{c̆_Q - c̃_Q_i^-, γ}·max{c̆_Q - c̃_Q_i^+, γ}. Other popular alternatives to computing c̆_Q_i^- and c̆_Q_i^+ that fit within our framework are pseudo-cost branching <cit.> and reliability branching <cit.>.


§ GUARANTEES FOR DATA-DRIVEN LEARNING TO BRANCH


In this section, we begin with our formal problem statement. We then present worst-case distributions over MILP instances demonstrating that learning over any data-independent discretization of the parameter space can be inadequate. Finally, we present sample complexity guarantees and a learning algorithm. Throughout the remainder of this paper, we assume that all aspects of the tree search algorithm except the variable selection policy, such as the node selection policy, are fixed.



 §.§ Problem statement

Let  be a distribution over MILPs Q. For example,  could be a distribution over clustering problems a biology lab solves day to day, formulated as MILPs. Let _1, …, _d be a set of variable selection scoring rules, such as those in Section <ref>. Our goal is to learn a convex combination μ_1_1+ ⋯ + μ_d_d of the scoring rules that is nearly optimal in expectation over . More formally, let  be an abstract cost function that takes as input a problem instance Q and a scoring rule  and returns some measure of the quality of B&B using  on input Q. For example, (Q, ) might be the number of nodes produced by running B&B using  on input Q.

We say that an algorithm (ϵ, δ)-learns a convex combination of the
d scoring rules _1, …, _d if for any distribution ,
with probability at least 1-δ over the draw of a sample
{Q_1, …, Q_m}∼^m, the algorithm returns
a convex combination = μ̂_1_1+ ⋯ +
μ̂_d_d such that _Q ∼[(Q,
)] - _Q ∼[(Q, ^*)] ≤ϵ, where ^* is the convex combination of _1, …,
_d with minimal expected cost. In this work, we prove that only a small
number of samples is sufficient to ensure (ϵ, δ)-learnability.

Following prior work (e.g., <cit.>), we assume that there is some cap κ on the range of the cost function . For example, if  is the size of the search tree, we may choose to terminate the algorithm when the tree size grows beyond some bound κ.  We also assume that the problem instances in the support of  are over n binary variables, for some n ∈.

Our results hold for cost functions that are tree-constant, which means that for any problem instance Q, so long as the scoring rules _1 and _2 result in the same search tree, (Q, _1) = (Q, _2).
For example, the size of the search tree is tree-constant.



 §.§ Impossibility results for data-independent approaches


In this section, we focus on MILP tree search and prove that it is impossible to find a nearly optimal B&B configuration using a data-independent discretization of the parameters.
Specifically, suppose _1(, , i) = min{c̆_Q - c̆_Q_i^+, c̆_Q - c̆_Q_i^-} and _2(, , i) = max{c̆_Q - c̆_Q_i^+, c̆_Q - c̆_Q_i^-} and suppose the cost function (Q, μ_1 + (1-μ)_2) measures the size of the tree produced by B&B when using a fixed but arbitrary node selection policy.
We would like to learn a nearly optimal convex combination μ_1 + (1-μ)_2 of these two rules with respect to .
<cit.> proposed setting μ = 1/2, <cit.> and <cit.> suggested setting μ = 1, and <cit.> found that μ = 2/3 performs well. <cit.> found that experimentally, μ = 5/6 performed best when comparing among μ∈{0, 1/2, 2/3, 5/6, 1}.

We show that for any discretization of the parameter space
[0, 1], there exists an infinite family of distributions over
MILP problem instances such that for any parameter in the
discretization, the expected tree size is exponential in n.
Yet, there exists an infinite number of parameters such
that the tree size is just a constant (with probability 1).
 The proof is in Appendix <ref>.

 theoremwcDist
 Let 
    _1(, , i) = min{c̆_Q - c̆_Q_i^+, c̆_Q - c̆_Q_i^-}, _2(, , i) = max{c̆_Q - c̆_Q_i^+, c̆_Q - c̆_Q_i^-},
 and (Q, μ_1 + (1-μ)_2) be the size of the tree produced by B&B. For every a,b such that 1/3 < a < b < 1/2 and for all even n ≥ 6, there exists an infinite family of distributions  over MILP instances with n variables such that if μ∈ [0,1]∖(a,b), then 
    _Q ∼[(Q, μ_1 + (1-μ)_2)] = Ω(2^(n-9)/4)
 and if μ∈ (a,b), then with probability 1, (Q, μ_1 + (1-μ)_2) = O(1). This holds no matter which node selection policy B&B uses.
 

 
We populate the support of the distribution  by relying on two helpful theorems: Theorem <ref> and <ref>. In Theorem <ref>, we prove that for all μ^* ∈ (0,1), there exists an infinite family ℱ_n, μ^* of MILP instances such that for any Q ∈ℱ_n, μ^*, if μ∈[0,μ^*), then the scoring rule μ_1 + (1-μ)_2 results in a B&B tree with O(1) nodes and if μ∈(μ^*,1], the scoring rule results a tree with 2^(n-4)/2 nodes. Conversely, in Theorem <ref>, we prove that there exists an infinite family 𝒢_n, μ^* of MILP instances such that for any Q ∈𝒢_n, μ^*, if μ∈[0,μ^*), then the scoring rule μ_1 + (1-μ)_2 results in a B&B tree with 2^(n-5)/4 nodes and if μ∈(μ^*,1], the scoring rule results a tree with O(1) nodes.
Now, let Q_a be an arbitrary instance in 𝒢_n, a and let Q_b be an arbitrary instance in ℱ_n, b. The theorem follows by letting  be a distribution such that _Q ∼[Q = Q_a] = _Q ∼[Q = Q_b] = 1/2. See Figure <ref> for an illustration.


Throughout the proof of this theorem, we assume the node selection policy is depth-first search. We then prove that for any infeasible MILP, if NSP and NSP' are two node selection policies and = μ_1 + (1-μ)_2 for any μ∈ [0,1], then tree  B&B builds using NSP and  equals the tree ' it builds using NSP' and  (see Theorem <ref>). Thus, the theorem holds for any node selection policy.


We now provide a proof sketch of Theorem <ref>, which helps us populate the support of the worst-case distributions in Theorem <ref>. The full proof is in Appendix <ref>.

theoremfamilies
 Let 
    _1(, , i) = min{c̆_Q - c̆_Q_i^+, c̆_Q - c̆_Q_i^-}, _2(, , i) = max{c̆_Q - c̆_Q_i^+, c̆_Q - c̆_Q_i^-},
 and (Q, μ_1 + (1-μ)_2) be the size of the tree produced by B&B. For all even n ≥ 6 and all μ^* ∈(1/3, 1/2), there exists an infinite family ℱ_n, μ^* of MILP instances such that for any Q ∈ℱ_n, μ^*, if μ∈[0,μ^*), then the scoring rule μ_1 + (1-μ)_2 results in a B&B tree with O(1) nodes and if μ∈(μ^*,1], the scoring rule results a tree with 2^(n-4)/2 nodes.



The MILP instances in ℱ_n, μ^* are inspired by a worst-case B&B instance introduced by <cit.>. He proved that for any odd n', every B&B algorithm will build a tree with 2^(n'-1)/2 nodes before it determines that for any c⃗∈^n', the following MILP is infeasible:

    [             maximize                c⃗·x⃗;           subject to 2∑_i = 1^n' x_i = n';                              x⃗∈{0,1}^n'. ]


We build off of this MILP to create the infinite family ℱ_n, μ^*. Each MILP in ℱ_n, μ^* combines a hard version of Jeroslow's instance  on n-3 variables {x_1, …, x_n-3} and an easy version on 3 variables {x_n-2, x_n-1, x_n}. Branch-and-bound only needs to determine that one of these problems is infeasible in order to terminate. The key idea of this proof is that if B&B branches on all variables in {x_n-2, x_n-1, x_n} first, it will terminate upon making a small tree. However, if B&B branches on all variables in {x_1, …, x_n-3} first, it will create a tree with exponential size before it terminates. The challenge is to design an objective function that enforces the first behavior when μ < μ^* and the second behavior when μ > μ^*. Proving this is the bulk of the work.

In a bit more detail, every instance in ℱ_n, μ^* is defined as follows. For any constant γ≥ 1, let c⃗_1 = γ(1, 2, …, n-3) and let c⃗_2 = γ(0, 3/2, 3-1/2μ^*). Let c⃗ = (c⃗_1, c⃗_2) ∈^n be the concatenation of c⃗_1 and c⃗_2. Let Q_γ,n be the MILP

    [                   maximize                      c⃗·x⃗;                 subject to     2∑_i = 1^n-3 x_i = n-3;                            2(x_n-2 + x_n-1 + x_n) = 3;                                           x⃗∈{0,1}^n. ]

We define ℱ_n, μ^* = {Q_n, γ : γ≥ 1}.

For example, if γ = 1 and n = 8, then Q_γ, n is 
    [                                          maximize             (1, 2, 3, 4, 5, 0, 3/2, 3-1/2μ^*) ·x⃗;                                        subject to [ 2 2 2 2 2 0 0 0; 0 0 0 0 0 2 2 2 ]x⃗ = [ 5; 3 ];                                                                                         x⃗∈{0,1}^8. ]


As is illustrated in Figure <ref>, we have essentially “glued together” two disjoint versions of Jeroslow's instance: the first five variables of Q_1, 8 correspond to a “big” version of Jeroslow's instance and the last three variables correspond to a small version. Since the goal is maximization, the solution to the LP relaxation of Q_1,8 will try to obtain as much value from the first five variables {x_1, …, x_5} as it can, but it is constrained to ensure that 2(x_1 + ⋯ + x_5) = 5. Therefore, the first five variables will be set to (0, 0, 1/2, 1, 1). Similarly, the solution to the LP relaxation of Q_1, 8 will set (x_6, x_7, x_8) = (0, 1/2, 1) because 3/2 < 3 - 1/2μ^* under our assumption that μ^* > 1/3. Thus, the solution to the LP relaxation of Q_1, 8 is (0, 0, 1/2, 1, 1, 0, 1/2, 1). There are only two fractional variables that B&B might branch on: x_3 and x_7. Straightforward calculations show that if  is the B&B tree so far, which just consists of the root node, μ_1(, Q_γ, n,3) + (1-μ)_2(, Q_γ, n,3) = γ/2 and μ_1(, Q_γ, n,7) + (1-μ)_2(, Q_γ, n,7) = 3γ/4 -  μγ/4μ^*. This means that B&B will branch first on variable x_7, which corresponds to the small version of Jeroslow's instance (see Figure <ref>) if and only if γ/2 < 3γ/4 -  μγ/4μ^*, which occurs if and only if μ < μ^*. We show that this first branch sets off a cascade: if B&B branches first on variable x_7, then it will proceed to branch on all variables in {x_6, x_7, x_8}, thus terminating upon making a small tree. Meanwhile, if it branches on variable x_3 first, it will then only branch on variables in {x_1, …, x_5}, creating a larger tree.

In the full proof, we generalize beyond eight variables to n, and expand the large version of Jeroslow's instance (as depicted in Figure <ref>) from five variables to n-3. When μ < μ^*, we simply track B&B's progress to make sure it only branches on
variables from the small version of Jeroslow's instance (x_n-2, x_n-1, x_n) before figuring out the MILP is infeasible. Therefore, the tree will have constant size. When μ > μ^*, we prove by induction that if B&B has only branched on variables from the
big version of Jeroslow's instance (x_1, …, x_n-3), it will continue to only branch on those variables.
We also prove it will branch on about half of these variables along each path of the B&B tree. The tree will thus have exponential size.
 



 §.§ Sample complexity guarantees


We now provide worst-case guarantees on the number of samples sufficient to (ϵ, δ)-learn a convex combination of scoring rules.
These results bound the number of samples sufficient to ensure that for any convex combination = μ_1_1 + ⋯ + μ_d_d of scoring rules, the empirical cost of tree search using  is close to its expected cost. Therefore, the algorithm designer can optimize (μ_1, …, μ_d) over the samples without any further knowledge of the distribution. Moreover these sample complexity guarantees apply for any procedure the algorithm designer uses to tune (μ_1, …, μ_d), be it an approximation, heuristic, or optimal algorithm. She can use our guarantees to bound the number of samples she needs to ensure that performance on the sample generalizes to the distribution.

 In Section <ref> we provide generalization guarantees for a family of  scoring rules we call path-wise, which includes many well-known scoring rules as special cases. In this case, the number of samples is surprisingly small given the complexity of these problems: it grows only quadratically with the number of variables. In Section <ref>, we provide guarantees that apply to any scoring rule, path-wise or otherwise.



  §.§.§ Path-wise scoring rules

The guarantees in this section apply broadly to a class of scoring rules we call path-wise scoring rules. Given a node Q in a search tree , we denote the path from the root of  to the node Q as _Q. The path _Q includes all nodes and edge labels from the root of  to Q. For example, Figure <ref> illustrates the path _Q from the root of the tree  in Figure <ref> to the node labeled Q. We now state the definition of path-wise scoring rules.

The function  is a path-wise scoring rule if for all search trees , all nodes Q in , and all variables x_i, 
    (, , i) = (_Q, , i)
 where _Q is the path from the root of  to .[Under this definition, the scoring rule can simulate B&B for any number of steps starting at any point in the tree and use that information to calculate the score, so long as Equality (<ref>) always holds.] See Figure <ref> for an illustration.



Definition <ref> requires that if the node Q appears at the end of the same path in two different B&B trees, then any path-wise scoring rule must assign every variable the same score with respect to Q in both trees.

Path-wise scoring rules include many well-studied rules as special cases, such as the most fractional, product, and linear scoring rules, as defined in Section <ref>. The same is true when B&B only partially solves the LP relaxations of Q_i^- and Q_i^+ for every variable x_i by running a small number of simplex iterations, as we describe in Section <ref> and as is our approach in our experiments. In fact, these scoring rules depend only on the node in question, rather than the path from the root to the node. We present our sample complexity bound for the more general class of path-wise scoring rules because this class captures the level of generality the proof holds for. On the other hand, pseudo-cost branching <cit.> and reliability branching <cit.>, two widely-used branching strategies, are not path-wise, but our more general results from Section <ref> do apply to those strategies.

In order to prove our generalization guarantees, we make use of the following key structure which bounds the number of search trees branch-and-bound will build on a given instance over the entire range of parameters. In essence, this is a bound on the intrinsic complexity of the algorithm class defined by the range of parameters, and this bound on algorithm class's intrinsic complexity implies strong generalization guarantees.


Let  be a tree-constant cost function, let _1 and _2 be two path-wise scoring rules, and let Q be an arbitrary problem instance over n binary variables. There are T ≤ 2^n(n-1)/2n^n intervals I_1, …, I_T partitioning [0,1] where for any interval I_j, across all μ∈ I_j, the scoring rule μ_1 + (1-μ)_2 results in the same search tree.



We prove this lemma first by considering the actions of an alternative algorithm A' which runs exactly like B&B, except it only fathoms nodes if they are integral or infeasible. We then relate the behavior of A' to the behavior of B&B to prove the lemma.

First, we prove the following bound on the number of search trees A' will build on a given instance over the entire range of parameters. This bound matches that in the lemma statement.

claimclaimIntervals
There are T ≤ 2^n(n-1)/2n^n intervals I_1, …, I_T partitioning [0,1] where for any interval I_j, the search tree A' builds using the scoring rule μ_1 + (1-μ)_2 is invariant across all μ∈ I_j.[This claim holds even when _1 and _2 are members of the more general class of depth-wise scoring rules, which we define as follows. For any search tree  of depth depth() and any j ∈ [n], let [j] be the subtree of  consisting of all nodes in  of depth at most j. We say that  is a depth-wise scoring rule if for all search trees , all j ∈ [depth()], all nodes Q of depth j, and all variables x_i, (, , i) = ([j], , i).]



We prove this claim by induction. For a tree , let [i] be the nodes of depth at most i. We prove that for i ∈{1,…, n}, there are T ≤ 2^i(i-1)/2n^i intervals I_1, …, I_T partitioning [0,1] where for any interval I_j and any two parameters μ, μ' ∈ I_j, if  and ' are the trees A' builds using the scoring rules μ_1 + (1-μ)_2 and μ'_1 + (1-μ')_2, respectively, then [i] = '[i]. Suppose that this is indeed the case for some i ∈{1,…, n} and consider an arbitrary interval I_j and any two parameters μ, μ' ∈ I_j. Consider an arbitrary node  in [i-1] (or equivalently, '[i-1]) at depth i-1. If Q is integral or infeasible, then it will be fathomed no matter which parameter μ∈ I_j the algorithm A' uses. Otherwise, for all μ∈ I_j, let _μ be the state of the search tree A' builds using the scoring rule μ_1 + (1-μ)_2 at the point when it branches on Q. By the inductive hypothesis, we know that across all μ∈ I_j, the path from the root to Q in _μ is invariant, and we refer to this path as _Q. Given a parameter μ∈ I_j, the variable x_k will be branched on at node  so long as k= _ℓ{μ_1(_μ,,ℓ) + (1-μ)_2(_μ,,ℓ)}, or equivalently, so long as k= _ℓ{μ_1(_Q,,ℓ) + (1-μ)_2(_Q,,ℓ)}. In other words, the decision of which variable to branch on is determined by a convex combination of the constant values _1(_Q,,ℓ) and _2(_Q,,ℓ) no matter which parameter μ∈ I_j the algorithm A' uses. Here, we critically use the fact that the scoring rule is path-wise.

Since μ_1(_Q,,ℓ) + (1-μ)_2(_Q,,ℓ) is a linear function of μ for all ℓ, there are at most n intervals subdividing the interval I_j such that the variable branched on at node  is fixed.

Moreover, there are at most 2^i-1 nodes at depth i-1, and each node similarly contributes a subpartition of I_j of size n. If we merge all 2^i-1 partitions, we have T' ≤ 2^i-1(n-1)+1 intervals I_1', …, I_T'' partitioning I_j where for any interval I_p' and any two parameters μ, μ' ∈ I_p', if  and ' are the trees A' builds using the scoring rules μ_1 + (1-μ)_2 and μ'_1 + (1-μ')_2, respectively, then [i] = '[i]. We can similarly subdivide each interval I_1, …, I_T. The claim then follows from counting the number of subdivisions.


Next, we explicitly relate the behavior of B&B to A', proving that the search tree B&B builds is a rooted subtree of the search tree A' builds.


Given a parameter μ∈ [0,1], let  and ' be the trees B&B and A' build respectively using the scoring rule μ_1 + (1-μ)_2. For any node Q of , let _Q be the path from the root of  to Q. Then _Q is a rooted subtree of '.



The path _Q can be labeled by a sequence of indices from {0,1} and a sequence of variables from {x_1, …, x_n} describing which variable is branched on and which value it takes on along the path _Q. Let ((j_1, x_i_1), …, (j_t, x_i_t)) be this sequence of labels, where t is the number of edges in _Q. We can similarly label every edge in '. We claim that there exists a path beginning at the root of ' with the labels ((j_1, x_i_1), …, (j_t, x_i_t)).

For a contradiction, suppose no such path exists. Let (j_τ, x_i_τ) be the earliest label in the sequence ((j_1, x_i_1), …, (j_t, x_i_t)) where there is a path beginning at the root of ' with the labels ((j_1, x_i_1), …, (j_τ-1, x_i_τ - 1)), but there is no way to continue the path using an edge labeled (j_τ, x_i_τ). There are exactly two reasons why this could be the case:


  * The node at the end of the path with labels ((j_1, x_i_1), …, (j_τ-1, x_i_τ - 1)) was fathomed by A'.

  * The algorithm A' branched on a variable other than x_i_τ at the end of the path labeled ((j_1, x_i_1), …, (j_τ-1, x_i_τ - 1)).


In the first case, since A' only fathoms a node if it is integral or infeasible, we know that B&B will also fathom the node at the end of the path with labels ((j_1, x_i_1), …, (j_τ-1, x_i_τ - 1)). However, this is not the case since B&B next branches on the variable x_i_τ.

The second case is also not possible since the scoring rules are both path-wise. In a bit more detail, let Q' be the node at the end of the path with labels ((j_1, x_i_1), …, (j_τ-1, x_i_τ - 1)). We refer to this path as _Q'. Let  (respectively, ') be the state of the search tree B&B (respectively, A') has built at the point it branches on Q'. We know that _Q' is the path from the root to Q' in both of the trees  and '. Therefore, for all variables x_k, μ_1(, Q', k) + (1-μ)_2(, Q', k) = μ_1(_Q', Q', k) + (1-μ)_2(_Q', Q', k) = μ_1(', Q', k) + (1-μ)_2(', Q', k). This means that B&B and A' will choose the same variable to branch on at the node Q'.

 Therefore, we have reached a contradiction, so the claim holds.


Next, we use Claims <ref> and <ref> to prove Lemma <ref>. Let I_1, …, I_T be the intervals guaranteed to exist by Claim <ref> and let I_t be an arbitrary one of the intervals. Let μ' and μ” be two arbitrary parameters from I_t. We will prove that the scoring rules μ'_1 + (1-μ')_2 and μ”_1 + (1-μ”)_2 result in the same B&B search tree. For a contradiction, suppose that this is not the case.
Consider the first iteration where B&B using the scoring rule μ'_1 + (1-μ')_2 differs from B&B using the scoring rule μ”_1 + (1-μ”)_2. By iteration, we mean lines <ref> through <ref> of Algorithm <ref>. Up until this iteration, B&B has built the same partial search tree . Since the node selection policy does not depend on μ' or μ”, B&B will choose the same leaf Q of the B&B search tree to branch on no matter which scoring rule it uses.

Suppose B&B chooses different variables to branch on in Step <ref> of Algorithm <ref> depending on whether it uses the scoring rule μ'_1 + (1-μ')_2 or μ”_1 + (1-μ”)_2. Let _Q be the path from the root of  to Q. By Claim <ref>, we know that the algorithm A' builds the same search tree using the two scoring rules. Let ' (respectively, ”) be the state of the search tree A' has built using the scoring rule μ'_1 + (1-μ')_2 (respectively, μ”_1 + (1-μ”)_2) by the time it branches on the node Q. By Claims <ref> and <ref>, we know that _Q is the path of from the root to Q of both ' and ”. By Claim <ref>,
we know that A' will branch on the same variable x_i at the node Q in both the trees ' and ”, so i = _j{μ'_1(', Q, j)  + (1-μ')_2(', Q, j)}, or equivalently, 
    i = _j{μ'_1(_Q, Q, j)  + (1-μ')_2(_Q, Q, j)},
 and i = _j{μ”_1(”, Q, j)  + (1-μ”)_2(”, Q, j)}, or equivalently, 
    i = _j{μ”_1(_Q, Q, j)  + (1-μ”)_2(_Q, Q, j)}.
 Returning to the search tree  that B&B is building, Equation (<ref>) implies that 
    i = _j{μ'_1(, Q, j)  + (1-μ')_2(, Q, j)}
 and Equation (<ref>) implies that i = _j{μ”_1(, Q, j)  + (1-μ”)_2(, Q, j)}.
Therefore, B&B will branch on x_i at the node Q no matter which scoring rule it uses. 

Finally, since the trees B&B has built so far are identical, the choice of whether or not to fathom the children Q_i^+ and Q_i^- does not depend on the scoring rule, so B&B will fathom the same nodes no matter whether it uses the scoring rule μ'_1 + (1-μ')_2 or μ”_1 + (1-μ”)_2. Therefore, we have reached a contradiction: the iterations were identical. We conclude that the lemma holds.


We now show how this structure implies a generalization guarantee. We formulate our guarantees in terms of pseudo-dimension. By classic results from learning theory, pseudo-dimension immediately implies generalization guarantees. Pseudo-dimension is defined as follows.

Let ℱ be a class of functions mapping an abstract domain  to the set [-κ,κ]. Let = {z_1, …, z_m} be a subset of  and let r_1, …, r_m ∈ be a set of targets. We say that r_1, …, r_m witness the shattering of  by ℱ if for all ' ⊆, there exists some function f_'∈ℱ such that for all z_i ∈', f_'(z_i) ≤ r_i and for all z_i ∉', f_'(z_i) > r_i. If there exists some r⃗∈^m that witnesses the shattering of  by ℱ, then we say that  is shatterable by ℱ. Finally, the pseudo-dimension of ℱ, denoted (), is the size of the largest set that is shatterable by ℱ.

Theorem <ref> provides generalization bounds in terms of pseudo-dimension.

For any distribution  over , with probability at least 1-δ over the draw of = {z_1, …, z_m}∼^m, for all f ∈ℱ, 
    |_z ∼[f(z)] - 1/m∑_i = 1^m f(z_i)| = O(κ√(()/m) + κ√(ln(1/δ)/m)).




Let  be a tree-constant cost function, let _1 and _2 be two path-wise scoring rules, and let 𝒞 be the set of functions {(·, μ_1 + (1-μ)_2) : μ∈ [0,1]}. Then (𝒞) = O(n^2).


 Suppose that (𝒞) = m and let = {Q_1, …, Q_m} be a shatterable set of problem instances. We know there exists a set of targets r_1, …, r_m ∈ that witness the shattering of  by 𝒞. This means that for every ' ⊆, there exists a parameter μ_' such that if Q_i ∈, then (Q_i, μ_'_1 + (1-μ_')_2) ≤ r_i. Otherwise (Q_i, μ_'_1 + (1-μ_')_2) > r_i. Let M = {μ_' : ' ⊆}. We will prove that  |M| ≤ m2^n(n-1)/2n^n + 1, and since 2^m = |M|, this means that (𝒞) = m = O(log(2^n(n-1)/2n^n)) = O(n^2) (see Lemma <ref> in Appendix <ref>).

To prove that |M| ≤ m2^n(n-1)/2n^n+1, we rely on Lemma <ref>, which tells us that for any problem instance Q, there are T ≤ 2^n(n-1)/2n^n intervals I_1, …, I_T partitioning [0,1] where for any interval I_j, across all μ∈ I_j, the scoring rule μ_1 + (1-μ)_2 results in the same search tree. If we merge all T intervals for all samples in , we are left with T' ≤ m2^n(n-1)/2n^n+1 intervals I_1', …, I_T'' where for any interval I_j' and any Q_i ∈, (Q_i, μ_1 + (1-μ)_2) is constant for all μ∈ I_j'. Therefore, at most one element of M can come from each interval, meaning that |M| ≤ T' ≤ m2^n(n-1)/2n^n+1, as claimed.




  §.§.§ General scoring rules


In this section, we provide generalization guarantees that apply to learning convex combinations of any set of scoring rules. Unlike the guarantees in Section <ref>, they depend on the size of the search trees B&B is allowed to build. For example, we may choose to terminate the algorithm when the tree size grows beyond some bound κ̅. The following lemma corresponds to Lemma <ref> for this setting. For the full proof, see Lemma <ref> in Appendix <ref> which proves the lemma for a more general tree search algorithm.


Let  be a tree-constant cost function, let _1, …, _d be d arbitrary scoring rules, and let Q be an arbitrary MILP over n binary variables. Suppose we limit B&B to producing search trees of
  size κ̅. There is a set ℋ of at most n^2(κ̅ + 1) hyperplanes such that for any connected component R of [0,1]^d ∖ℋ, the search tree B&B builds using the scoring rule μ_1_1 + ⋯ + μ_d_d is invariant across all (μ_1, …, μ_d) ∈ R.



  
  The proof has two steps. In Claim <ref>, we show that there are at most n^κ̅
  different search trees that B&B might produce for the instance Q as we
  vary the mixing parameter vector (μ_1, …, μ_d). In Claim <ref>, for each of the possible search trees
  𝒯 that might be produced, we show that the set of parameter values
  (μ_1, …, μ_d) which give rise to that tree lie in the intersection of n^κ̅ + 2 halfspaces. Of course, each of these halfspaces is defined by a hyperplane. Let ℋ be the union of all n^κ̅ + 2 hyperplanes over all n^κ̅ trees. We know that for any connected component R of [0,1]^d ∖ℋ, the search tree B&B builds using the scoring rule μ_1_1 + ⋯ + μ_d_d is invariant across all (μ_1, …, μ_d) ∈ R, so the lemma statement holds.


In the same way Lemma <ref> implies the pseudo-dimension bound in Theorem <ref>, Lemma <ref> also implies a pseudo-dimension bound. The proof is similar to that of Theorem <ref>. See Theorem <ref> in Appendix <ref> which proves the theorem for a more general tree search algorithm.


Let  be a tree-constant cost function and let _1, …, _d be d arbitrary scoring rules. Suppose we limit B&B to producing search trees of
  size κ̅. Let 𝒞 be the set of functions {(·, μ_1 + ⋯ + μ_d_d) : (μ_1, …, μ_d) ∈ [0,1]^d}. Then (𝒞) = O(dκ̅log n + dlog d).


Naturally, if the function  measures the size of the search tree B&B returns capped at some value κ as described in Section <ref>, we obtain the following corollary.


Let  be a tree-constant cost function, let _1, …, _d be d arbitrary scoring rules, and let κ∈ be an arbitrary tree size bound. Suppose that for any problem instance Q, (Q, μ_1 + ⋯ + μ_d_d) equals the minimum of the following two values: 1) The number of nodes in the search tree B&B builds using the scoring rule μ_1 + ⋯ + μ_d_d on input Q; and 2) κ. For any distribution  over problem instances Q with at most n variables, with probability at least 1-δ over the draw {Q_1, …, Q_m}∼^m, for any μ∈ [0,1], 
    |_Q ∼ [(Q, μ_1 + ⋯ + μ_d_d)] - 1/m∑_i = 1^m (Q_i, μ_1 + ⋯ + μ_d_d)|
    
    =    O(√(dκ^2(κlog n + log d)/m) + κ√(ln(1/δ)/m)).





  §.§.§ Learning algorithm


For the case where we wish to learn the optimal tradeoff between two scoring rules, we provide an algorithm in Appendix <ref> that finds the empirically optimal parameter μ̂ given a sample of m problem instances. By Theorems <ref>, <ref>, and <ref>, we know that so long as m is sufficiently large, μ̂ is nearly optimal in expectation.
 Our algorithm stems from the observation that for any tree-constant cost function  and any problem instance Q, (Q, μ_1 + (1-μ)_2) is simple: it is a piecewise-constant function of μ with a finite number of pieces. This is the same observation that we prove in Lemma <ref>. Given a sample of problem instances = {Q_1, …, Q_m}, our ERM algorithm constructs all m piecewise-constant functions, takes their average, and finds the minimizer of that function. In practice, we find that the number of pieces making up this piecewise-constant function is small, so our algorithm can learn over a training set of many problem instances.


§ EXPERIMENTS



In this section, we show that the parameter of the variable selection rule in
B&B algorithms for MILP can have a dramatic effect on the average tree size
generated for several domains, and no parameter value is effective across the
multiple natural distributions.



  
Experimental setup. We use the C API of IBM ILOG CPLEX
12.8.0.0 to override the default variable selection rule using a branch
callback.
Additionally, our callback
performs extra book-keeping to determine a finite set of
values for the parameter that give rise to all possible B&B trees for a given instance (for the given choice of branching rules that our algorithm is learning to weight). This ensures that there are no good or bad values for the parameter that get skipped; such skipping could be problematic according to our theory in Section <ref>.
We run CPLEX exactly once for each possible B&B tree on
each instance. Following <cit.>, and <cit.>, we disable CPLEX's cuts and primal heuristics, and we also disable its root-node preprocessing.
The CPLEX node selection policy
is set to “best bound” (aka. A^* in AI), which is the most typical choice in MILP. All experiments are run on a cluster of 64
c3.large Amazon AWS instances.

For each of the following application domains, Figure <ref> shows
the average B&B tree size produced for each possible value of the μ parameter
for the linear scoring rule, averaged over m independent samples from the
distribution.



    Combinatorial auctions.
 We generate m=100
instances of the combinatorial auction winner determination problem under the OR-bidding language <cit.>, which makes this problem equivalent to weighted set packing. The problem is NP-complete. We encode each instance as a binary MILP (see Example <ref>). We use the Combinatorial
Auction Test Suite (CATS) <cit.> to generate these instances.
We use the “arbitrary” generator with 200 bids and 100 goods and “regions” generator with 400
bids and 200 goods.



    Facility location.
 Suppose there is a set I of customers
and a set J of facilities that have not yet been built. The facilities each
produce the same good, and each consumer demands one unit of that good. Consumer
i can obtain some fraction y_ij of the good from facility j, which costs
them d_ijy_ij. Moreover, it costs f_j to construct facility j. The
goal is to choose a subset of facilities to construct while minimizing total
cost. In Appendix <ref> we show how to formulate facility
location as a MILP. We generate m=500 instances with 70 facilities and 70
customers each. Each cost d_ij is uniformly sampled from [0,
10^4] and each cost f_j is uniformly sampled from [0, 3·
10^3]. This distribution has regularly been used to generate benchmark
sets for facility location <cit.>.



    Clustering.
 Given n points P = {p_1, …,
p_n} and pairwise distances d(p_i, p_j) between each pair of points
p_i and p_j, the goal of k-means clustering is to find k centers
C = {c_1, …, c_k}⊆ P such that the following
objective function is minimized: ∑_i = 1^n min_j ∈ [k] d(p_i,
c_j)^2. In Appendix <ref>, we show how to formulate this
problem as a MILP. We generate m=500 instances with 35 points each and k =
5. We set d(i,i) = 0 for all i and choose d(i,j) uniformly at random from
[0,1] for i ≠ j. These distances do not satisfy the triangle inequality
and they are not symmetric (i.e., d(i,j) ≠ d(j,i)), which tends to lead
to harder MILP instances than using Euclidean distances between randomly chosen
points in ^d.



    Agnostically learning linear separators.
 Let p⃗_1,
…, p⃗_N be N points in ^d labeled by z_1, …, z_N ∈{-1,1}. Suppose we wish to learn a linear separator w⃗∈^d that
minimizes 0-1 loss, i.e., ∑_i = 1^N 1_{z_i⟨p⃗_i, w⃗⟩ < 0}. In
Appendix <ref>, we show how to formulate this problem as a MILP.
We generate m=500 problem instances with 50 points p⃗_1, …,
p⃗_50 from the 2-dimensional standard normal distribution. We sample the
true linear separator w⃗^* from the 2-dimensional standard Gaussian
distribution and label point p⃗_i by z_i = (⟨w⃗^*,
p⃗_i ⟩ ). We then choose 10 random points and flip their labels so
that there is no consistent linear separator.



  
Experimental results. The relationship between the variable
selection parameter and the average tree size varies greatly from application to
application. This implies that the parameters should be tuned on a
per-application basis, and that no parameter value is universally effective. In
particular, the optimal parameter for the “regions” combinatorial auction
problem, facility location, and clustering is close to 1. However, that value is
severely suboptimal for the “arbitrary” combinatorial auction domain,
resulting in trees that are
three times the size of the trees obtained under the optimal parameter value.



  
Data-dependent guarantees.
We now explore data-dependent generalization guarantees. To prove our worst-case guarantee
Theorem <ref>, we show in Lemma <ref> that for any
MILP instance over n binary variables, there are T ≤
2^n(n-1)/2n^n intervals I_1, …, I_T partitioning [0,1]
where for any interval I_j, across all μ∈ I_j, the scoring rule
μ_1 + (1-μ)_2 results in the same B&B tree. Our generalization guarantees grow logarithmically in
the number of intervals. In practice, we find that the number of
intervals partitioning [0,1] is much smaller than 2^n(n-1)/2n^n. In this section, we take advantage of this
data-dependent simplicity to derive stronger generalization guarantees when the number of
intervals partitioning [0,1] is small. To do so, we move from pseudo-dimension to Rademacher complexity <cit.> since Rademacher complexity implies distribution-dependent guarantees whereas pseudo-dimension implies generalization guarantees that are worst-case over the distribution.
We now define empirical Rademacher complexity.

Let ℱ be a class of functions mapping an abstract domain  to the set [-κ,κ]. The empirical Rademacher complexity of ℱ with respect to a sample = {z_1, …, z_m}⊆ of size m is defined as 
    (ℱ) = 1/m_σ⃗∼{-1,1}^m[sup_f ∈ℱ∑_i = 1^m σ[i] f(z_i)].


The following generalization guarantee based on Rademacher complexity is well-known.

For any distribution  over , with probability at least 1-δ over the draw of = {z_1, …, z_m}∼^m, for all f ∈ℱ, |_z ∼[f(z)] - 1/m∑_i = 1^m f(z_i)| ≤ 2(ℱ) + 4κ√(2/mln4/δ).


To obtain data-dependent generalization guarantees, we rely on the following theorem, which follows from truncating the proof of Massart's finite lemma <cit.>, as observed by <cit.>. For a function class  and a  set = {z_1, …, z_m}⊆, we use the notation () to denote the set of vectors {(f(z_1), …, f(z_m)) : f ∈}.


For a sample  of size m, suppose that () is finite.
Then 
    () ≤inf_λ > 01/λlog( ∑_a⃗∈()exp(1/2(λ ||a⃗||_2/m)^2)).



Figure <ref> shows a comparison of the worst-case versus
data-dependent guarantees. The latter are significantly better. For ease of comparison, we compare the data-dependent bound provided by Theorem <ref> with a variation of Theorem <ref> in terms of Rademacher complexity. See Theorem <ref> in Appendix <ref> for details.




§ CONSTRAINT SATISFACTION PROBLEMS


In this section, we describe tree search for constraint satisfaction problems. The generalization guarantee from Section <ref> also applies to tree search in this domain, as we describe in Appendix <ref>.

A constraint satisfaction problem (CSP) is a tuple (X, D, C), where X = {x_1, …, x_n} is a set of variables, D = {D_1, …, D_n} is a set of domains where D_i is the set of values variable x_i can take on, and C is a set of constraints between variables. Each constraint in C is a pair ((x_i_1, …, x_i_r), ψ) where ψ is a function mapping D_i_1×⋯× D_i_r to {0,1} for some r ∈ [n] and some i_1, …, i_r ∈ [n].
Given an assignment (y_1, …, y_n) ∈ D_1 ×⋯× D_n  of the variables in X, a constraint ((x_i_1, …, x_i_r), ψ) is satisfied if ψ(y_i_1, …, y_i_r) = 1.
The goal is to find an assignment that maximizes the number of satisfied constraints.

The degree of a variable x, denoted (x), is the number of constraints involving x. The dynamic degree of (an unassigned variable) x given a partial assignment y⃗, denoted (x, y⃗) is the number of constraints involving x and at least one other unassigned variable.

[Graph k-coloring]

Given a graph, the goal of this problem is to color its vertices using at most k colors such that no two adjacent vertices share the same color. This problem can be formulated as a CSP, as illustrated by the following example.
Suppose we want to 3-color the graph in Figure <ref> using pink, green, and orange. The four vertices correspond to the four variables X= {x_1, …, x_4}. The domain D_1 = ⋯ = D_4 = {pink, green, orange}. The only constraints on this problem are that no two adjacent vertices share the same color. Therefore we define ψ to be the “not equal” relation mapping {pink, green, orange}×{pink, green, orange}→{0,1} such that ψ(ω_1, ω_2) = 1_{ω_1 ≠ω_2}. Finally, we define the set of constraints to be 
    C = {((x_1, x_2), ψ), ((x_1, x_3), ψ), ((x_2, x_3), ψ), ((x_3, x_4), ψ)).
 See Figure <ref> for a coloring that satisfies all constraints (y_1 = y_4 = green,  y_2 = orange, and  y_3 = pink). 



  §.§.§ CSP tree search


CSP tree search begins by choosing a variable x_i with domain D_i and building |D_i| branches, each one corresponding to one of the |D_i| possible value assignments of x. Next, a node  of the tree is chosen, another variable x_j is chosen, and |D_j| branches from  are built, each corresponding to the possible assignments of x_j. The search continues and a branch is pruned if any of the constraints are not feasible given the partial assignment of the variables from the root to the leaf of that branch.



  §.§.§ Variable selection in CSP tree search


As in MILP tree search, there are many variable selection policies researchers have suggested for choosing which variable to branch on at a given node. Typically, algorithms associate a score for branching on a given variable x_i at node  in the tree , as in B&B. The algorithm then branches on the variable with the highest score.
We provide several examples of common variable selection policies below.



  
deg/dom and ddeg/dom <cit.>: deg/dom corresponds to the scoring rule (, , i) = (x_i)/|D_i| and ddeg/dom corresponds to the scoring rule (, , i) = (x_i, y⃗)/|D_i|, where y⃗ is the assignment of variables from the root of  to .



  
Smallest domain <cit.>: In this case, (, , i) = 1/|D_i|.



Our theory is for tree search and applies to both MILPs and CSPs.
It applies both to lookahead approaches that require learning the weighting of the two children (the more promising and less promising child) and to approaches that require learning the weighting of several different scoring rules.


§ CONCLUSIONS AND BROADER APPLICABILITY


In this work, we studied machine learning for tree search algorithm configuration. We showed how to learn a nearly optimal mixture of branching (e.g., variable selection) rules. Through experiments, we showed that using the optimal parameter for one application domain when solving problem instances from a different application domain can lead to a substantial tree size blow up. We proved that this blowup can even be exponential. 
We provided the first sample complexity guarantees for tree search algorithm configuration.
With only a small number of samples, the empirical cost incurred by using any mixture of two scoring rules will be close to its expected cost, where cost is an abstract measure such as tree size. We showed that using empirical Rademacher complexity, these bounds can be significantly tightened further.
Through theory and experiments, we showed that learning to branch is practical and hugely beneficial. 

While we presented the theory in the context of tree search, it also applies to other tree-growing applications. For example, it could be used for learning rules for selecting variables to branch on in order to construct small decision trees that correctly classify training examples. Similarly, it could be used for learning to branch in order to construct a desirable
taxonomy of items represented as a tree—for example for representing  customer segments in advertising day to day.



  
Acknowledgments.

This work was supported in part by the National Science Foundation under grants CCF-1422910, CCF-1535967,  IIS-1618714, IIS-1718457, IIS-1617590, CCF-1733556, a Microsoft Research Faculty Fellowship, an Amazon Research Award, a NSF Graduate Research Fellowship, and the ARO under award W911NF-17-1-0082.




plainnat


§ ADDITIONAL RELATED WORK


As in this work, <cit.> study variable selection policies. Their goal is to find a variable selection strategy that mimics the behavior of the classic branching strategy known as strong branching while running faster than strong branching. They split a single MILP instance into a training and test set. The beginning of the B&B algorithm is the training phase: their algorithm assigns features to each node and observes the variable selected to branch on by strong branching using the product scoring rule (see the definition in Section <ref>). Collecting these features and variable observations for a pre-specified number of nodes, they thus amass a training set. Their algorithm then uses this training set together with a classic ranking algorithm from the machine learning literature <cit.> to determine a function f that, ideally, will imitate strong branching. In a bit more detail, on each node the algorithm encounters as it explores the rest of the tree, the algorithm assigns features ϕ⃗ to that node, evaluates the function f(ϕ⃗) which returns a variable to branch on, and the algorithm branches on that variable. The hope is that f(ϕ⃗) matches the variable strong branching would choose to branch on at that node.

Other works have explored the use of machine learning techniques in the context of other aspects of B&B beyond variable selection. For example, <cit.> use machine learning to speed up branch-and-bound, focusing on speeding up the node selection policy. Their work does not provide any learning-theoretic guarantees. Beyond node selection, <cit.> also aim to learn a pruning policy, which determines whether to fathom a given node. This policy may occasionally fathom a node even when the branch contains the optimal solution, but ideally, this will happen infrequently or the resulting solution will be nearly optimal. Their learning algorithm takes as input a set of MIP instances and their optimal solutions. For each MIP in this set, the algorithm constructs a simple oracle which returns, given a set of B&B leaf nodes as input, the leaf whose feasible set contains the optimal solution. The learning algorithm uses the oracle to train the node selection and pruning policies using imitation learning. Ideally, the resulting node selection policy should choose the nodes the oracle selects, and the pruning policy should prune any node that does not contain the optimal solution in its feasible set. 


§ VARIABLE SELECTION POLICIES





§ PROOFS FROM SECTION <REF>




  
Notation. In the proofs in this section, we will use the following notation. Let Q be a MILP instance. Suppose that we branch on x_i and x_j, setting x_i = 0 and x_j = 1. We use the notation Q_i,j^-,+ to denote the resulting MILP. Similar, if we set x_i = 1 and x_j = 0, we denote the resulting MILP as Q_i,j^+,-.

*

 
We populate the support of the distribution  by relying on two helpful theorems: Theorem <ref> and <ref>. In Theorem <ref>, we prove that for all μ^* ∈(1/3, 2/3), there exists an infinite family ℱ_n, μ^* of MILP instances such that for any Q ∈ℱ_n, μ^*, if μ∈[0,μ^*), then the scoring rule μ_1 + (1-μ)_2 results in a B&B tree with O(1) nodes and if μ∈(μ^*,1], the scoring rule results a tree with 2^(n-4)/2 nodes. Conversely, in Theorem <ref>, we prove that there exists an infinite family 𝒢_n, μ^* of MILP instances such that for any Q ∈𝒢_n, μ^*, if μ∈[0,μ^*), then the scoring rule μ_1 + (1-μ)_2 results in a B&B tree with 2^(n-5)/4 nodes and if μ∈(μ^*,1], the scoring rule results a tree with O(1) nodes.

Now, let Q_a be an arbitrary instance in 𝒢_n, a and let Q_b be an arbitrary instance in ℱ_n, b. The theorem follows by letting  be a distribution such that _Q ∼[Q = Q_a] = _Q ∼[Q = Q_b] = 1/2. We know that if μ∈ [0,1] ∖ (a,b), then the expected value of (Q, μ_1 + (1-μ)_2) is
1/2(O(1) + 2^(n-5)/4) ≥ 2^(n-9)/4. Meanwhile, if μ∈ (a,b), then with probability 1, 
    (Q, μ_1 + (1-μ)_2) = O(1).


Throughout the proof of this theorem, we assume the node selection policy is depth-first search. We then prove that for any infeasible MILP, if NSP and NSP' are two node selection policies and = μ_1 + (1-μ)_2 for any μ∈ [0,1], then tree  B&B builds using NSP and  equals the tree ' it builds using NSP' and  (see Theorem <ref>). Thus, the theorem holds for any node selection policy.

*


For ease of notation in this proof, we will drop  from the input of the functions _1 and _2 since the scoring rules do not depend on , they only depend on the input MILP instance and variable.

For any constant γ≥ 1, let c⃗_1 = γ(1, 2, …, n-3) and let c⃗_2 = γ(0, 1.5, 3-1/2μ^*). Let c⃗ = (c⃗_1, c⃗_2) ∈^n be the concatenation of c⃗_1 and c⃗_2. Next, define the n-dimensional vectors a⃗_1 = 2∑_i = 1^n-3e⃗_i and a⃗_2 = 2∑_i = 1^3 e⃗_n-3+i, and let A be a matrix whose first row is a⃗_1 and second row is a⃗_2. Let Q_γ,n be the MILP

    [         maximize            c⃗·x⃗;       subject to Ax⃗ = (n-3, 3)^⊤;                       x⃗∈{0,1}^n. ]
 We define ℱ_n, μ^* = {Q_n, γ : γ≥ 1}.


If γ = 1 and n = 8, then Q_γ, n is 
    [                                          maximize             (1, 2, 3, 4, 5, 0, 1.5, 3-1/2μ^*) ·x⃗;                                        subject to [ 2 2 2 2 2 0 0 0; 0 0 0 0 0 2 2 2 ]x⃗ = [ 5; 3 ];                                                                                         x⃗∈{0,1}^8. ]


For every even n ≥ 6, both of the constraints a⃗_1 ·x⃗ = 2∑_i = 1^n-3 x_i = n-3 and a⃗_2 ·x⃗ = 2∑_i = 1 ^3 x_n-3+i = 3 are infeasible for x⃗∈{0,1}^n since 2∑_i = 1 ^n-3 x_i and 2∑_i = 1^3 x_n-3+i are even numbers but 3 and n-3 are odd numbers. The key idea of this proof is that if branch-and-bound branches on all variables in {x_n-2, x_n-1, x_n} first, it will terminate upon making a tree of size at most 2^3 = 8, since at most three branches are necessary to determine that a⃗_1 ·x⃗ = 2∑_i = 1^3 x_n-3+i = 3 is infeasible. However, if branch-and-bound branches on all variables in {x_1, …, x_n-3} first, it will create a tree with exponential size before it terminates.


Suppose μ < μ^*. Then for any MILP Q_γ, n∈_n, μ^*, μ_1 + (1-μ)_2 branches on all variables in {x_n-2, x_n-1, x_n} before branching on variables in {x_1, …, x_n-3}.



For ease of notation, for the remainder of this proof, we drop the subscript (γ, n) from Q_γ, n and denote this MILP as Q. We first need to determine the form of x̆⃗̆_Q, which is the optimal solution to the LP relaxation of Q.
 It is easiest to see how the LP relaxation will set the variables x_n-2, x_n-1, and x_n. The only constraints on these variables are that 2(x_n-2 + x_n-1 + x_n) = 3 and that x_n-2, x_n-1, x_n ∈ [0,1]. Recall that c⃗ = (1, 2, …, n-3, 0, 1.5, 3-1/2μ^*) is the vector defining the objective value of Q. Since μ^* > 1/3, we know that 1.5 < 3-1/2μ^*, which means that c[n-2] < c[n-1] < c[n]. Since the goal is to maximize c⃗·x⃗, the LP relaxation will set x_n-2 = 0, x_n-1 = 1/2, and x_n = 1. The logic for the first n-3 variables is similar. In this case, c[1] < c[2] < ⋯ < c[n-3], so the LP relaxation's solution will put as much weight as possible on the variable x_n-3, then as much weight as possible on the variable x_n-4, and so on, putting as little weight as possible on the variable x_1 since it has the smallest corresponding objective coefficient c[1]. Since the only constraints on these variables are that 2∑_i = 1^n-3 x_i = n-3 and x_1, …, x_n-3∈ [0,1], the LP objective value can set ⌊n-3/2⌋ of the variables to 1, it can set one variable to 1/2, and it has to set the rest of the variables to 0. Letting i = ⌈n-3/2⌉, this means the LP relaxation will set the first i - 1 variables x_1, ⋯ x_i-1 to zero, it will set x_i = 1/2, and it will set x_i + 1, …, x_n-3 to 1. In other words, 
    x̆_Q[j]
    =  0    if  j ≤⌊ (n-3)/2 ⌋ or  j = n-2
    1/2   if  j = ⌈ (n-3)/2 ⌉ or  j = n-1
    
    1    if ⌈ (n-3)/2 ⌉≤ j ≤ n-3  or  j = n.

For example, if n = 8, then x̆⃗̆_Q = (0, 0, 1/2, 1, 1, 0, 1/2, 1). (See Figure <ref>.) Therefore, the only candidate variables to branch on are x_n-1 and x_i where again, i = ⌈ (n-3)/2 ⌉.



To determine when variable B&B will branch on, we need to calculate x̆⃗̆_Q_i^- which is the solution to the LP relaxation of Q with the additional constraint that x_i = 0, as well as x_Q_i^+ which is the solution to the LP relaxation of Q with the additional constraint that x_i = 1, and x_Q_n-1^- and x_Q_n-1^+.
First, we will determine the form of the vectors x̆⃗̆_Q_n-1^- and x̆⃗̆_Q_n-1^+. Suppose we set x_n-1=0. We now need to ensure that 2(x_n-2 + 0 + x_n) = 3 and that x_n-2, x_n ∈ [0,1]. Since c[n-2] = 0 < 3 - 1/2μ^* = c[n], the solution to the LP relaxation of Q_n-1^- will set x_n-2 = 1/2 and x_n = 1. (See Figure <ref>.) Similarly, if we set x_n-1=1, we now need to ensure that 2(x_n-2 + 1 + x_n) = 3 and that x_n-2, x_n ∈ [0,1]. Therefore, the solution to the LP relaxation of Q_n-1^- will set x_n-2 = 0 and x_n = 1/2. (See Figure <ref>.) In other words, x̆⃗̆_Q_n-1^- = x̆⃗̆_Q - 1/2e⃗_n-1 + 1/2e⃗_n-2 and x̆⃗̆_Q_n-1^+ = x̆⃗̆_Q + 1/2e⃗_n-1 - 1/2e⃗_n.

The argument for x̆⃗̆_Q_i^- and x̆⃗̆_Q_i^- is similar. Recall that in x̆⃗̆_Q, the solution to the LP relaxation of the original MIP Q, we have that x̆_Q[i] = 1/2 since it is the median of the variables x_1, …, x_n-3. For all j > i, we have that x̆_Q[j] = 1 and for all j < i, we have that x̆_Q[j] = 0. Suppose we set x_i = 0. As before, the LP relaxation's solution will put as much weight as possible on the variable x_n-3, then as much weight as possible on the variable x_n-4, and so on, putting as little weight as possible on the variable x_1 since it has the smallest corresponding objective coefficient c[1]. Since it cannot set x_i = 1/2, it will set the next-best variable to 1/2, which is x_i-1. (See Figure <ref>.) In other words, x̆⃗̆_Q_i^- = x̆⃗̆_Q - 1/2e⃗_i + 1/2e⃗_i-1. If we set x_i = 1, the LP relaxation's solution will have to take some weight away from the variables x_i+1, …, x_n-3 since it needs to ensure that 2∑_i = 1^n-3 x_i = n-3. Therefore, it will set x_i+1 to 1/2 and x_j to 1 for all j > i+1. (See Figure <ref>.)
In other words, x̆⃗̆_Q_i^+ = x̆⃗̆_Q + 1/2e⃗_i - 1/2e⃗_i+1.

 Therefore, 
    c̆_Q_i^-   = c̆⃗̆_Q - 1/2⌈n-3/2⌉ + 1/2⌊n-3/2⌋ = c̆_Q - γ/2,
    c̆⃗̆_Q_i^+   = c̆⃗̆_Q +  1/2⌈n-3/2⌉ - 1/2(⌈n-3/2⌉ + 1) = c̆_Q - γ/2,
    c̆_Q_n-1^-   =c̆⃗̆_Q - 3γ/4,  and 
    c̆_Q_n-1^+   =c̆⃗̆_Q +3/4 - 1/2(3 - 1/2μ^*) = c̆⃗̆_Q - γ/4(3 - 1/μ^*).
 This means that c̆_Q - c̆_Q_i^- = c̆_Q - c̆_Q_i^+ = γ/2, c̆_Q - c̆_Q_n-1^- = 3γ/4, and c̆_Q - c̆_Q_n-1^+ = γ/4(3 - 1/μ^*). Therefore, μ_1(Q,i) + (1-μ)_2(Q,i) = γ/2 and μ_1(Q,n-1) + (1-μ)_2(Q,n-1) = μγ/4(3 - 1/μ^*) + 3γ(1-μ)/4 = 3γ/4 -  μγ/4μ^*. This means that μ_1(Q,i) + (1-μ)_2(Q,i) = γ/2 <3γ/4 -  μγ/4μ^* = μ_1(Q,n-1) + (1-μ)_2(Q,n-1) so long as μ < μ^*.

The next node branch-and-bound will explore is Q_n-1^-. The vector x̆⃗̆_Q_n-1^- has fractional values only in positions i and n-2. Branching on i, we again have that c̆_Q_n-1^- - c̆_Q_n-1,i^-,- = c̆_Q_n-1^- - c̆_Q_n-1,i^-,+ = γ/2.
Branching on n-2, Q_n-1, n-2^-,- is infeasible, so c̆_Q_n-1^- - c̆_Q_n-1,n-2^-,- equals some large number B ≥ ||c⃗||_1. Next, x̆⃗̆_Q_n-1, n-2^-,+ = x̆⃗̆_Q_n-1^- + 1/2e⃗_n-2 - 1/2e⃗_n, so c̆_Q_n-1, n-2^-,+ = c̆_Q_n-1^- - γ/2(3 - 1/2μ^*). Therefore, μ_1(Q_n-1^-,i) + (1-μ)_2(Q_n-1^-,i) = γ/2 and 
    μ_1(Q_n-1^-,n-2) + (1-μ)_2(Q_n-1^-,n-2)    = μγ/2(3 - 1/2μ^*) + (1 - μ)B
       = B + μ(3γ/2 - γ/4μ^* - B)
       ≥ B + μ^*(3γ/2 - γ/4μ^* - B)
       = B - γ/4 + μ^*(3γ/2 - B)
       > B - γ/4 + 3γ/4 - B/3γ/2 - B(3γ/2 - B)
       = B - γ/4 + 3γ/4 - B
       = γ/2,
 where the final inequality holds because μ^* < 1 < B-3γ/4/B - 3γ/2. Therefore, x_n-2 will be branched on next.

Since Q_n-1, n-2^-,- is infeasible, the next node branch-and-bound will explore is Q_n-1, n-2^-,+. The vector x̆⃗̆_Q_n-1, n-2^-, + has fractional values only in positions i and n. Both MILP instances Q_n-1, n-2, n^-, +, - and Q_n-1, n-2, n^-, +, + are infeasible, so μ_1(Q_n-1, n-2^-, +,n) + (1-μ)_2(Q_n-1, n-2^-, +,n) = B whereas μ_1(Q_n-1, n-2^-, +,i) + (1-μ)_2(Q_n-1, n-2^-, +,i) = γ/2, as before. Therefore, branch-and-bound will branch on x_n and fathom both children.

The next node branch-and-bound will explore is Q_n-1^+. The vector x̆⃗̆_Q_n-1^+ has fractional values only in positions i and n. Branching on i, we again have that c̆_Q_n-1^+ - c̆_Q_n-1,i^+,- = c̆_Q_n-1^+ - c̆_Q_n-1,i^+,+ = γ/2.
Branching on x_n, x̆⃗̆_Q_n-1, n^+,- = x̆⃗̆_Q_n-1^+ - 1/2e⃗_n + 1/2e⃗_n-2, so c̆_Q_n-1, n^+,- = c̆_Q_n-1^+ - γ/2(3 - 1/2μ^*).
Meanwhile, Q_n-1, n^+,+ is infeasible, so c̆_Q_n-1^+ - c̆_Q_n-1,n-2^+,+ = B.
 Therefore, μ_1(Q_n-1^+,i) + (1-μ)_2(Q_n-1^+,i) = γ/2 and μ_1(Q_n-1^+,n) + (1-μ)_2(Q_n-1^+,n) = μγ/2(3 - 1/2μ^*) + (1 - μ)B > γ/2. Therefore, x_n will be branched on next.

The next node branch-and-bound will explore is Q_n-1, n^+,-. The vector x̆⃗̆_Q_n-1, n^+,- has fractional values only in positions i and n-2. Both MILP instances Q_n-1, n, n-2^+, -, - and Q_n-1, n, n-2^+,-,- are infeasible, so μ_1(Q_n-1, n^-, +,n-2) + (1-μ)_2(Q_n-1, n^-, +,n-2) = B whereas μ_1(Q_n-1, n-2^-, +,i) + (1-μ)_2(Q_n-1, n-2^-, +,i) = γ/2, as before. Therefore, branch-and-bound will branch on x_n-2 and fathom both children.

At this point, all children have been fathomed, so branch-and-bound will terminate.



Suppose μ > μ^*. Then for any MILP Q_γ, n∈_n, μ^*, branch-and-bound with the scoring rule μ_1 + (1-μ)_2 will create a tree of depth at least 2^(n-5)/4.



To prove this lemma, we use induction to show that on any path from the root of the branch-and-bound tree to a node of depth i = ⌊ (n-3)/2 ⌋, if J are the set of indices branched on along that path, then J ⊆{x_1, …, x_n-3}. Even after branching on i nodes from {x_1, …, x_n-3}, the MILP will still be feasible, so the branch will not yet have been fathomed (since the original MILP is infeasible, a node will be fathomed only when it is infeasible). Therefore, branch-and-bound will continue down every branch to depth ⌊ (n-3)/2 ⌋, thus creating a tree with 2^(n-4)/2 nodes.


On any path from the root of the branch-and-bound tree to a node of depth i = ⌊ (n-3)/2 ⌋, if J are the set of indices branched on along that path, then J ⊆{x_1, …, x_n-3}.


We prove this claim by induction.

Inductive hypothesis. For j ≤⌊ (n-3)/2 ⌋, let J be the set of indices branched on along an arbitrary path of the branch-and-bound tree from the root to a node of depth j. Then J ⊆{x_1, …, x_n-3}.

Base case (j=0). As we saw in the proof of Lemma <ref>, if μ > μ^*, then branch-and-bound will first branch on x_i where i = ⌈ (n-3)/2 ⌉.

Inductive step. Let j be an arbitrary index such that 0 ≤ j ≤ i-1. Let J be the set of indices branched on along an arbitrary path of the branch-and-bound tree from the root to a node of depth j. We know from the inductive hypothesis that J ⊆{x_1, …, x_n-3}. Let Q' be the MILP at that node. Since j ≤⌊ (n-3)/2 ⌋ - 1, we know that the LP relaxation of Q' is feasible. Let z be the number of variables set to zero in J and let x_p_1, x_p_2, …, x_p_t be {x_1, …, x_n-3}∖ J ordered such that p_k < p_k' for k < k'. We know that the solution to the LP relaxation of Q' will have the first i' := ⌊ (n-3)/2 ⌋ - z variables x_p_1, …, x_p_i' set to 0, it will set x_p_i'+1 to 1/2, and it will set the remaining variables in {x_1, …, x_n-3}∖ J to 1. Thus, the fractional variables are x_p_i'+1 and x_n-1. Note that since z ≤  |J| ≤⌊ (n-3)/2 ⌋ - 1, i' = ⌊ (n-3)/2 ⌋ - z ≥ 1.

Suppose we branch on x_p_i'+1. If we set x_p_i'+1 = 0, then the LP relaxation of (Q')_p_i'+1^- will set x_p_i' to be 1/2 and otherwise the optimal solution will remain unchanged. Thus, c̆_Q' - c̆_(Q')_p_i' + 1^- = 
c̆_Q' - (c̆_Q' - γ p_i'+1/2 + γ p_i'/2) = γ(p_i'+1 - p_i')/2. Meanwhile, if we set x_p_i'+1 = 1, then the LP relaxation of (Q')_p_i'+1^- will set x_p_i'+2 to be 0 and otherwise the optimal solution will remain unchanged. Thus, c̆_Q' - c̆_(Q')_p_i' + 1^+ = c̆_Q' - (c̆_Q' + γ p_i'+1/2 - γ p_i'+2/2) = γ(p_i'+2 - p_i'+1)/2. Suppose that c̆_Q' - c̆_(Q')_p_i' + 1^+ > c̆_Q' - c̆_(Q')_p_i' + 1^-. Then 
    μ_1(Q', p_i'+1) + (1-μ)_2(Q', p_i'+1)    = γ/2(μ(p_i'+1 - p_i') + (1-μ)(p_i'+2 - p_i'+1) )
       ≥γ/2(μ + (1-μ))
       = γ/2.


 Meanwhile, suppose that c̆_Q' - c̆_(Q')_p_i' + 1^+≤c̆_Q' - c̆_(Q')_p_i' + 1^-. Then 
    μ_1(Q', p_i'+1) + (1-μ)_2(Q', p_i'+1)    =  γ/2(μ(p_i'+2 - p_i'+1) + (1-μ)( p_i'+1 - p_i') )
       ≥γ/2(μ + (1-μ))
       = γ/2.
 Meanwhile, as in the proof of Lemma <ref>, μ_1(Q',n-1) + (1-μ)_2(Q',n-1) = 3γ/4 -  μγ/4μ^* < γ/2 so long as μ > μ^*. Thus, branch-and-bound will branch next on x_p_i'.






Let 
    _1(Q, i) = min{c̆_Q - c̆_Q_i^+, c̆_Q - c̆_Q_i^-} and _2(Q, i) = max{c̆_Q - c̆_Q_i^+, c̆_Q - c̆_Q_i^-}.
 For all even n ≥ 6 and all μ^* ∈(1/3, 2/3), there exists an infinite family 𝒢_n, μ^* of MILP instances such that for any Q ∈𝒢_n, μ^*, if μ∈[0,μ^*), then the scoring rule μ_1 + (1-μ)_2 results in a branch-and-bound tree with Ω(2^(n-5)/4) nodes and if μ∈(μ^*,1], the scoring rule results a tree with O(1) nodes.




For any constant γ≥ 1, let c⃗_1 ∈^n-3 be a vector such that 
    c_1[i] =  0    if  i < (n-3)/2
    
    1.5    if  i = ⌈ (n-3)/2⌉
    
    3 - 1/2μ^*   if  i > (n-3)/2 + 1
 and let c⃗_2 = (1, 2, 3). Let c⃗ = γ(c⃗_1, c⃗_2) ∈^n be the concatenation of c⃗_1 and c⃗_2 multiplied with γ. For example, if γ = 1 and n = 8, then c⃗ = (0,0, 1.5, 3 - 1/2μ^*, 3 - 1/2μ^*, 1, 2, 3) Next, define the n-dimensional vectors a⃗_1 = 2∑_i = 1^n-3e⃗_i and a⃗_2 = 2∑_i = 1^3 e⃗_n-3+i, and let A be a matrix whose first row is a⃗_1 and second row is a⃗_2. Let Q_γ,n be the MILP

    [         maximize            c⃗·x⃗;       subject to Ax⃗ = (n-3, 3)^⊤;                       x⃗∈{0,1}^n. ]


We define 𝒢_n, μ^* = {Q_n, γ : γ≥ 1}.

For every even n ≥ 6, Q_γ, n, both of the constraints a⃗_1 ·x⃗ = 2∑_i = 1^n-3 x_i = n-3 and a⃗_2 ·x⃗ = 2∑_i = 1 ^3 x_n-3+i = 3 are infeasible for x⃗∈{0,1}^n since 2∑_i = 1 ^n-3 x_i and 2∑_i = 1^3 x_n-3+i are even numbers but 3 and n-3 are odd numbers. The key idea of this proof is that if branch-and-bound branches on all variables in {x_n-2, x_n-1, x_n} first, it will terminate upon making a tree of size at most 2^3 = 8, since at most three branches are necessary to determine that a⃗_1 ·x⃗ = 2∑_i = 1^3 x_n-3+i = 3 is infeasible. However, if branch-and-bound branches on all variables in {x_1, …, x_n-3} first, it will create a tree with exponential size before it terminates.



Suppose μ > μ^*. Then for any MILP Q_γ, n∈𝒢_n, μ^*, μ_1 + (1-μ)_2 branches on all variables in {x_n-2, x_n-1, x_n} before branching on variables in {x_1, …, x_n-3}.



For ease of notation, for the remainder of this proof, we drop the subscript (γ, n) from Q_γ, n and denote this MILP as Q.
The optimal solution to the LP relaxation of Q has the following form: 
    x̆⃗̆_Q[j]
    =  0    if  j ≤⌊ (n-3)/2 ⌋ or  j = n-2
    1/2   if  j = ⌈ (n-3)/2 ⌉ or  j = n-1
    
    1    if ⌈ (n-3)/2 ⌉≤ j ≤ n-3  or  j = n.

For example, if n = 8, then x̆⃗̆_Q = (0, 0, 1/2, 1, 1, 0, 1/2, 1). Therefore, the only candidate variables to branch on are x_n-1 and x_i where i = ⌈ (n-3)/2 ⌉. Branching on x_i, we have x̆⃗̆_Q_i^- = x̆⃗̆_Q - 1/2e⃗_i + 1/2e⃗_i-1 and x̆⃗̆_Q_i^+ = x̆⃗̆_Q + 1/2e⃗_i - 1/2e⃗_i+1. Branching on x_n-1, we have x̆⃗̆_Q_n-1^- = x̆⃗̆_Q - 1/2e⃗_n-1 + 1/2e⃗_n-2 and x̆⃗̆_Q_n-1^+ = x̆⃗̆_Q + 1/2e⃗_n-1 - 1/2e⃗_n. Therefore, 
    c̆_Q_i^-   = c̆⃗̆_Q - 3γ/4,
    c̆⃗̆_Q_i^+   = c̆⃗̆_Q +  3γ/4 - γ/2(3 - 1/2μ^*) = c̆_Q - 3γ/4( 1- 1/μ^*),
    c̆_Q_n-1^-   =c̆⃗̆_Q - γ + γ/2 =c̆⃗̆_Q - γ/2,  and 
    c̆_Q_n-1^+   =c̆⃗̆_Q +γ - 3γ/2 =c̆⃗̆_Q - γ/2.
 This means that c̆_Q - c̆_Q_i^- = 3γ/4, c̆_Q - c̆_Q_i^+ = γ/4(3 - 1/μ^*), and c̆_Q - c̆_Q_n-1^- = c̆_Q - c̆_Q_n-1^+ = γ/2. Therefore, μ_1(Q,i) + (1-μ)_2(Q,i) =  μγ/4(3 - 1/μ^*) + 3γ(1-μ)/4 = 3γ/4 -  μγ/4μ^* and μ_1(Q,n-1) + (1-μ)_2(Q,n-1) = γ/2. This means that μ_1(Q,i) + (1-μ)_2(Q,i) = 3γ/4 -  μγ/4μ^* < γ/2 = μ_1(Q,n-1) + (1-μ)_2(Q,n-1) so long as μ > μ^*.

The next node branch-and-bound will explore is Q_n-1^-. The vector x̆⃗̆_Q_n-1^- has fractional values only in positions i and n-2. Branching on i, we again have that c̆_Q_n-1^- - c̆_Q_n-1,i^-,- = 3γ/4 and c̆_Q_n-1^- - c̆_Q_n-1,i^-,+ = γ/4(3 - 1/μ^*).
Branching on n-2, Q_n-1, n-2^-,- is infeasible, so c̆_Q_n-1^- - c̆_Q_n-1,n-2^-,- equals some large number B ≥ ||c⃗||_1. Next, x̆⃗̆_Q_n-1, n-2^-,+ = x̆⃗̆_Q_n-1^- + 1/2e⃗_n-2 - 1/2e⃗_n, so c̆_Q_n-1, n-2^-,+ = c̆_Q_n-1^- - γ. Therefore, μ_1(Q_n-1^-,i) + (1-μ)_2(Q_n-1^-,i) = 3γ/4 -  μγ/4μ^* and 
    μ_1(Q_n-1^-,n-2) + (1-μ)_2(Q_n-1^-,n-2)    = μγ + (1 - μ)B
       = B + μ(γ-B)
       = B - μγ/4μ^* + μ(γ + γ/4μ^* -B)
        > B - μγ/4μ^* + 3γ/4 - B/γ + γ/4μ^* -B(γ + γ/4μ^* -B)
       = B - μγ/4μ^* + 3γ/4 - B
       = 3γ/4 -  μγ/4μ^*,
 where the final inequality holds because μ < 1 < B - 3γ/4/B - (γ + γ/(4μ^*)). Therefore, x_n-2 will be branched on next.

Since Q_n-1, n-2^-,- is infeasible, the next node branch-and-bound will explore is Q_n-1, n-2^-,+. The vector x̆⃗̆_Q_n-1, n-2^-, + has fractional values only in positions i and n. Since both MILP instances Q_n-1, n-2, n^-, +, - and Q_n-1, n-2, n^-, +, + are infeasible, so μ_1(Q_n-1, n-2^-, +,n) + (1-μ)_2(Q_n-1, n-2^-, +,n) = B whereas μ_1(Q_n-1, n-2^-, +,i) + (1-μ)_2(Q_n-1, n-2^-, +,i) = 3γ/4 -  μγ/4μ^* < B. Therefore, branch-and-bound will branch on x_n and fathom both children.

The next node branch-and-bound will explore is Q_n-1^+. The vector x̆⃗̆_Q_n-1^+ has fractional values only in positions i and n. Branching on i, we again have that c̆_Q_n-1^- - c̆_Q_n-1,i^-,- = 3γ/4 and c̆_Q_n-1^- - c̆_Q_n-1,i^-,+ = γ/4(3 - 1/μ^*).
Branching on x_n, x̆⃗̆_Q_n-1, n^+,- = x̆⃗̆_Q_n-1^+ - 1/2e⃗_n + 1/2e⃗_n-2, so c̆_Q_n-1, n^+,- = c̆_Q_n-1^+ - γ.
Meanwhile, Q_n-1, n^+,+ is infeasible, so c̆_Q_n-1^+ - c̆_Q_n-1, n-2^+,+ equals some large number B ≥ ||c⃗||_1.
 Therefore, μ_1(Q_n-1^+,i) + (1-μ)_2(Q_n-1^+,i) = 3γ/4 -  μγ/4μ^* and μ_1(Q_n-1^+,n) + (1-μ)_2(Q_n-1^+,n) = μγ + (1 - μ)B > 3γ/4 -  μγ/4μ^*. Therefore, x_n will be branched on next.

The next node branch-and-bound will explore is Q_n-1, n^+,-. The vector x̆⃗̆_Q_n-1, n^+,- has fractional values only in positions i and n-2. Since both MILP instances Q_n-1, n, n-2^+, -, - and Q_n-1, n, n-2^+,-,- are infeasible, so μ_1(Q_n-1, n^-, +,n-2) + (1-μ)_2(Q_n-1, n^-, +,n-2) = B whereas μ_1(Q_n-1, n-2^-, +,i) + (1-μ)_2(Q_n-1, n-2^-, +,i) = 3γ/4 -  μγ/4μ^* < B, as before. Therefore, branch-and-bound will branch on x_n-2 and fathom both children.

At this point, all children have been fathomed, so branch-and-bound will terminate.



Suppose μ < μ^*. Then for any MILP Q_γ, n∈𝒢_n, μ^*, branch-and-bound with the scoring rule μ_1 + (1-μ)_2 will create a tree of depth at least 2^(n-5)/4.



Let i =⌈ (n-3)/2 ⌉. We first prove two useful claims.


Let j be an even number such that 2 ≤ j ≤ i - 2 and let J = {x_i-j/2, …, x_i+j/2-1}. Suppose that B&B has branched on exactly the variables in J and suppose that the number of variables set to 1 equals the number of variables set to 0. Then B&B will next branch on the variable x_i+j/2. Similarly, suppose J = {x_i-j/2 + 1, x_i-j/2+2, …, x_i+j/2}. Suppose that B&B has branched on exactly the variables in J and suppose that the number of variables set to 1 equals the number of variables set to 0. Then B&B will next branch on the variable x_i-j/2.



Let Q be the MILP contained in the node at the end of the path. This proof has two cases.


  
Case 1: J = {x_i-j/2, x_i-j/2+1, …, x_i+j/2-1}. In this case, there is a set J_< = {x_1, …, x_i - j/2 - 1} of i-j/2 - 1 variables smaller than x_i that have not yet been branched on and there is a set J_> = {x_i + j/2, …, x_n-3} of n - 3 - (i+ j/2 -1)  = 2i - 1  - (i+ j/2 -1) = i - j/2 variables in {x_i+1, …, x_n-3} that have not yet been branched on. Since the number of variables set to 1 in J equals the number of variables set to 0, the LP relaxation will set the i - j/2 - 1 variables in J_< to 0, the i - j/2 - 1 variables in J_> ∖{x_i+j/2} to 1, and x_i+j/2 to 1/2. It will also set x_n-2 = 0, x_n-1 = 1/2, and x_n = 1. Therefore, the two fractional variables are x_i+j/2 and x_n-1. Branching on x_i+j/2, we have
x̆⃗̆_Q_i + j/2^- = x̆⃗̆_Q - 1/2e⃗_i + j/2 + 1/2e⃗_i - j/2 - 1 and
x̆⃗̆_Q_i + j/2^+ = x̆⃗̆_Q + 1/2e⃗_i + j/2 - 1/2e⃗_i + j/2 + 1. Branching on x_n-1, we have that
x̆⃗̆_Q_n-1^- = x̆⃗̆_Q - 1/2e⃗_n-1 + 1/2e⃗_n-2 and
x̆⃗̆_Q_n-1^+ = x̆⃗̆_Q + 1/2e⃗_n-1 - 1/2e⃗_n. Therefore, 
    c̆_Q_i + j/2^-   = c̆_Q - γ/2(3 - 1/2μ^*)
    c̆_Q_i + j/2^+   = c̆_Q
    c̆_Q_n-1^-   = c̆_Q - 1 + 1/2 = c̆_Q - γ/2
    c̆_Q_n-1^+   = c̆_Q + 1 - 3/2 = c̆_Q - γ/2


This means that c̆_Q - c̆_Q_i + j/2^-
= γ/2(3 - 1/2μ^*), c̆_Q - c̆_Q_i + j/2^+ = 0, and c̆_Q - c̆_Q_n-1^- = c̆_Q - c̆_Q_n-1^+ = γ/2. Therefore, μ_1(Q, i + j/2) + (1-μ)_2(Q, i + j/2) = γ(1 - μ)/2(3 - 1/2μ^*) and μ_1(Q, n-1) + (1-μ)_2(Q, n-1) = γ/2. Since μ < μ^* and μ^* ∈(1/3, 1/2), we have that 
    μ_1(Q, i + j/2) + (1-μ)_2(Q, i + j/2)    = γ(1 - μ)/2(3 - 1/2μ^*)
       ≥γ(1 - μ^*)/2(3 - 1/2μ^*)
       ≥γ/2.

Therefore, x_i + j/2 will be branched on next.



  
Case 2: J = {x_i-j/2 + 1, x_i-j/2+2, …, x_i+j/2}. 
In this case, there is a set J_< = {x_1, …, x_i- j/2} of i-j/2 variables smaller than x_i that have not yet 
been branched on and a set J_> = {x_i + j/2 + 1, …, x_n-3} of n - 3 - (i+ j/2)  = 2i - 1  - (i+ j/2) = i - j/2 - 1 variables in {x_i+1, …, x_n-3} that have not yet been branched on. Since the number 
of variables set to 1 in J equals the number of variables set to 0, the LP 
relaxation will set the i - j/2 - 1 variables in J_<∖{x_i-j/2} to 0, the i - j/2 - 1 variables in J_> ∖{x_i+j/2} to 1, and x_i-j/2 to 1/2. It will also set x_n-2 = 0, 
x_n-1 = 1/2, and x_n = 1. Therefore, the two fractional variables are 
x_i-j/2 and x_n-1. Branching on x_i-j/2, we have
x̆⃗̆_Q_i - j/2^- = x̆⃗̆_Q - 1/2e⃗_i - j/2 + 1/2e⃗_i - j/2 - 1 and
x̆⃗̆_Q_i - j/2^+ = x̆⃗̆_Q + 1/2e⃗_i - j/2 - 1/2e⃗_i + j/2 + 1. Branching on x_n-1, we have that
x̆⃗̆_Q_n-1^- = x̆⃗̆_Q - 1/2e⃗_n-1 + 1/2e⃗_n-2 and
x̆⃗̆_Q_n-1^+ = x̆⃗̆_Q + 1/2e⃗_n-1 - 1/2e⃗_n. Therefore, 
    c̆_Q_i - j/2^-   = c̆_Q
    c̆_Q_i - j/2^+   =  c̆_Q - γ/2(3 - 1/2μ^*)
    c̆_Q_n-1^-   = c̆_Q - γ + γ/2 = c̆_Q - γ/2
    c̆_Q_n-1^+   = c̆_Q + γ - 3γ/2 = c̆_Q - γ/2


This means that c̆_Q - c̆_Q_i-j/2^-
= γ/2(3 - 1/2μ^*), c̆_Q - c̆_Q_i-j/2^+= 0, and c̆_Q - c̆_Q_n-1^- = c̆_Q - c̆_Q_n-1^+ = γ/2 as in the previous case, so x_i - j/2 will be branched on next. 



Suppose that J is the set of variables branched on along a path of depth 2 ≤ j ≤ i - 2  where j is odd and let j' = ⌊ j/2⌋. Suppose that J = {x_i-j', x_i-j'+1, …, x_i+j'}. Moreover, suppose that the number of variables set to 1 in J equals the number of variables set to 0, plus or minus 1. Then B&B will either branch on x_i-j' - 1 or x_i+j'+1.



Let Q be the MILP contained a the end of the path. There are i - j' - 1 variables J_< = {x_1, …, x_i-j'-1} that are smaller than x_i that have not yet been branched on, and n-3 - (i+j') = 2i - 1 - (i + j') = i-j'-1 variables J_> = {x_i+j' + 1, …, x_n-3} in {x_i+1, …, x_n-3} that have not yet been branched on. Let z be the number of variables in J set to 0 and let o be the number of variables set to 1. This proof has two cases:


  
Case 1: z = o + 1. Since z + o = j, we know that z = j' + 1 and o = j'. Therefore, the LP relaxation will set the variables in J_< ∖{x_i-j' - 1} to zero for a total of |J_< ∖{x_i-j' - 1}| + z = i - j' - 2 + j' + 1 = i - 1 zeros, it will set the variables in J_> to one for a total of |J_>| + o = i - j' - 1 + j' = i-1 ones, and it will set x_i-j' - 1 to 1/2. It will also set x_n-2 = 0, x_n-1 = 1/2, and x_n = 1. Therefore, the two fractional variables are x_i-j' - 1 and x_n-1. Branching on x_i-j' - 1, we have
x̆⃗̆_Q_i -j' - 1^- = x̆⃗̆_Q - 1/2e⃗_i -j' - 1 + 1/2e⃗_i -j' - 2 and
x̆⃗̆_Q_i -j' - 1^+ = x̆⃗̆_Q + 1/2e⃗_i -j' - 1 - 1/2e⃗_i + j' + 1. Branching on x_n-1, we have that
x̆⃗̆_Q_n-1^- = x̆⃗̆_Q - 1/2e⃗_n-1 + 1/2e⃗_n-2 and
x̆⃗̆_Q_n-1^+ = x̆⃗̆_Q + 1/2e⃗_n-1 - 1/2e⃗_n. Therefore, 
    c̆_Q_i -j' - 1^-   = c̆_Q
    c̆_Q_i -j' - 1^+   = x̆⃗̆_Q - γ/2(3 - 1/2μ^*)
    c̆_Q_n-1^-   = c̆_Q - γ + γ/2 = c̆_Q - γ/2
    c̆_Q_n-1^+   = c̆_Q + γ - 3γ/2 = c̆_Q - γ/2


This means that c̆_Q - c̆_Q_i - j' - 1^- =0, c̆_Q - c̆_Q_i - j' - 1^+ = γ/2(3 - 1/2μ^*), and c̆_Q - c̆_Q_n - 1^-= c̆_Q - c̆_Q_n - 1^+ = γ/2. Therefore, μ_1(Q, i -j' - 1) + (1-μ)_2(Q, i -j' - 1) = γ(1 - μ)/2(3 - 1/2μ^*) and μ_1(Q, n-1) + (1-μ)_2(Q, n-1) = γ/2. Since μ < μ^* and μ^* ∈(1/3, 1/2), we have that 
    μ_1(Q, i -j' - 1) + (1-μ)_2(Q, i -j' - 1)    = γ(1 - μ)/2(3 - 1/2μ^*)
       ≥γ(1 - μ^*)/2(3 - 1/2μ^*)
       ≥γ/2.

Therefore, x_i -j' - 1 will be branched on next.



  
Case 1: z = o - 1. Since z + o = j, we know that z = j' and o = j' + 1. Therefore, the LP relaxation will set the variables in J_< to zero for a total of |J_<| + z = i - j' - 1 + j'= i - 1 zeros, it will set the variables in J_> ∖{x_i + j' + 1} to one for a total of |J_>∖{x_i + j' + 1}| + o = i - j' - 2 + j' +1 = i-1 ones, and it will set x_i + j' + 1 to 1/2. It will also set x_n-2 = 0, x_n-1 = 1/2, and x_n = 1. Therefore, the two fractional variables are x_i+j' + 1 and x_n-1. Branching on x_i+j' + 1, we have
x̆⃗̆_Q_i + j' + 1^- = x̆⃗̆_Q - 1/2e⃗_i + j' + 1 + 1/2e⃗_i -j' - 1 and
x̆⃗̆_Q_i + j' + 1^+ = x̆⃗̆_Q + 1/2e⃗_i + j' + 1 - 1/2e⃗_i + j' + 2. Branching on x_n-1, we have that
x̆⃗̆_Q_n-1^- = x̆⃗̆_Q - 1/2e⃗_n-1 + 1/2e⃗_n-2 and
x̆⃗̆_Q_n-1^+ = x̆⃗̆_Q + 1/2e⃗_n-1 - 1/2e⃗_n. Therefore, 
    c̆_Q_i + j' + 1^-   = c̆_Q - γ/2(3 - 1/2μ^*)
    c̆_Q_i + j' + 1^+   = x̆⃗̆_Q
    c̆_Q_n-1^-   = c̆_Q - γ + γ/2 = c̆_Q - γ/2
    c̆_Q_n-1^+   = c̆_Q + γ - 3γ/2 = c̆_Q - γ/2


This means that c̆_Q - c̆_Q_i + j' + 1^-
 =γ/2(3 - 1/2μ^*), c̆_Q - c̆_Q_i + j' + 1^+ = 0, and c̆_Q - c̆_Q_n - 1^- = c̆_Q - c̆_Q_n - 1^+ = γ/2. Therefore, μ_1(Q, i + j' + 1) + (1-μ)_2(Q, i +j' + 1) = γ(1 - μ)/2(3 - 1/2μ^*) and μ_1(Q, n-1) + (1-μ)_2(Q, n-1) = γ/2. As in the previous case, this means that x_i +j' + 1 will be branched on next.


We now prove by induction that there are 2^(⌈(n-3)/2⌉) - 1)/2≥ 2^(n-5)/4 paths in the B&B tree of length at least i-2. Therefore, the size of the tree is at least 2^(n-5)/4.



  
Inductive hypothesis. Let j be an arbitrary integer between 1 and i-2. If j is even, then there exist at least 2^j/2 paths in the B&B tree from the root to nodes of depth j such that if J is the set indices branched on along a given path, then J = {x_i-j/2, x_i-j/2+1, …, x_i+j/2-1} or J = {x_i-j/2 + 1, x_i-j/2+2, …, x_i+j/2}. Moreover, the number of variables set to 0 in J equals the number of variables set to 1. Meanwhile, if j is odd, let j' = ⌊ j/2⌋. There exist at least 2^(j+1)/2 paths in the B&B tree from the root to nodes of depth j such that if J is the set indices branched on along a given path, then J = {x_i-j', x_i-j'+1, …, x_i+j'}. Moreover, the number of variables set to 0 in J equals the number of variables set to 1, plus or minus 1.



  
Base case. To prove the base case, we need to show that B&B first branches on x_i. We saw that this will be the case in Lemma <ref> so long as μ < μ^*.



  
Inductive step. Let j be an arbitrary integer between 1 and i-3. There are two cases, one where j is even and one where j is odd. First, suppose j is even. From the inductive hypothesis, we know that there exist at least 2^j/2 paths in the B&B tree from the root to nodes of depth j such that if J is the set varibles branched on along a given path, then J = {x_i-j/2, x_i-j/2+1, …, x_i+j/2-1} or J = {x_i-j/2 + 1, x_i-j/2+2, …, x_i+j/2}. Moreover, the number of variables set to 0 in J equals the number of variables set to 1. From Claim <ref>, we know that in the first case, x_i+j/2 will be the next node B&B will branch on. This will create two new paths: {x_i-j/2, x_i-j/2+1, …, x_i+j/2} will be the set of variables branched along each path, and the number of variables set to 0 will equal the number of variables set to 1, plus or minus 1. Also from Claim <ref>, we know that in the second case, x_i-j/2 will be the next node B&B will branch on. This will also create two new paths: {x_i-j/2, x_i-j/2+1, …, x_i+j/2} will be the set of variables branched along each path, and the number of variables set to 0 will equal the number of variables set to 1, plus or minus 1. Since this is true for all 2^j/2 paths, this leads to a total of 2^j/2 + 1 = 2^(j+2)/2 paths, meaning the inductive hypothesis holds.

Next, suppose j is odd and let j' = ⌊ j/2⌋. From the inductive hypothesis, we know that there exist at least 2^(j+1)/2 paths in the B&B tree from the root to nodes of depth j such that if J is the set variables branched on along a given path, then J = {x_i-j', x_i-j'+1, …, x_i+j'}. Moreover, the number of variables set to 0 in J equals the number of variables set to 1, plus or minus 1. From Claim <ref>, we know that B&B will either branch on x_i-j' - 1 or x_i+j'+1. Suppose the number of variables set to 0 in J is 1 greater than the number of variables set to 1. If B&B branches on x_i-j' - 1, we can follow the path where x_i-j' - 1 = 1, and this will give us a new path where 
    {x_i-j' - 1, x_i-j', …, x_i+j'} = {x_i-(j + 1)/2, x_i-(j + 1)/2+1, …, x_i+(j + 1)/2 - 1}
 are the variables branched on and the number of variables set to 0 equals the number of variables set to 1. If B&B branches on x_i+j'+1, we can follow the path where x_i+j'+1 = 1, and this will give us a new path where 
    {x_i-j', x_i-j' + 1, …, x_i+j', x_i+j'+1} = {x_i-(j + 1)/2 +1, x_i-(j + 1)/2+1, …, x_i+(j + 1)/2}
 are the variables branched on and the number of variables set to 0 equals the number of variables set to 1. A symmetric argument holds if the number of variables set to 0 in J is 1 less than the number of variables set to 1. Therefore, all 2^(j+1)/2 paths can be extended by one edge, so the statement holds.




Let Q be an infeasible MILP, let NSP and NSP' be two node selection policies, and let  be a path-wise scoring rule. The tree  B&B builds using NSP and  equals the tree ' it builds using NSP' and .



For a contradiction, suppose ≠'. There must be a node Q_0 in  where if _Q_0 is the path from the root of  to Q_0, then _Q_0 is a rooted subtree of ', but either:


  * In , the node Q_0 is fathomed but in ', Q_0 is not fathomed, or

  * In , the node Q_0 is not fathomed, but for all children Q_0' of Q_0 in , if _Q_0' is the path from the root of  to Q_0', _Q_0' is not a rooted subtree of '.

We will show that neither case is possible, thus arriving at a contradiction. First, we know that since Q is infeasible, B&B will only fathom a node if it is infeasible. Therefore, the first case is impossible: if Q_0 is fathomed in , it must be infeasible, so it will also be fathomed in ', and vice versa. Therefore, we know that B&B must branch on Q_0 in both  and '. Let  be the state of the tree B&B has built using NSP and  by the time it branches on Q_0 and let ' be the state of the tree B&B has built using NSP' and  by the time it branches on Q_0. Since _Q_0 is a rooted subtree of both  and '̅, we know that for all variables x_i, (, Q_0, i) = (_Q, Q_0, i) = (', Q_0, i). Therefore, B&B will branch on the same variable in both  and ', which is a contradiction, since this means that for all children Q_0' of Q_0 in , if _Q_0' is the path from the root of  to Q_0', _Q_0' is a rooted subtree of '.



Let a ≥ 1 and b > 0. Then x < alog x + b implies that x < 4a log (2a) + 2b.


*
We prove this claim by induction.

Inductive hypothesis. For i ∈{1,…, n}, there are T ≤ 2^i(i-1)/2n^i intervals I_1, …, I_T partitioning [0,1] where for any interval I_j and any two parameters μ, μ' ∈ I_j, if  and ' are the trees A' builds using the scoring rules μ_1 + (1-μ)_2 and μ'_1 + (1-μ')_2, respectively, then [i] = '[i].



Base case. Before branching on any variables, the branch-and-bound tree _0 consists of a single root node Q. Given a parameter μ, A' will branch on variable x_k so long as 
    k = _ℓ∈ [n]{μ_1(_0, Q, ℓ) + (1-μ)_2(_0, Q, ℓ)}.

Since μ_1(_0, Q, ℓ) + (1-μ)_2(_0, Q, ℓ) is a linear function of μ for each ℓ∈ [n], we know that for any k ∈ [n], there is at most one interval I of the parameter space [0,1]
where k = _ℓ∈ [n]{μ_1 + (1-μ)_2}. Thus, there are T ≤ n = 2^1·(1-1)/2n^1 intervals I_1, …, I_T partitioning [0,1] where for any interval I_j, A' branches on the same variable at the root node using the scoring rule μ_1 + (1-μ)_2 across all μ∈ I_j.



Inductive step. Let i ∈{2, …, n} be arbitrary. From the inductive hypothesis, we know that there are T ≤ 2^(i-2)(i-1)/2n^i-1 intervals I_1, …, I_T partitioning [0,1] where for any interval I_j and any two parameters μ, μ' ∈ I_j, if  and ' are the trees A' builds using the scoring rules μ_1 + (1-μ)_2 and μ'_1 + (1-μ')_2, respectively, then [i-1] = '[i-1]. Consider an arbitrary node  in [i-1] (or equivalently, '[i-1]) at depth i-1. If Q is integral or infeasible, then it will be fathomed no matter which parameter μ∈ I_j the algorithm A' uses. Otherwise, for all μ∈ I_j, let _μ be the state of the search tree A' builds using the scoring rule μ_1 + (1-μ)_2 at the point when it branches on Q. By the inductive hypothesis, we know that across all μ∈ I_j, the path from the root to Q in _μ is invariant, and we refer to this path as _Q. Given a parameter μ∈ I_j, the variable x_k will be branched on at node  so long as k= _ℓ{μ_1(_μ,,ℓ) + (1-μ)_2(_μ,,ℓ)}, or equivalently, so long as k= _ℓ{μ_1(_Q,,ℓ) + (1-μ)_2(_Q,,ℓ)}. In other words, the decision of which variable to branch on is determined by a convex combination of the constant values _1(_Q,,ℓ) and _2(_Q,,ℓ) no matter which parameter μ∈ I_j the algorithm A' uses. Here, we critically use the fact that the scoring rule is path-wise.

Since μ_1(_Q,,ℓ) + (1-μ)_2(_Q,,ℓ) is a linear function of μ for all ℓ, there are at most n intervals subdividing the interval I_j such that the variable branched on at node  is fixed. Moreover, there are at most 2^i-1 nodes at depth i-1, and each node similarly contributes a subpartition of I_j of size n. If we merge all 2^i-1 partitions, we have T' ≤ 2^i-1(n-1)+1 intervals I_1', …, I_T'' partitioning I_j where for any interval I_p' and any two parameters μ, μ' ∈ I_p', if  and ' are the trees A' builds using the scoring rules μ_1 + (1-μ)_2 and μ'_1 + (1-μ')_2, respectively, then [i] = '[i]. We can similarly subdivide each interval I_1, …, I_T for a total of 
    T̅≤ 2^(i-1)(i-2)/2n^i-1(2^i-1(n-1)+1) ≤ 2^(i-1)(i-2)/2n^i-1(2^i-1n) = 2^i(i-1)/2n^i
 intervals I̅_1, …, I̅_T̅ partitioning [0,1] such that for any interval I̅_t, across all μ∈I̅_t and any two parameters μ, μ' ∈I̅_t, if  and ' are the trees A' builds using the scoring rules μ_1 + (1-μ)_2 and μ'_1 + (1-μ')_2, respectively, then [i] = '[i].




 §.§ Empirical Risk Minimization Algorithm
 

In this section we describe an empirical risk minimization algorithm capable of
finding the best mixture of two variable selection scoring rules for a given set
of problem instances Π^(1), …, Π^(m). We modify the tree search
algorithm so that given a problem instance Π and a mixing paramter μ∈
[0,1], the search algorithm keeps track of the largest interval I ⊂
[0,1] such that the behavior of the algorithm is identical to the current run
when run with any parameter μ' ∈ I. With this, we can enumerate all
possible behaviors of the algorithm for a single instance Π by running the
algorithm with μ = 0, followed by the smallest value of μ that will give
a different outcome, and so on, until we have covered the entire interval
[0,1]. This procedure results in running the tree search algorithm on the
instance Π exactly once for each possible behavior achievable across all
values of the parameter μ∈ [0,1]. By applying this algorithm to each
problem Π^(i) for i = 1, …, m, we discover how the tree search
algorithm would perform on every instance for any value of the mixing parameter
μ. This allows us to divide the interval [0,1] into a finite number of
intervals on which  is piecewise constant, and to compute the cost on
each interval.

To see why this additional book keeping is possible, suppose we are choosing
which variable to branch on in node  of tree . We have two scoring
rules _1 and _2 that each rank the candidate variables in
, and when we run the algorithm with parameter μ, we combine these
two scores as (1-μ)_1(, , i) + μ_2(, ,
i). For any parameter μ which results in the same variable having the
highest score, the variable chosen for branching in this node will be identical.
Let i^* be the variable chosen by the algorithm when run with parameter μ.
The set of all μ' for which i^* is the variable of the highest score is an
interval (and its end points can be found by solving a linear equation to
determine the value of μ' for which some other variable overtakes i^*
under the mixed score). Also, for every parameter μ' outside of
this interval, the algorithm would indeed branch on a different node, resulting
in a different outcome of the tree search algorithm. By taking the intersections
of these intervals across all branching variable choices, we find the largest
subset of [0,1] for which the algorithm would behave exactly the same, and
this subset is an interval. The overhead of this book keeping is only linear in
the number of candidate branch variables.

Psuedo-code for the ERM algorithm is given in Algorithm <ref>.





§ ADDITIONAL INFORMATION ABOUT EXPERIMENTS




  
Facility location.
Suppose there is a set I of customers
and a set J of facilities that have not yet been built. The facilities each
produce the same good, and each consumer demands one unit of that good. Consumer
i can obtain some fraction y_ij of the good from facility j, which costs
them d_ijy_ij. Moreover, it costs f_j to construct facility j. The
goal is to choose a subset of facilities to construct while minimizing total
cost. We can model this
problem as a MILP by assigning a binary variable x_j to each facility, which
represents whether or not it is built. The optimization is then over the
variables x_j and y_ij, as follows.

    [                                 minimize ∑_j ∈ J f_jx_j + ∑_j ∈ J, i ∈ I d_ijy_ij;                                     s.t.                         ∑_j ∈ J y_ij = 1                                  ∀ i ∈ I;                                                                         y_ij≤ x_j                           ∀ i ∈ I, j ∈ J;                                                                        x_j ∈{0,1}                                  ∀ j ∈ J;                                                                       y_ij∈ [0,1]                          ∀ i ∈ I, j ∈ J. ]




  
Clustering. We can formulate k-means clustering as a MILP by
assigning a binary variable x_i to each point p_i where x_i = 1 if and
only if p_i is a center, as well as a binary variable y_ij for each pair
of points p_i and p_j, where y_ij = 1 if and only if p_j is a center
and p_j is the closest center to p_i. We want to solve the following
problem:

    [                        min ∑_i,j ∈ [n] d(p_i,p_j)y_ij;                       s.t.          ∑_i = 1^n x_i = k;                                    ∑_j = 1^n y_ij = 1                  ∀ i ∈ [n];                                             y_ij≤ x_j                ∀ i,j ∈ [n];                                            x_i ∈{0,1}                  ∀ i ∈ [n];                                            y_ij∈{0,1}               ∀ i,j ∈ [n]. ]




  
Agnostically learning linear separators. We can formulate this
problem as a MILP as follows. Let M > maxp⃗_i_1.

    [                    min          ∑_i = 1^n x_i;                   s.t. z_i ⟨p⃗_i, w⃗⟩ > -Mx_i              ∀ i ∈ [n];                                 w[i] ∈ [-1,1]              ∀ i ∈ [n];                                    x_i ∈{0,1}             ∀ i ∈ [n]. ]

Since | ⟨p⃗_i, w⃗⟩| < M, the
inequality z_i ⟨p⃗_i, w⃗⟩ > -Mx_i ensures
that if z_i ⟨p⃗_i, w⃗⟩ > 0, then x_i will
equal 0, but if z_i ⟨p⃗_i, w⃗⟩≤ 0, then
x_i must equal 1.[In practice, we implement this constraint by
enforcing that z_i ⟨p⃗_i, w⃗⟩≥ -Mx_i +
γ for some tiny γ > 0 since MILP solvers cannot enforce strict
inequalities.]


Let  be a tree-constant cost function, let _1 and _2 be two path-wise scoring rules, and let  be a set of m problem instances over n binary variables. Let 𝒞 be the set of functions {(·, μ_1 + (1-μ)_2) : μ∈ [0,1]}. Then 
    (𝒞) ≤κ√(1/m(n^2 + 2nlog n + 2log m)).



 To prove this theorem, we rely on Lemma <ref>, which tells us that for any problem instance Π∈, there are T ≤ 2^n(n-1)/2n^n intervals I_1, …, I_T partitioning [0,1] where for any interval I_j, across all μ∈ I_j, the scoring rule μ_1 + (1-μ)_2 results in the same search tree.
Theorem <ref> then follows from this lemma and Massart's lemma <cit.>, which tells us that for any class  of functions with range [0, c], if N= |()|, then () ≤ c √(2log N/m). Lemma <ref> allows us to apply Massart's lemma with N ≤|2^n^2/2n^nm| and c = κ, since so long as the search tree is fixed for all μ in an interval I, we know that (Π, μ_1 + (1-μ)_2) is constant for all μ∈ I.


§ TREE SEARCH



A tree search algorithm takes as input a tuple Π = (X, D, f, g), where X = {x_1, …, x_n} is a set of variables, D = {D_1, …, D_n} is a set of domains where D_i is the finite set of values variable x_i can take on, f: D_1×⋯× D_n →{0,1} is a feasibility function, and g:D_1×⋯× D_n → is an objective function (if the problem is a satisfiability problem, rather than an optimization problem, we set g to be the constant zero function). We use y⃗∈ (D_1 ∪{⊤}) ×⋯× (D_n ∪{⊤}) to denote a partial solution to the problem instance Π, where y[i] is an assignment of the variable x_i and if y[i] = ⊤, it means the variable x_i has not yet been assigned a value.

Tree search builds a tree of partial solutions to Π until it finds the optimal solution.
We define two fathoming functions tree search can use to prune branches of the search tree,  and . The function (Π, y⃗) ∈{, } takes as input an instance Π and a partial solution y⃗ and determines whether or not to fathom the node containing the partial solution y⃗. Its output is only based on the local information contained in the partial solution y⃗, not the remainder of the search tree.
For example, in MIP, (Π, y⃗) = if the LP relaxation of the MIP given the partial solution y⃗ is integral or infeasible.
 The function (Π, y⃗, ) ∈{, } takes as input an instance Π, a partial solution y⃗, and a partial search tree  and determines whether or not to fathom the node in  containing the partial solution y⃗.
 For example, in MIP, the function  covers the case where a node is fathomed because LP relaxation's objective value given the partial solution contained in that node is no better than the objective value evaluated on the best known integral solution. In a bit more detail, suppose there is a fathomed leaf node in  containing a partial solution y⃗^* such that the LP relaxation of the MIP given the partial solution y⃗^* is integral, and let c^* be the objective value. Let c be the objective value of the LP relaxation of the MIP given the partial solution y⃗. We know that (Π, y⃗, ) = if c ≤ c^*.

See Algorithm <ref> for the tree search pseudo-code.



 §.§ Problem statement

The problem statement for general tree search is nearly identical to that in Section <ref>. We state it hear for clarity's sake.

Let  be a distribution over problem instances Π. Let _1, …, _d be a set of variable selection scoring rules, such as those in Section <ref>. Our goal is to learn a convex combination μ_1_1+ ⋯ + μ_d_d of the scoring rules that is nearly optimal in expectation over . More formally, let  be an abstract cost function that takes as input a problem instance Π and a scoring rule  and returns some measure of the quality of tree search using  on input Π.

We say that an algorithm (ϵ, δ)-learns a convex combination of the
d scoring rules _1, …, _d if for any distribution ,
with probability at least 1-δ over the draw of a sample
{Π_1, …, Π_m}∼^m, the algorithm returns
a convex combination = μ̂_1_1+ ⋯ +
μ̂_d_d such that _Π∼[(Π,
)] - _Π∼[(Π, ^*)] ≤ϵ, where ^* is the convex combination of _1, …,
_d with minimal expected cost. In this work, we prove that only a small
number of samples is sufficient to ensure (ϵ, δ)-learnability.

We assume that the problem instances in the support of  are over n D-ary variables, for some n, D ∈.[A variable is D-ary if it can take on at most D distinct values.]

Our results hold for cost functions that are tree-constant, which means that for any problem instance Π, so long as the scoring rules _1 and _2 result in the same search tree, (Π, _1) = (Π, _2).
For example, the size of the search tree is tree-constant.



 §.§ Path-wise scoring rules

We now slightly tweak the definition of score-based variable selection policies and path-wise scoring rules so that they apply to tree search more generally. The only difference is that a scoring rule will now be defined in terms of a partial solution, rather than a MILP.


Let  be a function that takes as input a partial search tree , a partial solution y⃗ contained in a leaf of , and an index i and returns a real value ((, Q, i) ∈). For a partial solution y⃗ contained in a leaf of a tree , let N_, y⃗ be the set of variables that have not yet been branched on along the path from the root of  to the leaf. A score-based variable selection policy selects the variable _x_j ∈ N_, y⃗{(, y⃗, j)} to branch on at the node Q.



Suppose y⃗ is a partial solution contained in the node of a search tree . We say that (, y⃗, i) is a path-wise scoring rule if the value of (, y⃗, i) depends only on the node , the variable x_i, and the path from the root of  to the node containing y⃗, which we denote as _y⃗. Specifically, (, y⃗, i) = (_y⃗, y⃗, i).


The following lemma parallels Lemma <ref>.


Let  be a tree-constant cost function, let _1 and _2 be two path-wise scoring rules, and let Π be an arbitrary problem instance over n D-ary variables. There are T ≤ D^n(n-1)/2n^n intervals I_1, …, I_T partitioning [0,1] where for any interval I_j, across all μ∈ I_j, the scoring rule μ_1 + (1-μ)_2 results in the same search tree.



We prove this lemma first by considering the actions of an alternative algorithm TS' which runs exactly like Algorithm <ref> except it does not use the function , but rather skips Steps <ref> and <ref> of Algorithm <ref>. We then relate the behavior of TS' to the behavior of Algorithm <ref> to prove the lemma.

First, we prove the following bound on the number of search trees TS' will build on a given instance over the entire range of parameters. Note that this bound matches that in the lemma statement.

claimclaimIntervals
There are T ≤ D^n(n-1)/2n^n intervals I_1, …, I_T partitioning [0,1] where for any interval I_j, the search tree TS' builds using the scoring rule μ_1 + (1-μ)_2 is invariant across all μ∈ I_j.


We prove this claim by induction.

Inductive hypothesis. For i ∈{1,…, n}, there are T ≤ D^i(i-1)/2n^i intervals I_1, …, I_T partitioning [0,1] where for any interval I_j and any two parameters μ, μ' ∈ I_j, if  and ' are the trees TS' builds using the scoring rules μ_1 + (1-μ)_2 and μ'_1 + (1-μ')_2, respectively, then [i] = '[i].



Base case. Before branching on any variables, the seasrch tree _0 consists of a single root node containing the empty partial solution y⃗ = (⊤, …, ⊤). Given a parameter μ, TS' will branch on variable x_k so long as 
    k = _ℓ∈ [n]{μ_1(_0, y⃗, ℓ) + (1-μ)_2(_0, y⃗, ℓ)}.

Since μ_1(_0, y⃗, ℓ) + (1-μ)_2(_0, y⃗, ℓ) is a linear function of μ for each ℓ∈ [n], we know that for any k ∈ [n], there is at most one interval I of the parameter space [0,1]
where k = _ℓ∈ [n]{μ_1 + (1-μ)_2}. Thus, there are T ≤ n = D^1·(1-1)/2n^1 intervals I_1, …, I_T partitioning [0,1] where for any interval I_j, TS' branches on the same variable at the root node using the scoring rule μ_1 + (1-μ)_2 across all μ∈ I_j.



Inductive step. Let i ∈{2, …, n} be arbitrary. From the inductive hypothesis, we know that there are T ≤ D^(i-2)(i-1)/2n^i-1 intervals I_1, …, I_T partitioning [0,1] where for any interval I_j and any two parameters μ, μ' ∈ I_j, if  and ' are the trees TS' builds using the scoring rules μ_1 + (1-μ)_2 and μ'_1 + (1-μ')_2, respectively, then [i-1] = '[i-1]. Consider an arbitrary node containing a partial solution y⃗ in [i-1] (or equivalently, '[i-1]) at depth i-1. If (Π, y⃗) =, then it will be fathomed no matter which parameter μ∈ I_j the algorithm TS' uses. Otherwise, for all μ∈ I_j, let _μ be the state of the search tree TS' builds using the scoring rule μ_1 + (1-μ)_2 at the point when it branches on the node containing y⃗. By the inductive hypothesis, we know that across all μ∈ I_j, the path from the root to this node in _μ is invariant, and we refer to this path as _y⃗. Given a parameter μ∈ I_j, the variable x_k will be branched on at this node so long as k= _ℓ{μ_1(_μ,y⃗,ℓ) + (1-μ)_2(_μ,y⃗,ℓ)}, or equivalently, so long as k= _ℓ{μ_1(_y⃗,y⃗,ℓ) + (1-μ)_2(_y⃗,y⃗,ℓ)}. In other words, the decision of which variable to branch on is determined by a convex combination of the constant values _1(_y⃗,y⃗,ℓ) and _2(_y⃗,y⃗,ℓ) no matter which parameter μ∈ I_j the algorithm TS' uses. Here, we critically use the fact that the scoring rule is path-wise.

Since μ_1(_y⃗,y⃗,ℓ) + (1-μ)_2(_y⃗,y⃗,ℓ) is a linear function of μ for all ℓ, there are at most n intervals subdividing the interval I_j such that the variable branched on at the node containing y⃗ is fixed. Moreover, there are at most D^i-1 nodes at depth i-1, and each node similarly contributes a subpartition of I_j of size n. If we merge all D^i-1 partitions, we have T' ≤ D^i-1(n-1)+1 intervals I_1', …, I_T'' partitioning I_j where for any interval I_p' and any two parameters μ, μ' ∈ I_p', if  and ' are the trees TS' builds using the scoring rules μ_1 + (1-μ)_2 and μ'_1 + (1-μ')_2, respectively, then [i] = '[i]. We can similarly subdivide each interval I_1, …, I_T for a total of 
    T̅≤ D^(i-1)(i-2)/2n^i-1(D^i-1(n-1)+1) ≤ D^(i-1)(i-2)/2n^i-1(D^i-1n) = D^i(i-1)/2n^i
 intervals I̅_1, …, I̅_T̅ partitioning [0,1] such that for any interval I̅_t, across all μ∈I̅_t and any two parameters μ, μ' ∈I̅_t, if  and ' are the trees TS' builds using the scoring rules μ_1 + (1-μ)_2 and μ'_1 + (1-μ')_2, respectively, then [i] = '[i].


Next, we explicitly relate the behavior of Algorithm <ref> to TS', proving that the search tree Algorithm <ref> builds is a rooted subtree of the search tree TS' builds.


Given a parameter μ∈ [0,1], let  and ' be the trees Algorithm <ref> and TS' build, respectively, using the scoring rule μ_1 + (1-μ)_2. For an arbitrary node of , let y⃗ be the partial solution contained in that node and let _y⃗ be the path from the root of  to the node. Then _y⃗ is a rooted subtree of '.



Note that the path _y⃗ can be labeled by a sequence of indices from {1, …, D} and a sequence of variables from {x_1, …, x_n} describing which variable is branched on and which value it takes on along the path _y⃗. Let ((j_1, x_i_1), …, (j_t, x_i_t)) be this sequence of labels, where t is the number of edges in _y⃗. We can similarly label every edge in '. We claim that there exists a path beginning at the root of ' with the labels ((j_1, x_i_1), …, (j_t, x_i_t)).

For a contradiction, suppose no such path exists. Let (j_τ, x_i_τ) be the earliest label in the sequence ((j_1, x_i_1), …, (j_t, x_i_t)) where there is a path beginning at the root of ' with the labels ((j_1, x_i_1), …, (j_τ-1, x_i_τ - 1)), but there is no way to continue the path using an edge labeled (j_τ, x_i_τ). There are exactly two reasons why this could be the case:


  * The node at the end of the path with labels ((j_1, x_i_1), …, (j_τ-1, x_i_τ - 1)) was fathomed by TS'.

  * The algorithm TS' branched on a variable other than x_i_τ at the end of the path labeled ((j_1, x_i_1), …, (j_τ-1, x_i_τ - 1)).


Let y⃗' be the partial solution contained in the node at the end of the path with labels 
    ((j_1, x_i_1), …, (j_τ-1, x_i_τ - 1)).
 We refer to this path as _y⃗'.
In the first case, since TS' only fathoms the node containing the partial solution y⃗' if (Π, y⃗') =, we know that Algorithm <ref> will also fathom this node. However, this is not the case since Algorithm <ref> next branches on the variable x_i_τ.

The second case is also not possible since the scoring rules are both path-wise. Let  (respectively, ') be the state of the search tree Algorithm <ref> (respectively, A') has built at the point it branches on the node containing y⃗'. We know that _y⃗' is the path from the root this node in both of the trees  and '. Therefore, for all variables x_k, μ_1(, y⃗', k) + (1-μ)_2(, y⃗', k) = μ_1(_y⃗', y⃗', k) + (1-μ)_2(_y⃗', y⃗', k) = μ_1(', y⃗', k) + (1-μ)_2(', y⃗', k). This means that Algorithm <ref> and TS' will choose the same variable to branch on at the node containing the partial solution y⃗'.

 Therefore, we have reached a contradiction, so the claim holds.


Next, we use Claims <ref> and <ref> to prove Lemma <ref>. Let I_1, …, I_T be one of the interval guaranteed to exist by Claim <ref> and let I_t be an arbitrary one of the intervals. Let μ' and μ” be two arbitrary parameters from I_t. We will prove that the scoring rules μ'_1 + (1-μ')_2 and μ”_1 + (1-μ”)_2 result in the same search tree. For a contradiction, suppose that this is not the case. 
Consider the first iteration where of Algorithm <ref> using the scoring rule μ'_1 + (1-μ')_2 differs from Algorithm <ref> using the scoring rule μ”_1 + (1-μ”)_2, where
  an iteration corresponds to lines <ref> through <ref> of Algorithm <ref>. Up until this iteration, Algorithm <ref> has built the same partial search tree . Since the node selection policy does not depend on μ' or μ”, Algorithm <ref> will choose the same leaf of the search tree to branch on no matter which scoring rule it uses. Let y⃗ be the partial solution contained in this leaf.

Suppose Algorithm <ref> chooses different variables to branch on depending on the scoring rule. Let _y⃗ be the path from the root of  to the node containing the partial solution y⃗. By Claim <ref>, we know that the algorithm TS' builds the same search tree using the two scoring rules. Let ' (respectively, ”) be the state of the search tree TS' has built using the scoring rule μ'_1 + (1-μ')_2 (respectively, μ”_1 + (1-μ”)_2) by the time it branches on the node containing the partial solution y⃗. By Claims <ref> and <ref>, we know that _y⃗ is the path of from the root to the node containing the partial solution y⃗ of both ' and ”. By Claim <ref>,
we know that TS' will branch on the same variable x_i at this node in both the trees ' and ”, so i = _j{μ'_1(', y⃗, j)  + (1-μ')_2(', y⃗, j)}, or equivalently, 
    i = _j{μ'_1(_y⃗, y⃗, j)  + (1-μ')_2(_y⃗, y⃗, j)},
 and i = _j{μ”_1(”, y⃗, j)  + (1-μ”)_2(”, y⃗, j)}, or equivalently, 
    i = _j{μ”_1(_y⃗, y⃗, j)  + (1-μ”)_2(_y⃗, y⃗, j)}.
 Returning to the search tree  that Algorithm <ref> is building, Equation (<ref>) implies that 
    i = _j{μ'_1(, y⃗, j)  + (1-μ')_2(, y⃗, j)}
 and Equation (<ref>) implies that i = _j{μ”_1(, y⃗, j)  + (1-μ”)_2(, y⃗, j)}.
Therefore, Algorithm <ref> will branch on x_i at the node containing the partial solution y⃗ no matter which scoring rule it uses.

Finally, since  and  do not depend on the parameter μ, whether or not Algorithm <ref> fathoms any of the nodes in Steps <ref> through <ref> does not depend on μ' or μ”.

We have reached a contradiction by showing that the two iterations of Algorithm <ref> are identical. Therefore, the lemma holds.




  §.§.§ General scoring rules


In this section, we provide generalization guarantees that apply to learning convex combinations of any set of scoring rules, as in Section <ref>. The following lemma corresponds to Lemma <ref> for this setting.


Let  be a tree-constant cost function, let _1, …, _d be d arbitrary scoring rules, and let Π be an arbitrary problem instance over n D-ary variables. Suppose we limit Algorithm <ref> to producing search trees of
  size κ̅. There is a set ℋ of at most n^2(κ̅ + 1) hyperplanes such that for any connected component R of [0,1]^d ∖ℋ, the search tree Algorithm <ref> builds using the scoring rule μ_1_1 + ⋯ + μ_d_d is invariant across all (μ_1, …, μ_d) ∈ R.



  
  The proof has two steps. In Claim <ref>, we show that there are at most n^κ̅
  different search trees that Algorithm <ref> might produce for the instance Π as we
  vary the mixing parameter vector (μ_1, …, μ_d). In Claim <ref>, for each of the possible search trees
  𝒯 that might be produced, we show that the set of parameter values
  (μ_1, …, μ_d) which give rise to that tree lie in the intersection of n^κ̅ + 2 halfspaces. These facts together prove
  the lemma.
  
  
  There are only n^κ̅ different search trees that can
  be achieved by varying the parameter vector (μ_1, …, μ_d).
  


Fix any d mixing parameters (μ_1, …, μ_d) and
  let v_1, …, v_κ̅∈ [n] be the sequence of branching variables
  chosen by Algorithm <ref> run with scoring rule μ_1_1 + ⋯ + μ_d_d, ignoring which node of
  the tree each variable was chosen for. That is, v_1 is the variable branched
  on at the root, v_2 is the variable branched on at the next unfathomed node
  chosen by the node selection policy, and so on. If Algorithm <ref> with scoring rule
  μ_1_1 + ⋯ + μ_d_d produces a tree of size k < κ̅, then define v_t = 1 for
  all t ≥ k (we are just padding the sequence v_1, v_2, … so that it
  has length κ̅). We will show that whenever two sets of mixing parameters (μ_1, …, μ_d)
  and (μ_1', …, μ_d') give rise to the same sequence of branching variable selections,
  they in fact produce identical search trees. This will imply that the number
  of distinct trees that can be produced by Algorithm <ref> with scoring rules of the
  form μ_1_1 + ⋯ + μ_d_d is at most n^κ̅, since there are only n^κ̅
  distinct sequences of κ̅ variables v_1, …, v_κ̅∈ [n].

  Let (μ_1, …, μ_d)
  and (μ_1', …, μ_d') be two sets of mixing parameters, and suppose running Algorithm <ref> with
  μ_1_1 + ⋯ + μ_d_d and μ_1'_1 + ⋯ + μ_d'_d both results in the sequence of branching
  variable decisions being v_1, …, v_κ̅. We prove that the resulting
  search trees are identical by induction on the iterations of the algorithm, where
  an iteration corresponds to lines <ref> through <ref> of Algorithm <ref>. Our base case is before the first iteration when the two trees are trivially
  equal, since they both contain just the root node. Now suppose that up until
  the beginning of iteration t the two trees were identical. Since the two trees
  are identical, the node selection policy will choose the same node to branch
  on in both cases. In both trees, the
  algorithm will choose the same variable to branch on, since the sequence of
  branching variable choices v_1, …, v_κ̅ is shared. Finally, if any of the children are fathomed, they will be
  fathomed in both trees, since the they are identical. It follows that
  all steps of Algorithm <ref> maintain equality between the two trees, and the claim
  follows. Also, whenever the sequence of branching variables differ,
  then the search tree produced will not be the same. In particular, on the
  first iteration where the two sequences disagree, the tree built so far will be
  identical up to that point, but the next variable branched on will be
  different, leading to different trees.


  Next, we argue that for any given search tree 𝒯 produced by
  Algorithm <ref>, the set of mixing parameters (μ_1, …, μ_d) giving rise to 𝒯 is defined by the intersection of n^κ̅ + 2 halfspaces.


For a given search tree , there are at most n^κ̅ + 2 halfspaces such that Algorithm <ref> using the scoring rule μ_1_1 + ⋯ + μ_d_d builds the tree  if and only if (μ_1, …, μ_d) lies in the intersection of those halfspaces.
  
  
  
  Let v_1, …, v_κ̅ be the sequence of branching variable
  choices that gives rise to tree 𝒯. We will prove the claim by
  induction on iterations completed by Algorithm <ref>. Let _t be the state of Algorithm <ref> after t iterations.
  
  Induction hypothesis. For a given index t ∈ [κ̅], there are at most tn^2 halfspaces such that Algorithm <ref> using the scoring rule μ_1_1 + ⋯ + μ_d_d builds the partial tree _t after t iterations if and only if (μ_1, …, μ_d) lies in the intersection of those halfspaces.

Base case.
    In the base case, before
  the first iteration, the set of parameters that will produce the partial search
  tree consisting of just the root is the entire set of parameters, which vacuously is the intersection of zero hyperplanes.
  
  Inductive step.
  For the
  inductive step, let t < κ̅ be an arbitrary tree size. By the inductive
  hypothesis, we know that there exists a set ℬ of at most tn^2 halfspaces such that Algorithm <ref> using the scoring rule μ_1_1 + ⋯ + μ_d_d builds the partial tree _t after t iterations if and only if (μ_1, …, μ_d) lies in the intersection of those halfspaces. Let y⃗ be the partial solution contained in the next node that Algorithm <ref> will
  branch on given _t. We know that Algorithm <ref> will choose to branch on
  variable v_t+1 at node  if and only if
  
  
    μ_1_1(, y⃗,v_t+1) + ⋯ + μ_d_d(, y⃗,v_t+1)
    
      >    max_v' ≠ v_t+1{μ_1_1(, y⃗,v') + ⋯ + μ_d_d(, y⃗,v')}
      .

  
  Since these functions are linear in (μ_1, …, μ_d), there are at most n^2 halfspaces defining the region where v_t + 1 = {μ_1_1(, y⃗,v') + ⋯ + μ_d_d(, y⃗,v')}. Let ℬ' be this set of halfspaces. Algorithm <ref> using the scoring rule μ_1_1 + ⋯ + μ_d_d builds the partial tree _t after t iterations if and only if (μ_1, …, μ_d) lies in the intersection of the (t+1)n^2 halfspaces in the set ℬ∪ℬ'.
  



Let  be a tree-constant cost function and let _1, …, _d be d arbitrary scoring rules. Suppose we limit Algorithm <ref> to producing search trees of
  size κ̅. Let 𝒞 be the set of functions {(·, μ_1 + ⋯ + μ_d_d) : (μ_1, …, μ_d) ∈ [0,1]^d}. Then (𝒞) = O(dκ̅log n + dlog d).


 Suppose that (𝒞) = m and let = {Π_1, …, Π_m} be a shatterable set of problem instances. We know there exists a set of targets r_1, …, r_m ∈ that witness the shattering of  by 𝒞. This means that for every ' ⊆, there exists a parameter vector (μ_1,', …, μ_d, ') such that if Π_i ∈', then (Π_i, μ_1,'_1 + ⋯ + μ_d, '_d) ≤ r_i. Otherwise 
    (Π_i, μ_1,'_1 + ⋯ + μ_d, '_d) > r_i.
 Let M = {(μ_1,', …, μ_d, ') : ' ⊆}. We will prove that  |M| = O(dm^dn^2d(κ̅ + 1)), and since 2^m = |M|, this means that (𝒞) = m = O(dκ̅log n + dlog d) (see Lemma <ref> in Appendix <ref>).

To prove that |M| ≤ mn^κ̅ + 1, we rely on Lemma <ref>, which tells us that for any problem instance Π, there is a set ℋ of at most T ≤ n^2(κ̅ + 1) hyperplanes such that for any connected component R of [0,1]^d ∖ℋ, the search tree Algorithm <ref> builds using the scoring rule μ_1_1 + ⋯ + μ_d_d is invariant across all (μ_1, …, μ_d) ∈ R. If we merge all T hyperplanes for all samples in , we are left with a set ℋ' of T' ≤ mn^2(κ̅ + 1) hyperplanes where for any connected component R of [0,1]^d ∖ℋ' and any Π_i ∈, the search tree Algorithm <ref> builds using the scoring rule μ_1_1 + ⋯ + μ_d_d given as input Π_i is invariant across all (μ_1, …, μ_d) ∈ R. Therefore, at most one element of M can come from each connected component, of which there are O(d|ℋ'|^d) = O(dm^dn^2d(κ̅ + 1)). Therefore, |M| = O(dm^dn^2d(κ̅ + 1)), as claimed.


Naturally, if the function  measures the size of the search tree Algorithm <ref> returns capped at some value κ as described in Section <ref>, we obtain the following corollary.


Let  be a tree-constant cost function, let _1, …, _d be d arbitrary scoring rules, and let κ∈ be an arbitrary tree size bound. Suppose that for any problem instance Π, (Π, μ_1 + ⋯ + μ_d_d) equals the minimum of the following two values: 1) The number of nodes in the search tree Algorithm <ref> builds using the scoring rule μ_1 + ⋯ + μ_d_d on input Π; and 2) κ. For any distribution  over problem instances Π with at most n variables, with probability at least 1-δ over the drawn {Π^(1), …, Π^(m)}∼^m, for any μ∈ [0,1], 
    |_Π∼ [(Π, μ_1 + ⋯ + μ_d_d)] - 1/m∑_i = 1^m (Π^(i), μ_1 + ⋯ + μ_d_d)|
    
    =    O(√(dκ^2(κlog n + log d)/m) + κ√(ln(1/δ)/m)).



