West Virginia University
Dataless Neural Networks for Boolean Satisfiability and Network Optimization
Abstract
dc:description.abstractCombinatorial optimization problems (COPs) require searching over a finite solution space subject to constraints, with the goal of satisfying an objective function. They arise in operations research, scheduling, resource allocation, circuit design, and many other fields. Many problems in combinatorial optimization (including satisfiability and network design) are NP-hard. Traditionally, researchers have built approximate solvers that return near- optimal solutions efficiently by developing increasingly sophisticated heuristics and meta- heuristics. Deep learning has provided new opportunities for improving combinatorial solvers by leveraging neural guidance to prune the search space. Traditional neural networks have distinct drawbacks in this context: separate training and inference phases require significant computational resources and limit generalizability to unseen problem instances. This thesis addresses the challenge by leveraging large-scale parallelization and data- less neural networks (dNNs), an emerging player in the field. The dataless approach has made real-time optimization possible without prior training. This advancement has substantially changed the memory needed to use a neural combinatorial solver. In this work, we have designed, implemented, and evaluated four dNNs for separate problems in satisfiability and network optimization. Experimental results show competitive or superior performance against commercial solvers, with improved scalability. We present empirical results for our implementations of the dataless approach.
Degree
thesis:*- Name thesis:degree_name
- MS
- Level thesis:degree_level
- Thesis
- Discipline thesis:degree_discipline
- Lane Department of Computer Science and Electrical Engineering
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Gautier, Andrew Evan
- Contributors dc:contributor
-
- Piotr Wojciechowski
- K. Subramani
- Thomas Devine
Subjects
dc:subject × 15- dNNs
- MAX-SAT
- Combinatorial Optimization
- Cycle Detection
- Neural Combinatorial Optimization
- Machine Learning
- Deep Learning
- SATLIB
- Applied Mathematics
- Computer Engineering
- Computer Sciences
- Electrical and Computer Engineering
- Materials Science and Engineering
- Mathematics
- Operations Research, Systems Engineering and Industrial Engineering
Identifiers
dc:identifier.*- Identifier
-
<p><a href="https://orcid.org/0009-0007-6185-5781">https://orcid.org/0009-0007-6185-5781</a></p>
https://researchrepository.wvu.edu/etd/13471