Breaking the Odd Cycle: Regularization and First-Order Optimization for the Maximum s-Plex Problem

Categories Network Optimization, Nonlinear Optimization Tags , , ,

Building on a new regularized continuous formulation which avoids spurious solutions of the maximum s-plex problem, we develop a tailored block-coordinate first-order method that combines away-step Frank-Wolfe updates on the standard simplex with linear optimization over the fractional b-matching polytope. We establish finite stabilization of the auxiliary variables, convergence to stationary points, and finite support … Read more

Integer programming on polytopes of Chvátal rank one is as hard as lattice problems

Categories Cutting Plane Approaches, Integer Programming, Polyhedra Tags , , , , ,

A rational polyhedron has Chvátal rank at most one if a single round of Chvátal-Gomory cuts yields its integer hull. For such polyhedra, integer feasibility is in NP ∩ coNP by a result of Boyd and Pulleyblank from the early 1980s, so it is unlikely to be NP-hard. Whether it is polynomial has remained open … Read more

Linearizable Instances of the Quadratic Minimum Spanning Tree Problem on 3-Connected Graphs

Categories 0-1 Programming, Combinatorial Optimization, Quadratic Programming Tags , , ,

An instance of the quadratic minimum spanning tree problem (QMSTP) is called linearizable if it can be rewritten as an instance of the linear minimum spanning tree problem in such a way that the objective function value is preserved at all feasible solutions. Previous work has shown that a sufficient condition for linearizability is that … Read more

Weakly Quasar-Convex Optimization

Categories Convex and Nonsmooth Optimization, Generalized Convexity/Monoticity, Nonlinear Optimization Tags , , , ,

This paper introduces the class of weakly quasar-convex functions, a notion that simultaneously generalizes weak convexity (and hence convexity) and quasar-convexity. We establish the theoretical foundation for this new class by developing its basic calculus, deriving characterizations, and systematically investigating its closure and structural properties. Building on these tools, we analyze the proximal point algorithm … Read more

GPU-Accelerated Bregman Douglas–Rachford Splitting for Discrete Optimal Transport

Categories Convex and Nonsmooth Optimization, Optimization Software and Modeling Systems Tags , ,

We present GPU-accelerated Bregman Douglas–Rachford splitting algorithm (BDRS) for discrete optimal transport problem in three input formats: an explicit cost matrix, a point cloud with a ground cost between them, and a separable cost on a regular grid. For each input format, we propose hardware-aware designs of mathematically equivalent representations for the BDRS iterations to … Read more

Affine Decision Rules for Robust Optimization with Decision-Dependent Information Discovery

Categories Robust Optimization Tags , , , , ,

We study robust optimization problems with decision-dependent information discovery under polyhedral uncertainty and continuous recourse. We first establish structural properties of the resulting min–max–min problem, including existence of solutions and a condition under which information discovery has no value. Then, we develop a heuristic approach that combines affine decision rules with scenario generation and show … Read more

Adversarial Training for Deep Hedging in Nonstationary Markets

Categories Applications - OR and Management Sciences, Robust Optimization, Stochastic Programming Tags , , , ,

Deep hedging learns trading policies from historical or simulated market trajectories, yet under nonstationarity these training paths may not represent future market conditions. We propose WRAP (Wasserstein-Reweighting Adversarial Perturbation), a drift-aware adversarial training framework derived from a two-budget distributionally robust optimization (DRO) formulation. The formulation is anchored to a weighted empirical reference distribution whose fixed … Read more

Robust Out-of-Distribution Stochastic Optimization Based on Wasserstein-Metric Meta-Distribution Support Learning

Categories Optimization in Data Science, Robust Optimization, Stochastic Programming Tags , , , , ,

We study stochastic optimization with a completely unobserved target distribution and samples from related source distributions. Treating the sources and the target as independent draws from a common meta-distribution, we propose Wasserstein-metric meta-distribution support learning (MDSL). The model jointly learns the center and radius of a Wasserstein ball, with an exclusion parameter controlling the fraction … Read more

Small extended formulations for group-constrained flows and cographic integer hulls

Categories Graphs and Matroids, Integer Programming, Polyhedra Tags , , , , ,

We construct small extended formulations for nonnegative integer flows whose arc labels have a prescribed sum in a finite abelian group. For circulations, the formulation is a single integral network that combines cycles even when they lie in different components. This yields an O(Δn²) bound for strictly Δ-modular cographic integer hulls of translated cones, improving … Read more

A Data-Driven Linear Programming Model for Energy-Optimal Metro Timetables

Categories Applications - OR and Management Sciences, Scheduling, Transportation Tags , , , ,

We propose a data-driven linear programming model to compute energy-optimal timetables for networks operating under communications-based train control (CBTC); the model was developed in collaboration with Hitachi Rail Canada, the largest provider of CBTC systems worldwide. Our model minimizes the network’s effective energy consumption, defined as the total traction energy consumed by the trains minus … Read more