Month: October 2026

Symmetry Presolving for Mixed-Integer Programs: Binary Structure Preservation and Relations to Orbital Branching

Categories Integer Programming Tags , , , ,

This paper investigates a presolving method for handling symmetries in mixed-integer programs, based on inequalities computed from so-called Schreier-Sims tables. We show that an iterative application of this method together with merging variables produces an instance for which the symmetry group is trivial. We then prove that the problem structure can be preserved for certain … Read more

Sharp proximity for group-labeled matroid bases

Categories Combinatorial Optimization, Graphs and Matroids, Integer Programming Tags , , ,

Let the elements of a matroid be labeled in an abelian group, and let \(F\) be a finite set of forbidden basis-label sums. We prove that, for every representable matroid, every basis is within \(|F|\) exchanges of an \(F\)-avoiding basis whenever one exists. This resolves the unweighted proximity conjecture for representable matroids over arbitrary fields, … Read more

Second-Moment Stochastic Approximation Methods

Categories Data Science Algorithms, Data Science Theory, Optimization in Data Science Tags , ,

Classical stochastic approximation methods rely on estimators of the first moment (mean) of a random regression function. We study methods that employ estimators of both the first and the second moments, which include modern deep-learning optimizers such as Adam and Muon as special cases. We derive second-moment stochastic approximation methods through the lens of optimal … Read more

A Facet Enumeration Algorithm for Convex Polytopes

Categories Basic Sciences Applications, Convex and Nonsmooth Optimization, Linear Programming Tags , , ,

This paper proposes a simple facet enumeration algorithm for convex polytopes. The complexity of the algorithm is analyzed. The algorithm is implemented in Matlab. Some polytopes with known H-representations and V-representations are used as test examples. The preliminary numerical test shows the effectiveness and efficiency of the proposed algorithm. Due to the duality between the … Read more

Are Single-Leader-Multi-Follower Problems Particular Cases of Bilevel Optimization?

Categories Bilevel Optimization, Game Theory, Global Optimization Tags , , ,

For more than 20 years, single-leader multi-follower (SLMF) problems have been treated as a more difficult class of problems in comparison to bilevel optimization. In this work we challenge this common belief, studying whether SLMF problems can be reformulated as equivalent bilevel optimization problems. We consider both optimistic and pessimistic formulations. For the optimistic case … Read more

Robust and Distributionally Robust Risk Budgeting with Mean Absolute Deviation

Categories Finance and Economics, Nonsmooth Optimization, Robust Optimization Tags , , ,

We propose robust and distributionally robust formulations of the risk budgeting problem under the mean absolute deviation (MAD) risk measure. The proposed models address uncertainty in asset returns and their distribution while allocating portfolio risk according to prescribed risk budgets. We first develop a robust model in which historical return observations are perturbed within a … Read more

Optimal charge scheduling of electric vehicle fleets through dynamic pricing and intraday market trading

Categories Bilevel Optimization, Energy Tags , , , ,

We consider an electricity supplier for a large commercial electric vehicle (EV) fleet. The supplier uses a dynamic pricing scheme for buying and selling energy from and to the fleet, enabling the supplier to trade any deviations from the agreed day-ahead (DA) position in the intraday auction (IDA) market, while taking into account the behavior … Read more

A sharp local threshold for integer feasibility in three-way transportation polytopes

Categories Integer Programming, Polyhedra Tags , , , , , ,

Abstract: A three-way transportation polytope consists of nonnegative three-way arrays with prescribed sums along every coordinate line. We show that its geometry and the difficulty of finding its integer points are both controlled by one local quantity: the number of cells on a line that can be positive. The change happens between two and three. … Read more

Box-Cone Representations of Bound-Factor RLT Constraints in Semidefinite Relaxations

Categories 0-1 Programming, Quadratic Programming, Semi-definite Programming Tags , , , , ,

Linear inequalities can generate large constraint systems in semidefinite relaxations of binary quadratic programs, making the quadratic subproblems of splitting methods expensive to solve. We develop a box-cone representation of bound-factor reformulation-linearization technique (RLT) constraints in semidefinite relaxations of binary quadratic programs. These constraints arise by multiplying each original linear inequality by every binary variable … Read more

Out-of-Distribution Wasserstein Ambiguity Set Construction with Inclusive and Exclusive Evidence

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

Distributionally robust optimization hedges a decision against an ambiguity set of candidate distributions. In a cold-start setting the target distribution is unobserved and no sample from it is available, so only related source distributions provide evidence for constructing that set. We propose an inclusive-exclusive Wasserstein ball model that jointly learns a center and radius from … Read more