<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-21T01:18:52Z</responseDate><request verb="GetRecord" identifier="oai:macsphere.mcmaster.ca:11375/33733" metadataPrefix="dim">https://prod-ms-be.lib.mcmaster.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:macsphere.mcmaster.ca:11375/33733</identifier><datestamp>2026-10-07T07:12:32Z</datestamp><setSpec>com_11375_271</setSpec><setSpec>col_11375_272</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:doc="http://www.lyncode.com/xoai" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Hassini, Elkafi</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author">Sharman, Bharat</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="department">Computational Engineering and Science</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2026-10-06T18:04:43Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2026</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/11375/33733</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://doi.org/10.71548/25503</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="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.</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="degreetype">Thesis</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="degree">Doctor of Philosophy (PhD)</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso">en</dim:field>
   <dim:field mdschema="dc" element="rights" lang="en">Attribution-NonCommercial-NoDerivs 2.5 Canada</dim:field>
   <dim:field mdschema="dc" element="rights" qualifier="uri">http://creativecommons.org/licenses/by-nc-nd/2.5/ca/</dim:field>
   <dim:field mdschema="dc" element="title">Methodologies for predicting and explaining the empirical hardness of graph-based combinatorial optimization problems</dim:field>
   <dim:field mdschema="dc" element="type">Thesis</dim:field>
   <dim:field mdschema="others" element="access-status">embargo</dim:field>
</dim:dim></metadata></record></GetRecord></OAI-PMH>