Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning

Introduction

Algorithm designs for combinatorial optimization problems (COPs) are important and challenging tasks. A wide variety of real-world problems are COPs, such as vehicle routing (Toth & Vigo 2002), network design (Johnson et al. 1978), path planning (Pohl 1970) and mechanism design (De Vries & Vohra 2003) problems, and a majority of them are NP-hard to solve. In the past few decades, algorithms, including optimal algorithms, approximation algorithms and heuristic algorithms, have been studied extensively due to the importance of COPs. Those algorithms are mostly designed by human through costly processes that often require deep understanding of the problem domains and their underlying structures as well as considerable time and effort.

Recently, there has been an increased interest to automate algorithm designs for COPs with machine learning (ML). Many ML approaches learn to either construct or improve solutions within an algorithmic framework, such as greedy search, local search or tree search, for a specific COP, such as the traveling salesman problem (TSP) (Xin et al. 2021; Zheng et al. 2021), vehicle routing problem (VRP) (Kool et al. 2018) or independent set problem (Li et al. 2018), and are often not easily applicable to other COPs.

In contrast, Integer Linear Programs (ILPs) can flexibly encode and solve a broad family of COPs, such as minimum vertex cover, set covering and facility location problems. ILPs can be solved by Branch and Bound (BnB) (Land & Doig 2010), an optimal tree search algorithm that can achieve state-of-the-art for ILPs. Over the past decades, BnB has been improved tremendously to become the core of many popular ILP solvers such as SCIP (Bestuzheva et al. 2021), CPLEX (Cplex 2009) and Gurobi (Gurobi Optimization, LLC 2022). However, due to its exhaustive search nature, it is hard for BnB to scale to large instances (Khalil et al. 2016; Gasse et al. 2019).

On the other hand, Large Neighborhood Search (LNS) has recently been shown to find high quality solutions much faster than BnB for large ILP instances (Song et al. 2020; Wu et al. 2021; Sonnerat et al. 2021; Huang et al. 2022a). LNS starts from an initial solution (i.e., a feasible assignment of values to variables) and then improves the current best solution by iteratively picking a subset of variables to reoptimize while leaving others fixed. Picking which subset to reoptimize, i.e., the destroy heuristic, is a critical component in LNS. Hand-crafted destroy heuristics, such as the randomized heuristic (Song et al. 2020; Sonnerat et al. 2021) and the Local Branching (LB) heuristic (Fischetti & Lodi 2003), are often either inefficient (slow to find good subsets) or ineffective (find subsets of bad quality). ML-based destroy heuristics have also been proposed and outperform hand-crafted ones. State-of-the-art approaches include IL-LNS (Sonnerat et al. 2021) that uses imitation learning (IL) to imitates the LB heuristic and RL-LNS (Wu et al. 2021) that uses a similar framework to IL-LNS but trained with reinforcement learning (RL).

In this paper, we propose a novel ML-based LNS for ILPs, namely CL-LNS , that uses contrastive learning (CL) (Chen et al. 2020; Khosla et al. 2020) to learn efficient and effective destroy heuristics. Similar to IL-LNS (Sonnerat et al. 2021), we learn to imitate the Local Branching (LB) heuristic, a destroy heuristic that selects the optimal subset of variables within the Hamming ball of the incumbent solutions. LB requires solving another ILP with same size as the original problem and thus is computationally expensive. We not only use the optimal subsets provided by LB as the expert demonstration (as in IL-LNS), but also leverage intermediate solutions and perturbations. When solving the ILP for LB, intermediate solutions are found and those that are close to optimal in term of effectiveness become positive samples. We also collect negative samples by randomly perturbing the optimal subset. With both positive and negative samples, instead of a classification loss as in IL-LNS, we use a contrastive loss that encourages the model to predict the subset similar to the positive samples but dissimilar to the negative ones with similarity measured by dot products (Oord et al. 2018; He et al. 2020). Finally, we also use a richer set of features and use graph attention networks (GAT) instead of GCN, to further boost performance.

Empirically, we show that CL-LNS outperforms state-of-the-art ML and non-ML approaches at different runtime cutoffs ranging from a few minutes to an hour in terms of multiple metrics, including the primal gap, the primal integral, the best performing rate and the survival rate, demonstrating the effectiveness and efficiency of CL-LNS. In addition, CL-LNS shows great generalization performance on test instances two times larger than training instances.

Background

In this section, we first define ILPs and then introduce LNS for ILP solving and the Local Branching (LB) heuristic.

An integer linear program (ILP) is defined as

2 LNS for ILP solving

