Learning Backdoors for Mixed Integer Linear Programs with Contrastive Learning

A Mixed Integer Linear Programming (MILP) is defined as

where $A\in\mathbb{R}^{m\times n},b\in\mathbb{R}^{m},c\in\mathbb{R}^{n}$, and the non-empty set $I\subseteq{1,...,n}$ indexes the binary variables. A solution to the MILP is a feasible assignment of values to the variables. In this paper, we focus on the formulation above that consists of continuous and binary variables due to MCTS data collection limited to this setting, but our contrastive learning framework can still be applied to MILP with non-binary integer variables.

Given a MILP instance defined by the tuple $(A,b,c,I)$, a “strong backdoor" of size $K\ll|I|$ is a set of integer variables $B$, $|B|=K$, $B\subset I$ such that branching exclusively on variables from $B$ results in a provably optimal solution or a proof of infeasibility. The order in which decision variables are considered for branching can affect the performance of the solver’s primal heuristics, which in turn affects pruning in Branch-and-Bound. We refer to [7, 11] for a detailed discussion of why order matters in practice in MILP solvers. To distinguish from “strong backdoors”, we introduce term “backdoor” to denote a set of integer variables where prioritizing branching on them reduces solving time. Throughout the paper, we use “candidate backdoors” to describe a set of integer variables currently under evaluation, which may or may not yield improvements in solving time.

Backdoors are first introduced by [47] for SAT solving and, over the years, many approaches are proposed to find backdoors to improve SAT solving  [38, 30]. Observing the connection between SAT and MILP, [7] generalize the concept of backdoors and propose two forms of random sampling to find backdoors: uniform sampling and biased sampling to favor ones that are more fractional in the LP relaxation solutions, while [11] propose another strategy that formulates finding backdoors as a Set Covering Problem. Recently, [28] contributed to a third strategy for finding backdoors using Monte-Carlo tree search, which balances exploration and exploitation by design. Utilizing a reward function based on the tree weight in the Branch-and-Bound tree, MCTS approximates the backdoor’s strength without the need to solve time-consuming MILP instances. However, the quality of the backdoors it finds varies and it is also time-consuming (5+ hours) for MCTS to find backdoors, which opens the floor for learning-based techniques to find backdoors  [10].

Several studies have applied ML to improve heuristic decisions in Branch-and-Bound, such as which node to select next to expand [18, 41, 31], which variable to branch on next [26, 13, 15], which cut to select next [44, 39], which primal heuristics to run next [27, 4]. Another line of work focuses on improving speed to find primal solutions. [42, 43, 22] use ML to iteratively decide which subsets of variables to re-optimize for a given solution to a MILP. [17, 36] learn to predict high-quality solutions to MILPs with supervised learning.

Contrastive Learning is a discriminative approach that aims at grouping similar samples closer and dissimilar samples far from each other [25]. It has been successfully applied in both computer vision area [19] and natural language processing area [34]. The work of contrastive learning on graph representation has also been extensively studied [48], but it has not been explored much for CO problem domains.  [35] derive a contrastive loss for decision-focused learning to solve CO problems with uncertain inputs.  [8] use contrastive pre-training to learn good representations for the boolean satisfiability problem.  [22] use contrastive learning to learn efficient and effective destroy heuristics in large neighborhood search for MILPs. [23] use contrastive learning to predict optimal solutions to MILPs in the predict-and-search algorithm.

Diverging from previous approaches for finding or predicting backdoors [10, 11, 7], we incorporate contrastive learning to predict backdoors. The key challenge lies in determining high-quality positive samples and similar negative samples for effective training. a MILP instance can be represented as a tuple $P=(A,b,c,I)$, where $A,b,c$ are the coefficients of the constraints or objectives and $I$ is the set of integer variables. Our objective is to collect a training dataset $D$. Specifically, for every training instance $P$, we collect positive samples $S_{p}$ and negative samples $S_{n}$ specific to $P$.

We employ the Monte-Carlo Tree Search Algorithm proposed in [28] to collect candidate backdoors. MCTS will return a set of candidate backdoors with their associate tree weights in the Branch-and-Bound tree, which are approximations of the strength of backdoors. We select the top $k$ candidate backdoors $B_{1},B_{2},\dots,B_{k}$ with the highest tree weights, and solve the MILP $P$ with these candidate backdoors to obtain their runtimes $t_{1},t_{2},\dots,t_{k}$. When we solve a MILP with a backdoor, we set the branching priority for variables in the backdoor higher than other variables, i.e., we always branch on variables from the backdoor whenever there is one that needs to be branched on. Positive samples $S_{p}$ are chosen as $p$ shortest-runtime backdoors better than Gurobi and negative samples $S_{n}$ are chosen as $q$ longest-runtime backdoors worse than Gurobi. The approach ensures that the positive samples are backdoors with high MILP runtime performance. In contrast, the negative samples are similar to positive samples but have worse runtime performance, enabling the ML model to learn to discriminate between backdoors and non-backdoors effectively. In experiments, we set $k=50$ and $p=q=5$. Details of data collection design and sensitive analysis are provided in Appendix [3].

