Sequence learning improves decision making in mixed integer programming
Sequence-Structured Decision Learning for Branch-and-Bound in Mixed-Integer Linear Programming
Machine Learning
Summary
Mixed-integer linear programs are solved by exploring many options in a search tree, guided by choices about which nodes to select and how to branch. The authors propose Seq-BnB, a method that looks at the entire sequence of previous decisions and their results to make better choices next. It treats the search process like a story made of tokens and uses machine learning to understand the global context rather than relying on local information alone. Their experiments show that this approach reduces the number of nodes explored and speeds up finding solutions compared to traditional and other learning methods.
What this means in practice
- •For operations research teams: Enhance mixed-integer linear programming solvers with sequence-aware learning to reduce search time and nodes explored in scheduling and planning tasks.
- •For automated optimization software developers: Incorporate global sequence-based decision models into branch-and-bound components to improve solver efficiency on large and diverse problem instances.
Authors
Tengfei Liu, Jinrun Liu, Bai Yan, Yuhui Shi, Qi Zhao
Abstract
Branch-and-bound (BnB) solves mixed-integer linear programs by constructing and exploring a search tree. Node selection and branching are two recurrent decisions that directly determine the tree. Learning-based approaches typically optimize either decision in isolation and condition on a mostly local view, leaving the coupled evolution of the search tree insufficiently modeled. This paper proposes Seq-BnB, a sequence-structured framework that learns branching and node selection from a shared global representation of the evolving BnB process. Seq-BnB serializes node creations, node updates, node-selection events, and branching events into typed tokens, producing a causal event sequence of the search trajectory. A self-attention encoder summarizes this global search history, a bipartite graph neural network encodes the current LP relaxation, and context-conditioned decision heads score branching variables and open nodes. To reduce distribution shift between expert demonstrations and learned policies, Seq-BnB is trained with DAgger-style data aggregation. On four MILP benchmark families, Seq-BnB consistently processes fewer BnB nodes than heuristic and learning-based baselines, with strong solution times on both standard and larger transfer instances. While this paper evaluates Seq-BnB instantiation for branching and node selection, it accommodates additional solver decisions, such as cut selection, by introducing new action tokens and decision heads.