LNS is a heuristic algorithm that starts with an initial solution and then iteratively destroys and reoptimizes a part of the solution until a runtime limit is exceeded or some stopping condition is met. Let $\mathcal{I}=(\boldsymbol{A},\boldsymbol{b},\boldsymbol{c})$ be the input ILP, where $\boldsymbol{A},\boldsymbol{b}$ and $\boldsymbol{c}$ are the coefficients defined in Equation (1), and $\boldsymbol{x}^{0}$ be the initial solution (typically found by running BnB for a short runtime). In iteration $t\geq 0$ of LNS, given the incumbent solution $\boldsymbol{x}^{t}$, defined as the best solution found so far, a destroy heuristic selects a subset of $k^{t}$ variables $\mathcal{X}^{t}=\{x_{i_{1}},\ldots,x_{i_{k^{t}}}\}$. The reoptimization is done by solving a sub-ILP with $\mathcal{X}^{t}$ being the variables while fixing the values of $x_{j}\notin\mathcal{X}^{t}$ the same as in $\boldsymbol{x}^{t}$. The solution to the sub-ILP is the new incumbent solution $\boldsymbol{x}^{t+1}$ and then LNS proceeds to iteration $t+1$. Compared to BnB, LNS is more effective in improving the objective value $\boldsymbol{c}^{\mathsf{T}}x$ especially on difficult instances (Song et al. 2020; Sonnerat et al. 2021; Wu et al. 2021). Compared to other local search methods, LNS explores a large neighborhood in each step and thus, is more effective in avoiding local minima.

Adaptive methods are commonly used to set the neighborhood size $k^{t}$ in previous work (Sonnerat et al. 2021; Huang et al. 2022a). The initial neighborhood size $k^{0}$ is set to a constant or a fraction of the number of variables. In this paper, we consider the following adaptive method (Huang et al. 2022a): in iteration $t$, if LNS finds an improved solution, we let $k^{t+1}=k^{t}$, otherwise $k^{t+1}=\min\{\gamma\cdot k^{t},\beta\cdot n\}$ where $\gamma>1$ is a constant and we upper bound $k^{t}$ to a constant fraction $\beta<1$ of the number of variables to make sure the sub-ILP is not too large (thus, too difficult) to solve. Adaptively setting $k^{t}$ helps LNS escape local minima by expanding the search neighborhood when it fails to improve the solution.

3 LB Heuristic

The LB Heuristic (Fischetti & Lodi 2003) is originally proposed as a primal heuristic in BnB but also applicable in LNS for ILP solving (Sonnerat et al. 2021; Liu et al. 2022). Given the incumbent solution $\boldsymbol{x}^{t}$ in iteration $t$ of LNS, LB aims to find the subset of variables to destroy $\mathcal{X}^{t}$ such that it leads to the optimal $\boldsymbol{x}^{t+1}$ that differs from $\boldsymbol{x}^{t}$ on at most $k^{t}$ variables, i.e., it computes the optimal solution $\boldsymbol{x}^{t+1}$ that sits within a given Hamming ball of radius $k^{t}$ centered around $\boldsymbol{x}^{t}$. To find $\boldsymbol{x}^{t+1}$, the LB heuristic solves the LB ILP that is exactly the same ILP from input but with one additional constraint that limits the distance between $\boldsymbol{x}^{t}$ and $\boldsymbol{x}^{t+1}$: $\sum_{i\in[n]:x^{t}_{i}=0}x^{t+1}_{i}+\sum_{i\in[n]:x^{t}_{i}=1}(1-x^{t+1}_{i})\leq k^{t}.$ The LB ILP is of the same size of the input ILP (i.e., it has the same number of variables and one more constraint), therefore, it is often too slow to be useful in practice.

Related Work

In this section, we summarize related work on LNS for ILPs and other COPs, learning to solve ILPs with BnB and contrastive learning for COPs. We also summarize additional related work on LNS-based primal heuristics for BnB and learning to solve other COPs in Appendix.

Huge effort has been made to improve BnB for ILPs in the past decades, but LNS for ILPs has not been studied extensively. Recently, Song et al. 2020 show that even a randomized destroy heuristic in LNS can outperform state-of-the-art BnB. They also show that an ML-guided decomposition-based LNS can achieve even better performance, where they apply RL and IL to learn destroy heuristics that decompose the set of variables into equally-sized subsets using a classification loss. Sonnerat et al. 2021 learn to select variables by imitating LB. RL-LNS (Wu et al. 2021) uses a similar framework but trained with RL and outperforms Song et al. 2020. Both Wu et al. 2021 and Sonnerat et al. 2021 use the bipartite graph representations of ILPs to learn the destroy heuristics represented by GCNs. Another line of related work focuses on improving LB. Liu et al. 2022 use ML to tune the runtime limit and neighborhood sizes for LB. Huang et al. 2022a propose LB-RELAX to select variables by solving the LP relaxation of LB.

Besides ILPs, LNS has been applied to solve many COPs, such as VRP (Ropke & Pisinger 2006; Azi et al. 2014), TSP (Smith & Imeson 2017), scheduling (Kovacs et al. 2012; Žulj et al. 2018) and path planning problems (Li et al. 2022; Li et al. 2021a). ML methods have also been applied to improve LNS for those applications (Chen & Tian 2019; Lu et al. 2019; Hottung & Tierney 2020; Li et al. 2021b; Huang et al. 2022b).

