A Graph Convolutional Network approach for enhancing Set Covering Problem solvers

The Set Covering Problem (SCP) is an NP-hard combinatorial optimization problem with applications in telecommunication, logistics, and transportation. Solving SCP is computationally challenging due to the combinatorial explosion of potential solutions, particularly for large instances. This study proposes a Graph Convolutional Network (GCN) to approximate optimal solutions for SCP. A bipartite graph representation of SCP is employed to predict node priority, serving as a warm start for the Gurobi solver. The GCN is trained on solutions from a classical greedy algorithm. The method integrates GCNs and Gurobi, unifying data-driven prediction and exact solver for better computation efficiency and scalability. Experimental evaluations on benchmark SCP instances show that the Hybrid Model reduces computational time and enhances Gurobi's performance, offering a robust framework for SCP and other large-scale combinatorial optimization problems. Ultimately, this research will help in my future work to predict and identify conservation regions in ecological conservation.

Grantor dc:publisher

University of Tennessee at Chattanooga

Author dc:creator

• Cobbinah, Hagar

Contributors dc:contributor

• Weerasena, Lakmali
• Aniekan, Ebiefung; Cox, Christopher L.; Gao, Lani
• College of Arts and Sciences

• Combinatorial optimization
• Convolutions (Mathematics)--Graphic methods
• Integer programming

Licence

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language

English, eng

Repository record dc:identifier

https://scholar.utc.edu/theses/1001

OAI identifier oai:identifier

oai:scholar.utc.edu:theses-2180