Paperlane

no. 5 · Friday 30 October 2026

A Compressive Sensing Inspired Monte-Carlo Method for Combinatorial Optimization

Baptiste Chevalier, Shimpei Yamaguchi, Wojciech Roga and Masahiro Takeoka

math.OC · v3 · 21 pp

Abstract

In this paper, we present a Monte-Carlo Compressive Optimization algorithm, a new method for black-box combinatorial optimization, which only assumes that the objective is compressible. The method relies on random queries to the objective function in order to estimate generalized moments. Next, a greedy algorithm from compressive sensing is repurposed to find the global optimum when not overfitting to the samples. We provide numerical results giving evidence that our method is competitive by comparing it with digital annealing. Moreover, we give theoretical justification for the success of the algorithm and analyze its properties. The practicality of our algorithm is enhanced by the ability to tune the heuristic parameters to the available computational resources. An end-to-end open-source implementation is available to use our method.

comments
21 pages, 7 figures, 1 table
fields
Optimization and Control
pdf ↗ page arXiv:2510.24755 ↗