2 Learning to Solve ILPs with BnB

Several studies have applied ML to improve BnB. The majority of works focus on learning to either select variables to branch on (Khalil et al. 2016; Gasse et al. 2019; Gupta et al. 2020; Zarpellon et al. 2021) or select nodes to expand (He et al. 2014; Labassi et al. 2022). There are also works on learning to schedule and run primal heuristics (Khalil et al. 2017; Chmiela et al. 2021) and to select cutting planes (Tang et al. 2020; Paulus et al. 2022; Huang et al. 2022c).

3 Contrastive Learning for COPs

While contrastive learning of visual representations (Hjelm et al. 2019; He et al. 2020; Chen et al. 2020) and graph representations (You et al. 2020; Tong et al. 2021) have been studied extensively, it has not been explored much for COPs. Mulamba et al. 2021 derive a contrastive loss for decision-focused learning to solve COPs with uncertain inputs that can be learned from historical data, where they view non-optimal solutions as negative samples. Duan et al. 2022 use contrastive pre-training to learn good representations for the boolean satisfiability problem.

Contrastive Learning for LNS

Our goal is to learn a policy, a destroy heuristic represented by an ML model, that selects a subset of variables to destroy and reoptimize in each LNS iteration. Specifically, let $\boldsymbol{s}^{t}=(\mathcal{I},\boldsymbol{x}^{t})$ be the current state in iteration $t$ of LNS where $\mathcal{I}=(\boldsymbol{A},\boldsymbol{b},\boldsymbol{c})$ is the ILP and $\boldsymbol{x}^{t}$ is the incumbent solution, the policy predicts an action $\boldsymbol{a}^{t}=(a_{1}^{t},\ldots,a_{n}^{t})\in\{0,1\}^{n}$, a binary representation of the selected variables $\mathcal{X}^{t}$ indicating whether $x_{i}$ is selected ($a^{t}_{i}=1$) or not ($a^{t}_{i}=0$). We use contrastive learning to learn to predict high quality $\boldsymbol{a}^{t}$ such that, after solving the sub-ILP derived from $\boldsymbol{a}^{t}$ (or $\mathcal{X}^{t}$), the resulting incumbent solution $\boldsymbol{x}^{t+1}$ is improved as much as possible. Next, we describe how we prepare data for contrastive learning, the policy network and the contrastive loss used in training, and finally introduce how the learned policy is used in CL-LNS.

Following previous work by Sonnerat et al. 2021, we use LB as the expert policy to collect good demonstrations to learn to imitate. Formally, for a given state $\boldsymbol{s}^{t}=(\mathcal{I},\boldsymbol{x}^{t})$, we use LB to find the optimal action $\boldsymbol{a}^{t}$ that leads to the minimum $\boldsymbol{c}^{\mathsf{T}}\boldsymbol{x}^{t+1}$ after solving the sub-ILP. Different from the previous work, we use contrastive learning to learn to make discriminative predictions of $\boldsymbol{a}^{t}$ by contrasting positive and negative samples (i.e., good and bad examples of actions $\boldsymbol{a}^{t}$). In the following, we describe how we collect the positive sample set $\mathcal{S}_{\mathsf{p}}^{t}$ and the negative sample set $\mathcal{S}_{\mathsf{n}}^{t}$.

During data collection, given $\boldsymbol{s}^{t}=(\mathcal{I},\boldsymbol{x}^{t})$, we solve the LB ILP with the incumbent solution $\boldsymbol{x}^{t}$ and neighborhood size $k^{t}$ to find the optimal $\boldsymbol{x}^{t+1}$. LNS proceeds to iteration $t+1$ with $\boldsymbol{x}^{t+1}$ until no improving solution $\boldsymbol{x}^{t+1}$ could be found by the LB ILP within a runtime limit. In experiments, the LB ILP is solved with SCIP 8.0.1 (Bestuzheva et al. 2021) with an hour runtime limit and $k^{t}$ is fine-tuned for each type of instances. After each solve of the LB ILP, in addition to the best solution found, SCIP records all intermediate solutions found during the solve. We look for intermediate solutions $\boldsymbol{x}^{\prime}$ whose resulting improvements on the objective value is at least $0<\alpha_{\mathsf{p}}\leq 1$ times the best improvement (i.e., $\boldsymbol{c}^{\mathsf{T}}(\boldsymbol{x}^{t}-\boldsymbol{x}^{\prime})\geq\alpha_{\mathsf{p}}\cdot\boldsymbol{c}^{\mathsf{T}}(\boldsymbol{x}^{t}-\boldsymbol{x}^{t+1})$) and consider their corresponding actions as positive samples. We limit the number of the positive samples $|\mathcal{S}^{t}_{\mathsf{p}}|$ to $u_{\mathsf{p}}$. If more than $u_{\mathsf{p}}$ positive samples are available, we record the top $u_{\mathsf{p}}$ ones to avoid large computational overhead with too many samples when computing the contrastive loss (see Section 4.3). $\alpha_{\mathsf{p}}$ and $u_{\mathsf{p}}$ are set to $0.5$ and $10$, respectively, in experiments.

