McMaster University
Methodologies for predicting and explaining the empirical hardness of graph-based combinatorial optimization problems
Abstract
dc:description.abstractThe thesis advances three integrated contributions for graph-based combinatorial optimization: (1) Proposes a Graph-based Combinatorial Optimization-Hardness Prediction and Explanation Framework, a two-stage approach that first predicts instance-level portfolio relative empirical hardness using machine learning on generic graph features and then explains predictions using association rule mining (ARM). Applied to 3,287 maximum clique problem (MCP) instances drawn from COLLAB, IMDB-BINARY, and TWITTER benchmarks, the framework achieves a weighted F1 ≈0.992 using features: two adjacency matrix-based spectral statistics and the number of nodes. It then extracts high-support, human-readable rules that align with these features and accurately characterize hard instances. (2) Performs instance space analysis on 6138 instances to compare five state-of-the-art algorithms, revealing that Mixed Order Maximum Clique (MOMC) dominates ∼74.7% of the instance space while Gurobi and CliSAT excel in distinct regions. A model trained on small graphs predicts the best algorithm for large BHOSLIB and DIMACS instances with top-1 accuracy ≈88% and top-2 ≈97%, enabling presolution algorithm selection. (3) Introduces ARM-Explainer, a post-hoc, model-level method that mines rules linking node features to a graph neural network (GNN)’s clique-membership predictions. Adding informative node features improves GNN performance on large graphs; for BHOSLIB–DIMACS, the median largest clique found increases by ≈22%. Limitations include: a binary hardness label used in the first study and the concentration on MCP and small-to-medium sized graphs in some analyses. The thesis discusses extensions to edge-weighted and path-based problems, including travelling salesperson problem (TSP) and location routing problem (LRP), the integration of edge features, and improved modelling of heavy-tailed runtimes for exact methods.
Degree
thesis:*- Department dc:contributor.department
- Computational Engineering and Science
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Sharman, Bharat
- Advisor dc:contributor.advisor
-
- Hassini, Elkafi
Rights
dc:rights- Statement dc:rights
-
- Attribution-NonCommercial-NoDerivs 2.5 Canada
- Licence dc:rights.uri
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Identifier URI
- https://doi.org/10.71548/25503