Geometric Algorithms for Neural Combinatorial Optimization with Constraints
This work addresses a central problem in neural combinatorial optimization for researchers and practitioners, offering a novel method to handle constraints, though it is incremental in building on existing SSL paradigms.
The paper tackles the challenge of solving combinatorial optimization problems with discrete constraints using self-supervised learning, by developing a differentiable framework that leverages convex geometry to decompose neural network outputs into feasible solutions, resulting in consistent outperformance of neural baselines in experiments.
Self-Supervised Learning (SSL) for Combinatorial Optimization (CO) is an emerging paradigm for solving combinatorial problems using neural networks. In this paper, we address a central challenge of SSL for CO: solving problems with discrete constraints. We design an end-to-end differentiable framework that enables us to solve discrete constrained optimization problems with neural networks. Concretely, we leverage algorithmic techniques from the literature on convex geometry and Carathéodory's theorem to decompose neural network outputs into convex combinations of polytope corners that correspond to feasible sets. This decomposition-based approach enables self-supervised training but also ensures efficient quality-preserving rounding of the neural net output into feasible solutions. Extensive experiments in cardinality-constrained optimization show that our approach can consistently outperform neural baselines. We further provide worked-out examples of how our method can be applied beyond cardinality-constrained problems to a diverse set of combinatorial optimization tasks, including finding independent sets in graphs, and solving matroid-constrained problems.