Collecting Negative Samples 𝒮𝗇t\mathcal{S}_{\mathsf{n}}^{t}

Negative samples are critical parts of contrastive learning to help distinguish between good and bad demonstrations. We collect a set of $c_{\mathsf{n}}^{t}$ negative samples $\mathcal{S}_{\mathsf{n}}^{t}$, where $c_{\mathsf{n}}^{t}=\kappa|\mathcal{S}_{\mathsf{p}}^{t}|$ and $\kappa$ is a hyperparameter to control the ratio between the numbers of positive and negative samples. Suppose $\mathcal{X}^{t}$ is the optimal set of variables selected by LB. We then perturb $\mathcal{X}^{t}$ to get $\hat{\mathcal{X}}^{t}$ by replacing $5\%$ of the variables in $\mathcal{X}^{t}$ with the same number of those not in $\mathcal{X}^{t}$ uniformly at random. We then solve the corresponding sub-ILP derived from $\hat{\mathcal{X}}^{t}$ to get a new incumbent solution $\hat{\boldsymbol{x}}^{t+1}$. If the resulting improvement of $\hat{\boldsymbol{x}}^{t+1}$ is less than $0\leq\alpha_{\mathsf{n}}<1$ times the best improvement (i.e., $\boldsymbol{c}^{\mathsf{T}}(\boldsymbol{x}^{t}-\hat{\boldsymbol{x}}^{t+1})\leq\alpha_{\mathsf{n}}\cdot\boldsymbol{c}^{\mathsf{T}}(\boldsymbol{x}^{t}-\boldsymbol{x}^{t+1})$), we consider its corresponding action as a negative sample. We repeat this $c_{\mathsf{n}}^{t}$ times to collect negative samples. If less than $c_{\mathsf{n}}^{t}$ negative samples is collected, we increase the perturbation rate from $5\%$ to $10\%$ and generate another $c_{\mathsf{n}}^{t}$ samples. We keep increasing the perturbation rate at an increment of $5\%$ until $c_{\mathsf{n}}^{t}$ negative samples are found or it reaches $100\%$. In experiments, we set $\kappa=9$ and $\alpha_{\mathsf{n}}=0.05$, and it takes less than 3 minutes to collect negative samples for each state.

2 Policy Network

Following previous work on learning for ILPs (Gasse et al. 2019; Sonnerat et al. 2021; Wu et al. 2021), we use a bipartite graph representation of ILP to encode a state $\boldsymbol{s}^{t}$. The bipartite graph consists of $n+m$ nodes representing the $n$ variables and $m$ constraints on two sides, respectively, with an edge connecting a variable and a constraint if the variable has a non-zero coefficient in the constraint. Following Sonnerat et al. 2021, we use features proposed in Gasse et al. 2019 for node features and edge features in the bipartite graph and also include a fixed-size window of most recent incumbent values as variable node features with the window size set to 3 in experiments. In addition to features used in Sonnerat et al. 2021, we include features proposed in Khalil et al. 2016 computed at the root node of BnB to make it a richer set of variable node features.

3 Training with a Contrastive Loss

Given a set of ILP instance for training, we follow the expert’s trajectory to collect training data. Let $\mathcal{D}=\{(\boldsymbol{s},\mathcal{S}_{\mathsf{p}},\mathcal{S}_{\mathsf{n}})\}$ be the set of states with their corresponding sets of positive and negative samples in the training data. A contrastive loss is a function whose value is low when the predicted action $\pi_{\boldsymbol{\theta}}(\boldsymbol{s})$ is similar to the positive samples $\mathcal{S}_{\mathsf{p}}$ and dissimilar to the negative samples $\mathcal{S}_{\mathsf{n}}$. With similarity measured by dot products, a form of supervised contrastive loss, called InfoNCE (Oord et al. 2018; He et al. 2020), is used in this paper:

where $\tau$ is a temperature hyperparameter set to 0.07 (He et al. 2020) in experiments.

4 Applying Learned Policy π𝜽\pi_{\boldsymbol{\theta}}

