Articles

Journal Articles

First-Order Methods for Wasserstein Distributionally Robust Constrained Optimization

Published in Preprint arXiv, 2026

We consider constrained problems in which input data are affected by errors. In such settings, Wasserstein distributionally robust optimization provides a principled framework to mitigate model risk by optimizing against worst-case data distributions within Wasserstein ambiguity sets. However, the numerical resolution of the resulting problems remains challenging, especially in constrained settings. In this paper, we provide a general, practical way to solve Wasserstein distributionally robust formulations in the presence of constraints. Our approach only requires a linear minimization oracle for the feasible set, and combines two key ingredients: (i) an entropic regularization of the distributionally robust value function, which makes it possible to compute stochastic gradient estimators, and (ii) a stochastic Frank-Wolfe algorithm, which minimizes the regularized robust objective while naturally handling constraints. We illustrate the method, its tractability, and its interests against empirical risk minimization, on two operations research problems: the traffic assignment and the minimum quadratic spanning tree.

Recommended citation: Hubert Villuendas, Mathieu Besançon and Jérôme Malick. (2026). "First-Order Methods for Wasserstein Distributionally Robust Constrained Optimization." preprint arXiv:2607.11460.
Download Paper

Knapsack with compactness: a Semidefinite Approach

Published in Preprint arXiv, 2025

The min-knapsack problem with compactness constraints extends the classical knapsack problem, in the case of ordered items, by introducing a restriction ensuring that they cannot be too far apart. This problem has applications in statistics, particularly in the detection of change-points in time series. In this paper, we propose a semidefinite programming approach for this problem, incorporating compactness in constraints or in objective. We study and compare the different relaxations, and argue that our method provides high-quality heuristics and tight bounds. In particular, the single hyperparameter of our penalized semidefinite models naturally balances the trade-off between compactness and accuracy of the computed solutions. Numerical experiments illustrate, on the hardest instances, the effectiveness and versatility of our approach compared to the existing mixed-integer programming formulation.

Recommended citation: Hubert Villuendas, Mathieu Besançon and Jérôme Malick. (2025). "Knapsack with compactness: a semidefinite approach." preprint arXiv:2504.17543.
Download Paper