The UTC Graduate School is pleased to announce that Hagar Cobbinah will present Master’s research titled, A Graph Convolutional Network Approach for Enhancing Set Covering Problem Solvers on 02/28/2025 at 12:30 PM in 700 Vine Street, Rm 392, Lupton Hall. Everyone is invited to attend.
Mathematics
Chair: Lakmali Weerasena
Co-Chair:
Abstract:
The Set Covering Problem (SCP) is a classical NP-hard combinatorial optimization problem with applications in operations research, logistics, transportation, and telecommunications. Solving SCP efficiently remains challenging due to the combinatorial explosion of potential solutions, particularly for large instances. This study proposes a computationally efficient approach using a Graph Convolutional Network (GCN) to approximate optimal solutions for SCP. A bipartite graph representation of SCP is employed to predict the priority order of nodes, which serves as a warm start for the Gurobi solver. The GCN is trained on solutions generated by a classical greedy algorithm. By integrating GCNs with Gurobi, the proposed method combines data-driven predictions with exact optimization, resulting in faster computation and improved scalability. Experimental evaluations on benchmark SCP instances demonstrate that this hybrid approach significantly reduces computational time and enhances Gurobi’s performance, offering a robust framework for tackling 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. In this context, sets can represent regions, and items can represent ecological species.