We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Batch-Wise Permutation Feature Importance Evaluation and Problem-Specific Bigraph for Learn-to-Branch.
- Authors
Niu, Yajie; Peng, Chen; Liao, Bolin
- Abstract
The branch-and-bound algorithm for combinatorial optimization typically relies on a plethora of handcraft expert heuristics, and a research direction, so-called learn-to-branch, proposes to replace the expert heuristics in branch-and-bound with machine learning models. Current studies in this area typically use an imitation learning (IL) approach; however, in practice, IL often suffers from limited training samples. Thus, it has been emphasized that a small-dataset fast-training scheme for IL in learn-to-branch is worth studying, so that other methods, e.g., reinforcement learning, may be used for subsequent training. Thus, this paper focuses on the IL part of a mixed training approach, where a small-dataset fast-training scheme is considered. The contributions are as follows. First, to compute feature importance metrics so that the state-of-the-art bigraph representation can be effectively reduced for each problem type, a batch-wise permutation feature importance evaluation method is proposed, which permutes features within each batch in the forward pass. Second, based on the evaluated importance of the bigraph features, a reduced bigraph representation is proposed for each of the benchmark problems. The experimental results on four MILP benchmark problems show that our method improves branching accuracy by 8% and reduces solution time by 18% on average under the small-dataset fast-training scheme compared to the state-of-the-art bigraph-based learn-to-branch method. The source code is available online at GitHub.
- Subjects
REINFORCEMENT learning; PERMUTATIONS; BENCHMARK problems (Computer science); MACHINE learning; SOURCE code; BILEVEL programming; COMBINATORIAL optimization; IMAGE encryption
- Publication
Electronics (2079-9292), 2022, Vol 11, Issue 14, pN.PAG
- ISSN
2079-9292
- Publication type
Article
- DOI
10.3390/electronics11142253