MSc Thesis Defense: Müge Dedeoğlu, LEARNING TO RELAX NON-CONVEX QUADRATICALLY CONSTRAINED QUADRATIC PROGRAMS WITHIN A SPATIAL BRANCH-AND-BOUND CONTEXT, Date & Time: 20 July, 2026 – 2:00 PM, Place: FENS 2019

LEARNING TO RELAX NON-CONVEX QUADRATICALLY CONSTRAINED QUADRATIC PROGRAMS WITHIN A SPATIAL BRANCH-AND-BOUND CONTEXT

Müge Dedeoğlu
Industrial Engineering, MSc Thesis, 2026

Thesis Jury

   Assoc. Prof. Burak Kocuk (Thesis Advisor)

  Asst. Prof. Ezgi Karabulut Türkseven

  Assoc. Prof. Firdevs Ulus

Date & Time: July 20th, 2026 – 2:00 PM

Place: FENS 2019

Keywords : non-convex optimization, quadratically constrained quadratic programming, convex relaxations, spatial branch-and-bound, machine learning

Abstract

Convex relaxations play a central role in global optimization methods for non-convex quadratically constrained quadratic programs because they provide valid lower bounds within branch-and-bound algorithms. This study extends learning-based relaxation selection from a root-node comparison to a spatial branch-and-bound context. The goal is to predict whether a linear programming relaxation or a strengthened semidefinite programming relaxation is more favorable by accounting for both lower-bound quality and computational effort inside branch-and-bound. The framework generates separate linear programming and strengthened semidefinite programming branch-and-bound trees and studies two selection settings. In static relaxation selection, the model chooses a relaxation using only dimension-independent features computed from the original problem before tree search. In dynamic relaxation selection, a limited number of early nodes are first explored, and their bound improvement, infeasibility, and pruning are combined with the static features before the final choice. The relaxation-selection task is formulated through two supervised learning approaches: classification and regression. The evaluated tools include XGBoost, Gradient Boosting, Random Forest, and tripartite graph neural networks. Experiments are conducted on synthetic problem instances and MINLPLib benchmark instances. The best-performing models achieve accuracies above 0.95 in many synthetic and benchmark settings, showing that the proposed framework can provide reliable relaxation-selection decisions across different datasets and evaluation settings. Overall, dynamic selection improves over static selection most clearly in transfer and benchmark settings, indicating that early branch-and-bound information provides additional value for relaxation selection.