Transformer method improves solving large binary optimization problems
Autoregressive Differentiable Method for Integer Programming
Machine Learning
Summary
Solving problems with yes-no decisions, like packing items within limits, can be very hard for computers. The authors developed a new way that uses a transformer model to decide those yes-no choices step-by-step while staying within allowed solutions. They first teach the model by showing it good example solutions, then refine it with penalties for invalid solutions. When tested on tough packing problems with up to 10,000 yes-no variables, their method worked better than current best open-source solvers. Interestingly, their approach helps jump over tricky obstacles in the solution search space by turning the problem into a continuous form inside the model.
What this means in practice
- •For operations research teams: Improve solution quality and speed for large-scale binary resource allocation problems by integrating transformer-based optimization models.
- •For logistics planners: Enhance planning for packing and loading operations involving complex constraints with more effective binary decision models.
Authors
Ouns El Harzli, Yudong Cao
Abstract
We introduce an autoregressive differentiable method to solve 0-1 integer programs. We fix an arbitrary order of the binary variables and we train a transformer to predict the next bit while remaining in the feasible set. Our method is first trained on feasible incumbents provided by any solver, thus allowing us to initialize the transformer in the feasible set. Our procedure then implements a Lagrangian penalty to penalize infeasible solutions, and the transformer is further trained to explore the feasible set using Gumbel-softmax activations on the relaxed objective. We have tested our method on non-convex instances of quadratic knapsack problem and demonstrated consistent improvement upon state-of-the-art open-source solvers for dense problems up to 10,000 binary variables. In particular, we empirically demonstrate a phenomenon akin to a tunneling effect where the effective change of variables from binary variable to the continuous weights of the transformer that the method implements enables crossing barriers in the relaxed objective landscape.