95 citations · 203 across the 21 of their papers we have counts for
22 papers
Low-Budget Active Learning through Entropic Optimal Transport
Rim Hajal, Mathieu Besançon, Jérôme Malick
We consider low-budget active learning, which consists of selecting a limited number of points, the coreset, such that a model can be trained to high accuracy on the selection only…
On the Iterate Convergence of AdaGrad for Generalized Smooth Convex Optimization
Mathieu Besançon, Tung Quoc Le
We prove sequential convergence results for the AdaGrad algorithm family optimizing convex differentiable objectives. Specifically, we provide necessary and sufficient conditions f…
Graph Isomorphism: Mixed-Integer Convex Optimization from First-Order Methods
Wenjie Xiao, Mathieu Besançon, Patrick Gelß +3
The graph isomorphism (GI) problem, which asks whether two graphs are structurally identical, occupies a unique position in computational complexity -- it is neither known to be so…
Efficient Sparse Flow Decomposition Methods for RNA Multi-Assembly
Mathieu Besançon
Decomposing a flow on a Directed Acyclic Graph (DAG) into a weighted sum of a small number of paths is an essential task in operations research and bioinformatics. This problem, re…
Improved algorithms and novel applications of the FrankWolfe.jl library
Mathieu Besançon, Sébastien Designolle, Jannis Halbey +6
Frank-Wolfe (FW) algorithms have emerged as an essential class of methods for constrained optimization, especially on large-scale problems. In this paper, we summarize the algorith…
A Multi-Reference Relaxation Enforced Neighborhood Search Heuristic in SCIP
Suresh Bolusani, Gioni Mexi, Mathieu Besançon +1
This paper proposes and evaluates a Multi-Reference Relaxation Enforced Neighborhood Search (MRENS) heuristic within the SCIP solver. This study marks the first integration and eva…
Solving the Optimal Experiment Design Problem with Mixed-Integer Convex Methods
Deborah Hendrych, Mathieu Besançon, Sebastian Pokutta
We tackle the Optimal Experiment Design Problem, which consists of choosing experiments to run or observations to select from a finite set to estimate the parameters of a system. T…
Probabilistic Lookahead Strong Branching via a Stochastic Abstract Branching Model
Gioni Mexi, Somayeh Shamsi, Mathieu Besançon +1
Strong Branching (SB) is a cornerstone of all modern branching rules used in the Branch-and-Bound (BnB) algorithm, which is at the center of Mixed-Integer Programming solvers. In i…
The MIP Workshop 2023 Computational Competition on Reoptimization
Suresh Bolusani, Mathieu Besançon, Ambros Gleixner +5
This paper describes the computational challenge developed for a computational competition held in 2023 for the anniversary of the Mixed Integer Programming Work…
Scylla: a matrix-free fix-propagate-and-project heuristic for mixed-integer optimization
Gioni Mexi, Mathieu Besançon, Suresh Bolusani +3
We introduce Scylla, a primal heuristic for mixed-integer optimization problems. It exploits approximate solves of the Linear Programming relaxations through the matrix-free Primal…
A Context-Aware Cutting Plane Selection Algorithm for Mixed-Integer Programming
Mark Turner, Timo Berthold, Mathieu Besançon
The current cut selection algorithm used in mixed-integer programming solvers has remained largely unchanged since its creation. In this paper, we propose a set of new cut scoring…
Branching via Cutting Plane Selection: Improving Hybrid Branching
Mark Turner, Timo Berthold, Mathieu Besançon +1
Cutting planes and branching are two of the most important algorithms for solving mixed-integer linear programs. For both algorithms, disjunctions play an important role, being use…
How Many Clues To Give? A Bilevel Formulation For The Minimum Sudoku Clue Problem
Gennesaret Tjusila, Mathieu Besançon, Mark Turner +1
It has been shown that any 9 by 9 Sudoku puzzle must contain at least 17 clues to have a unique solution. This paper investigates the more specific question: given a particular com…
Enabling Research through the SCIP Optimization Suite 8.0
Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen +32
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. The focus of…
Improved local models and new Bell inequalities via Frank-Wolfe algorithms
Sébastien Designolle, Gabriele Iommazzo, Mathieu Besançon +3
In Bell scenarios with two outcomes per party, we algorithmically consider the two sides of the membership problem for the local polytope: constructing local models and deriving se…
Cutting Plane Selection with Analytic Centers and Multiregression
Mark Turner, Timo Berthold, Mathieu Besançon +1
Cutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We…
Flexible Differentiable Optimization via Model Transformations
Mathieu Besançon, Joaquim Dias Garcia, Benoît Legat +1
We introduce DiffOpt.jl, a Julia library to differentiate through the solution of optimization problems with respect to arbitrary parameters present in the objective and/or constra…
Interpretable Neural Networks with Frank-Wolfe: Sparse Relevance Maps and Relevance Orderings
Jan Macdonald, Mathieu Besançon, Sebastian Pokutta
We study the effects of constrained optimization formulations and Frank-Wolfe algorithms for obtaining interpretable neural network predictions. Reformulating the Rate-Distortion E…
Scalable Frank-Wolfe on Generalized Self-concordant Functions via Simple Steps
Alejandro Carderera, Mathieu Besançon, Sebastian Pokutta
Generalized self-concordance is a key property present in the objective function of many important learning problems. We establish the convergence rate of a simple Frank-Wolfe vari…
FrankWolfe.jl: a high-performance and flexible toolbox for Frank-Wolfe algorithms and Conditional Gradients
Mathieu Besançon, Alejandro Carderera, Sebastian Pokutta
We present FrankWolfe.jl, an open-source implementation of several popular Frank-Wolfe and Conditional Gradients variants for first-order constrained optimization. The package is d…
Complexity of near-optimal robust versions of multilevel optimization problems
Mathieu Besançon, Miguel F. Anjos, Luce Brotcorne
Near-optimality robustness extends multilevel optimization with a limited deviation of a lower level from its optimal solution, anticipated by higher levels. We analyze the complex…
Distributions.jl: Definition and Modeling of Probability Distributions in the JuliaStats Ecosystem
Mathieu Besançon, Theodore Papamarkou, David Anthoff +4
Random variables and their distributions are a central part in many areas of statistical methods. The Distributions.jl package provides Julia users and developers tools for working…