Promoting Generalization for Exact Solvers via Adversarial Instance Augmentation

Inspired by the fact that the MILP problem structures are included in the instance graph structures, we propose to augment the instances by masking variables, constraints, and edges in instance bipartite graphs to promote the diversity of graph structures. These operators are also reasonable from a real-world perspective. Notice that many MILP problems arise from real-world scheduling scenarios. These problems often feature variables that represent available workers, machines, vehicles, or other material resources, and they feature constraints that formulate the scheduling restrictive relationship among these resources. Therefore, these simple and reliable augmentation operators can also simulate perturbations of real-world resources, i.e., certain materials are inaccessible or some restrictions are lifted. Moreover, recent studies have shown that GNNs struggle to process certain “foldable” MILPs, as stated in [44]. In real-world scenarios, CO instances are highly structural and symmetric, resulting in numerous such structures in the training data that GNNs are unable to distinguish. This issue exacerbates the challenges posed by the limited diversity of training data. By augmenting the graph structures, AdaSolver effectively breaks the symmetric structures in training instances and promotes the diversity of instance graph structures. Thus, instance augmentation can improve not only the generalization ability of branching policy but also the sample efficiency, in which we can use fewer instances to attain comparable performance as we show in Section 8.3.

In practice, we control the usage of augmentation operators and masking proportion so that the augmented instances preserve a similar problem structure and computational hardness with the original instances, preventing harmful effects on training.

The instance augmenter is a function $\Phi:\mathcal{G}\to\mathcal{G}$ mapping an instance bipartite graph $G$ to the augmented instance graph $\Phi(G)$ by applying augmentation operators on $G$. However, two challenges for the instance augmentation remain to address. First, employing structural augmentation on a bipartite graph is generally a non-differentiable process. It is thus intractable to train the adversarial augmenter since the non-differentiable mapping $\Phi$ poses challenges for backward propagation and the gradient-based update fails. Second, the training efficiency of the augmenter and branching policy network is different. The training of the augmenter is much slower than the branching policy network since the augmenter will receive much less training data than the branching policy network. The adversarial augmenter operates on MILP instance graphs $\{G_{k}\}_{k}$ to obtain augmented instances $\{\Phi(G_{k})\}_{k}$. Later the expert policy runs on each augmented instance to generate a sequence of branching samples containing solving states and actions $\{({\mathbf{s}},\pi_{E}({\mathbf{s}}))\}$ in the IL setting, or the agent runs on the augmented instances to collect samples $\{({\mathbf{s}},a,r({\mathbf{s}},a))\}$ in the RL setting to calibrate the branching policy. Consequently, the adversarial augmenter receives significantly less training data $\{\Phi(G_{k})\}_{k}$ than the branching policy. The issues of non-differentiability and unsatisfactory training efficiency require a sample-efficient training strategy under sparse supervised signals. Therefore, we resort to a contextual bandit version of the proximal policy optimization (PPO) algorithm [17].

To formulate the graph augmentation as a contextual bandit problem, we view the solver as the environment and the adversarial augmenter as the agent. A contextual bandit problem can be represented as the tuple $(\mathcal{G},\mathcal{A}^{\text{CB}},r^{\text{CB}})$. To avoid misleading notations with branching MDP, here we use the superscript CB to specify the contextual bandit formulation. Then we specify the state space ${\mathcal{G}}$, the action space $\mathcal{A}^{\text{CB}}$ and reward function $r^{\text{CB}}:{\mathcal{G}}\times\mathcal{A}^{\text{CB}}\to\mathbb{R}$ for a MILP instance as follows.

• •

  The state space $\mathcal{G}$, or context vector space, also known as the context vector space, is the set of graph representations of MILP instances.

• •

  An action $a^{\text{CB}}=(V^{\text{CB}},E^{\text{CB}},W^{\text{CB}})\in\mathcal{A}^{\text{CB}}$, where $V^{\text{CB}}$, $E^{\text{CB}}$ and $W^{\text{CB}}$ are the subsets of variables, edges, and constraints to mask, respectively. The agent applies action $a^{\text{CB}}$ to an instance graph $G$ to obtain an augmented instance graph $\Phi(G)$. After that, we collect branching samples on it.

• •

  The reward $r^{\text{CB}}(G,a^{\text{CB}})$ is defined to be the average loss of branching policy under the samples collected from the augmented graph $\Phi(G)$ from $G$.

