The stable set problem admits various binary linear and quadratic formulations. The Shor relaxation of a particular quadratic formulation is the well-known theta body. We consider aggregations of quadratic constraints of this formulation, yielding exact and inexact quadratic formulations of the stable set problem, and then establish conditions under which the aggregated quadratic formulation is … Read more
Classical optimization methods determine a single optimal or near-optimal solution for a decision problem. In many applications, however, the decision maker is interested in evaluating a pool of high-quality solutions, to encode fairness-oriented criteria or to obtain a portfolio of alternatives to use in case of unexpected scenarios. In this paper, we consider the problem … Read more
We study energy-efficient operation of underground train networks, where energy from regenerative braking is usable only if another train in the same electrically isolated subnetwork accelerates simultaneously. Timetabling models for this setting typically fix one velocity profile per leg and running time, which limits the matching of braking and accelerating phases. We drop this assumption … Read more
Imagine that you are in front of a cockpit with several on–off buttons. If you were to thoroughly test it, you would need to try a prohibitive number of configurations. But since most bugs in practice can be isolated to interactions among few components, having tests that cover every possible pairwise configuration is a good … Read more
Physics-Inspired Graph Neural Networks (PI-GNNs) reformulate MAX-CUT as QUBO energy minimization, training a GNN to produce soft binary node assignments without labeled data. The baseline PI-GCN uses static, degree-normalized aggregation, while its attention-augmented counterpart PI-GAT—built on GATv2—introduces additional hyperparameters whose effects remain uncharacterized. This paper addresses that gap through controlled experiments on five Gset benchmark … Read more
The diverse constraints of industrial applications lead to variants of two-dimensional (2D) irregular packingproblems that require tailored solution methods. This paper addresses a real-world industrial challenge byproposing a new problem definition, the maximum reusable contiguous area problem (MRCAP), and a novelmetric, the maximum contiguous area, to measure and maximize the contiguous unused area in a … Read more
We present a polynomial-time algorithm for optimally coloring perfect graphs that is based entirely on graph-theoretic operations. At its core, the algorithm decides whether a perfect graph contains a clique of a given size by iteratively counting walks in the graph with certain weights assigned to its edges and nonedges. These weights are initialized according … Read more
Network design problems increasingly arise in settings where strategic infrastructure decisions and operational routing choices are made by different actors. Such interactions are naturally modeled as bilevel problems: a network operator designs or modifies a network, while users respond by selecting routes according to their own utilities. This structure captures many applications in transportation and … Read more
Assortment optimization selects a subset of items to maximize expected revenue under a discrete choice model and is widely used in revenue management and online platforms. Its combinatorial nature creates a practical tension among generality, scalability, and provable guarantees: model-specific algorithms can be strong when their structural assumptions hold, but are hard to adapt across … Read more
The Maximum Closure Problem asks for a maximum-weight closed subset of a precedence-constrained set of vertices; when vertex weights depend affinely on a scalar parameter $\lambda$, as in open-pit mine scheduling, the goal becomes computing the optimal closed set for every value of $\lambda$ at once. We address this problem when the precedence graph is … Read more