We apply the learned policy $\pi_{\boldsymbol{\theta}}$ in LNS. In iteration $t$, let $(v_{1},\cdots,v_{n}):=\pi_{\boldsymbol{\theta}}(\boldsymbol{s}^{t})$ be the variable scores output by the policy. To select $k^{t}$ variables, CL-LNS greedily selects those with the highest scores. Previous works (Sonnerat et al. 2021; Wu et al. 2021) commonly use sampling methods to select the variables, but those sampling methods are empirically worse than our greedy method in CL-LNS. However, when the adaptive neighborhood size $k^{t}$ reaches its upper bound $\beta\cdot n$, CL-LNS may repeat the same prediction due to deterministic selection process. When this happens, we switch to the sampling method introduced in (Sonnerat et al. 2021). The sampling method selects variables sequentially: at each step, a variable $x_{i}$ that has not been selected yet is selected with probability proportional to $v_{i}^{\eta}$, where $\eta$ is a temperature parameter set to $0.5$ in experiments.

Empirical Evaluation

In this section, we introduce our evaluation setup and then present the results. Our code will be made available to the public upon publication.

We evaluate on four NP-hard problem benchmarks that are widely used in existing studies (Wu et al. 2021; Song et al. 2020; Scavuzzo et al. 2022), which consist of two graph optimization problems, namely the minimum vertex cover (MVC) and maximum independent set (MIS) problems, and two non-graph optimization problems, namely the combinatorial auction (CA) and set covering (SC) problems. We first generate a test set of 100 small instances for each problem, namely MVC-S, MIS-S, CA-S and SC-S. MVC-S instances are generated according to the Barabasi-Albert random graph model (Albert & Barabási 2002), with 1,000 nodes and average degree 70 following (Song et al. 2020). MIS-S instances are generated according to the Erdos-Renyi random graph model (Erdos et al. 1960), with 6,000 nodes and average degree 5 following (Song et al. 2020). CA-S instances are generated with 2,000 items and 4,000 bids according to the arbitrary relations in Leyton-Brown et al. 2000. SC-S instances are generated with 4,000 variables and 5,000 constraints following Wu et al. 2021. We then generate another test set of 100 large instances for each problem by doubling the number of variables, namely MVC-L, MIS-L, CA-L and SC-L. For each test set, Table 1 shows its average numbers of variables and constraints. More details of instance generation are included in Appendix.

For data collection and training, we generate another set of 1,024 small instances for each problem. We split these instances into training and validation sets, each consisting of 896 and 128 instances, respectively.

Baselines

We compare CL-LNS with five baselines: (1) BnB: using SCIP (v8.0.1), the state-of-the-art open-source ILP solver, with the aggressive mode fine-tuned to focus on improving the objective value; (2) RANDOM: LNS which selects the neighborhood by uniformly sampling $k^{t}$ variables without replacement; (3) LB-RELAX (Huang et al. 2022a): LNS which selects the neighborhood with the LB-RELAX heuristics; (4) IL-LNS (Sonnerat et al. 2021); (5) RL-LNS (Wu et al. 2021). We compare with two more baselines in Appendix. For each ML approach, a separate model is trained for each problem on the small training set and tested on both small and large test sets. We implement IL-LNS and fine tune its hyperparameters for each problem since the authors do not fully open source the code. IL-LNS uses the same training dataset as CL-LNS but uses only the positive samples. For RL-LNS, we use the code and hyperparameters provided by the authors and train the models with five random seeds to select one with the best performance on the validation sets. We do not compare to the approach by Song et al. 2020 since it performs worse than RL-LNS on multiple problems (Wu et al. 2021).

Metrics

We use the following metrics to evaluate all approaches: (1) The primal bound is the objective value of the ILP; (2) The primal gap (Berthold 2006) is the normalized difference between the primal bound $v$ and a precomputed best known objective value $v^{*}$, defined as $\frac{|v-v^{*}|}{\max(v,v^{*},\epsilon)}$ if $v$ exists and $v\cdot v^{*}\geq 0$, or 1 otherwise. We use $\epsilon=10^{-8}$ to avoid division by zero; (3) The primal integral (Achterberg et al. 2012) at time $q$ is the integral on $[0,q]$ of the primal gap as a function of runtime. It captures the quality of and the speed at which solutions are found; (4) The survival rate to meet a certain primal gap threshold is the fraction of instances with primal gaps below the threshold (Sonnerat et al. 2021); (5) The best performing rate of an approach is the fraction of instances on which it achieves the best primal gap (including ties) compared to all approaches at a given runtime cutoff. Since BnB and LNS are both anytime algorithms, we show these metrics as a function of runtime or the number of iterations in LNS (when applicable) to demonstrate their anytime performance.

Hyperparameters

