Advancing discrete optimization: novel approaches with dataless neural networks

Combinatorial optimization focuses on finding the most favorable combinations of discrete variables under predefined constraints. Notable challenges in this field include the maximum satisfiability and maximum independent set problems. The inherent discreteness of these problems precludes them from being differentiable in their standard formulations. This paper explores an innovative approach to differentiable discrete optimization by utilizing recently discovered dataless neural networks. These networks offer a means to construct a singular differentiable function mirroring the complexities of the maximum independent set problem. Leveraging the framework of dataless neural networks, we extend this methodology to derive differentiable representations for a range of NP-hard discrete problems, providing rigorous proof of their validity. Our proposed differentiable formulations present a pathway for integrating continuous differentiable optimization techniques into traditional discrete optimization paradigms, offering a roadmap for future empirical exploration.