For decades, researchers have complained that contiguity constraints make problems like districting much harder than other combinatorial optimization problems. This has prompted the use of integer programming models with inexact contiguity constraints that may be fast in practice but are invalid in the sense that they cut off or “overlook” some contiguous solutions. Examples include … Read more
Classical Benders decomposition fails when the subproblem is a mixed-integer program, due to the absence of strong duality. We propose a novel class of dual-free indicator cuts that are applicable to all Benders-decomposable problems with a pure-integer master problem and mixed-integer linear programming (MILP) subproblems. These cuts are derived from the monotonicity property of the … Read more
We address the problem of optimal route planning for competitive orien- teering on real terrain. A Geographic Information System (GIS) pipeline transforms orienteering map data and digital terrain models into a fully asymmetric cost matrix that captures directional slope costs (via the Minetti metabolic model) and cumulative athlete fatigue. The resulting problem, the Asymmetric Orienteering … Read more
Parameter estimation is a fundamental challenge in the calibration of ordinary differential equation (ODE) models, where repeated numerical integration can lead to high computational cost. In this work, we investigate whether quantum algorithms can be leveraged to assist parameter estimation in nonlinear dynamical systems. We develop a hybrid classical–quantum framework that reformulates a data-assimilation-augmented parameter … Read more
We study the computation of a second shortest simple \(s\)–\(t\) path (2-SP) in a directed graph with \(n\) nodes, \(m\) arcs and nonnegative integer arc costs bounded by \(C\). Working with reduced costs and a depth-first search that gives priority to a fixed shortest path \(P_{st}\), every candidate second path is a prefix of \(P_{st}\), … Read more
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