Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning

Taoan HuangAaron M. FerberYuandong TianBistra DilkinaBenoit Steiner

article2023ICML45 citationsOutstanding Paper Award at the ICML 2023 SODS Workshop (top-2 paper)

Proposes a contrastive learning framework, CL-LNS, that trains graph attention networks on positive and negative neighborhood samples from local branching to learn fast, high-quality destroy heuristics for Large Neighborhood Search in integer linear programming.

Listen

Many complex organizational problems—including supply chain routing, facility location, and resource scheduling—are formulated as Integer Linear Programs. Standard exact solvers, which rely on tree-search algorithms, frequently struggle to scale to large problem instances within practical time limits. While Large Neighborhood Search provides a fast heuristic alternative by iteratively freezing most decision variables and reoptimizing small subsets, existing methods rely on rules that are either too slow to compute or ineffective at choosing which variables to reoptimize.

The main objective of the article is to design and evaluate a machine learning approach, called CL-LNS, that uses contrastive learning to train fast, high-quality variable selection policies for Large Neighborhood Search. The article demonstrates that this approach finds significantly better solutions faster than existing standard and learning-based solvers across multiple problem classes.

The authors evaluated the framework across four benchmark optimization domains: minimum vertex cover, maximum independent set, combinatorial auctions, and set covering. Models were trained on relatively small problem instances by gathering positive solution samples from intermediate solver states and negative samples generated through controlled random perturbations. The selection policy was parameterized using graph attention networks enriched with root-node search features, and then tested against five established solvers and learning baselines across both standard problem sizes and larger out-of-distribution instances with twice the number of variables over runtimes ranging from 15 to 60 minutes.

Across all test benchmarks, CL-LNS consistently achieved state-of-the-art anytime optimization performance. On standard test instances, it reduced the average primal gap by 32% to 42% and the average primal integral by 26% to 59% compared to the second-best approach at a 60-minute cutoff. When applied to problems twice as large as those seen during training, CL-LNS generalized effectively, reducing the primal gap by up to 94.4% and the primal integral by up to 57.1% relative to the best baseline. Furthermore, ablation experiments confirmed that using contrastive loss provided the primary performance boost, while attention networks and enriched features delivered additional cumulative speed and quality improvements.

These findings indicate that contrastive learning is an effective paradigm for accelerating complex combinatorial optimization without requiring domain-specific manual tuning. Organizations running compute-heavy operational workflows can achieve higher-quality solutions under tighter runtime budgets, lowering computational costs and improving turnaround times for time-critical planning.

Organizations seeking to accelerate large-scale integer programming workflows should consider piloting contrastive-learning-enhanced Large Neighborhood Search pipelines for recurring problem structures. Future research and development should focus on integrating these learned search heuristics into exact branch-and-bound solvers to maintain mathematical optimality guarantees and testing cross-domain generalization across distinct problem families.

The reported evaluation is subject to certain limitations, as the framework was validated on four synthetic benchmark families and does not provide theoretical guarantees of finding mathematically optimal solutions. Nevertheless, because the framework demonstrated consistent performance gains across both small and doubled instance sizes across diverse problem types, stakeholders can maintain high confidence in its ability to significantly improve heuristic solution quality on structured integer programs.

Anthropic Meta University of Southern California contrastive learning high-quality solutions inductive logic programming (ilp)integer linear programs contrastive learning large neighborhood search

arXiv: 2302.01578 facebookresearch/CL-LNS

Paper: Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon, Yoshua Bengio et al. (2018). This methodological review explains how learned policies can guide or augment discrete-optimization solvers, providing the framework for understanding CL-LNS’s learned search decisions.
Paper: Learning Combinatorial Optimization Algorithms over Graphs, Elias Boutros Khalil et al. (2017). Its graph-based learned optimization policies introduce the neural decision-making approach that CL-LNS adapts to select variables during search.
Paper: Learning to Branch with Tree MDPs, Lara Scavuzzo et al. (2022). Its learned branching policies for integer programs clarify how machine learning can guide solver variable choices, a close precursor to CL-LNS’s variable-selection policy.

No sufficiently relevant recommendations were found.

Cover for Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning

Abstract

