@misc{TurnerBertholdBesancon, author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu}, title = {A Context-Aware Cutting Plane Selection Algorithm for Mixed-Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91691}, abstract = {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 measures, cut filtering techniques, and stopping criteria, extending the current state-of-the-art algorithm and obtaining a 5\\% performance improvement for SCIP over the MIPLIB 2017 benchmark set.}, language = {en} } @misc{TurnerBertholdBesanconetal., author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu and Koch, Thorsten}, title = {Cutting Plane Selection with Analytic Centers and Multiregression}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89065}, abstract = {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 propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method.}, language = {en} } @misc{TurnerBertholdBesanconetal., author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu and Koch, Thorsten}, title = {Branching via Cutting Plane Selection: Improving Hybrid Branching}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91120}, abstract = {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 used both as branching candidates and as the foundation for some cutting planes. We relate branching decisions and cutting planes to each other through the underlying disjunctions that they are based on, with a focus on Gomory mixed-integer cuts and their corresponding split disjunctions. We show that selecting branching decisions based on quality measures of Gomory mixed-integer cuts leads to relatively small branch-and-bound trees, and that the result improves when using cuts that more accurately represent the branching decisions. Finally, we show how the history of previously computed Gomory mixed-integer cuts can be used to improve the performance of the state-of-the-art hybrid branching rule of SCIP. Our results show a 4\% decrease in solve time, and an 8\% decrease in number of nodes over affected instances of MIPLIB 2017.}, language = {en} } @inproceedings{CardereraPokuttaMathieu, author = {Carderera, Alejandro and Pokutta, Sebastian and Mathieu, Besan{\c{c}}on}, title = {Simple steps are all you need: Frank-Wolfe and generalized self-concordant functions}, series = {Thirty-fifth Conference on Neural Information Processing Systems, NeurIPS 2021}, booktitle = {Thirty-fifth Conference on Neural Information Processing Systems, NeurIPS 2021}, abstract = {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 variant that uses the open-loop step size strategy 𝛾𝑑 = 2/(𝑑 + 2), obtaining a O (1/𝑑) convergence rate for this class of functions in terms of primal gap and Frank-Wolfe gap, where 𝑑 is the iteration count. This avoids the use of second-order information or the need to estimate local smoothness parameters of previous work. We also show improved convergence rates for various common cases, e.g., when the feasible region under consideration is uniformly convex or polyhedral.}, language = {en} } @article{MathieuCardereraPokutta, author = {Mathieu, Besan{\c{c}}on and Carderera, Alejandro and Pokutta, Sebastian}, title = {FrankWolfe.jl: a high-performance and flexible toolbox for Frank-Wolfe algorithms and Conditional Gradients}, series = {INFORMS Journal on Computing}, volume = {34}, journal = {INFORMS Journal on Computing}, number = {5}, doi = {10.1287/ijoc.2022.1191}, pages = {2383 -- 2865}, abstract = {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 designed with flexibility and high performance in mind, allowing for easy extension and relying on few assumptions regarding the user-provided functions. It supports Julia's unique multiple dispatch feature, and it interfaces smoothly with generic linear optimization formulations using MathOptInterface.jl.}, language = {en} } @article{BesanconAnjosBrotcorne, author = {Besan{\c{c}}on, Mathieu and Anjos, Miguel F. and Brotcorne, Luce}, title = {Complexity of near-optimal robust versions of multilevel optimization problems}, series = {Optimization Letters}, volume = {15}, journal = {Optimization Letters}, number = {8}, doi = {10.1007/s11590-021-01754-9}, pages = {2597 -- 2610}, abstract = {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 complexity of near-optimal robust multilevel problems, where near-optimal robustness is modelled through additional adversarial decision-makers. Near-optimal robust versions of multilevel problems are shown to remain in the same complexity class as the problem without near-optimality robustness under general conditions.}, language = {en} } @inproceedings{MacDonaldBesanconPokutta, author = {MacDonald, Jan and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian}, title = {Interpretable Neural Networks with Frank-Wolfe: Sparse Relevance Maps and Relevance Orderings}, series = {Proceedings of the International Conference on Machine Learning}, booktitle = {Proceedings of the International Conference on Machine Learning}, language = {en} } @misc{TjusilaBesanconTurneretal., author = {Tjusila, Gennesaret and Besancon, Mathieu and Turner, Mark and Koch, Thorsten}, title = {How Many Clues To Give? A Bilevel Formulation For The Minimum Sudoku Clue Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-90902}, abstract = {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 completed Sudoku grid, what is the minimum number of clues in any puzzle whose unique solution is the given grid? We call this problem the Minimum Sudoku Clue Problem (MSCP). We formulate MSCP as a binary bilevel linear program, present a class of globally valid inequalities, and provide a computational study on 50 MSCP instances of 9 by 9 Sudoku grids. Using a general bilevel solver, we solve 95\\% of instances to optimality, and show that the solution process benefits from the addition of a moderate amount of inequalities. Finally, we extend the proposed model to other combinatorial problems in which uniqueness of the solution is of interest.}, language = {en} } @misc{BestuzhevaBesanconChenetal., author = {Bestuzheva, Ksenia and Besan{\c{c}}on, Mathieu and Chen, Wei-Kun and Chmiela, Antonia and Donkiewicz, Tim and van Doornmalen, Jasper and Eifler, Leon and Gaul, Oliver and Gamrath, Gerald and Gleixner, Ambros and Gottwald, Leona and Graczyk, Christoph and Halbig, Katrin and Hoen, Alexander and Hojny, Christopher and van der Hulst, Rolf and Koch, Thorsten and L{\"u}bbecke, Marco and Maher, Stephen J. and Matter, Frederic and M{\"u}hmer, Erik and M{\"u}ller, Benjamin and Pfetsch, Marc E. and Rehfeldt, Daniel and Schlein, Steffan and Schl{\"o}sser, Franziska and Serrano, Felipe and Shinano, Yuji and Sofranac, Boro and Turner, Mark and Vigerske, Stefan and Wegscheider, Fabian and Wellner, Philipp and Weninger, Dieter and Witzig, Jakob}, title = {The SCIP Optimization Suite 8.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-85309}, abstract = {The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 8.0 of the SCIP Optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type for cut selection, and a complete rework of the way nonlinear constraints are handled. Additionally, SCIP 8.0 now supports interfaces for Julia as well as Matlab. Further, UG now includes a unified framework to parallelize all solvers, a utility to analyze computational experiments has been added to GCG, dual solutions can be postsolved by PaPILO, new heuristics and presolving methods were added to SCIP-SDP, and additional problem classes and major performance improvements are available in SCIP-Jack.}, language = {en} } @article{TurnerBertholdBesanconetal., author = {Turner, Mark and Berthold, Timo and Besan{\c{c}}on, Mathieu and Koch, Thorsten}, title = {Branching via Cutting Plane Selection: Improving Hybrid Branching}, publisher = {Springer}, abstract = {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 used both as branching candidates and as the foundation for some cutting planes. We relate branching decisions and cutting planes to each other through the underlying disjunctions that they are based on, with a focus on Gomory mixed-integer cuts and their corresponding split disjunctions. We show that selecting branching decisions based on quality measures of Gomory mixed-integer cuts leads to relatively small branch-and-bound trees, and that the result improves when using cuts that more accurately represent the branching decisions. Finally, we show how the history of previously computed Gomory mixed-integer cuts can be used to improve the performance of the state-of-the-art hybrid branching rule of SCIP. Our results show a \$4\\%\$ decrease in solve time, and an \$8\\%\$ decrease in number of nodes over affected instances of MIPLIB 2017.}, language = {en} }