Mixed-Integer Linear Optimization via Learning-Based Two-Layer Large Neighborhood Search
Wenbo Liu, Akang Wang, Wenguo Yang, Qingjiang Shi · 2024
Read Mixed-Integer Linear Optimization via Learning-Based Two-Layer Large Neighborhood Search by Wenbo Liu, Akang Wang, Wenguo Yang, Qingjiang Shi (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-08206.txt.
Introduction
Wenbo Liu, Akang Wang, Wenguo Yang, and Qingjiang Shi speed up a search method for mixed-integer planning problems in this 2024 paper. Large neighborhood search improves solutions by re-solving slices of the problem, but for big instances the slices themselves become costly. Learning models can guide which slices to pick.
Their two-layer scheme applies the same search idea to the auxiliary problems, so only small problems reach a standard solver. A light graph transformer informs the neighborhood design. On public benchmarks the method gained up to two thirds over plain large neighborhood search. Gains over top solvers reached even higher. The authors present the recursion as the key to scaling learning-guided search.
Catalog record
| CREATOR | Wenbo Liu, Akang Wang, Wenguo Yang, Qingjiang Shi |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-08206
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Mixed-Integer Linear Optimization via Learning-Based Two-Layer Large Neighborhood Search Wenbo Liu, Akang Wang, Wenguo Yang, Qingjiang Shi Abstract Mixed-integer linear programs (MILPs) are extensively used to model practical problems such as planning and scheduling. A prominent method for solving MILPs is large neighborhood search (LNS), which iteratively seeks improved solutions within specific neighborhoods. Recent advancements have integrated machine learning techniques into LNS to guide the construction of these neighborhoods effectively. However, for large-scale MILPs, the search step in LNS becomes a computational bottleneck, relying on off-the-shelf solvers to optimize auxiliary MILPs of substantial size. To address this challenge, we introduce a two-layer LNS (TLNS) approach that employs LNS to solve both the original MILP and its auxiliary MILPs, necessitating the optimization of only small-sized MILPs using off-the-shelf solvers. Additionally, we incorporate a lightweight graph transformer model to inform neighborhood design. We conduct extensive computational experiments using public benchmarks. The results indicate that our learning-based TLNS approach achieves remarkable performance gains–up to 66 % 66\% and 96 % 96\% over LNS and state-of-the-art MILP solvers, respectively. 1 Introduction Mixed-integer linear programs (MILPs) have become a cornerstone in various industrial applications, including network design [ 17 ] , production planning [ 19 ] , and route optimization [ 24 ] . The resolution of MILPs typically poses \mathcal{NP} -hard challenges, with general-purpose MILP solvers resorting to the branch-and-bound method for systematic enumeration of candidate solutions. However, tackling large-scale MILPs with a branch-and-bound algorithm proves computationally demanding due to its exhaustive search nature. In practical scenarios, primal heuristic methods are commonly employed to efficiently identify high-quality feasible solutions. Although these heuristics do not guarantee optimality, they consistently deliver outstanding solutions for significantly larger MILPs. One of the most prominent heuristic methods for addressing MILPs is large neighborhood search (LNS) [ 21 ] . LNS often refines an incumbent solution by iteratively constructing a neighborhood of interest and searching within such a region via optimization of auxiliary MILPs. Lots of efforts [ 2 , 4 , 5 , 11 , 20 ] have been devoted to building neighborhoods by use of heuristics, delegating the search step to off-the-shelf MILP solvers. Recently, machine learning (ML) techniques have been extensively utilized to expedite the optimization of MILPs [ 6 , 18 , 30 ] . These endeavors have been prompted by the recognition that MILPs arising from similar applications often exhibit recurrent patterns, which can be effectively captured through ML techniques. LNS also benefits from ML techniques [ 12 , 22 , 23 , 29 ] , where neighborhood construction is informed by utilizing graph neural networks (GNNs) on the graph representation of MILPs. Despite promising advancements, these learning-based LNS methods still have ample room for improvement. On one hand, while neighborhood construction shows potential for enhancement, it often overlooks improvements in the search step. On the other hand, the number of GNN layers (typically 2 ) is limited due to issues with over-smoothing [ 15 ] , rendering these applications incapable of effective message passing between distant variable nodes. Figure 1: An overview of our proposed learning-enhanced TLNS framework. The red part represents the learning-enhanced neighborhood construction stage while the green part denotes the neighborhood search stage. The purple part indicates that the presolve operator transforms the original MILP to a reduced MILP while the postsolve operator reverses the transformation. Previous efforts, in both classic and learning-enhanced settings, focused on designing effective neighborhoods, leaving the search procedure to off-the-shelf MILP solvers. However, relying on exact solvers to optimize auxiliary MILPs during the search stage could still be computationally expensive for large-sized problems. Recognizing that searching for high-quality solutions still involves optimizing MILPs, we adopt a learning-based LNS approach once more. In our method, we propose applying learning-based LNS to tackle both the original MILP and its auxiliary MILPs, which necessitates optimizing only small-sized sub-MILPs using off-the-shelf solvers. Additionally, we employ a lightweight graph transformer model to expand the receptive field of GNNs. We call this method “learning-based Two-Layer LNS” (TLNS). The overall algorithm is outlined in 1 . The distinct contributions of our work can be summarized as follows. • We introduce a novel TLNS algorithm designed to identify high-quality solutions for MILPs. Unlike traditional approaches, TLNS applies LNS to optimize not only the original MILP (outer layer) but also its auxiliary MILPs (inner layer), employing a divide-and-conquer strategy. To the best of our knowledge, this represents the first attempt to extend LNS to a multi-layer version specifically tailored for addressing MILPs. • We employ a lightweight graph transformer model trained with contrastive loss to effectively guide the construction of neighborhoods in LNS, furthermore boosting the algorithmic performance. • We conduct extensive computational experiments on public benchmarks and the results show that TLNS achieves up to 66\% and 96\% improvements over LNS and the state-of-the-art MILP solvers, respectively. The remainder of this paper is organized as follows. Section 2 introduces preliminaries along with basic techniques that will be used in our method. Section 3 presents our proposed TLNS method and how it is enhanced by ML techniques. In Section 4 , we conduct experiments to evaluate the performance of our method and finally we draw conclusions and discuss future work in Section 5 . 1.1 Related Works Traditional LNS [ 20 ] proposed to use a mutation neighborhood by fixing a random subset of integer variables at the incumbent. [ 5 ] introduced the local branching (LB) method, defining a neighborhood as a Hamming ball around the incumbent solution, while [ 11 ] proposed to utilize solutions to continuous relaxations in LB for building neighborhoods. RINS [ 4 ] constructs a promising neighborhood using information contained in the continuous relaxation of an MILP as well as the incumbent, while RENS [ 2 ] relies purely on the continuous relaxation. Though many aforementioned LNS heuristics have been deployed within MILP solvers, their computational effort makes it impractical to apply all of them frequently. One exception is the work of [ 10 ] in which the author considered eight popular LNS heuristics and proposed to adaptively select one of them for execution via online learning. Learning-based LNS The first attempt to enhance LNS with ML is [ 22 ] , in which the authors proposed to imitate the best neighborhood out of a few randomly sampled ones. Building upon this, [ 23 ] improved the imitation learning approach by employing LB as an expert. Furthermore, [ 12 ] collected both positive and negative solution samples from LB and then utilized contrastive loss to learn and construct neighborhoods. Alternatively, reinforcement learning (RL) was applied by [ 29 ] to explore a promising policy for constructing neighborhoods while [ 16 ] focused on enhancing LB and utilized RL to inform the radius of the Hamming ball. 2 Preliminaries Mixed-Integer Linear Programs An MILP is formulated as : \displaystyle\underset{x\in S}{\min} \displaystyle c^{\top}x (1) where x denotes the decision variable and S\coloneqq\left\{x\in\mathbb{Z}^{q}\times\mathbb{R}^{n-q}:Ax\leq b,l\leq x\leq u\right\} represents the feasible region for x . l,u,c\in\mathbb{R}^{n},b\in\mathbb{R}^{m} and A\in\mathbb{R}^{m\times n} are given parameters. For the sake of simplicity, we assume that all variables are binary, i.e., x_{i}\in\left\{0,1\right\}\;\forall i=1,2,...,n . Let M:=(A,b,c,l,u,q) denote an MILP instance for convenience. Large Neighborhood Search In this work, we focus