Year: 2026

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 Complete Characterization of Optimal Subgradient Methods for Lipschitz Convex Minimization

Categories Nonsmooth Optimization, Semi-definite Programming Tags ,

We consider the design of optimal fixed-step first-order methods for $M$-Lipschitz convex optimization given $\|x_0-x_\star\|\leq D$. Prior works have identified several distinct fixed-step methods, parameterized by a matrix of stepsizes $W$, with the (information-theoretic) minimax optimal rate $MD/\sqrt{N+1}$ of objective gap convergence. We provide a complete characterization of every optimal fixed-step method. Moreover, we show … Read more

Exact Branch-and-Price Algorithm for Live Operating Room Reoptimization

Categories (Mixed) Integer Linear Programming, Multi-Criteria Optimization, Scheduling Tags , , , ,

Live reoptimization of operating room schedules is required to cope with disruptions such as emergency arrivals and deviations in surgery durations under strict time limits. The resulting problem can be formulated as a large-scale Resource Constrained Project Scheduling Problem (RCPSP). While exact optimization methods are attractive in this context due to their ability to provide … Read more

Beyond Hand-Derived Inequalities: Decision Diagrams for Cut Generation in Binary Polynomial Optimization

Categories 0-1 Programming, Cutting Plane Approaches, Integer Programming Tags , ,

We study cutting-plane generation for binary polynomial optimization (BPO), whose feasible region is the multilinear set of a hypergraph. Strong inequalities for this set—such as two-links, flowers, and odd $\beta$-cycles—are classically hand-derived for fixed support patterns. Instead, we propose a decision-diagram (DD) approach: for any chosen support, it separates a facet-defining cut in the local … Read more

Entropy-Smooth Convex Optimization Cannot Be Accelerated

Categories Convex and Nonsmooth Optimization, Convex Optimization, Optimization in Data Science Tags , ,

We prove an $\Omega(L/T)$ lower bound for the convergence rate of minimization in the class of functions that are convex and $L$-smooth relative to negative entropy on the standard $d$-simplex, valid for every first-order method when $d = \Omega(T^2)$. In particular, this shows that mirror descent is optimal up to a logarithmic factor in this … 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

A Data-Assimilation-Augmented Optimization Framework for Parameter Estimation in Dynamical Systems

Categories Control Applications, Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

Parameter estimation in nonlinear dynamical systems from observational data is a fundamental inverse problem with applications in many disciplines such as epidemiology, systems biology, climate science, and related fields. In practice, this is further complicated by the fact that observational data are often noisy, sparse, and available only for a subset of the state variables. … 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

A new theorem of alternatives leading to sufficient conditions for the superiorization guarantee question of Dynamic String-Averaging in the inconsistent case

Categories Basic Sciences Applications, Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization

We study the Superiorization Methodology (SM) in the context of the General Dynamic String-Averaging (GDSA) method in the inconsistent case (that is, where the input operators don’t have a common fixed point) which primarily aims at achieving convex feasibility while simultaneously reducing an objective function. In many scientific and real-world problems modeled as constrained minimization … Read more

On the boundedness of infinite products of relaxed projections: perturbations resilience and dynamic string-averaging

Categories Basic Sciences Applications, Convex Optimization, Infinite Dimensional Optimization Tags , , , , , , , , ,

Very recently (2026), Bauschke and Tung extended from finite- to infinite-dimensional Hilbert spaces a result published by Meshulam in 1996 (following an earlier result of Aharoni-Duchet-Wajnryb from 1984) regarding the boundedness of infinite products of relaxed projections onto a finite family of closed affine subspaces. In the present note we extend in various ways the … Read more