We conduct experiments on 2.5GHz Intel Xeon Platinum 8259CL CPUs with 32 GB memory. Trainings are done on a NVIDIA A100 GPU with 40 GB memory. All experiments use the hyperparameters described below unless stated otherwise. We use SCIP (v8.0.1) (Bestuzheva et al. 2021) to solve the sub-ILP in every iteration of LNS. To run LNS, we find an initial solution by running SCIP for 10 seconds. We set the time limit to 60 minutes to solve each instance and 2 minutes for solving the sub-ILP in every LNS iteration. All approaches require a neighborhood size $k^{t}$ in LNS, except for BnB and RL-LNS ($k^{t}$ in RL-LNS is defined implicitly by how the policy is used). For LB-RELAX, IL-LNS and CL-LNS, the initial neighborhood size $k^{0}$ is set to $100,3000,1000$ and $150$ for MVC, MIS, CA and SC, respectively, except $k^{0}$ is set to $150$ for SC for IL-LNS; for RANDOM, it is set to $200,3000,1500$ and $200$ for MVC, MIS, CA and SC, respectively. All approaches use adaptive neighborhood sizes with $\gamma=1.02$ and $\beta=0.5$, except for BnB and RL-LNS. For IL-LNS, when applying its learned policies, we use the sampling methods on MVC and CA instances and the greedy method on SC and MIS instances. For CL-LNS, the greedy method is used on all instances. Additional details on hyperparameter tunings are provided in Appendix.

For data collection, we use different neighborhood sizes $k^{0}=50,500,200$ and $50$ for MVC, MIS, CA and SC, respectively, which we justify in Section 5.2. We set $\gamma=1$ and run LNS with LB until no new incumbent solution found. The runtime limit for solving LB in every iteration is set to 1 hour. For training, we use the Adam optimizer (Kingma & Ba 2015) with learning rate $10^{-3}$. We use a batch size of 32 and train for 30 epochs (the training typically converges in less than 20 epochs and 24 hours).

2 Results

Figure 1 shows the primal gap as a function of runtime. Table 2 presents the average primal gap and primal integral at 60 minutes runtime cutoff on small and large instances, respectively (see results at 15, 30 and 45 minutes runtime cutoff in Appendix). Note that we were not able to reproduce the results on CA-S and CA-L reported in Wu et al. 2021 for RL-LNS despite using their code and repeating training with five random seeds. CL-LNS shows significantly better anytime performance than all baselines on all problems, achieving the smallest average primal gap and primal integral. It also demonstrates strong generalization performance on large instances unseen during training. Figure 2 shows the survival rate to meet the $1.00\%$ primal gap threshold. CL-LNS achieves the best survival rate at 60 minutes runtime cutoff on all instances, except that, on SC-L, its final survival rate is slightly worse than RL-LNS but it achieves the rate with much shorter runtime. On MVC-L, MIS-S and MIS-L instances, several baselines achieve the same survival rate as CL-LNS but it always achieves the rates with the shortest runtime. Figure 3 shows the best performing rate on the small test instances where CL-LNS consistently performs best on 50% to 100% of the instances. In Appendix, we present strong results in comparison with two more baselines and on one more performance metric.

Both IL-LNS and CL-LNS learn to imitate LB. On the small test instances, we run LB with two different neighborhood sizes, one that is fine-tuned in data collection and the other the same as CL-LNS, for 10 iterations and compare its per iteration performance with IL-LNS and CL-LNS. This allows us to compare the quality of the learned policies to the expert independently of their speed. The runtime limit per iteration for LB is set to 1 hour. Figure 4 shows the primal bound as a function of number of iterations. The table in the figure summarizes the neighborhood sizes and the average runtime per iteration. For LB, the result shows that the neighborhood size affects the overall performance. Intuitively, using a larger neighborhood size in LB allows LNS to find better incumbent solutions due to being able to explore larger neighborhoods. However, in practice, LB becomes less efficient in finding good incumbent solutions as the neighborhood size increases, sometimes even performs worse than using a smaller neighborhood size (the one for data collection). The neighborhood size for data collection is fine-tuned on validation sets to achieve the best primal bound upon convergences, allowing the ML models to observe demonstrations that lead to as good primal bounds as possible in training. However, when using the ML models in testing, we have the incentive to use a larger neighborhood size and fine tune it since we no longer suffer from the bottleneck of LB. We therefore fine tune the neighborhood sizes for IL-LNS and CL-LNS separately on validation sets. CL-LNS has a strong per-iteration performance that is consistently better than IL-LNS. With the fine-tuned neighborhood size, CL-LNS even outperforms the expert that it learns from (LB for data collection) on MIS-S and CA-S.

Ablation Study

We evaluate how contrastive learning and two enhancements contribute to CL-LNS’s performance. Compared to IL-LNS, CL-LNS uses (1) addition features from Khalil et al. 2016 and (2) GAT instead of GCN. We denote by “FF” the full feature set used in CL-LNS and “PF” the partial feature set in IL-LNS. In addition to IL-LNS and CL-LNS, we evaluate the performance of IL-LNS with FF and GAT (denoted by IL-LNS-GAT-FF), CL-LNS with GCN and PF (denoted by CL-LNS-GCN-PF) as well as CL-LNS with GAT and PF (denoted by CL-LNS-GAT-PF) on MVC-S and CA-S. Figure 5 shows the primal gap as a function of runtime. Table 3 presents the primal gap and primal integral at 60 minutes runtime cutoff. The result shows that IL-LNS-GAT-FF, imitation learning with the two enhancements, still performs worse than CL-LNS-GCN-PF without any enhancements. CL-LNS-GCN-PF and CL-LNS-GAT-PF perform similarly in terms of the primal gaps but CL-LNS-GAT-PF has better primal integrals, showing the benefit of replacing GCN with GAT. On MVC-S, three variants of CL-LNS have similar average primal gaps and on CA-S, CL-LNS has better average primal gap than the other two variants. But adding the two enhancement helps improve the primal integral, leading to the overall best performance of CL-LNS on both MVC-S and CA-S.

