Advancing discrete optimization: novel approaches with dataless neural networks

Sangram K. Jena (), K. Subramani () and Alvaro Velasquez ()
Additional contact information
Sangram K. Jena: University of Alaska Fairbanks
K. Subramani: West Virginia University
Alvaro Velasquez: University of Colorado Boulder

Journal of Combinatorial Optimization, 2025, vol. 50, issue 4, No 8, 20 pages

Abstract: Abstract 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.

Keywords: Dissociation set; k-coloring; Distance matching; Hamilton cycle; Path set; NP-complete; dNN (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01354-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:50:y:2025:i:4:d:10.1007_s10878-025-01354-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01354-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().