We represent the MILP $P=(A,b,c,I)$ as a bipartite graph as in  [13]. The featured bipartite graph $P^{\prime}=(G,V,C,E)$, with graph $G$ containing variable nodes and constraint nodes. Additionally, there is an edge $(i,j)$ in edge matrix $\epsilon$ between a variable node $i$ and a constraint node $j$ if variable $i$ appears in constraint $j$ with nonzero coefficient, i.e., $A_{ji}\neq 0$. Constraint, variable, and edge features are represented as matrices $V\in\mathbb{R}^{n\times d},C\in\mathbb{R}^{m\times c^{\prime}},E\in\mathbb{R}^{m\times n\times e}$. The bipartite graph representation ensures the MILP encoding is invariant to variable and constraint permutation. Additionally, we can use a variety of predictive models designed for variable-sized graphs, enabling deployment on problems with varying numbers of variables and constraints. We use features proposed in [13], which include 15 variable features (e.g., variable types, coefficients, upper and lower bound, root LP related features), 4 constraint features (e.g., constant, sense), and 1 edge feature for coefficients.

We learn a policy $\pi$ represented by a Graph Attention Network (GAT) [2], which takes the bipartite graph $P^{\prime}$ as input and outputs a score vector with one score per decision variable. To increase the modeling capacity and to manipulate node interactions proposed by our architecture, we use embedding layers in the network to first adjust the size of feature embeddings to $V^{1}\in\mathbb{R}^{n\times L},C^{1}\in\mathbb{R}^{m\times L},E^{1}\in\mathbb{R}^{|\epsilon|\times L}$ accordingly. Then, GAT performs two rounds of message passing. In the first round, each constraint node in $C^{1}$ attends to its neighbors using an attention structure with $H$ attention heads to get update constraint embeddings $C^{2}$. Similarly, each variable node in $V^{1}$ attends to its neighbors to get updated variable embeddings $V^{2}$ with another set of attention weights in the second round. Finally, the network applies a multi-layer perceptron with a sigmoid function to obtain a score between 0 and 1 for each variable. In experiments, layer size $L$ and number of attention heads $H$ are set to 64 and 8. Full details of the network architecture are provided in Appendix [3].

The model is trained with a contrastive loss to score each decision variable by learning to emulate superior backdoors and avoid inferior ones. Given a set of MILP instances for training, let $D=(P^{\prime},S_{p},S_{n})$ be the set of one training data where $P^{\prime}$ is the bipartite representation of MILP instance $P$, $S_{p}$ is the set of positive samples and $S_{n}$ is the set of negative samples associated with $P$. With similarity measured by dot products, we use the InfoNCE [37] contrastive loss $L(P^{\prime},S_{p},S_{n})=$

to train the policy $\pi$, where $\tau$ is a temperature hyperparameter set to $0.07$ in experiment following  [22]. By choosing faster solving time backdoors as positive samples and those similar to the positive ones but with lower quality as negative samples, the model learns to generate embeddings closer to positive samples and further away from negative ones.

During testing, given a MILP instance, we use the same data representation introduced in section 4.2 to convert it to a bipartite graph and use the graph as the input to GAT. Then, GAT outputs a score vector with one score for each variable. We greedily select the binary variables with the highest scores as the predicted backdoors by user-defined backdoor size. For the scorer model in [10], predicting the backdoor differs from our contrastive learning model. They first sample 50 candidate backdoors with the predefined backdoor size using the random biased sampling method [7] and input each backdoor to the scorer model to get an output score. They select the candidate backdoor with the highest score as the predicted backdoor. The backdoor predicted by the scorer model contains strong randomness within the 50 candidate backdoors it samples, thus causing the predicted one to have highly variate performance results. Our contrastive learning model is deterministic based on greedy selection and can also output a backdoor with any size requested by the users. Finally, we assign the branching priority for variables in the backdoor before the start of the tree search in the MILP solver and then collect statistics of solving the problem to optimality for later evaluation.

We evaluate on several ILP problem domains, Generalized Independent Set Problem (GISP), Set Cover (SC), Combinatorial Auction (CA), and Maximum Independent Set (MIS) that are widely used in existing studies [42, 10, 22]. For each problem domain, we generate Small (S) and Large (L) instances for it. Following [10], GISP-S and GISP-L instances are generated with 150 nodes and 175 nodes, respectively, with the node reward set to 100 and edge removal cost set to 1; In order to keep a similar evaluation procedure (e.g., Gurobi being able to solve to optimality within certain runtime) and diverse hardness of the problems, we choose the size of the three other problem domains as follows: Following [22], SC-S instances have 1,000 variables and 1,200 constraints and SC-L instances have 1,000 variables and 1,500 constraints, with density set to 0.05 for both; Following  [33], CA-S instances are generated with 150 items and 750 bids and CA-L instances are generated with 200 items and 1,000 bids according to the arbitrary relations; Following [22], MIS-S and MIS-L instances are generated according to the Erdos-Renyi random graph model [9], with an average degree of 4 and 1,250 and 1,500 nodes, respectively.

