Geometric Algorithms for Neural Combinatorial Optimization with Constraints

Nikolaos Karalias (Massachusetts Institute of Technology) · Akbar Rafiey (New York University) · Yifei Xu (New York University) · Zhishang Luo (University of California, San Diego) · Behrooz Tahmasebi (Harvard University ) · Connie Jiang (Massachusetts Institute of Technology) · Stefanie Jegelka (TU Munich)

carathéodory's theoremcardinality-constrained optimizationcombinatorial optimizationconvex combinationsconvex geometrydiscrete constraintsend-to-end differentiable frameworkfeasible setsindependent setsmatroid-constrained problemsneural baselinesoptimization taskspolytope cornersquality-preserving roundingself-supervised learning

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.