Integer Linear Programs (ILPs) are powerful tools for modeling and solving a large number of combinatorial optimization problems. Recently, it has been shown that Large Neighborhood Search (LNS), as a heuristic algorithm, can find high-quality solutions to ILPs faster than Branch and Bound. However, how to find the right heuristics to maximize the performance of LNS remains an open problem. In this paper, we propose a novel approach, CL-LNS, that delivers state-of-the-art anytime performance on several ILP benchmarks measured by metrics including the primal gap, the primal integral, survival rates and the best performing rate. Specifically, CL-LNS collects positive and negative solution samples from an expert heuristic that is slow to compute and learns a more efficient one with contrastive learning. We use graph attention networks and a richer set of features to further improve its performance.

Knowls

Knowl 1 — CL-LNS learns an LNS destroy policy from Local Branching demonstrations
model/method
CL-LNS is a learned destroy heuristic for large neighborhood search (LNS) on binary integer linear programs. At iteration $t$ , its input is the ILP and the current incumbent feasible assignment $x^t$ ; its policy assigns a score to each variable and selects a neighborhood of variables to reoptimize while fixing all other variables to their values in $x^t$ . The selected neighborhood is repaired by solving the resulting sub-ILP, and the incumbent is updated if a better solution is found. Training uses Local Branching (LB) as an expert: LB searches for an improved solution within a Hamming-distance limit around the incumbent. CL-LNS learns to produce useful neighborhoods from this expensive expert’s demonstrations, augmented with intermediate and deliberately perturbed examples, so that neighborhood selection at test time uses the learned policy rather than repeatedly solving the LB problem.
Knowl 2 — Training examples contrast strong LB solutions with weak perturbed neighborhoods
model/method
For each training state, the authors solve the LB subproblem using the current incumbent and neighborhood size, recording the best solution and intermediate feasible solutions found by SCIP. If the best improvement is $c^T(x^t-x^{t+1})$ , an intermediate solution $x'$ is a positive example when $c^T(x^t-x')\geq \alpha_p c^T(x^t-x^{t+1})$ . At most $u_p$ positive examples are retained, choosing the largest improvements when there are too many. The experiments use $\alpha_p=0.5$ and $u_p=10$ .

To construct negative examples, start from the variable subset selected by LB and randomly replace 5% of its variables with the same number of variables outside the subset. Solve the corresponding sub-ILP; its selected subset is negative when its improvement is at most $\alpha_n$ times the best LB improvement. Collect $\kappa |S_p^t|$ negative examples, where $S_p^t$ is the positive set and $\kappa=9$ ; use $\alpha_n=0.05$ . If the current perturbation rate yields too few negatives, increase it in 5-percentage-point steps, up to 100%, and continue sampling. LB data collection uses a one-hour solve limit per state. The improvement criteria presume a minimization objective and a positive best improvement.
Knowl 3 — A bipartite graph attention network scores ILP variables
model/method
The CL-LNS policy represents an ILP as a bipartite graph with one node for each variable, one for each constraint, and an edge wherever a variable has a nonzero coefficient in a constraint. Variable, constraint, and edge features include the features used in prior ILP graph-learning work; variable features also include a window of the three most recent incumbent values and additional variable features computed at the root node of branch-and-bound.

Feature and edge embeddings are produced by two-layer MLPs with 64 hidden units per layer, ReLU activations, and embedding dimension $d=64$ . The graph network makes two attention-based message-passing rounds: constraint nodes attend to neighboring variables first, then variable nodes attend to the updated neighboring constraints. Each round uses $H=8$ attention heads. A two-layer, 64-hidden-unit MLP maps each final variable representation to a scalar, and a sigmoid produces one score in $[0,1]$ per variable.
Knowl 4 — InfoNCE contrasts each positive neighborhood against negative neighborhoods
equation
Training examples are triples $(s,S_p,S_n)$ , where $s$ is an ILP-and-incumbent state, $S_p$ is its set of positive binary neighborhood vectors, and $S_n$ is its set of negative binary neighborhood vectors. The policy $\pi_\theta(s)\in[0,1]^n$ scores the $n$ ILP variables, and a neighborhood vector $a\in\{0,1\}^n$ indicates which variables are selected. CL-LNS minimizes the supervised contrastive InfoNCE loss, using dot products as the similarity measure:
$\mathcal{L}(\theta)=\sum_{(s,S_p,S_n)\in D}-\frac{1}{|S_p|}\sum_{a\in S_p}\log\frac{\exp(a^T\pi_\theta(s)/\tau)}{\sum_{a'\in S_n\cup\{a\}}\exp(a'^T\pi_\theta(s)/\tau)}.$
Here $D$ is the collected training set, $\theta$ denotes the policy parameters, and the temperature is $\tau=0.07$ in the experiments. The loss encourages the policy scores to align with each positive neighborhood relative to the negative neighborhoods. The policy is trained with Adam at learning rate $10^{-3}$ , batch size 32, for 30 epochs.
Knowl 5 — Greedy score ranking selects neighborhoods, with sampling as a repetition fallback
model/method
At test time, CL-LNS ranks the variable scores produced by its policy and selects the $k^t$ highest-scoring variables for reoptimization. It uses an adaptive neighborhood size: if an LNS iteration improves the incumbent, keep the size; otherwise increase it to $\min(\gamma k^t,\beta n)$ , where $n$ is the number of variables. The experiments use $\gamma=1.02$ and $\beta=0.5$ .

