Differentiable Discrete Optimization Using Dataless Neural Networks

The area of combinatorial optimization is characterized by the search for optimal combinations of discrete variables that satisfy some set of constraints. Famous problems in this space include maximum satisfiability and maximum independent set. Due to their discrete dynamics, these problems are not differentiable in their natural formulations. In this paper, we explore the counter-intuitive direction of differentiable discrete optimization by leveraging the recently discovered dataless neural networks, which have been used to yield a single differentiable function that is equivalent to the maximum independent set problem. In particular, we leverage the dataless neural networks framework to derive differentiable forms for a variety of NP-hard discrete problems and prove the correctness of our derivations. The proposed differentiable forms open up the avenue for continuous differentiable optimization to be brought to bear on classical discrete optimization problems.