For integer activities, conditioning on the support makes a fixed-charge objective affine. If every support-conditioned cell is integral, an optimal solution is a vertex of its cell for arbitrary fixed charges and marginal rates. A totally unimodular constraint matrix with integral data guarantees this condition. This surviving property is weaker than the classical conclusions. A … Read more
The symmetry measure of a convex body \(S\subset\mathbb{R}^n\) is given by: \[ \mathrm{sym}(S):=\max\{\alpha\ge0:\text{ there exists }x\in S\text{ such that } -\alpha(S-x)\subseteq S-x\}\,, \]where such an \(x\) is called a Minkowski center. We prove that every convex body \(S\) admits a \(\sqrt{\frac{n}{\mathrm{sym}(S)}}\)-rounding of \(S\), namely, there exists an origin-centered ellipsoid \(E\) and a center \(c\) such … Read more
Feature-based newsvendor models use observable covariates to tailor inventory decisions, aiming to balance holding and shortage costs under demand uncertainty. However, high-dimensional feature sets often hinder interpretability and inflate data collection and implementation costs. This paper studies variable selection for the feature-based newsvendor problem under a hard cardinality constraint on the number of selected features. … Read more
We give a simple example that disproves the following 2015 conjecture of Lacoste-Julien and Jaggi concerning the pyramidal width (aka facial distance): The pyramidal width of a set of vertices is non-increasing when another vertex is added (assuming that all previous points remain vertices). In contrast to the recent example by Zhao (arXiv:2607.29555), our counterexample … Read more
We address the classical Dantzig – Fulkerson – Johnson formulation of the symmetric metric Traveling Salesman Problem and study the integrality gap of its linear relaxation, namely the Subtour Elimination Problem (SEP). This integrality gap is conjectured to be 4/3. We prove that, when solving a problem on n nodes, if the optimal SEP solution … Read more
The Ramsey number R(m,n) is the smallest order at which every red-blue edge coloring of a complete graph must contain a blue clique (a complete subgraph) of size m or a red clique of size n. Determining these numbers exactly is extremely hard, and even certifying a lower bound requires exhibiting an explicit coloring that … Read more
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