Learning variable selection rules for the branch-and-bound algorithm using reinforcement learning

Abstract

Mixed Integer Linear Programming (MILP) is a generalization of classical linear programming where we restrict some (or all) variables to take integer values. Numerous real-world problems can be modeled as MILPs, such as production planning, scheduling, network design optimization and many more. MILPs are, in fact, NP-hard. State-of-the-art solvers use the branch-and-bound algorithm, an exact method that, in combination with a diverse mixture of heuristics, can tackle a fair range of practical problems. This algorithm sequentially partitions the search space using linear relaxations, thus creating a search tree. The exploration ends only when a solution, together with its proof of optimality, is found. The tree’s size can vary dramatically depending on the approach that is used to create it and explore it. One of the most influential decision-making strategies within the branch-and-bound algorithm is the branching rule, i.e., the criterion that is used to subdivide the search space. Currently, there is no mathematical understanding of this complex process. For this reason, all widely accepted branching rules are based on hand-crafted strategies which have been shown to perform well in practice. The work presented in this report is part of a blossoming line of research in the intersection of Combinatorial Optimization and Machine Learning. Specifically, we take further steps in the direction of branching rule discovery through machine learning techniques. In contrast to previously proposed methods which relied on supervised learning, we take the novel approach of leveraging a Reinforcement Learning (RL) algorithm. Our goal is to achieve a data-driven acceleration of the tree search. In this thesis, we lay the fundamental groundwork for the integration of RL into the branch-and-bound process. Through the proposed model, we gain insights on the benefits and limitations of RL, while improving on the state-of-the-art branching rules for a particular class of instances.