Neural network method improves solving complex optimization problems
Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe
Machine LearningArtificial Intelligence
Summary
Solving problems that involve making the best choice from many options is very hard when strict rules must be followed. The authors introduce a way for neural networks to suggest solutions without being limited to the rules at first. Then, their method adjusts these ideas into actual valid solutions using a mathematical technique called Frank-Wolfe. This makes training the network easier and produces better final answers on problems like routing and assignment tasks.
What this means in practice
- •For logistics planners: Improve routing and assignment plans by integrating neural network predictions with guaranteed valid schedules.
- •For software developers for optimization tools: Create optimization engines that learn from their own solutions and handle complex constraints more flexibly.
Authors
Akbar Rafiey, Yifei Xu, Nikolaos Karalias
Abstract
Self-supervised learning for combinatorial optimization has emerged as a promising paradigm for solving discrete optimization problems with neural networks, but a central challenge remains: handling hard combinatorial constraints within continuous, gradient-based training. Continuously extending combinatorial objectives to convex domains is a powerful technique, yet existing approaches often require projection steps that constrain neural network outputs to lie inside the feasible polytope and rely on ad-hoc and problem-specific constructions. We propose a general framework in which the neural network is allowed to predict arbitrary continuous vectors that could potentially lie outside of the feasible polytope. These predictions are then approximated by sparse convex combinations of feasible solutions using a geometric decomposition algorithm based on Frank--Wolfe methods and approximate Caratheodory results. This decomposition induces an a.e.-differentiable, self-supervised loss defined as the expected value of the discrete objective. The same procedure provides an automatic rounding guarantee at inference time. We demonstrate strong empirical performance across multiple combinatorial problems, including the Quadratic Assignment Problem, Maximum Coverage, and the Traveling Salesperson Problem.