We describe the training process for the augmenter policy network $\Phi_{\eta}$ with parameters $\eta$ under the contextual bandit formulation as follows. In practice, the augmenter policy network takes as input an instance graph and outputs the masking probability of each node and edge. We select an action and record the predicted probability, i.e., $a^{\text{CB}}=\max_{a}\Phi_{\eta}(a|G)$. We leverage a learnable state-value function $V_{\alpha}:\mathcal{G}\to\mathbb{R}$ with parameters $\alpha$ to calculate the variance-reduced estimation of the advantage function $\hat{A}=r^{\text{CB}}-V_{\alpha}(G)$. In order to improve the training efficiency of the augmenter, we use a replay buffer $\mathcal{B}$ consisting of the tuples $(G,\hat{A},\Phi_{\eta}(a^{\text{CB}}|G))$ under the history augmentation policy for performing experience replay. We use $\lambda(\eta)=\frac{\Phi_{\eta_{\text{current}}}(a^{\text{CB}}|G)}{\Phi_{\eta_{\text{old}}}(a^{\text{CB}}|G)}$ to represent the probability proportion of the current policy and old policies sampled from the buffer. Finally, we reach the training objective of the adversarial augmenter, which includes the policy network and state-value function, by minimizing

where $\epsilon$ is the clip ratio. We show in Table VII that the sample-efficient bandit algorithm plays a vital role in the overall training process.

The adversarial augmenter tends to produce instances quite different from the original distribution, leading to some extremely easy or hard instances. This is because the training objective is to maximize the loss of the GNN on the augmented data, but the augmenter does not receive any restrictions on the augmentation. Thus, the augmenter may ignore the distribution information and just produce some hard OOD instances, which might break the MILP problem structures. To address this problem, we leverage a discriminator network $D_{\psi}$ to identify and remove those instances that severely deviate from the original distribution.

We instantiate the discriminator using a graph convolutional encoder and an MLP decoder. The graph encoder extracts the structure information of the MILP instance and the decoder predicts the probability that the instance is from the original distribution or not. To train the discriminator, we minimize the objective

When inference, the discriminator takes as input the augmented graph and decides to use the instance for training the GNN when $D(G)>0.5$ and discard it otherwise. Moreover, we use an additional regularized reward for the GNN, i.e.,

to control the augmentation, where $\beta=0.01$ is a constant.

We provide the pseudo-code for the AdaSolver framework in Algorithm 1.

We evaluate the performance of our proposed AdaSolver on four widely used benchmarks of NP-hard synthesis problem families and a challenging real-world Anonymous dataset. The synthesis datasets include the set covering, combinatorial auctions, capacitated facility location and maximum independent set. We follow the conventional data generation settings in [10], [26] and [27]. In each benchmark, we generate $10000$ training instances and $2000$ validation instances for AdaSolver. For the final evaluation, we generate an in-distribution testing set of 32 instances $D_{1}$, and five transfer sets $D_{2}-D_{6}$ of 32 instances with larger scales. We emphasize that the instance scales in the transfer datasets increase in order and the maximum scale of the dataset is much larger than that in the previous works. The Anonymous dataset is a well-recognized real-world dataset consisting of a curated subset of the challenge MILPLIB library. It consists of large-scale instances with 98 for training, 20 for validation and 20 for testing. The instances in the Anonymous dataset have an average of 49603 constraints and 37881 variables.

We report the instances’ scale for each benchmark in Table I. Due to the limited space, More information about benchmarks and instance generation for the synthesis datasets can be found in Appendix C.

We report the average solving time (Time, lower is better) and primal-dual integral (PD integral, lower is better) for different branching approaches for the comparative experiments. For more details on the PD integral metric, please see Appendix A.3. Moreover, we provide more results in terms of another two well-recognized metrics, i.e., the average branching nodes (Node) and the average primal-dual gap (PD gap, lower is better) in Appendix E.1.

Following [12], we mainly focus on the Time metric in the distributions where the solver can solve all the instances within the time limit since the solving time is the most direct metric to reflect the solving efficiency. However, the average solving time is almost the same for the distributions where the solvers cannot solve out most of the instances within the limited time. As a result, it is hard to tell which method has the best performance thus the solving time metric is not suitable in these distributions. So we focus on another well-recognized metric primal-dual integral in these distributions instead. Given a time limit, the lower primal-dual integral implies the better quality of the found feasible solutions by the solver. Specifically, we focus on the Time metric on $D_{1}-D_{2}$ for the synthesis benchmarks, $D_{3}$ for the combinatorial auctions and capacitated facility location benchmarks. We focus on the primal-dual integral on the other distributions.