If the neighborhood has reached its upper bound and deterministic top-score selection repeats a previous neighborhood, CL-LNS switches to sequential weighted sampling without replacement. At each selection step, an unselected variable $i$ is sampled with probability proportional to $v_i^\eta$ , where $v_i$ is its policy score and $\eta=0.5$ . The initial neighborhood size is tuned for each problem and approach.

Knowl 6 — Evaluation covers four ILP benchmarks and two instance sizes

experimental setup

Evaluation uses minimum vertex cover (MVC), maximum independent set (MIS), combinatorial auction (CA), and set covering (SC). There are 100 test instances per problem at each size. MVC instances use Barabási–Albert graphs (1,000 nodes, average degree 70 at small size); MIS uses Erdős–Rényi graphs (6,000 nodes, average degree 5); small CA instances use 2,000 items and 4,000 bids; small SC instances use 4,000 variables and 5,000 constraints. Large instances double the number of variables. The reported average test-instance dimensions are:

	MVC-S	MIS-S	CA-S	SC-S	MVC-L	MIS-L	CA-L	SC-L
Variables	1,000	6,000	4,000	4,000	2,000	12,000	8,000	8,000
Constraints	65,100	23,977	2,675	5,000	135,100	48,027	5,353	5,000

For each problem, separate policies are trained on 1,024 small instances, split into 896 training and 128 validation instances, and tested on both sizes. SCIP 8.0.1 supplies the initial solution after 10 seconds and solves each LNS repair subproblem with a two-minute limit; each test instance has a 60-minute runtime cutoff. The main comparisons are SCIP branch-and-bound (BnB), random LNS, LB-RELAX, imitation-learning IL-LNS, and reinforcement-learning RL-LNS. Experiments run on 2.5 GHz Intel Xeon Platinum 8259CL CPUs with 32 GB memory; training uses an NVIDIA A100 GPU with 40 GB memory.

Knowl 7 — At 60 minutes CL-LNS has the best mean primal gap and primal integral

data/table

The table compares CL-LNS with the strongest non-CL-LNS result for each metric and benchmark at the 60-minute cutoff. Primal gap (PG) is reported in percent; primal integral (PI) measures the accumulated primal gap over runtime, so lower values indicate better solution quality and/or faster improvement. Each entry is the mean and standard deviation over 100 test instances. Learned policies were trained only on small instances; the large-instance results therefore measure size generalization.

Benchmark	CL-LNS PG (%)	Best other PG (%)	CL-LNS PI	Best other PI
MVC-S	$0.17\pm0.09$	IL-LNS: $0.29\pm0.23$	$8.7\pm6.7$	IL-LNS: $19.2\pm10.2$
MIS-S	$0.15\pm0.15$	IL-LNS: $0.22\pm0.17$ ; RL-LNS: $0.22\pm0.14$	$12.8\pm5.4$	RL-LNS: $17.2\pm5.2$
CA-S	$0.65\pm0.32$	IL-LNS: $1.09\pm0.51$	$50.7\pm22.7$	IL-LNS: $90.0\pm20.8$
SC-S	$0.50\pm0.58$	LB-RELAX: $0.86\pm0.83$	$26.2\pm12.8$	LB-RELAX: $63.2\pm31.6$ ; IL-LNS: $63.2\pm34.3$
MVC-L	$0.05\pm0.04$	IL-LNS: $0.27\pm0.23$	$9.1\pm3.4$	IL-LNS: $21.2\pm8.1$
MIS-L	$0.12\pm0.11$	RL-LNS: $0.14\pm0.12$	$12.9\pm4.4$	RL-LNS: $18.9\pm4.1$
CA-L	$0.09\pm0.10$	LB-RELAX: $1.61\pm1.50$	$116.1\pm18.0$	RL-LNS: $197.0\pm28.5$
SC-L	$0.58\pm0.45$	RL-LNS: $0.66\pm0.72$	$39.2\pm23.2$	IL-LNS: $79.1\pm42.4$