Conclusion

We proposed CL-LNS, that uses a contrastive loss to learn efficient and effective destroy heuristics in LNS for ILPs. We presented a novel data collection process tailored for CL-LNS and used GAT with a richer set of features to further improve its performance. Empirically, CL-LNS significantly outperformed state-of-the-art approaches on four ILP benchmarks w.r.t. to the primal gap, the primal integral, the best performing rate and the survival rate. CL-LNS achieved good generalization performance on out-of-distribution instances. It is future work to learn policies that can generalize across problem domains. CL-LNS does not guarantee optimality and it is also interesting future work to integrate it in BnB for which many other learning techniques are developed. Our approach is closely related to and could be useful for many problems of identifying substructures in combinatorial searches, for example, identifying backdoor variables in ILPs (Ferber et al. 2022) and selecting neighborhoods in LNS for other COPs.

References

Appendix

Appendix A Additional Related Work

LNS-based primal heuristics is a family of primal heuristics in BnB and have been studied extensively in past decades. With the same purpose of improving primal bounds, the main differences between the LNS-based primal heuristics in BnB and LNS for ILPs are: (1) LNS-based primal heuristics are executed periodically at different search tree nodes during the search and the execution schedule is itself dynamic, because they are often more expensive to run than the other primal heuristics in BnB; (2) the destroy heuristics in LNS-based primal heuristics are often designed to use information specific to BnB, such as the dual bound and the LP relaxation at a search tree node, and they are not directly applicable in LNS for ILPs in our setting.

Next, we briefly summarize the destroy heuristics in LNS-based primal heuristics:

Crossover heuristics (Rothberg 2007): it destroys variables that have different values in a set of selected known solutions (typically two). The Mutation heuristics (Rothberg 2007) destroys a random subset of variables.

Relaxation Induced Neighborhood Search (RINS) (Danna et al. 2005): it destroys variables whose values disagree in the solution of the LP relaxation at the search tree node and the incumbent solution.

Relaxation Enforced Neighborhood Search (RENS) (Berthold 2014): it restricts the neighborhood to be the feasible roundings of the LP relaxation at the current search tree node.

Local Branching (LB)(Fischetti & Lodi 2003): it restricts the neighborhood to a ball around the current incumbent solution.

Distance Induced Neighborhood Search (DINS) (Ghosh 2007): it takes the intersection of the neighborhoods of the Crossover, Local Branching and Relaxation Induced Neighborhood Search heuristics.

Graph-Induced Neighborhood Search (GINS) (Maher et al. 2017): it destroys the breadth-first-search neighborhood of a variable in the bipartite graph representation of the ILP.

Recently, an adaptive LNS primal heuristic (Hendel 2022) has been proposed to combine the power of these heuristics, where it essentially solves a multi armed bandit problem to choose which heuristic to apply.

A.2 Learning to Solve Other COPs

ML has been applied to solve a number of COPs, including traveling salesman problems (Xin et al. 2021; Zheng et al. 2021), vehicle routing (Kool et al. 2018), boolean satisfiability (Selsam et al. 2018; Amizadeh et al. 2018) and general graph optimization problems (Khalil et al. 2017; Li et al. 2018).

Appendix B Network Architecture

Appendix C Additional Details of Instance Generation

We present the ILP formulations for the minimum vertex cover (MVC), maximum independent set (MIS), set covering (SC) and combinatorial auction (CA) problems.

In an MVC instance, we are given an undirected graph $G=(V,E)$. The goal is to select the smallest subset of nodes such that at least one end point of every edge in the graph is selected:

C.2 MIS

In an MIS instance, we are given an undirected graph $G=(V,E)$. The goal is to select the largest subset of nodes such that no two nodes in the subsets are connected by an edge in $G$:

C.3 SC

In an SC instance, we are given $m$ elements and a collection $S$ of $n$ sets whose union is the set of all elements. The goal is to select a minimum number of sets from $S$ such that the union of the selected set is still the set of all elements:

C.4 CA

In a CA instance, we are given $n$ bids $\{(B_{i},p_{i}):i\in[n]\}$ for $m$ items, where $B_{i}$ is a subset of items and $p_{i}$ is its associated bidding price. The objective is to allocate items to bids such that the total revenue is maximized:

