publications
2026
- preprintDiscrete eigenvalue optimization from entropic smoothing and first-order methodsDeborah Hendrych, Mathieu Besançon, and Sebastian Pokutta2026
We study the maximization of the minimum eigenvalue under combinatorial and integrality constraints. We propose a new approach based on branch-and-bound combines entropic smoothing of the minimum eigenvalue function and Frank-Wolfe methods over concave relaxations of the constraints, thereby exploiting combinatorial structure through linear optimization oracles. We establish approximation and convergence guarantees, including for truncated gradients computed from partial eigendecompositions, and introduce rank- and eigenvalue-based pruning and duality-based variable fixing. We evaluate the method on E-optimal experimental design and maximum algebraic connectivity problems and compare it with SCIP-SDP. The results show that our approach is particularly effective for large-dimensional instances and problems with additional combinatorial structure, whereas SCIP-SDP performs better on moderately sized instances with simpler constraints.
@misc{2026_HendrychBesanconPokutta_DiscreteEigenvalueOptimization_2608-27024, archiveprefix = {arXiv}, primaryclass = {math.OC}, year = {2026}, tags = {discrete eigenvalue optimization, mixed-integer optimization, entropic smoothing, first-order methods}, author = {Hendrych, Deborah and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian}, title = {Discrete eigenvalue optimization from entropic smoothing and first-order methods}, date = {2026-08-27} } - CPAIOR26Graph Isomorphism: Mixed-Integer Convex Optimization from First-Order MethodsWenjie Xiao, Mathieu Besançon, Patrick Gelß, and 3 more authorsProceedings of the International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 2026
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 solvable in polynomial time, nor proven to be NP-complete. We propose a convex mixed-integer formulation of the problem and leverage first-order convex optimization to tackle it, following a stream of recent work on optimization-driven graph isomorphism detection. We strengthen our formulation with variable fixing techniques that prove highly effective while preserving the polyhedral structure. We perform extensive computations evaluating the performance of different families of methods including a mixed-integer convex formulation, mixed-integer linear optimization, local search and spectral heuristics over a collection of challenging GI instances. We find that a high level of symmetry is beneficial for optimization-based methods. On the other hand, presolving techniques that detect local substructures to fix variables are crucial for asymmetric instances. The proposed method outperforms the second best approach, the integer feasibility approach, on 6 of the 12 graphs families and is on par with it on symmetric families.
@article{xiao2025graph, title = {Graph Isomorphism: Mixed-Integer Convex Optimization from First-Order Methods}, author = {Xiao, Wenjie and Besan{\c{c}}on, Mathieu and Gel{\ss}, Patrick and Hendrych, Deborah and Klus, Stefan and Pokutta, Sebastian}, journal = {Proceedings of the International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research}, year = {2026}, archiveprefix = {arXiv}, primaryclass = {math.OC}, tags = {graph isomorphism, mixed-integer optimization, first-order methods} } - MPCA Frank-Wolfe-based primal heuristic for quadratic mixed-integer optimizationGioni Mexi, Deborah Hendrych, Sébastien Designolle, and 2 more authorsMathematical Programming Computation, 2026
We propose a primal heuristic for quadratic mixed-integer problems. Our method extends the Boscia framework – originally a mixed-integer convex solver leveraging a Frank-Wolfe-based branch-and-bound approach – to address nonconvex quadratic objective and constraints. We reformulate nonlinear constraints, introduce preprocessing steps, and a suite of heuristics including rounding strategies, gradient-guided selection, and large neighborhood search techniques that exploit integer-feasible vertices generated during the Frank-Wolfe iterations. Computational results demonstrate the effectiveness of our method in solving challenging MIQCQPs, achieving improvements on QPLIB instances within minutes and winning first place in the Land-Doig MIP Computational Competition 2025.
@article{2025_MexiEtAl_Frankwolfeheuristic_2508-01299, archiveprefix = {arXiv}, primaryclass = {math.OC}, year = {2026}, journal = {Mathematical Programming Computation}, doi = {10.1007/s12532-026-00340-3}, author = {Mexi, Gioni and Hendrych, Deborah and Designolle, S{\'e}bastien and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian}, title = {A {Frank-Wolfe}-based primal heuristic for quadratic mixed-integer optimization}, tags = {Frank-Wolfe, convex optimization, mixed-integer optimization} }
2025
- preprintSparseSwaps: Tractable LLM Pruning Mask Refinement at ScaleMax Zimmer, Christophe Roux, Moritz Wagner, and 2 more authors2025
The resource requirements of neural networks can be significantly reduced through pruning - the removal of seemingly less important parameters. However, for LLMs, full retraining to recover pruning-induced performance degradation is often prohibitive and classical approaches such as magnitude pruning are suboptimal on Transformers. State-of-the-art methods hence solve a layer-wise mask selection problem: finding a pruning mask that minimizes per-layer pruning error on a small set of calibration data. Exactly solving this problem is computationally infeasible due to its combinatorial nature and the size of the search space, and existing approaches rely on approximations or heuristics. We demonstrate that the mask selection problem can be made drastically more tractable at LLM scale. To that end, we decouple the rows by enforcing equal sparsity levels per row. This allows us to derive optimal 1-swaps (exchanging one kept and one pruned weight) computable efficiently via the Gram matrix. We propose a simple 1-swap algorithm that warmstarts from any pruning mask, runs efficiently on GPUs at LLM scale, and is essentially hyperparameter-free. Our approach reduces per-layer pruning error by up to 60% over Wanda (Sun et al., 2024) and consistently improves perplexity and zero-shot accuracy across state-of-the-art GPT architectures.
@article{zimmer2025sparseswaps, title = {SparseSwaps: Tractable LLM Pruning Mask Refinement at Scale}, author = {Zimmer, Max and Roux, Christophe and Wagner, Moritz and Hendrych, Deborah and Pokutta, Sebastian}, year = {2025}, archiveprefix = {arXiv}, primaryclass = {cs.LG}, tags = {LLM pruning, sparsity} } - ACM TOMSImproved algorithms and novel applications of the FrankWolfe.jl libraryMathieu Besançon, Sébastien Designolle, Jannis Halbey, and 6 more authorsACM Transactions on Mathematical Software, 2025
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 algorithmic design choices and progress made in the last years of the development of FrankWolfe.jl, a Julia package gathering high-performance implementations of state-of-the-art FW variants. We review key use cases of the library in the recent literature, which match its original dual purpose: first, becoming the de-facto toolbox for practitioners applying FW methods to their problem, and second, offering a modular ecosystem to algorithm designers who experiment with their own variants and implementations of algorithmic blocks. Finally, we demonstrate the performance of several FW variants on important problem classes in several experiments, which we curated in a separate repository for continuous benchmarking.
@article{besanccon2025improved, title = {Improved algorithms and novel applications of the {FrankWolfe.jl} library}, author = {Besan{\c{c}}on, Mathieu and Designolle, S{\'e}bastien and Halbey, Jannis and Hendrych, Deborah and Kuzinowicz, Dominik and Pokutta, Sebastian and Troppens, Hannah and Herrmannsdoerfer, Daniel Viladrich and Wirth, Elias}, journal = {ACM Transactions on Mathematical Software}, year = {2025}, tags = {Frank-Wolfe, Julia, convex optimization}, } - preprintBoscia. jl: A review and tutorialWenjie Xiao, Deborah Hendrych, Mathieu Besançon, and 1 more author2025
ixed-integer nonlinear optimization (MINLP) comprises a large class of problems that are challenging to solve and exhibit a wide range of structures. The Boscia framework Hendrych et al. (2025b) focuses on convex MINLP where the nonlinearity appears in the objective only. This paper provides an overview of the framework and practical examples to illustrate its use and customizability. One key aspect is the integration and exploitation of Frank-Wolfe methods as continuous solvers within a branch-and-bound framework, enabling inexact node processing, warm-starting and explicit use of combinatorial structure among others. Three examples illustrate its flexibility, the user control over the optimization process and the benefit of oracle-based access to the objective and its gradient. The aim of this tutorial is to provide readers with an understanding of the main principles of the framework.
@article{xiao2025boscia, title = {Boscia. jl: A review and tutorial}, author = {Xiao, Wenjie and Hendrych, Deborah and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian}, archiveprefix = {arXiv}, primaryclass = {math.OC}, year = {2025}, tags = {Boscia, Julia, convex optimization, mixed-integer optimization} } - MPCConvex mixed-integer optimization with Frank-Wolfe methodsDeborah Hendrych, Hannah Troppens, Mathieu Besançon, and 1 more authorMathematical Programming Computation, 2025
Mixed-integer nonlinear optimization encompasses a broad class of problems that present both theoretical and computational challenges. We propose a new type of method to solve these problems based on a branch-and-bound algorithm with convex node relaxations. These relaxations are solved with a Frank–Wolfe algorithm over the convex hull of mixed-integer feasible points instead of the continuous relaxation via calls to a mixed-integer linear solver as the linear minimization oracle. The proposed method computes feasible solutions while working on a single representation of the polyhedral constraints, leveraging the full extent of mixed-integer linear solvers without an outer approximation scheme and can exploit inexact solutions of node subproblems.
@article{hendrych2023convex, title = {Convex mixed-integer optimization with {Frank-Wolfe} methods}, author = {Hendrych, Deborah and Troppens, Hannah and Besançon, Mathieu and Pokutta, Sebastian}, journal = {Mathematical Programming Computation}, year = {2025}, volume = {17}, pages = {731-757}, primaryclass = {math.OC}, tags = {mixed-integer optimization, Frank-Wolfe, convex optimization}, } - ICML25Secant Line Search for Frank-Wolfe AlgorithmsDeborah Hendrych, Mathieu Besançon, David Martı́nez-Rubio, and 1 more authorPMLR, 2025
We present a new step-size strategy based on the secant method for Frank-Wolfe algorithms. This strategy, which requires mild assumptions about the function under consideration, can be applied to any Frank-Wolfe algorithm. It is as effective as full line search and, in particular, allows for adapting to the local smoothness of the function, such as in (Pedregosa et al., 2020), but comes with a significantly reduced computational cost, leading to higher effective rates of convergence. We provide theoretical guarantees and demonstrate the effectiveness of the strategy through numerical experiments.
@article{hendrych2025secant, title = {Secant Line Search for {Frank-Wolfe} Algorithms}, author = {Hendrych, Deborah and Besan{\c{c}}on, Mathieu and Mart{\'\i}nez-Rubio, David and Pokutta, Sebastian}, journal = {PMLR}, year = {2025}, tags = {Frank-Wolfe, convex optimization}, }
2024
- INFORMSNetwork Design for the Traffic Assignment Problem with Mixed-Integer Frank-WolfeKartikey Sharma, Deborah Hendrych, Mathieu Besançon, and 1 more authorIn Proceedings of the INFORMS Optimization Society Conference, 2024
We tackle the network design problem for centralized traffic assignment, which can be cast as a mixed-integer convex optimization (MICO) problem. For this task, we propose different formulations and solution methods in both a deterministic and a stochastic setting in which the demand is unknown in the design phase. We leverage the recently proposed Boscia framework, which can solve MICO problems when the main nonlinearity stems from a differentiable objective function. Boscia tackles these problems by branch-and-bound with continuous relaxations solved approximately with Frank-Wolfe algorithms. We compare different linear relaxations and the corresponding subproblems solved by Frank-Wolfe, and alternative problem formulations to identify the situations in which each performs best. Our experiments evaluate the different approaches on instances from the Transportation Networks library and highlight the suitability of the mixed-integer Frank-Wolfe algorithm for this problem. In particular, we find that the Boscia framework is particularly applicable to this problem and that a mixed-integer linear Frank-Wolfe subproblem performs well for the deterministic case, while a penalty-based approach, with decoupled feasible regions for the design and flow variables, dominates other approaches for stochastic instances with many scenarios.
@inproceedings{2024_SharmaHendrychBesanconPokutta_NetworkdesignMicoFrankwolfe, year = {2024}, booktitle = {Proceedings of the INFORMS Optimization Society Conference}, archiveprefix = {arXiv}, primaryclass = {math.OC}, author = {Sharma, Kartikey and Hendrych, Deborah and Besançon, Mathieu and Pokutta, Sebastian}, title = {Network Design for the Traffic Assignment Problem with Mixed-Integer {Frank-Wolfe}}, tags = {network design, mixed-integer optimization, Frank-Wolfe} } - SEA24Solving the Optimal Experiment Design Problem with Mixed-integer Convex MethodsDeborah Hendrych, Mathieu Besançon, and Sebastian PokuttaIn Proceedings of the Symposium on Experimental Algorithms, 2024
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. The objective is to maximize some measure of information gained about the system from the observations, leading to a convex integer optimization problem. We leverage Boscia.jl, a recent algorithmic framework, which is based on a nonlinear branch-and-bound algorithm with node relaxations solved to approximate optimality using Frank-Wolfe algorithms. One particular advantage of the method is its efficient utilization of the polytope formed by the original constraints which is preserved by the method, unlike alternative methods relying on epigraph-based formulations. We assess the method against both generic and specialized convex mixed-integer approaches. Computational results highlight the performance of the proposed method, especially on large and challenging instances.
@inproceedings{2023_HendrychBesanconPokutta_Optimalexperimentdesign, year = {2024}, booktitle = {Proceedings of the Symposium on Experimental Algorithms}, doi = {10.4230/LIPIcs.SEA.2024.16}, archiveprefix = {arXiv}, primaryclass = {math.OC}, author = {Hendrych, Deborah and Besançon, Mathieu and Pokutta, Sebastian}, title = {Solving the Optimal Experiment Design Problem with Mixed-integer Convex Methods}, tags = {optimal experiment design, mixed-integer optimization, Frank-Wolfe} }