CL-LNS has the lowest mean PG and PI in all eight test sets. The authors report that on small instances it reduces average PG by 32%–42% and average PI by 26%–59% relative to the second-best approach at 60 minutes; on large instances, the corresponding reductions reach 94.4% and 57.1%.

Knowl 8 — CL-LNS reaches low-gap solutions quickly across most survival tests
empirical result
On 100 test instances per benchmark, the authors measure survival rate as the fraction of instances whose primal gap falls below 1.00% by a given runtime. At the 60-minute cutoff, CL-LNS has the highest survival rate on every test set except SC-L, where RL-LNS finishes slightly higher; CL-LNS reaches the target in substantially less time on SC-L. On MVC-L, MIS-S, and MIS-L, some baselines eventually match CL-LNS's survival rate, but CL-LNS reaches those rates sooner. A separate best-performing-rate metric counts, including ties, the fraction of instances on which an approach has the lowest primal gap at a runtime cutoff. CL-LNS is best on 50%–100% of small-instance cases and has the highest rate in most large-instance cases.

Knowl 9 — Ablations show contrastive training and richer features improve results

empirical result

An ablation on MVC-S and CA-S compares imitation versus contrastive training and varies the graph network and feature set. “PF” denotes the partial feature set used by IL-LNS; “FF” adds the richer variable features used by CL-LNS. PG is in percent and PI is measured at a 60-minute cutoff; entries are means and standard deviations across 100 test instances.

	MVC-S PG	MVC-S PI	CA-S PG	CA-S PI
IL-LNS (GCN, PF)	$0.29\pm0.23$	$19.2\pm10.2$	$1.09\pm0.51$	$90.0\pm20.8$
IL-LNS (GAT, FF)	$0.24\pm0.17$	$15.3\pm7.3$	$1.13\pm0.63$	$78.9\pm22.7$
CL-LNS (GCN, PF)	$0.17\pm0.10$	$11.4\pm8.8$	$0.75\pm0.40$	$57.9\pm21.2$
CL-LNS (GAT, PF)	$0.16\pm0.09$	$10.1\pm0.6$	$0.76\pm0.39$	$53.8\pm22.1$
CL-LNS (GAT, FF)	$0.17\pm0.09$	$8.7\pm6.7$	$0.65\pm0.32$	$50.7\pm22.7$

Imitation learning with GAT and richer features remains worse than contrastive learning with GCN and partial features, supporting the contribution of the contrastive objective. Comparing the partial-feature contrastive variants, GAT improves PI over GCN. Adding the richer features to the full CL-LNS gives the best CA-S PG and PI and the best MVC-S PI among these variants.

Knowl 10 — The method neither guarantees optimality nor establishes cross-domain transfer
limitation
CL-LNS is an LNS heuristic and does not guarantee that it finds an optimal ILP solution. The experiments train a separate policy for each of four problem domains. They demonstrate generalization to instances with twice as many variables as the training instances, but do not establish that one learned policy transfers across different problem domains. The authors identify cross-domain policy generalization and integration of CL-LNS into branch-and-bound as future directions.

Coverage note — The detailed per-iteration comparison with the LB expert, intermediate runtime-cutoff tables, and appendix comparisons involving LB, GRAPH, and gap-to-virtual-best are omitted as supporting diagnostics; the principal benchmark, generalization, and ablation results are retained.

References

