Back to search

McMaster University

Methodologies for predicting and explaining the empirical hardness of graph-based combinatorial optimization problems

Abstract

dc:description.abstract

The 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
Language dc:language.iso
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Sharman, Bharat. Methodologies for predicting and explaining the empirical hardness of graph-based combinatorial optimization problems. 2026. https://hdl.handle.net/11375/33733