Learning to Search in Local Branching
- URL: http://arxiv.org/abs/2112.02195v1
- Date: Fri, 3 Dec 2021 23:54:29 GMT
- Title: Learning to Search in Local Branching
- Authors: Defeng Liu, Matteo Fischetti and Andrea Lodi
- Abstract summary: Local branching (LB) has been proposed to produce improving solutions to mixed-integer linear programming problems.
For a LB algorithm, the choice of the neighborhood size is critical to performance.
In this work, we investigate the relation between the size of the search neighborhood and the behavior of the underlying LB algorithm.
- Score: 3.3946853660795884
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Finding high-quality solutions to mixed-integer linear programming problems
(MILPs) is of great importance for many practical applications. In this
respect, the refinement heuristic local branching (LB) has been proposed to
produce improving solutions and has been highly influential for the development
of local search methods in MILP. The algorithm iteratively explores a sequence
of solution neighborhoods defined by the so-called local branching constraint,
namely, a linear inequality limiting the distance from a reference solution.
For a LB algorithm, the choice of the neighborhood size is critical to
performance. Although it was initialized by a conservative value in the
original LB scheme, our new observation is that the best size is strongly
dependent on the particular MILP instance. In this work, we investigate the
relation between the size of the search neighborhood and the behavior of the
underlying LB algorithm, and we devise a leaning based framework for guiding
the neighborhood search of the LB heuristic. The framework consists of a
two-phase strategy. For the first phase, a scaled regression model is trained
to predict the size of the LB neighborhood at the first iteration through a
regression task. In the second phase, we leverage reinforcement learning and
devise a reinforced neighborhood search strategy to dynamically adapt the size
at the subsequent iterations. We computationally show that the neighborhood
size can indeed be learned, leading to improved performances and that the
overall algorithm generalizes well both with respect to the instance size and,
remarkably, across instances.
Related papers
- Offline RL via Feature-Occupancy Gradient Ascent [9.983014605039658]
We study offline Reinforcement Learning in large infinite-horizon discounted Markov Decision Processes (MDPs)
We develop a new algorithm that performs a form of gradient ascent in the space of feature occupancies.
We show that the resulting simple algorithm satisfies strong computational and sample complexity guarantees.
arXiv Detail & Related papers (2024-05-22T15:39:05Z) - PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback [106.63518036538163]
We present a novel unified bilevel optimization-based framework, textsfPARL, formulated to address the recently highlighted critical issue of policy alignment in reinforcement learning.
Our framework addressed these concerns by explicitly parameterizing the distribution of the upper alignment objective (reward design) by the lower optimal variable.
Our empirical results substantiate that the proposed textsfPARL can address the alignment concerns in RL by showing significant improvements.
arXiv Detail & Related papers (2023-08-03T18:03:44Z) - Non-stationary Reinforcement Learning under General Function
Approximation [60.430936031067006]
We first propose a new complexity metric called dynamic Bellman Eluder (DBE) dimension for non-stationary MDPs.
Based on the proposed complexity metric, we propose a novel confidence-set based model-free algorithm called SW-OPEA.
We show that SW-OPEA is provably efficient as long as the variation budget is not significantly large.
arXiv Detail & Related papers (2023-06-01T16:19:37Z) - New Characterizations and Efficient Local Search for General Integer
Linear Programming [17.80124240223163]
This work proposes new characterizations of linear programming (ILP) with the concept of boundary solutions.
We develop a new local search algorithm Local-ILP, which is efficient for solving general ILP validated on a large heterogeneous problem dataset.
Experiments conducted on the MIPLIB dataset show the effectiveness of our algorithm in solving large-scale hard ILP problems.
arXiv Detail & Related papers (2023-04-29T07:22:07Z) - DeciLS-PBO: an Effective Local Search Method for Pseudo-Boolean
Optimization [10.513103815142731]
We find two ways to improve the local search algorithms in solving Pseudo-Boolean Optimization (PBO)
Our algorithm DeciLS-PBO has a promising performance compared to the state-of-the-art algorithms.
arXiv Detail & Related papers (2023-01-28T17:03:56Z) - Local Branching Relaxation Heuristics for Integer Linear Programs [39.40838358438744]
Large Neighborhood Search (LNS) is a popular algorithm for solving optimization problems (COP)
In this paper, we focus on designing effective and efficient linears in LNS for integer programs (ILP)
Our proposed relaxations, LB-RELAX and its variants, use the linear programming of LB to select neighborhoods.
arXiv Detail & Related papers (2022-12-15T22:53:09Z) - GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP,
and Beyond [101.5329678997916]
We study sample efficient reinforcement learning (RL) under the general framework of interactive decision making.
We propose a novel complexity measure, generalized eluder coefficient (GEC), which characterizes the fundamental tradeoff between exploration and exploitation.
We show that RL problems with low GEC form a remarkably rich class, which subsumes low Bellman eluder dimension problems, bilinear class, low witness rank problems, PO-bilinear class, and generalized regular PSR.
arXiv Detail & Related papers (2022-11-03T16:42:40Z) - A General Framework for Sample-Efficient Function Approximation in
Reinforcement Learning [132.45959478064736]
We propose a general framework that unifies model-based and model-free reinforcement learning.
We propose a novel estimation function with decomposable structural properties for optimization-based exploration.
Under our framework, a new sample-efficient algorithm namely OPtimization-based ExploRation with Approximation (OPERA) is proposed.
arXiv Detail & Related papers (2022-09-30T17:59:16Z) - Reinforcement Learning for Branch-and-Bound Optimisation using
Retrospective Trajectories [72.15369769265398]
Machine learning has emerged as a promising paradigm for branching.
We propose retro branching; a simple yet effective approach to RL for branching.
We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables.
arXiv Detail & Related papers (2022-05-28T06:08:07Z) - Learning the Step-size Policy for the Limited-Memory
Broyden-Fletcher-Goldfarb-Shanno Algorithm [3.7470451129384825]
We consider the problem of how to learn a step-size policy for the Limited-Memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) algorithm.
We propose a neural network architecture with local information of the current gradient as the input.
The step-length policy is learned from data of similar optimization problems, avoids additional evaluations of the objective function, and guarantees that the output step remains inside a pre-defined interval.
arXiv Detail & Related papers (2020-10-03T09:34:03Z) - FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity
to Non-IID Data [59.50904660420082]
Federated Learning (FL) has become a popular paradigm for learning from distributed data.
To effectively utilize data at different devices without moving them to the cloud, algorithms such as the Federated Averaging (FedAvg) have adopted a "computation then aggregation" (CTA) model.
arXiv Detail & Related papers (2020-05-22T23:07:42Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.