1.Achterberg, T., Berthold, T., and Hendel, G. Rounding and propagation heuristics for mixed integer programming. In Operations research proceedings 2011, pp. 71–76. Springer, 2012.
2.Albert, R. and Barabasi, A.-L. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
3.Amaral, A. R. An exact approach to the one-dimensional facility layout problem. Operations research, 56(4):1026–1033, 2008.
4.Amizadeh, S., Matusevych, S., and Weimer, M. Learning to solve circuit-sat: An unsupervised differentiable approach. In International Conference on Learning Representations, 2018.
5.Azi, N., Gendreau, M., and Potvin, J.-Y. An adaptive large neighborhood search for a vehicle routing problem with multiple routes. Computers & Operations Research, 41:167–173, 2014.
6.Berthold, T. Primal heuristics for mixed integer programs. PhD thesis, Zuse Institute Berlin (ZIB), 2006.
7.Berthold, T. Rens. Mathematical Programming Computation, 6(1):33–54, 2014.
8.Bestuzheva, K., Besançon, M., Chen, W.-K., Chmiela, A., Donkiewicz, T., van Doornmalen, J., Eifler, L., Gaul, O., Gamrath, G., Gleixner, A., Gottwald, L., Graczyk, C., Halbig, K., Hoen, A., Hojny, C., van der Hulst, R., Koch, T., Lubbecke, M., Maher, S. J., Matter, F., Muhmer, E., Müller, B., Pfetsch, M. E., Rehfeldt, D., Schlein, S., Schlosser, F., Serrano, F., Shinano, Y., Sofranac, B., Turner, M., Vigerske, S., Wegscheider, F., Wellner, P., Weninger, D., and Witzig, J. The SCIP Optimization Suite 8.0. Technical report, Optimization Online, December 2021. URL http://www.optimization-online.org/DB_HTML/2021/12/8728.html.
9.Brody, S., Alon, U., and Yahav, E. How attentive are graph attention networks? International conference on learning representations, 2022.
10.Chen, T., Kornblith, S., Norouzi, M., and Hinton, G. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pp. 1597–1607. PMLR, 2020.
11.Chen, X. and Tian, Y. Learning to perform local rewriting for combinatorial optimization. Advances in Neural Information Processing Systems, 32, 2019.
12.Chmiela, A., Khalil, E., Gleixner, A., Lodi, A., and Pokutta, S. Learning to schedule heuristics in branch and bound. Advances in Neural Information Processing Systems, 34:24235–24246, 2021.
13.Cplex, I. I. V12. 1: User’s manual for cplex. International Business Machines Corporation, 46(53):157, 2009.
14.Danna, E., Rothberg, E., and Pape, C. L. Exploring relaxation induced neighborhoods to improve mip solutions. Mathematical Programming, 102(1):71–90, 2005.
15.De Vries, S. and Vohra, R. V. Combinatorial auctions: A survey. INFORMS Journal on computing, 15(3):284–309, 2003.
16.Dilkina, B. and Gomes, C. P. Solving connected subgraph problems in wildlife conservation. In CPAIOR, volume 6140, pp. 102–116. Springer, 2010.
17.Duan, H., Vaezipoor, P., Paulus, M. B., Ruan, Y., and Maddison, C. Augment with care: Contrastive learning for combinatorial problems. In International Conference on Machine Learning, pp. 5627–5642. PMLR, 2022.
18.Erdos, P., Renyi, A., et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17–60, 1960.
19.Eysenbach, B., Zhang, T., Levine, S., and Salakhutdinov, R. R. Contrastive learning as goal-conditioned reinforcement learning. Advances in Neural Information Processing Systems, 35:35603–35620, 2022.
20.Ferber, A., Song, J., Dilkina, B., and Yue, Y. Learning pseudo-backdoors for mixed integer programs. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 91–102. Springer, 2022.
21.Fischetti, M. and Lodi, A. Local branching. Mathematical programming, 98(1):23–47, 2003.
22.Gasse, M., Chetelat, D., Ferroni, N., Charlin, L., and Lodi, A. Exact combinatorial optimization with graph convolutional neural networks. Advances in Neural Information Processing Systems, 32, 2019.
23.Ghosh, S. Dins, a mip improvement heuristic. In International Conference on Integer Programming and Combinatorial Optimization, pp. 310–323. Springer, 2007.
24.Gupta, P., Gasse, M., Khalil, E., Mudigonda, P., Lodi, A., and Bengio, Y. Hybrid models for learning to branch. Advances in neural information processing systems, 33:18087–18097, 2020.
25.Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2022. URL https://www.gurobi.com.
26.He, H., Daume III, H., and Eisner, J. M. Learning to search in branch and bound algorithms. Advances in neural information processing systems, 27, 2014.
27.He, K., Fan, H., Wu, Y., Xie, S., and Girshick, R. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 9729–9738, 2020.
28.Hendel, G. Adaptive large neighborhood search for mixed integer programming. Mathematical Programming Computation, 14(2):185–221, 2022.
29.Heragu, S. S. and Kusiak, A. Efficient models for the facility layout problem. European Journal of Operational Research, 53(1):1–13, 1991.
30.Hjelm, R. D., Fedorov, A., Lavoie-Marchildon, S., Grewal, K., Bachman, P., Trischler, A., and Bengio, Y. Learning deep representations by mutual information estimation and maximization. International conference on learning representations, 2019.
31.Hottung, A. and Tierney, K. Neural large neighborhood search for the capacitated vehicle routing problem. In ECAI 2020, pp. 443–450. IOS Press, 2020.
32.Hu, Y., Yao, Y., and Lee, W. S. A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs. Knowledge-Based Systems, 204:106244, 2020.
33.Huang, T. and Dilkina, B. Enhancing seismic resilience of water pipe networks. In Proceedings of the 3rd ACM SIGCAS Conference on Computing and Sustainable Societies, pp. 44–52, 2020.
34.Huang, T., Dilkina, B., and Koenig, S. Learning node-selection strategies in bounded suboptimal conflict-based search for multi-agent path finding. In International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2021a.
35.Huang, T., Koenig, S., and Dilkina, B. Learning to resolve conflicts for multi-agent path finding with conflict-based search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 11246–11253, 2021b.
36.Huang, T., Li, J., Koenig, S., and Dilkina, B. Anytime multi-agent path finding via machine learning-guided large neighborhood search. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 9368–9376, 2022a.
37.Huang, T., Ferber, A., Tian, Y., Dilkina, B., and Steiner, B. Local branching relaxation heuristics for integer linear programs. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 96–113. Springer, 2023a.
38.Huang, T., Shivashankar, V., Caldara, M., Durham, J., Li, J., Dilkina, B., and Koenig, S. Deadline-aware multi-agent tour planning. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), 2023b.
39.Huang, Z., Wang, K., Liu, F., Zhen, H.-L., Zhang, W., Yuan, M., Hao, J., Yu, Y., and Wang, J. Learning to select cuts for efficient mixed-integer programming. Pattern Recognition, 123:108353, 2022b.
40.Johnson, D. S., Lenstra, J. K., and Kan, A. R. The complexity of the network design problem. Networks, 8(4):279–285, 1978.
41.Khalil, E., Le Bodic, P., Song, L., Nemhauser, G., and Dilkina, B. Learning to branch in mixed integer programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
42.Khalil, E., Dai, H., Zhang, Y., Dilkina, B., and Song, L. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017a.
43.Khalil, E. B., Dilkina, B., Nemhauser, G. L., Ahmed, S., and Shao, Y. Learning to run heuristics in tree search. In Ijcai, pp. 659–666, 2017b.
44.Khosla, P., Teterwak, P., Wang, C., Sarna, A., Tian, Y., Isola, P., Maschinot, A., Liu, C., and Krishnan, D. Supervised contrastive learning. Advances in Neural Information Processing Systems, 33:18661–18673, 2020.
45.Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. 2015.
46.Kool, W., Van Hoof, H., and Welling, M. Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475, 2018.
47.Kovacs, A. A., Parragh, S. N., Doerner, K. F., and Hartl, R. F. Adaptive large neighborhood search for service technician routing and scheduling problems. Journal of scheduling, 15(5):579–600, 2012.
48.Labassi, A. G., Chetelat, D., and Lodi, A. Learning to compare nodes in branch and bound with graph neural networks. Advances in neural information processing systems, 2022.
49.Land, A. H. and Doig, A. G. An automatic method for solving discrete programming problems. In 50 Years of Integer Programming 1958-2008, pp. 105–132. Springer, 2010.
50.Leyton-Brown, K., Pearson, M., and Shoham, Y. Towards a universal test suite for combinatorial auction algorithms. In Proceedings of the 2nd ACM conference on Electronic commerce, pp. 66–76, 2000.
51.Li, J., Chen, Z., Harabor, D., Stuckey, P. J., and Koenig, S. Anytime multi-agent path finding via large neighborhood search. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 4127–4135, 2021a.
52.Li, J., Chen, Z., Harabor, D., Stuckey, P. J., and Koenig, S. MAPF-LNS2: Fast repairing for multi-agent path finding via large neighborhood search. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 10256–10265, 2022.
53.Li, S., Yan, Z., and Wu, C. Learning to delegate for large-scale vehicle routing. Advances in Neural Information Processing Systems, 34:26198–26211, 2021b.
54.Li, Z., Chen, Q., and Koltun, V. Combinatorial optimization with graph convolutional networks and guided tree search. Advances in neural information processing systems, 31, 2018.
55.Liu, D., Fischetti, M., and Lodi, A. Learning to search in local branching. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 3796–3803, 2022.
56.Lu, H., Zhang, X., and Yang, S. A learning-based iterative method for solving vehicle routing problems. In International conference on learning representations, 2020.
57.Maher, S. J., Fischer, T., Gally, T., Gamrath, G., Gleixner, A., Gottwald, R. L., Hendel, G., Koch, T., Lubbecke, M., Miltenberger, M., et al. The scip optimization suite 4.0. 2017.
58.Manne, A. S. On the job-shop scheduling problem. Operations research, 8(2):219–223, 1960.
59.Mulamba, M., Mandi, J., Diligenti, M., Lombardi, M., Lopez, V. B., and Guns, T. Contrastive losses and solution caching for predict-and-optimize. In 30th International Joint Conference on Artificial Intelligence, pp. 2833. International Joint Conferences on Artificial Intelligence, 2021.
60.Oord, A. v. d., Li, Y., and Vinyals, O. Representation learning with contrastive predictive coding. arXiv preprint arXiv:1807.03748, 2018.
61.Paulus, M. B., Zarpellon, G., Krause, A., Charlin, L., and Maddison, C. Learning to cut by looking ahead: Cutting plane selection via imitation learning. In International conference on machine learning, pp. 17584–17600. PMLR, 2022.
62.Pohl, I. Heuristic search viewed as path finding in a graph. Artificial intelligence, 1(3-4):193–204, 1970.
63.Prouvost, A., Dumouchelle, J., Scavuzzo, L., Gasse, M., Chetelat, D., and Lodi, A. Ecole: A gym-like library for machine learning in combinatorial optimization solvers. In Learning Meets Combinatorial Algorithms at NeurIPS2020, 2020. URL https://openreview.net/forum?id=IVc9hqgibyB.
64.Ropke, S. and Pisinger, D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation science, 40(4):455–472, 2006.
65.Rothberg, E. An evolutionary algorithm for polishing mixed integer programming solutions. INFORMS Journal on Computing, 19(4):534–541, 2007.
66.Scavuzzo, L., Chen, F. Y., Chetelat, D., Gasse, M., Lodi, A., Yorke-Smith, N., and Aardal, K. Learning to branch with tree mdps. arXiv preprint arXiv:2205.11107, 2022.
67.Selsam, D., Lamm, M., Bunz, B., Liang, P., de Moura, L., and Dill, D. L. Learning a sat solver from single-bit supervision. arXiv preprint arXiv:1802.03685, 2018.
68.Smith, S. L. and Imeson, F. Glns: An effective large neighborhood search heuristic for the generalized traveling salesman problem. Computers & Operations Research, 87:1–19, 2017.
69.Song, J., Yue, Y., Dilkina, B., et al. A general large neighborhood search framework for solving integer linear programs. Advances in Neural Information Processing Systems, 33:20012–20023, 2020.
70.Sonnerat, N., Wang, P., Ktena, I., Bartunov, S., and Nair, V. Learning a large neighborhood search algorithm for mixed integer programs. arXiv preprint arXiv:2107.10201, 2021.
71.Tang, Y., Agrawal, S., and Faenza, Y. Reinforcement learning for integer programming: Learning to cut. In International conference on machine learning, pp. 9367–9376. PMLR, 2020.
72.Tian, Y. Understanding deep contrastive learning via coordinate-wise optimization. In Advances in Neural Information Processing Systems, 2022.
73.Tong, Z., Liang, Y., Ding, H., Dai, Y., Li, X., and Wang, C. Directed graph contrastive learning. Advances in Neural Information Processing Systems, 34:19580–19593, 2021.
74.Toth, P. and Vigo, D. The vehicle routing problem. SIAM, 2002.
75.Wu, Y., Song, W., Cao, Z., and Zhang, J. Learning large neighborhood search policy for integer programming. Advances in Neural Information Processing Systems, 34:30075–30087, 2021.
76.Xin, L., Song, W., Cao, Z., and Zhang, J. Neurolkh: Combining deep learning model with lin-kernighan-helsgaun heuristic for solving the traveling salesman problem. Advances in Neural Information Processing Systems, 34:7472–7483, 2021.
77.You, Y., Chen, T., Sui, Y., Chen, T., Wang, Z., and Shen, Y. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 33:5812–5823, 2020.
78.Yu, C., Li, Q., Gao, S., and Prorok, A. Accelerating multi-agent planning using graph transformers with bounded suboptimality. arXiv preprint arXiv:2301.08451, 2023.
79.Zarpellon, G., Jo, J., Lodi, A., and Bengio, Y. Parameterizing branch-and-bound search trees to learn branching policies. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 3931–3939, 2021.
80.Zhang, S., Li, J., Huang, T., Koenig, S., and Dilkina, B. Learning a priority ordering for prioritized planning in multi-agent path finding. In Proceedings of the International Symposium on Combinatorial Search, volume 15, pp. 208–216, 2022.
81.Zheng, J., He, K., Zhou, J., Jin, Y., and Li, C.-M. Combining reinforcement learning with lin-kernighan-helsgaun algorithm for the traveling salesman problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 12445–12452, 2021.
82.Zulj, I., Kramer, S., and Schneider, M. A hybrid of adaptive large neighborhood search and tabu search for the order-batching problem. European Journal of Operational Research, 264(2):653–664, 2018.