To show our method can work on general MILP cases, we also evaluate on Facility Location (FC) and Neural Network Verification (NN). Following  [13], FC instances are generated with 100 facilities supplying 200 customers. Following  [36], NN instances are a convolutional neural network is verified on each image in the MNIST dataset, giving rise to a corresponding dataset of MILPs. Table 1 shows average numbers of variables, constraints, and average Gurobi solving time of 100 test instances from each problem domain. More details of instance generation are included in the Appendix [3].

We refrained from evaluating our methodology on heterogeneous MILP datasets like MIPLIB [14] due to the challenges in training an effective model using backdoors collected from a variety of MILP distributions. Instead, we target homogeneous settings from Distributional MIPLIB [24] because many real-world scenarios require solving a homogeneous family of problems, where instances share similar structures but differ slightly in problem size or numerical coefficients. Since MCTS backdoor collection in [28] only works with mixed-binary instances due to the ease of implementation of the tree weight for binary problems, we have limited our problem domains to MILP with only binary variables. In practice, we believe contrastive learning-based training still applies when using LP-based sampling to collect data.

Data Collection We generate 200 small instances for each problem domain. We use the MCTS framework to collect backdoors of size 8 for each instance over 5 hours with 10 parallel workers. We follow [28] and choose 8, which shows promising results on finding high-quality backdoors on 164 problem domains From MILPLIB2017. We select the top 50 backdoors measured by tree weight function, solve the problems using those backdoors with MILP solver, and record the runtime. For contrastive loss, we select the 5 fastest candidate backdoors as positive samples and 5 slowest candidate backdoors as negative samples.

Baselines We compare our contrastive learning model (cl) with several baselines: Gurobi (grb), the scorer model (scorer) and the scorer with the classifier (scorer+cls). scorer is the previous method  [10] that predicts the score for candidate backdoors using supervised learning and scorer+cls is scorer with cls to predict whether to use the backdoor output by the score or not. The scorer and cl models are trained with 200 instances, with 160 and 40 instances for training and validation, respectively. For cls, we generate another 200 instances, with 160 and 40 instances for training and validation, respectively. To train the classifier for scorer+cls, we use random sampling based on the LP relaxation [7] to generate random 50 candidate backdoors and use scorer to select the best one to collect runtime statistics. Then, we assign labels for each instance based on the runtime of the selected backdoor over the Gurobi runtime and use a cross-entropy loss to train the classifier following [10]. To train the classifier for cl+cls, we collect the runtime statistics from the backdoor output directly from cl model and the rest is the same as scorer+cls.

We did not compare other learning for Branch-and-Bound  [41, 13] baselines because we believe their works are conjunctive of ours. Our model just predicts a small set of variables before the solving, and during the solving; it is still applicable to use other decision-making approaches. Also, their approaches required the specific implementation of solvers, which limited them to open-source solver SCIP, while our approach can be applied to the current state-of-art solver Gurobi, which makes our baseline more competitive than theirs.

Metrics To compare the performance of the methods, we test on 100 instances for each problem domain and report summary statistics of runtime to solve the problem to optimality, including mean, standard deviation, 25th percentile, median, and 75th percentile. We also report the wins, ties, and losses over Gurobi. We consider the runtime of the full pipeline, including feature extractor, inference for the GAT model, sampling or greedy selection, and solving the MILP. When cls suggests using Gurobi, we record a “tie” to give insight into model predictions even though there is a slight loss in runtime due to the ML overhead.

Backdoor Collection Quality For each problem domain, we gathered solve times from 50 MCTS selected candidate backdoors across 200 instances. This resulted in a dataset comprising solve times for 10,000 candidate backdoors. Figure 4 displays histograms of the normalized runtimes, which we calculated by dividing the solve time with a candidate backdoor by the original solve time for each of the 10,000 candidate backdoors in every problem domain. We observe significant improvement in MCTS data collection over the previous sampling method. Specifically, we noted that over half of the candidate backdoors outperformed the baseline solve time in the GISP-S, FC, and NN problem domains. In stark contrast, the sampling method employed in  [10] failed to identify any backdoors that improved the original solve times for SC-S, CA-S, and MIS-S domains. However, our approach demonstrated a considerable portion of candidate backdoors with better performance. The improvement of candidate backdoors directly leads to a higher quality of training data, which helps train more accurate models for backdoor prediction.