A Graph-Neural-Network-Powered Solver Framework for Graph Optimization Problems

Area of Science:

• Computer Science
• Artificial Intelligence
• Operations Research

Background:

• Constraint Satisfaction Problems (CSPs) and Combinatorial Optimization Problems (COPs) are often solved using backtracking with branching heuristics.
• Existing branching heuristics are either problem-specific and complex, or general but potentially suboptimal.
• A need exists for heuristics that balance generality with problem-specific efficiency.

Purpose of the Study:

• To introduce a solver framework that integrates Shannon entropy into branching heuristics for CSPs and COPs.
• To develop a method that enables backtracking to navigate problems with reduced uncertainty.
• To learn probability distributions for branching using Graph Neural Networks (GNNs).

Main Methods:

• Developed a solver framework utilizing Shannon entropy for branching heuristics.
• Employed Graph Neural Network (GNN) models to learn probability distributions.
• Utilized loss functions derived from the probabilistic method for GNN training.

Main Results:

• The framework was applied to the NP-hard (minimum) dominating-clique and edge-clique-cover problems.
• Achieved competitive results compared to state-of-the-art solvers.
• Demonstrated reduced branching for the dominating-clique problem and smaller edge clique covers (ECCs) for the edge-clique-cover problem.

Conclusions:

• The proposed Shannon entropy-based branching heuristic framework effectively bridges the gap between general and specific heuristics.
• The GNN-driven approach provides a practical method for learning effective branching strategies.
• The framework shows promise for improving performance on complex NP-hard optimization problems.