Citation

MLA

Huang, T., et al. “Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning”. International Conference on Machine Learning, vol. 202, 2023, pp. 13869–90, https://proceedings.mlr.press/v202/huang23g.html.

APA

Huang, T., Ferber, A. M., Tian, Y., Dilkina, B., & Steiner, B. (2023). Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning. International Conference on Machine Learning, 202, 13869–13890. https://proceedings.mlr.press/v202/huang23g.html

Chicago

Huang, T., A. M. Ferber, Y. Tian, B. Dilkina, and B. Steiner. 2023. “Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning”. International Conference on Machine Learning 202: 13869–90. https://proceedings.mlr.press/v202/huang23g.html.

Harvard

Huang, T. et al. (2023) “Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning”, International Conference on Machine Learning. PMLR, pp. 13869–13890. Available at: https://proceedings.mlr.press/v202/huang23g.html.

Vancouver

1. Huang T, Ferber AM, Tian Y, Dilkina B, Steiner B (2023) Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning. In: International Conference on Machine Learning. PMLR, pp 13869–13890

BibTeX

@InProceedings{pmlr-v202-huang23g,
  title = 	 {Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning},
  author =       {Huang, Taoan and Ferber, Aaron M and Tian, Yuandong and Dilkina, Bistra and Steiner, Benoit},
  booktitle = 	 {Proceedings of the 40th International Conference on Machine Learning},
  pages = 	 {13869--13890},
  year = 	 {2023},
  editor = 	 {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan},
  volume = 	 {202},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {23--29 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v202/huang23g/huang23g.pdf},
  url = 	 {https://proceedings.mlr.press/v202/huang23g.html},
  abstract = 	 {Integer Linear Programs (ILPs) are powerful tools for modeling and solving a large number of combinatorial optimization problems. Recently, it has been shown that Large Neighborhood Search (LNS), as a heuristic algorithm, can find high-quality solutions to ILPs faster than Branch and Bound. However, how to find the right heuristics to maximize the performance of LNS remains an open problem. In this paper, we propose a novel approach, CL-LNS, that delivers state-of-the-art anytime performance on several ILP benchmarks measured by metrics including the primal gap, the primal integral, survival rates and the best performing rate. Specifically, CL-LNS collects positive and negative solution samples from an expert heuristic that is slow to compute and learns a more efficient one with contrastive learning. We use graph attention networks and a richer set of features to further improve its performance.}
}

Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning

Abstract

Topics

Keywords

Knowls

Knowl 1 — CL-LNS learns an LNS destroy policy from Local Branching demonstrations

Knowl 2 — Training examples contrast strong LB solutions with weak perturbed neighborhoods

Knowl 3 — A bipartite graph attention network scores ILP variables

Knowl 4 — InfoNCE contrasts each positive neighborhood against negative neighborhoods

Knowl 5 — Greedy score ranking selects neighborhoods, with sampling as a repetition fallback