Combinatorial Optimization

Optimal Route Planning for Orienteering: Branch-and-Cut with Terrain Cost Surfaces and Fatigue

Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Transportation

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

A Quantum Optimization Framework for Data-Assimilation-Augmented Parameter Estimation

Categories Combinatorial Optimization, Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

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

Second shortest simple paths in directed graphs: a crossing decomposition and a span-adaptive exact algorithm

Categories Combinatorial Optimization, Graphs and Matroids, Network Optimization Tags , , , ,

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

Aggregated quadratic formulations and semidefinite relaxations of the stable set polytope

Categories Combinatorial Optimization, Semi-definite Programming Tags , , ,

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

Computing diverse solutions to optimization problems

Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Combinatorial Optimization Tags , ,

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

Integrating Power Profile Optimization with Timetabling for Underground Train Networks

Categories (Mixed) Integer Linear Programming, Polyhedra, Transportation Tags , , ,

We study energy-efficient operation of underground train networks by integrating power profile optimization with timetable design in a single mixed-integer optimization framework. The model minimizes traction energy by synchronizing braking and acceleration across trains sharing a power subnetwork to exploit regenerative energy and flexibly allocating running times to promote coasting. Unlike timetable-only approaches with fixed … Read more

Optimal Combinatorial Testing with Constraints: The Balancing Act

Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering, Graphs and Matroids

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

Attention Mechanisms in Physics-Inspired Graph Neural Networks for the Max-Cut Problem

Categories Combinatorial Optimization, Graphs and Matroids, Network Optimization Tags , , ,

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

Random-Key Optimization for 2D Irregular Packing with Reusable Area Evaluation

Categories Applications - OR and Management Sciences, Meta Heuristics, Parallel Algorithms, Production and Logistics Tags , ,

The diverse constraints of industrial applications lead to variants of 2D irregular packing problems that require tailored solution methods. This paper addresses a real-world industrial challenge by proposing a new problem definition, the Maximum Reusable Contiguous Area Problem (MRCAP), and a novel metric, the Maximum Contiguous Area, developed to measure and maximize the contiguous unused … Read more

A Polynomial-Time Algorithm for Coloring Perfect Graphs Based on Walk Counting

Categories Combinatorial Optimization, Semi-definite Programming Tags , ,

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