The Node metric reflects the size of B&B searching trees. When the solver solves out an instance, fewer explored nodes imply a more efficient searching policy.

Our baselines include a SCIP branching rule and six learning-based branchers containing the competitive IL-based and RL-based approaches. The SCIP branching rule is the traditional state-of-the-art reliability pseudo-cost (RPB) branching heuristic. We then introduce the learning-based branching baselines. SVMRank [9] uses a support vector machine for learning to select the branching variables. Trees [48] is a branching policy using ExtraTrees. LMart [49] is based on LambdaMART. tMDP+DFS is a reinforcement learning method based on tree MDP [11]. TreeGate is a tree search branching approach [36] trained with imitation learning. GNN is the graph neural network approach for learning to branch [10]. Finally, we build our AdaSolver framework on the IL-based GNN branching policy [10] (GNN) and RL-based GNN branching policy (tMDP+DFS) [11], resulting in two methods AdaSolver-IL and AdaSolver-RL. As stated in [11], the RL-based method performs worse than RPB or the IL-based baselines. For RL-based setting, we thus mainly focus on the improvement of AdaSovler-RL over the underlying RL-based solvers.

Throughout all experiments, the backend solver is the state-of-the-art open-source solver SCIP 7.0.3. The solving time limit on a testing instance is 900s. Similar to [10, 26, 27], we deactivate solver restarts and allow employing cutting plane generation module only at the root node. We keep all the other SCIP parameters to default so as to better observe the improvements from AdaSolver and make comparisons of these approaches as fair.

For model training, we use Adam optimizer [50] to optimize the model parameters. When training AdaSolver, the adversarial augmenter randomly chooses training instances to perform augmentation in each training epoch. We then collect branching samples from the augmented instances. We choose the augmentation operators that perform the best for each benchmark. More details for these baselines and our AdaSolver are available in Appendix D.

We evaluate the generalization ability of AdaSolver and compare it to other baselines on four benchmarks of generated datasets (see Table II). According to Table II, our AdaSolver-IL consistently outperforms the baselines in the four synthesis benchmarks in terms of Time or PD Integral metric. AdaSolver-RL has a significant improvement over the underlying RL-based solver. Please refer to Appendix E.1 for results in terms of Nodes and PD gap metrics.

In the easier distributions $D_{1}$ and $D_{2}$, AdaSolver-IL achieves the shortest solving time and outperforms all the baselines. The GNN is a competitive baseline that outperforms other learning-based baselines on much of the distributions $D_{1}$ and $D_{2}$ of the four benchmarks. While LambdaMart is another promising learning-based baseline with stable performance. Compared to GNN, AdaSolver-IL achieves 27.66% improvement of solving time on the $D_{1}$ and $D_{2}$, leading to a total of 39.06% acceleration over the RPB heuristics. AdaSolver-RL improves the solving time of tMDP+DFS up to 12.12%. The results demonstrate that the AdaSolver is effective in improving the performance in the in-distribution or minor out-of-distribution situations.

In the harder distributions $D_{3}-D_{6}$, AdaSolver still significantly outperforms other baselines with the lowest PD integral, leading to an improvement of 11.12% over GNN and 13.15% over tMDP+DFS. This demonstrates that AdaSolver can consistently enhance the generalization ability of the underlying solvers to instances with over five times to ten times larger scales.

We summarize the improvement of AdaSolver over the underlying learning-based solver GNN and tMDP+DFS in Table III, demonstrating the effectiveness of AdaSolver.

To evaluate the performance in real-world applications, we deploy AdaSolver to a large-scale real-world Anonymous dataset, a widely-used subset of the MILPLIB library. The instances’ constraint number in the Anonymous dataset ranges from 3375 to 159823, and the variable number ranges from 1613 to 92261. The wide range of problem scales as well as real-world perturbations pose significant challenges for the learning-based methods. The results are summarized in Table IV, which demonstrates that AdaSolver is able to improve the performance of the underlying solvers both in IL and RL settings. AdaSolver-IL can reach the best PD gap and AdaSolver-RL has the best PD integral metric. The performance of AdaSolver sheds light on the generalizable neural solvers in real-world applications.

We compare AdaSolver with its variance that uses reinforce algorithm to train the augmenter (AdaSolver-REINFORCE) in Table VII. The AdaSolver outperforms AdaSolver-REINFORCE in all distributions of the set covering and combinatorial auctions benchmarks. It is well-known that PPO is much more sample-efficient than reinforce, and AdaSolver further improves the performance using the sample-efficient training method.