Appendix D Additional Details on Hyperparameter Tuning

For RL-LNS, we use all the hyperparameters provided in their code (Wu et al. 2021) in our experiments. For the other LNS methods, all hyperparameters used in experiments are fine-tuned on the validation set and the hyperparameter tunings are described in the following.

For $\beta$ which upper bounds the neighborhood size, we tried values from $\{0.25,0.5,0.6,0.7\}$. $\beta=0.25$ is the worst for all approaches, resulting in the highest gap. For LB-RELAX, IL-LNS and CL-LNS, all values perform similarly (because they select effective neighborhoods early in the search and their neighborhood sizes either do not reach the upper bound or they already converge to good solutions before reaching it). For RANDOM and GRAPH, $\beta=0.5$ is the best for them. So we set $\beta=0.5$ consistently for all approaches.

For initial neighborhood sizes $k^{0}$, we observe that the best values are sensitive for approaches that need longer runtime to select variables, such as LB-RELAX, IL-LNS and CL-LNS, thus they need the right $k^{0}$ from the beginning and we fine tune it for them. For RANDOM and GRAPH, their runtime for selecting variables is short, and with the adaptive neighborhood size mechanism, they could very quickly find the right neighborhood size and are insensitive to $k^{0}$. They converge to the same primal gaps ($<1\%$ relative differences) with similar primal integrals ($<2\%$ relative differences) using different $k^{0}$. Despite that the differences are small, we still use the best $k^{0}$ for them.

For $\gamma$ that controls the rate at which $k^{t}$ increases, we tried values from $\{1,1.01,1.02,1.05\}$. Overall, $\gamma$ does not have a big impact on the performance if $\gamma>1$, however $\gamma=1$ is far worse than the others.

For the runtime limit for each repair operation, we tried different limits of 0.5, 1, 2 and 5 minutes. All approaches are not sensitive to it since most repairs are finished within 20 seconds. Except for IL-LNS on the SC instances, it selects neighborhoods that require a longer time to repair and a 2-minute runtime limit is necessary. We therefore use 2 minutes consistently.

For BnB, the aggressive mode is fune-tuned for each problem on the validation set. With the aggressive mode turned on, BnB (SCIP) does not always deliver better anytime performance than having it turned off. Based on the validation results, the aggressive mode is turned on for MVC and SC instances and turned off for CAT and MIS instances.

For IL-LNS, it uses the same training dataset as CL-LNS but uses only the positive samples. We fine tune its hyperparameters for each problem on the validation set, resulting in a different $k^{0}$ on the SC instance from CL-LNS. Also in Sonnerat et al. 2021, they use sampling methods to select variables when using the learned policy. For the temperature parameter $\eta$ in the sampling method, we tried values from $\{1/2,2/3,1\}$ and $\eta=0.5$ performs the best overall. However, in our experiment, we observe that our greedy method described in Section 4.4 works better for IL-LNS on SC and MIS instances, thus, CL-LNS is compared against the corresponding results on SC and MIS instances.

For LB-RELAX, there are three variants of it presented in Huang et al. 2022a. We present only the best of the three variants for each problem in the paper for simplicity.

In Table 4, we summarize all the hyperparameters with their notations and values used in our experiments.

Appendix E Additional Experimental Results

In this section, we add two more baselines and evaluate all approaches on one more metric. We show that CL-LNS outperforms all approaches in terms of all metrics.

LB: LNS which selects the neighborhood with the LB heuristics. We set the time limit to 10 minutes for solving the LB ILP in each iteration;

GRAPH: LNS which selects the neighborhood based on the bipartite graph representation of the ILP similar to GINS (Maher et al. 2017). A bipartite graph representation consists of nodes representing the variables and constraints on two sides, respectively, with an edge connecting a variable and a constraint if a variable has a non-zero coefficient in the constraint. It runs a breadth-first search starting from a random variable node in the bipartite graph and selects the first $k^{t}$ variable nodes expanded.

Figure 6 shows the full results on the primal gap as a function of runtime. Figure 7 shows the full results on the survival rate as a function of runtime. Figure 8 shows the full results on the primal bound as a function of runtime. Tables 5, 6, 7 and 8 present the average primal bound, primal gap and primal integral at 15, 30, 45 and 60 minutes runtime cutoff, respectively, on the small instances. Tables 9, 10, 11 and 12 present the average primal bound, primal gap and primal integral at 15, 30, 45 and 60 minutes runtime cutoff, respectively, on the large instances.

Next, we evaluate the performance with one additional metric: The gap to virtual best at time $q$ for an approach is the normalized difference between its best primal bound found up to time $q$ and the best primal bound found up to time $q$ by any approach in the portfolio.

Figure 9 shows the full results on the best performing rate as a function of runtime. Figure 10 shows the full results on the gap to virtual best as a function of runtime.