Committee Chair

Weerasena, Lakmali

Committee Member

Aniekan, Ebiefung; Cox, Christopher L.; Gao, Lani

Department

Dept. of Mathematics

College

College of Arts and Sciences

Publisher

University of Tennessee at Chattanooga

Place of Publication

Chattanooga (Tenn.)

Abstract

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.

Acknowledgments

This research was made possible through the support and guidance of many people. First, I would like to thank the Mathematics Department and the Graduate School of UTC for providing me with the opportunity to earn a graduate degree in Mathematics. Additionally, I would like to extend my sincerest gratitude to my Supervisor and Mentor, Prof. Lakmali Weerasena, for her remarkable guidance and direction throughout the research process. Further, I would like to express my heartfelt gratitude to my committee members, Prof. Aniekan Ebiefung, Prof. Lani Gao, and Prof. Christopher L. Cox, for the valuable feedback and suggestions they provided.

Degree

M. S.; A thesis submitted to the faculty of the University of Tennessee at Chattanooga in partial fulfillment of the requirements of the degree of Master of Science.

Date

5-2025

Subject

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

Keyword

Optimization; Graph Convolutional Network; Set Covering Problem; Integer Programming Problem

Document Type

Masters theses

DCMI Type

Text

Extent

xi, 93 leaves

Language

English

Rights

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

License

http://creativecommons.org/licenses/by/4.0/

Download

Share

COinS