@article{AnztBachDruskatetal.2020, author = {Anzt, H. and Bach, F. and Druskat, S. and L{\"o}ffler, F. and Loewe, A. and Renard, B. Y. and Seemann, G. and Struck, A. and Achhammer, E. and Appell, F. and Bader, M. and Brusch, L. and Busse, C. and Chourdakis, G. and Dabrowski, P. W. and Ebert, P. and Flemisch, B. and Friedl, S. and Fritzsch, B. and Funk, M. D. and Gast, V. and Goth, F. and Grad, J.-N. and Hermann, Sibylle and Hohmann, F. and Janosch, S. and Kutra, D. and Linxweiler, J. and Muth, T. and Peters-Kottig, Wolfgang and Rack, F. and Raters, F. H. C. and Rave, S. and Reina, G. and Reißig, M. and Ropinski, T. and Schaarschmidt, J. and Seibold, H. and Thiele, J. P. and Uekermann, B. and Unger, S. and Weeber, R.}, title = {An environment for sustainable research software in Germany and beyond: current state, open challenges, and call for action [version 1; peer review: 1 approved, 1 approved with reservations]}, journal = {F1000Research}, number = {9:295}, doi = {10.12688/f1000research.23224.1}, pages = {28}, year = {2020}, abstract = {Research software has become a central asset in academic research. It optimizes existing and enables new research methods, implements and embeds research knowledge, and constitutes an essential research product in itself. Research software must be sustainable in order to understand, replicate, reproduce, and build upon existing research or conduct new research effectively. In other words, software must be available, discoverable, usable, and adaptable to new needs, both now and in the future. Research software therefore requires an environment that supports sustainability. Hence, a change is needed in the way research software development and maintenance are currently motivated, incentivized, funded, structurally and infrastructurally supported, and legally treated. Failing to do so will threaten the quality and validity of research. In this paper, we identify challenges for research software sustainability in Germany and beyond, in terms of motivation, selection, research software engineering personnel, funding, infrastructure, and legal aspects. Besides researchers, we specifically address political and academic decision-makers to increase awareness of the importance and needs of sustainable research software practices. In particular, we recommend strategies and measures to create an environment for sustainable research software, with the ultimate goal to ensure that software-driven research is valid, reproducible and sustainable, and that software is recognized as a first class citizen in research. This paper is the outcome of two workshops run in Germany in 2019, at deRSE19 - the first International Conference of Research Software Engineers in Germany - and a dedicated DFG-supported follow-up workshop in Berlin.}, language = {en} } @article{EiflerGleixner2021, author = {Eifler, Leon and Gleixner, Ambros}, title = {A Computational Status Update for Exact Rational Mixed Integer Programming}, journal = {Integer Programming and Combinatorial Optimization: 22th International Conference, IPCO 2021}, doi = {10.1007/978-3-030-73879-2_12}, year = {2021}, abstract = {The last milestone achievement for the roundoff-error-free solution of general mixed integer programs over the rational numbers was a hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. We describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal heuristics, employs a faster rational LP solver based on LP iterative refinement, and is able to produce independently verifiable certificates of optimality. We study the significantly improved performance and give insights into the computational behavior of the new algorithmic components. On the MIPLIB 2017 benchmark set, we observe an average speedup of 6.6x over the original framework and 2.8 times as many instances solved within a time limit of two hours.}, language = {en} } @misc{EiflerGleixner2021, author = {Eifler, Leon and Gleixner, Ambros}, title = {A Computational Status Update for Exact Rational Mixed Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81298}, year = {2021}, abstract = {The last milestone achievement for the roundoff-error-free solution of general mixed integer programs over the rational numbers was a hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. We describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal heuristics, employs a faster rational LP solver based on LP iterative refinement, and is able to produce independently verifiable certificates of optimality. We study the significantly improved performance and give insights into the computational behavior of the new algorithmic components. On the MIPLIB 2017 benchmark set, we observe an average speedup of 6.6x over the original framework and 2.8 times as many instances solved within a time limit of two hours.}, language = {en} } @inproceedings{SofranacGleixnerPokutta2021, author = {Sofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {An Algorithm-Independent Measure of Progress for Linear Constraint Propagation}, volume = {210}, booktitle = {27th International Conference on Principles and Practice of Constraint Programming (CP 2021)}, doi = {10.4230/LIPIcs.CP.2021.52}, pages = {52:1 -- 52:17}, year = {2021}, abstract = {Propagation of linear constraints has become a crucial sub-routine in modern Mixed-Integer Programming (MIP) solvers. In practice, iterative algorithms with tolerance-based stopping criteria are used to avoid problems with slow or infinite convergence. However, these heuristic stopping criteria can pose difficulties for fairly comparing the efficiency of different implementations of iterative propagation algorithms in a real-world setting. Most significantly, the presence of unbounded variable domains in the problem formulation makes it difficult to quantify the relative size of reductions performed on them. In this work, we develop a method to measure -- independently of the algorithmic design -- the progress that a given iterative propagation procedure has made at a given point in time during its execution. Our measure makes it possible to study and better compare the behavior of bounds propagation algorithms for linear constraints. We apply the new measure to answer two questions of practical relevance: (i) We investigate to what extent heuristic stopping criteria can lead to premature termination on real-world MIP instances. (ii) We compare a GPU-parallel propagation algorithm against a sequential state-of-the-art implementation and show that the parallel version is even more competitive in a real-world setting than originally reported.}, language = {en} } @article{CardereraPokutta2020, author = {Carderera, Alejandro and Pokutta, Sebastian}, title = {Second-order Conditional Gradient Sliding}, year = {2020}, abstract = {Constrained second-order convex optimization algorithms are the method of choice when a high accuracy solution to a problem is needed, due to their local quadratic convergence. These algorithms require the solution of a constrained quadratic subproblem at every iteration. We present the \emph{Second-Order Conditional Gradient Sliding} (SOCGS) algorithm, which uses a projection-free algorithm to solve the constrained quadratic subproblems inexactly. When the feasible region is a polytope the algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations. Once in the quadratic regime the SOCGS algorithm requires O(log(log1/ε)) first-order and Hessian oracle calls and O(log(1/ε)log(log1/ε)) linear minimization oracle calls to achieve an ε-optimal solution. This algorithm is useful when the feasible region can only be accessed efficiently through a linear optimization oracle, and computing first-order information of the function, although possible, is costly.}, language = {en} } @article{MathieuCardereraPokutta2022, 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}, volume = {34}, journal = {INFORMS Journal on Computing}, number = {5}, doi = {10.1287/ijoc.2022.1191}, pages = {2383 -- 2865}, year = {2022}, 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{AbbasAmbainisAugustinoetal.2024, author = {Abbas, Amira and Ambainis, Andris and Augustino, Brandon and B{\"a}rtschi, Andreas and Buhrman, Harry and Coffrin, Carleton and Cortiana, Giorgio and Dunjko, Vedran and Egger, Daniel J. and Elmegreen, Bruce G. and Franco, Nicola and Fratini, Filippo and Fuller, Bryce and Gacon, Julien and Gonciulea, Constantin and Gribling, Sander and Gupta, Swati and Hadfield, Stuart and Heese, Raoul and Kircher, Gerhard and Kleinert, Thomas and Koch, Thorsten and Korpas, Georgios and Lenk, Steve and Marecek, Jakub and Markov, Vanio and Mazzola, Guglielmo and Mensa, Stefano and Mohseni, Naeimeh and Nannicini, Giacomo and O'Meara, Corey and Tapia, Elena Pe{\~n}a and Pokutta, Sebastian and Proissl, Manuel and Rebentrost, Patrick and Sahin, Emre and Symons, Benjamin C. B. and Tornow, Sabine and Valls, V{\´i}ctor and Woerner, Stefan and Wolf-Bauwens, Mira L. and Yard, Jon and Yarkoni, Sheir and Zechiel, Dirk and Zhuk, Sergiy and Zoufal, Christa}, title = {Challenges and opportunities in quantum optimization}, volume = {6}, journal = {Nature Reviews Physics}, publisher = {Springer Science and Business Media LLC}, issn = {2522-5820}, arxiv = {http://arxiv.org/abs/2312.02279}, doi = {10.1038/s42254-024-00770-9}, pages = {718 -- 735}, year = {2024}, language = {en} } @misc{HosodaMaherShinanoetal.2021, author = {Hosoda, Junko and Maher, Stephen J. and Shinano, Yuji and Villumsen, Jonas Christoffer}, title = {Location, transshipment and routing: An adaptive transportation network integrating long-haul and local vehicle routing}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-83438}, year = {2021}, abstract = {The routing of commodities is a tactical problem in supply chain management that aims to synchronise transportation services connecting a network of warehouses and consolidation locations. This paper considers the routing of commodities in a transportation network that is flexible in response to demand through changes to regional warehouse clustering and the designation of consolidation locations. Traditionally, warehouse clustering and consolidation locations are determined as part of strategic planning that is performed months to years in advance of operations---limiting the flexibility in transportation networks to respond to changes in demand. A mathematical programming-based algorithmic framework is proposed to integrate the strategic decisions of location planning with tactical decisions of vehicle routing and synchronisation. A multi-armed bandit problem is developed to explore warehouse clustering decisions and exploit those that lead to small transportation costs. An extensive computational study will show that the proposed algorithmic framework effectively integrates strategic and tactical planning decisions to reduce the overall transportation costs.}, language = {en} } @inproceedings{SofranacGleixnerPokutta2020, author = {Sofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse Matrices}, booktitle = {2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3)}, arxiv = {http://arxiv.org/abs/2009.07785}, doi = {10.1109/IA351965.2020.00007}, pages = {1 -- 11}, year = {2020}, abstract = {Fast domain propagation of linear constraints has become a crucial component of today's best algorithms and solvers for mixed integer programming and pseudo-boolean optimization to achieve peak solving performance. Irregularities in the form of dynamic algorithmic behaviour, dependency structures, and sparsity patterns in the input data make efficient implementations of domain propagation on GPUs and, more generally, on parallel architectures challenging. This is one of the main reasons why domain propagation in state-of-the-art solvers is single thread only. In this paper, we present a new algorithm for domain propagation which (a) avoids these problems and allows for an efficient implementation on GPUs, and is (b) capable of running propagation rounds entirely on the GPU, without any need for synchronization or communication with the CPU. We present extensive computational results which demonstrate the effectiveness of our approach and show that ample speedups are possible on practically relevant problems: on state-of-the-art GPUs, our geometric mean speed-up for reasonably-large instances is around 10x to 20x and can be as high as 195x on favorably-large instances.}, language = {en} } @article{ŠofranacGleixnerPokutta2022, author = {Šofranac, Boro and Gleixner, Ambros and Pokutta, Sebastian}, title = {Accelerating domain propagation: An efficient GPU-parallel algorithm over sparse matrices}, volume = {109}, journal = {Parallel Computing}, doi = {10.1016/j.parco.2021.102874}, pages = {102874}, year = {2022}, abstract = {• Currently, domain propagation in state-of-the-art MIP solvers is single thread only. • The paper presents a novel, efficient GPU algorithm to perform domain propagation. • Challenges are dynamic algorithmic behavior, dependency structures, sparsity patterns. • The algorithm is capable of running entirely on the GPU with no CPU involvement. • We achieve speed-ups of around 10x to 20x, up to 180x on favorably-large instances.}, language = {en} } @article{GleixnerHendelGamrathetal.2021, author = {Gleixner, Ambros and Hendel, Gregor and Gamrath, Gerald and Achterberg, Tobias and Bastubbe, Michael and Berthold, Timo and Christophel, Philipp M. and Jarck, Kati and Koch, Thorsten and Linderoth, Jeff and L{\"u}bbecke, Marco and Mittelmann, Hans and Ozyurt, Derya and Ralphs, Ted and Salvagnin, Domenico and Shinano, Yuji}, title = {MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library}, volume = {13}, journal = {Mathematical Programming Computation}, number = {3}, doi = {10.1007/s12532-020-00194-3}, pages = {443 -- 490}, year = {2021}, abstract = {We report on the selection process leading to the sixth version of the Mixed Integer Programming Library. Selected from an initial pool of over 5,000 instances, the new MIPLIB 2017 collection consists of 1,065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, the compilation of these sets was done using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encoded requirements on diversity and balancedness with respect to instance features and performance data.}, language = {en} } @misc{BestuzhevaVoelkerGleixner2023, author = {Bestuzheva, Ksenia and V{\"o}lker, Helena and Gleixner, Ambros}, title = {Strengthening SONC Relaxations with Constraints Derived from Variable Bounds}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89510}, year = {2023}, abstract = {Nonnegativity certificates can be used to obtain tight dual bounds for polynomial optimization problems. Hierarchies of certificate-based relaxations ensure convergence to the global optimum, but higher levels of such hierarchies can become very computationally expensive, and the well-known sums of squares hierarchies scale poorly with the degree of the polynomials. This has motivated research into alternative certificates and approaches to global optimization. We consider sums of nonnegative circuit polynomials (SONC) certificates, which are well-suited for sparse problems since the computational cost depends on the number of terms in the polynomials and does not depend on the degrees of the polynomials. We propose a method that guarantees that given finite variable domains, a SONC relaxation will yield a finite dual bound. This method opens up a new approach to utilizing variable bounds in SONC-based methods, which is particularly crucial for integrating SONC relaxations into branch-and-bound algorithms. We report on computational experiments with incorporating SONC relaxations into the spatial branch-and-bound algorithm of the mixed-integer nonlinear programming framework SCIP. Applying our strengthening method increases the number of instances where the SONC relaxation of the root node yielded a finite dual bound from 9 to 330 out of 349 instances in the test set.}, language = {en} } @misc{BestuzhevaGleixnerVoelker2022, author = {Bestuzheva, Ksenia and Gleixner, Ambros and V{\"o}lker, Helena}, title = {Strengthening SONC Relaxations with Constraints Derived from Variable Bounds}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-88306}, year = {2022}, abstract = {Certificates of polynomial nonnegativity can be used to obtain tight dual bounds for polynomial optimization problems. We consider Sums of Nonnegative Circuit (SONC) polynomials certificates, which are well suited for sparse problems since the computational cost depends only on the number of terms in the polynomials and does not depend on the degrees of the polynomials. This work is a first step to integrating SONC-based relaxations of polynomial problems into a branch-and-bound algorithm. To this end, the SONC relaxation for constrained optimization problems is extended in order to better utilize variable bounds, since this property is key for the success of a relaxation in the context of branch-and-bound. Computational experiments show that the proposed extension is crucial for making the SONC relaxations applicable to most constrained polynomial optimization problems and for integrating the two approaches.}, language = {en} } @article{TjusilaBesanconTurneretal.2024, author = {Tjusila, Gennesaret and Besan{\c{c}}on, Mathieu and Turner, Mark and Koch, Thorsten}, title = {How Many Clues To Give? A Bilevel Formulation For The Minimum Sudoku Clue Problem}, volume = {54}, journal = {Operations Research Letters}, doi = {10.1016/j.orl.2024.107105}, pages = {107105}, year = {2024}, 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} } @article{RaminBestuzhevaGargaloetal.2021, author = {Ramin, Elham and Bestuzheva, Ksenia and Gargalo, Carina and Ramin, Danial and Schneider, Carina and Ramin, Pedram and Flores-Alsina, Xavier and Andersen, Maj M. and Gernaey, Krist V.}, title = {Incremental design of water symbiosis networks with prior knowledge: The case of an industrial park in Kenya}, volume = {751}, journal = {Science of the Total Environment}, doi = {https://doi.org/10.1016/j.scitotenv.2020.141706}, year = {2021}, abstract = {Industrial parks have a high potential for recycling and reusing resources such as water across companies by creating symbiosis networks. In this study, we introduce a mathematical optimization framework for the design of water network integration in industrial parks formulated as a large-scale standard mixed-integer non-linear programming (MINLP) problem. The novelty of our approach relies on i) developing a multi-level incremental optimization framework for water network synthesis, ii) including prior knowledge of demand growth and projected water scarcity to evaluate the significance of water-saving solutions, iii) incorporating a comprehensive formulation of water network synthesis problem including multiple pollutants and different treatment units and iv) performing a multi-objective optimization of the network including freshwater savings and relative cost of the network. The significance of the proposed optimization framework is illustrated by applying it to an existing industrial park in a water-scarce region in Kenya. Firstly, we illustrated the benefits of including prior knowledge to prevent an over-design of the network at the early stages. In the case study, we achieved a more flexible and expandable water network with 36\% lower unit cost at the early stage and 15\% lower unit cost at later stages for the overall maximum freshwater savings of 25\%. Secondly, multi-objective analysis suggests an optimum freshwater savings of 14\% to reduce the unit cost of network by half. Moreover, the significance of symbiosis networks is highlighted by showing that intra-company connections can only achieve a maximum freshwater savings of 17\% with significantly higher unit cost (+45\%). Finally, we showed that the values of symbiosis connectivity index in the Pareto front correspond to higher freshwater savings, indicating the significant role of the symbiosis network in the industrial park under study. This is the first study, where all the above elements have been taken into account simultaneously for the design of a water reuse network.}, language = {en} } @inproceedings{BestuzhevaGleixnerVoelker2022, author = {Bestuzheva, Ksenia and Gleixner, Ambros and V{\"o}lker, Helena}, title = {Strengthening SONC Relaxations with Constraints Derived from Variable Bounds}, booktitle = {Proceedings of the Hungarian Global Optimization Workshop HUGO 2022}, arxiv = {http://arxiv.org/abs/2211.05518}, pages = {41 -- 44}, year = {2022}, abstract = {Certificates of polynomial nonnegativity can be used to obtain tight dual bounds for polynomial optimization problems. We consider Sums of Nonnegative Circuit (SONC) polynomials certificates, which are well suited for sparse problems since the computational cost depends only on the number of terms in the polynomials and does not depend on the degrees of the polynomials. This work is a first step to integrating SONC-based relaxations of polynomial problems into a branch-and-bound algorithm. To this end, the SONC relaxation for constrained optimization problems is extended in order to better utilize variable bounds, since this property is key for the success of a relaxation in the context of branch-and-bound. Computational experiments show that the proposed extension is crucial for making the SONC relaxations applicable to most constrained polynomial optimization problems and for integrating the two approaches.}, language = {en} } @misc{Francobaldi2021, type = {Master Thesis}, author = {Francobaldi, Matteo}, title = {Learning to Use Local Cuts}, year = {2021}, abstract = {We propose a machine learning approach to address a specific algorithmic question that arises during the solving process of a mixed-integer linear programming problem, namely, whether to use cutting planes only at the root node or also at internal nodes of the branch-and-bound search tree, or equivalently, whether to run a cut-and-branch or rather a branch-and-cut algorithm. Within a supervised regression framework, we develop three machine learning models, Linear Model, Random Forest and Neural Network, for predicting the relative performance between the two methods, local-cut and no-local-cut. Hence, through an extensive computational study conducted with FICO Xpress over a large test bed of problems, we evaluate the produced strategies, and we show that they are able to provide, upon the existing policies, a significant improvement to the performance of the solver. In fact, a variant of the random forest suggested in the present work has already been implemented by the development team of Xpress, and released with version 8.13 of the software.}, language = {en} } @article{HendelAndersonLeBodicetal.2021, author = {Hendel, Gregor and Anderson, Daniel and Le Bodic, Pierre and Pfetsch, Marc}, title = {Estimating the Size of Branch-And-Bound Trees}, journal = {INFORMS Journal on Computing}, doi = {10.1287/ijoc.2021.1103}, year = {2021}, abstract = {This paper investigates the estimation of the size of Branch-and-Bound (B\&B) trees for solving mixed-integer programs. We first prove that the size of the B\&B tree cannot be approximated within a factor of~2 for general binary programs, unless P equals NP. Second, we review measures of the progress of the B\&B search, such as the gap, and propose a new measure, which we call leaf frequency. We study two simple ways to transform these progress measures into B\&B tree size estimates, either as a direct projection, or via double-exponential smoothing, a standard time-series forecasting technique. We then combine different progress measures and their trends into nontrivial estimates using Machine Learning techniques, which yields more precise estimates than any individual measure. The best method we have identified uses all individual measures as features of a random forest model. In a large computational study, we train and validate all methods on the publicly available MIPLIB and Coral general purpose benchmark sets. On average, the best method estimates B\&B tree sizes within a factor of 3 on the set of unseen test instances even during the early stage of the search, and improves in accuracy as the search progresses. It also achieves a factor 2 over the entire search on each out of six additional sets of homogeneous instances we have tested. All techniques are available in version 7 of the branch-and-cut framework SCIP.}, language = {en} } @misc{EiflerGleixnerPulaj2021, author = {Eifler, Leon and Gleixner, Ambros and Pulaj, Jonad}, title = {A Safe Computational Framework for Integer Programming applied to Chv{\´a}tal's Conjecture}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-84444}, year = {2021}, abstract = {We describe a general and safe computational framework that provides integer programming results with the degree of certainty that is required for machine-assisted proofs of mathematical theorems. At its core, the framework relies on a rational branch-and-bound certificate produced by an exact integer programming solver, SCIP, in order to circumvent floating-point roundoff errors present in most state-of-the-art solvers for mixed-integer programs. The resulting certificates are self-contained and checker software exists that can verify their correctness independently of the integer programming solver used to produce the certificate. This acts as a safeguard against programming errors that may be present in complex solver software. The viability of this approach is tested by applying it to finite cases of Chv{\´a}tal's conjecture, a long-standing open question in extremal combinatorics. We take particular care to verify also the correctness of the input for this specific problem, using the Coq formal proof assistant. As a result we are able to provide a first machine-assisted proof that Chv{\´a}tal's conjecture holds for all downsets whose union of sets contains seven elements or less.}, language = {en} } @article{EiflerGleixnerPulaj2022, author = {Eifler, Leon and Gleixner, Ambros and Pulaj, Jonad}, title = {A Safe Computational Framework for Integer Programming applied to Chv{\´a}tal's Conjecture}, volume = {48}, journal = {ACM Transactions on Mathematical Software}, number = {2}, doi = {10.1145/3485630}, year = {2022}, abstract = {We describe a general and safe computational framework that provides integer programming results with the degree of certainty that is required for machine-assisted proofs of mathematical theorems. At its core, the framework relies on a rational branch-and-bound certificate produced by an exact integer programming solver, SCIP, in order to circumvent floating-point roundoff errors present in most state-of-the-art solvers for mixed-integer programs.The resulting certificates are self-contained and checker software exists that can verify their correctness independently of the integer programming solver used to produce the certificate. This acts as a safeguard against programming errors that may be present in complex solver software. The viability of this approach is tested by applying it to finite cases of Chv{\´a}tal's conjecture, a long-standing open question in extremal combinatorics. We take particular care to verify also the correctness of the input for this specific problem, using the Coq formal proof assistant. As a result we are able to provide a first machine-assisted proof that Chv{\´a}tal's conjecture holds for all downsets whose union of sets contains seven elements or less.}, language = {en} } @article{EiflerGleixner2022, author = {Eifler, Leon and Gleixner, Ambros}, title = {A computational status update for exact rational mixed integer programming}, journal = {Mathematical Programming}, publisher = {Springer}, doi = {10.1007/s10107-021-01749-5}, year = {2022}, abstract = {The last milestone achievement for the roundoff-error-free solution of general mixed integer programs over the rational numbers was a hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. We describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal heuristics, employs a faster rational LP solver based on LP iterative refinement, and is able to produce independently verifiable certificates of optimality. We study the significantly improved performance and give insights into the computational behavior of the new algorithmic components. On the MIPLIB 2017 benchmark set, we observe an average speedup of 10.7x over the original framework and 2.9 times as many instances solved within a time limit of two hours.}, language = {en} } @article{BesanconAnjosBrotcorne2021, author = {Besan{\c{c}}on, Mathieu and Anjos, Miguel F. and Brotcorne, Luce}, title = {Complexity of near-optimal robust versions of multilevel optimization problems}, volume = {15}, journal = {Optimization Letters}, number = {8}, doi = {10.1007/s11590-021-01754-9}, pages = {2597 -- 2610}, year = {2021}, 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{CriadoMartinezRubioPokutta2022, author = {Criado, Francisco and Mart{\´i}nez-Rubio, David and Pokutta, Sebastian}, title = {Fast Algorithms for Packing Proportional Fairness and its Dual}, volume = {36}, booktitle = {Proceedings of the Conference on Neural Information Processing Systems}, year = {2022}, abstract = {The proportional fair resource allocation problem is a major problem studied in flow control of networks, operations research, and economic theory, where it has found numerous applications. This problem, defined as the constrained maximization of sum_i log x_i, is known as the packing proportional fairness problem when the feasible set is defined by positive linear constraints and x ∈ R≥0. In this work, we present a distributed accelerated first-order method for this problem which improves upon previous approaches. We also design an algorithm for the optimization of its dual problem. Both algorithms are width-independent.}, language = {en} } @inproceedings{CardereraPokuttaMathieu2021, 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}, booktitle = {Thirty-fifth Conference on Neural Information Processing Systems, NeurIPS 2021}, year = {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{Kerdreuxd'AspremontPokutta2021, author = {Kerdreux, Thomas and d'Aspremont, Alexandre and Pokutta, Sebastian}, title = {Local and Global Uniform Convexity Conditions}, year = {2021}, abstract = {We review various characterizations of uniform convexity and smoothness on norm balls in finite-dimensional spaces and connect results stemming from the geometry of Banach spaces with scaling inequalities used in analysing the convergence of optimization methods. In particular, we establish local versions of these conditions to provide sharper insights on a recent body of complexity results in learning theory, online learning, or offline optimization, which rely on the strong convexity of the feasible set. While they have a significant impact on complexity, these strong convexity or uniform convexity properties of feasible sets are not exploited as thoroughly as their functional counterparts, and this work is an effort to correct this imbalance. We conclude with some practical examples in optimization and machine learning where leveraging these conditions and localized assumptions lead to new complexity results.}, language = {en} } @article{EiflerNicolasThouveninGleixner2024, author = {Eifler, Leon and Nicolas-Thouvenin, Jules and Gleixner, Ambros}, title = {Combining Precision Boosting with LP Iterative Refinement for Exact Linear Optimization}, journal = {INFORMS Journal on Computing}, doi = {10.1287/ijoc.2023.0409}, year = {2024}, abstract = {This article studies a combination of the two state-of-the-art algorithms for the exact solution of linear programs (LPs) over the rational numbers, i.e., without any roundoff errors or numerical tolerances. By integrating the method of precision boosting inside an LP iterative refinement loop, the combined algorithm is able to leverage the strengths of both methods: the speed of LP iterative refinement, in particular in the majority of cases when a double-precision floating-point solver is able to compute approximate solutions with small errors, and the robustness of precision boosting whenever extended levels of precision become necessary. We compare the practical performance of the resulting algorithm with both puremethods on a large set of LPs and mixed-integer programs (MIPs). The results show that the combined algorithm solves more instances than a pure LP iterative refinement approach, while being faster than pure precision boosting. When embedded in an exact branch-and-cut framework for MIPs, the combined algorithm is able to reduce the number of failed calls to the exact LP solver to zero, while maintaining the speed of the pure LP iterative refinement approach.}, language = {en} } @misc{EiflerNicolasThouveninGleixner2023, author = {Eifler, Leon and Nicolas-Thouvenin, Jules and Gleixner, Ambros}, title = {Combining Precision Boosting with LP Iterative Refinement for Exact Linear Optimization}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-92573}, year = {2023}, abstract = {This article studies a combination of the two state-of-the-art algorithms for the exact solution of linear programs (LPs) over the rational numbers, i.e., without any roundoff errors or numerical tolerances. By integrating the method of precision boosting inside an LP iterative refinement loop, the combined algorithm is able to leverage the strengths of both methods: the speed of LP iterative refinement, in particular in the majority of cases when a double-precision floating-point solver is able to compute approximate solutions with small errors, and the robustness of precision boosting whenever extended levels of precision become necessary. We compare the practical performance of the resulting algorithm with both puremethods on a large set of LPs and mixed-integer programs (MIPs). The results show that the combined algorithm solves more instances than a pure LP iterative refinement approach, while being faster than pure precision boosting. When embedded in an exact branch-and-cut framework for MIPs, the combined algorithm is able to reduce the number of failed calls to the exact LP solver to zero, while maintaining the speed of the pure LP iterative refinement approach.}, language = {en} } @inproceedings{ZimmerSpiegelPokutta2023, author = {Zimmer, Max and Spiegel, Christoph and Pokutta, Sebastian}, title = {How I Learned to Stop Worrying and Love Retraining}, booktitle = {Proceedings of International Conference on Learning Representations}, year = {2023}, language = {en} } @inproceedings{WirthKerdreuxPokutta2023, author = {Wirth, Elias and Kerdreux, Thomas and Pokutta, Sebastian}, title = {Acceleration of Frank-Wolfe Algorithms with Open Loop Step-sizes}, booktitle = {Proceedings of International Conference on Artificial Intelligence and Statistics}, year = {2023}, language = {en} } @inproceedings{WirthKeraPokutta2023, author = {Wirth, Elias and Kera, and Pokutta, Sebastian}, title = {Approximate Vanishing Ideal Computations at Scale}, booktitle = {Proceedings of International Conference on Learning Representations}, year = {2023}, language = {en} } @article{DesignolleBesanconIommazzoetal.2023, author = {Designolle, S{\´e}bastien and Besan{\c{c}}on, Mathieu and Iommazzo, Gabriele and Knebel, Sebastian and Gelß, Patrick and Pokutta, Sebastian}, title = {Improved Local Models and New Bell Inequalities Via Frank-Wolfe Algorithms}, volume = {5}, journal = {Physical Review Research}, doi = {10.1103/PhysRevResearch.5.043059}, pages = {043059}, year = {2023}, abstract = {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 separating hyperplanes, that is, Bell inequalities. We take advantage of the recent developments in so-called Frank-Wolfe algorithms to significantly increase the convergence rate of existing methods. First, we study the threshold value for the nonlocality of two-qubit Werner states under projective measurements. Here, we improve on both the upper and lower bounds present in the literature. Importantly, our bounds are entirely analytical; moreover, they yield refined bounds on the value of the Grothendieck constant of order three: 1.4367⩽KG(3)⩽1.4546. Second, we demonstrate the efficiency of our approach in multipartite Bell scenarios, and present local models for all projective measurements with visibilities noticeably higher than the entanglement threshold. We make our entire code accessible as a julia library called BellPolytopes.jl.}, language = {en} } @article{KruserSharmaHolletal.2023, author = {Kruser, Jacqueline M. and Sharma, Kartikey and Holl, Jane L. and Nohadani, Omid}, title = {Identifying Patterns of Medical Intervention in Acute Respiratory Failure: A Retrospective Observational Study}, volume = {5}, journal = {Critical Care Explorations}, number = {10}, doi = {10.1097/CCE.0000000000000984}, pages = {p e0984}, year = {2023}, language = {en} } @article{BienstockMunozPokutta2023, author = {Bienstock, Daniel and Mu{\~n}oz, Gonzalo and Pokutta, Sebastian}, title = {Principled Deep Neural Network Training Through Linear Programming}, volume = {49}, journal = {Discrete Optimization}, doi = {10.1016/j.disopt.2023.100795}, year = {2023}, abstract = {Deep learning has received much attention lately due to the impressive empirical performance achieved by training algorithms. Consequently, a need for a better theoretical understanding of these problems has become more evident and multiple works in recent years have focused on this task. In this work, using a unified framework, we show that there exists a polyhedron that simultaneously encodes, in its facial structure, all possible deep neural network training problems that can arise from a given architecture, activation functions, loss function, and sample size. Notably, the size of the polyhedral representation depends only linearly on the sample size, and a better dependency on several other network parameters is unlikely. Using this general result, we compute the size of the polyhedral encoding for commonly used neural network architectures. Our results provide a new perspective on training problems through the lens of polyhedral theory and reveal strong structure arising from these problems.}, language = {en} } @inproceedings{GłuchTuranNagarajanetal.2025, author = {Głuch, Grzegorz and Turan, Berkant and Nagarajan, Sai Ganesh and Pokutta, Sebastian}, title = {The Good, the Bad and the Ugly: Meta-Analysis of Watermarks, Transferable Attacks and Adversarial Defenses}, booktitle = {Proceedings of the Conference on Neural Information Processing Systems}, year = {2025}, language = {en} } @article{LeinsGonnermannMuellerTeichmann2024, author = {Leins, Nicolas and Gonnermann-M{\"u}ller, Jana and Teichmann, Malte}, title = {Comparing head-mounted and handheld augmented reality for guided assembly}, journal = {Journal on Multimodal User Interfaces}, year = {2024}, language = {en} } @inproceedings{KeraPelleritiIshiharaetal.2025, author = {Kera, Hiroshi and Pelleriti, Nico and Ishihara, Yuki and Zimmer, Max and Pokutta, Sebastian}, title = {Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms}, booktitle = {Proceedings of the Conference on Neural Information Processing Systems}, year = {2025}, language = {en} } @article{HendrychTroppensBesanconetal.2025, author = {Hendrych, Deborah and Troppens, Hannah and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian}, title = {Convex mixed-integer optimization with Frank-Wolfe methods}, volume = {17}, journal = {Mathematical Programming Computation}, doi = {10.1007/s12532-025-00288-w}, pages = {731 -- 757}, year = {2025}, language = {en} } @inproceedings{GonnermannMuellerBrandenburgerVladovaetal.2023, author = {Gonnermann-M{\"u}ller, Jana and Brandenburger, Bonny and Vladova, Gergana and Gronau, Norbert}, title = {To What Extent Can Individualisation in Terms of Different Types of Mode Improve Learning Outcomes and Learner Satisfaction? A Pre-study}, booktitle = {Proceedings of the Hawaii International Conference on System Sciences}, year = {2023}, language = {en} } @inproceedings{GonnermannMuellerLeinsGronauetal.2024, author = {Gonnermann-M{\"u}ller, Jana and Leins, Nicolas and Gronau, Norbert and Kosch, Thomas}, title = {Value by design: Reducing Cognitive Load by Using Visual Guidance in Augmented RealityAn Eye-Tracking Study}, booktitle = {Proceedings of the International Conference on Information Systems}, year = {2024}, language = {en} } @article{GonnermannMuellerKrueger2024, author = {Gonnermann-M{\"u}ller, Jana and Kr{\"u}ger, Jule M.}, title = {Unlocking Augmented Reality Learning Design Based on Evidence From Empirical Cognitive Load Studies—A Systematic Literature Review}, journal = {Journal of Computer Assisted Learning}, year = {2024}, language = {en} } @article{GelssKleinMateraetal.2025, author = {Gelß, Patrick and Klein, Rupert and Matera, Sebastian and Schmidt, Burkhard}, title = {Quantum dynamics of coupled excitons and phonons in chain-like systems: tensor train approaches and higher-order propagators}, volume = {162}, journal = {The Journal of Chemical Physics}, doi = {10.1063/5.0258904}, year = {2025}, language = {en} } @inproceedings{HendrychBesanconMartinezRubioetal.2025, author = {Hendrych, Deborah and Besan{\c{c}}on, Mathieu and Mart{\´i}nez-Rubio, David and Pokutta, Sebastian}, title = {Secant line search for Frank-Wolfe algorithms}, volume = {267}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, arxiv = {http://arxiv.org/abs/2501.18775}, pages = {23005 -- 23029}, year = {2025}, language = {en} } @inproceedings{FayadZimmerSchwartzetal.2025, author = {Fayad, Ibrahim and Zimmer, Max and Schwartz, Martin and Ciais, Philippe and Gieseke, Fabian and Belouze, Gabriel and Brood, Sarah and De Truchis, Aurelien and d'Aspremont, Alexandre}, title = {DUNIA: Pixel-Sized Embeddings via Cross-Modal Alignment for Earth Observation Applications}, volume = {267}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, arxiv = {http://arxiv.org/abs/2502.17066}, pages = {16375 -- 16406}, year = {2025}, language = {en} } @inproceedings{PaulsZimmerTuranetal.2025, author = {Pauls, Jan and Zimmer, Max and Turan, Berkant and Saatchi, Sassan and Ciais, Philippe and Pokutta, Sebastian and Gieseke, Fabian}, title = {Capturing Temporal Dynamics in Large-Scale Canopy Tree Height Estimation}, volume = {267}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, arxiv = {http://arxiv.org/abs/2501.19328}, pages = {48422 -- 48438}, year = {2025}, language = {en} } @article{KlusGelss2025, author = {Klus, Stefan and Gelß, Patrick}, title = {Continuous optimization methods for the graph isomorphism problem}, volume = {14}, journal = {Information and Inference: A Journal of the IMA}, number = {2}, doi = {10.1093/imaiai/iaaf011}, year = {2025}, language = {en} } @inproceedings{MundingerZimmerKiemetal.2025, author = {Mundinger, Konrad and Zimmer, Max and Kiem, Aldo and Spiegel, Christoph and Pokutta, Sebastian}, title = {Neural Discovery in Mathematics: Do Machines Dream of Colored Planes?}, volume = {267}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, arxiv = {http://arxiv.org/abs/2501.18527}, pages = {45236 -- 45255}, year = {2025}, language = {en} } @inproceedings{PelleritiZimmerWirthetal.2025, author = {Pelleriti, Nico and Zimmer, Max and Wirth, Elias and Pokutta, Sebastian}, title = {Approximating Latent Manifolds in Neural Networks via Vanishing Ideals}, volume = {267}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, arxiv = {http://arxiv.org/abs/2502.15051}, pages = {48734 -- 48761}, year = {2025}, language = {en} } @inproceedings{RouxMartinezRubioPokutta2025, author = {Roux, Christophe and Mart{\´i}nez-Rubio, David and Pokutta, Sebastian}, title = {Implicit Riemannian optimism with applications to min-max problems}, volume = {267}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, arxiv = {http://arxiv.org/abs/2501.18381}, pages = {52139 -- 52172}, year = {2025}, language = {en} } @inproceedings{TuranAsadullaSteinmannetal.2025, author = {Turan, Berkant and Asadulla, Suhrab and Steinmann, David and Stammer, Wolfgang and Pokutta, Sebastian}, title = {Neural Concept Verifier: Scaling Prover-Verifier Games via Concept Encodings}, booktitle = {Proceedings of the ICML Workshop on Actionable Interpretability}, year = {2025}, language = {en} } @article{BolusaniBesanconGleixneretal.2024, author = {Bolusani, Suresh and Besan{\c{c}}on, Mathieu and Gleixner, Ambros and Berthold, Timo and D'Ambrosio, Claudia and Mu{\~n}oz, Gonzalo and Paat, Joseph and Thomopulos, Dimitri}, title = {The MIP workshop 2023 computational competition on reoptimization}, volume = {16}, journal = {Mathematical Programming Computation}, doi = {10.1007/s12532-024-00256-w}, pages = {255 -- 266}, year = {2024}, abstract = {This paper describes the computational challenge developed for a computational competition held in 2023 for the 20th anniversary of the Mixed Integer Programming Workshop. The topic of this competition was reoptimization, also known as warm starting, of mixed integer linear optimization problems after slight changes to the input data for a common formulation. The challenge was to accelerate the proof of optimality of the modified instances by leveraging the information from the solving processes of previously solved instances, all while creating high-quality primal solutions. Specifically, we discuss the competition's format, the creation of public and hidden datasets, and the evaluation criteria. Our goal is to establish a methodology for the generation of benchmark instances and an evaluation framework, along with benchmark datasets, to foster future research on reoptimization of mixed integer linear optimization problems.}, language = {en} } @article{CardereraBesanconPokutta2024, author = {Carderera, Alejandro and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian}, title = {Scalable Frank-Wolfe on generalized self-concordant functions via simple steps}, volume = {34}, journal = {SIAM Journal on Optimization}, number = {3}, doi = {10.1137/23M1616789}, year = {2024}, language = {en} } @inproceedings{EiflerWitzigGleixner2024, author = {Eifler, Leon and Witzig, Jakob and Gleixner, Ambros}, title = {Branch and cut for partitioning a graph into a cycle of clusters}, volume = {14594}, booktitle = {Combinatorial Optimization. ISCO 2024}, doi = {10.1007/978-3-031-60924-4_8}, pages = {97 -- 108}, year = {2024}, abstract = {In this paper we study formulations and algorithms for the cycle clustering problem, a partitioning problem over the vertex set of a directed graph with nonnegative arc weights that is used to identify cyclic behavior in simulation data generated from nonreversible Markov state models. Here, in addition to partitioning the vertices into a set of coherent clusters, the resulting clusters must be ordered into a cycle such as to maximize the total net flow in the forward direction of the cycle. We provide a problem-specific binary programming formulation and compare it to a formulation based on the reformulation-linearization technique (RLT). We present theoretical results on the polytope associated with our custom formulation and develop primal heuristics and separation routines for both formulations. In computational experiments on simulation data from biology we find that branch and cut based on the problem-specific formulation outperforms the one based on RLT.}, language = {en} } @inproceedings{GhannamMexiLametal.2024, author = {Ghannam, Mohammed and Mexi, Gioni and Lam, Edward and Gleixner, Ambros}, title = {Branch and price for the length-constrained cycle partition problem}, booktitle = {Proceedings of INFORMS Optimization Society Conference}, year = {2024}, language = {en} } @article{GuptaHamannMueyesseretal.2023, author = {Gupta, Pranshu and Hamann, Fabian and M{\"u}yesser, Alp and Sgueglia, Amedeo and Parczyk, Olaf}, title = {A general approach to transversal versions of Dirac-type theorems}, volume = {55}, journal = {Bulletin of the London Mathematical Society}, number = {6}, pages = {2817 -- 2839}, year = {2023}, language = {en} } @article{GebhardHahnKlimrothPenschucketal.2022, author = {Gebhard, Oliver and Hahn-Klimroth, Max and Penschuck, Manuel and Rolvien, Maurice and Scarlett, Jonathan and Tan, Nelvin and Parczyk, Olaf}, title = {Near optimal sparsity-constrained group testing: improved bounds}, journal = {IEEE Transactions on Information Theory}, year = {2022}, language = {en} } @article{ParczykPokuttaSpiegeletal.2024, author = {Parczyk, Olaf and Pokutta, Sebastian and Spiegel, Christoph and Szab{\´o}, Tibor}, title = {New Ramsey multiplicity bounds and search heuristics}, journal = {Foundations of Computational Mathematics}, doi = {10.1007/s10208-024-09675-6}, year = {2024}, language = {en} } @article{AllenPfenningerParczyk2024, author = {Allen, Peter and Pfenninger, Vincent and Parczyk, Olaf}, title = {Resilience for tight Hamiltonicity}, volume = {4}, journal = {Combinatorial Theory}, number = {1}, doi = {10.5070/C64163846}, year = {2024}, language = {en} } @article{BoettcherSguegliaSkokanetal.2022, author = {B{\"o}ttcher, Julia and Sgueglia, Amedeo and Skokan, Jozef and Parczyk, Olaf}, title = {Triangles in randomly perturbed graphs}, journal = {Combinatorics, Probability and Computing}, year = {2022}, language = {en} } @article{BarrosCavalarMotaetal.2022, author = {Barros, Gabriel F. and Cavalar, Bruno P. and Mota, Guilherme O. and Parczyk, Olaf}, title = {Anti-Ramsey threshold of cycles for sparse graphs}, journal = {Discrete Applied Mathematics}, year = {2022}, language = {en} } @article{KohayakawaMotaSchnitzeretal.2023, author = {Kohayakawa, Yoshiharu and Mota, Guilherme O. and Schnitzer, Jakob and Parczyk, Olaf}, title = {Anti-Ramsey threshold of complete graphs for sparse graphs}, journal = {Discrete Mathematics}, year = {2023}, language = {en} } @inproceedings{PaulsZimmerKellyetal.2024, author = {Pauls, Jan and Zimmer, Max and Kelly, Una M and Schwartz, Martin and Saatchi, Sassan and Ciais, Philippe and Pokutta, Sebastian and Brandt, Martin and Gieseke, Fabian}, title = {Estimating canopy height at scale}, volume = {235}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {39972 -- 39988}, year = {2024}, abstract = {We propose a framework for global-scale canopy height estimation based on satellite data. Our model leverages advanced data preprocessing techniques, resorts to a novel loss function designed to counter geolocation inaccuracies inherent in the ground-truth height measurements, and employs data from the Shuttle Radar Topography Mission to effectively filter out erroneous labels in mountainous regions, enhancing the reliability of our predictions in those areas. A comparison between predictions and ground-truth labels yields an MAE/RMSE of 2.43 / 4.73 (meters) overall and 4.45 / 6.72 (meters) for trees taller than five meters, which depicts a substantial improvement compared to existing global-scale products. The resulting height map as well as the underlying framework will facilitate and enhance ecological analyses at a global scale, including, but not limited to, large-scale forest and biomass monitoring.}, language = {en} } @inproceedings{HendrychBesanconPokutta2024, author = {Hendrych, Deborah and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian}, title = {Solving the optimal experiment design problem with mixed-integer convex methods}, volume = {301}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, doi = {10.4230/LIPIcs.SEA.2024.16}, pages = {16:1 -- 16:22}, year = {2024}, abstract = {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 our method against both generic and specialized convex mixed-integer approaches. Computational results highlight the performance of our proposed method, especially on large and challenging instances.}, language = {en} } @inproceedings{KiemPokuttaSpiegel2024, author = {Kiem, Aldo and Pokutta, Sebastian and Spiegel, Christoph}, title = {Categorification of Flag Algebras}, booktitle = {Discrete Mathematics Days 2024}, doi = {10.37536/TYSP5643}, pages = {259 -- 264}, year = {2024}, language = {en} } @inproceedings{KiemPokuttaSpiegel2024, author = {Kiem, Aldo and Pokutta, Sebastian and Spiegel, Christoph}, title = {The Four-Color Ramsey Multiplicity of Triangles}, booktitle = {Discrete Mathematics Days 2024}, doi = {10.37536/TYSP5643}, pages = {13 -- 18}, year = {2024}, language = {en} } @article{HahnKlimrothParczykPerson2024, author = {Hahn-Klimroth, Max and Parczyk, Olaf and Person, Yury}, title = {Minimum degree conditions for containing an r-regular r-connected spanning subgraph}, volume = {118}, journal = {European Journal of Combinatorics}, doi = {10.1016/j.ejc.2024.103940}, pages = {103940}, year = {2024}, language = {en} } @article{MundingerPokuttaSpiegeletal.2024, author = {Mundinger, Konrad and Pokutta, Sebastian and Spiegel, Christoph and Zimmer, Max}, title = {Extending the Continuum of Six-Colorings}, volume = {34}, journal = {Geombinatorics Quarterly}, number = {1}, arxiv = {http://arxiv.org/abs/2404.05509}, pages = {20 -- 29}, year = {2024}, language = {en} } @inproceedings{MundingerPokuttaSpiegeletal.2024, author = {Mundinger, Konrad and Pokutta, Sebastian and Spiegel, Christoph and Zimmer, Max}, title = {Extending the Continuum of Six-Colorings}, booktitle = {Discrete Mathematics Days 2024}, doi = {10.37536/TYSP5643}, pages = {178 -- 183}, year = {2024}, language = {en} } @inproceedings{MartinezRubioRouxPokutta2024, author = {Mart{\´i}nez-Rubio, David and Roux, Christophe and Pokutta, Sebastian}, title = {Convergence and Trade-Offs in Riemannian Gradient Descent and Riemannian Proximal Point}, volume = {235}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {34920 -- 34948}, year = {2024}, abstract = {In this work, we analyze two of the most fundamental algorithms in geodesically convex optimization: Riemannian gradient descent and (possibly inexact) Riemannian proximal point. We quantify their rates of convergence and produce different variants with several trade-offs. Crucially, we show the iterates naturally stay in a ball around an optimizer, of radius depending on the initial distance and, in some cases, on the curvature. Previous works simply assumed bounded iterates, resulting in rates that were not fully quantified. We also provide an implementable inexact proximal point algorithm and prove several new useful properties of Riemannian proximal methods: they work when positive curvature is present, the proximal operator does not move points away from any optimizer, and we quantify the smoothness of its induced Moreau envelope. Further, we explore beyond our theory with empirical tests.}, language = {en} } @article{DezaPokuttaPournin2024, author = {Deza, Antoine and Pokutta, Sebastian and Pournin, Lionel}, title = {The complexity of geometric scaling}, volume = {52}, journal = {Operations Research Letters}, doi = {10.1016/j.orl.2023.11.010}, pages = {107057}, year = {2024}, language = {en} } @article{Pokutta2024, author = {Pokutta, Sebastian}, title = {The Frank-Wolfe algorithm: a short introduction}, volume = {126}, journal = {Jahresbericht der Deutschen Mathematiker-Vereinigung}, doi = {10.1365/s13291-023-00275-x}, pages = {3 -- 35}, year = {2024}, language = {en} } @inproceedings{WaeldchenSharmaTuranetal.2024, author = {W{\"a}ldchen, Stephan and Sharma, Kartikey and Turan, Berkant and Zimmer, Max and Pokutta, Sebastian}, title = {Interpretability Guarantees with Merlin-Arthur Classifiers}, volume = {238}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {1963 -- 1971}, year = {2024}, abstract = {We propose an interactive multi-agent classifier that provides provable interpretability guarantees even for complex agents such as neural networks. These guarantees consist of lower bounds on the mutual information between selected features and the classification decision. Our results are inspired by the Merlin-Arthur protocol from Interactive Proof Systems and express these bounds in terms of measurable metrics such as soundness and completeness. Compared to existing interactive setups, we rely neither on optimal agents nor on the assumption that features are distributed independently. Instead, we use the relative strength of the agents as well as the new concept of Asymmetric Feature Correlation which captures the precise kind of correlations that make interpretability guarantees difficult. We evaluate our results on two small-scale datasets where high mutual information can be verified explicitly.}, language = {en} } @inproceedings{ZimmerSpiegelPokutta2024, author = {Zimmer, Max and Spiegel, Christoph and Pokutta, Sebastian}, title = {Sparse Model Soups}, booktitle = {12th International Conference on Learning Representations (ICLR 2024)}, publisher = {Curran Associates, Inc.}, isbn = {9781713898658}, year = {2024}, language = {en} } @inproceedings{BuiCombettesWoodstock2022, author = {B{\´u}i, M. N. and Combettes, P. L. and Woodstock, Zev}, title = {block-activated algorithms for multicomponent fully nonsmooth minimization}, booktitle = {Proceedings of ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)}, year = {2022}, language = {en} } @article{BolusaniRalphs2022, author = {Bolusani, Suresh and Ralphs, Ted K.}, title = {a framework for generalized Benders' decomposition and its applications to multilevel optimization}, journal = {Mathematical Programming}, year = {2022}, language = {en} } @article{WilkenBesanconKratochviletal.2022, author = {Wilken, St. Elmo and Besan{\c{c}}on, Mathieu and Kratochv{\´i}l, Miroslav and Kuate, Chilperic Armel Foko and Trefois, Christophe and Gu, Wei and Ebenh{\"o}h, Oliver}, title = {Interrogating the effect of enzyme kinetics on metabolism using differentiable constraint-based models}, journal = {Metabolic Engineering}, year = {2022}, language = {en} } @inproceedings{CombettesWoodstock2022, author = {Combettes, P. L. and Woodstock, Zev}, title = {signal recovery from inconsistent nonlinear observations}, booktitle = {Proceedings of ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)}, year = {2022}, language = {en} } @article{HintermuellerStengl2024, author = {Hinterm{\"u}ller, Michael and Stengl, Steven-Marian}, title = {A Generalized 𝛤-Convergence Concept for a Class of Equilibrium Problems}, volume = {34}, journal = {Journal of Nonlinear Science}, number = {83}, doi = {10.1007/s00332-024-10059-x}, year = {2024}, language = {en} } @article{StenglGelssKlusetal.2024, author = {Stengl, Steven-Marian and Gelß, Patrick and Klus, Stefan and Pokutta, Sebastian}, title = {Existence and uniqueness of solutions of the Koopman--von Neumann equation on bounded domains}, volume = {57}, journal = {Journal of Physics A: Mathematical and Theoretical}, number = {39}, doi = {10.1088/1751-8121/ad6f7d}, year = {2024}, language = {en} } @article{BoettcherParczykSguegliaetal.2024, author = {B{\"o}ttcher, Julia and Parczyk, Olaf and Sgueglia, Amedeo and Skokan, Jozef}, title = {The square of a Hamilton cycle in randomly perturbed graphs}, volume = {65}, journal = {Random Structures \& Algorithms}, number = {2}, doi = {10.1002/rsa.21215}, pages = {342 -- 386}, year = {2024}, language = {en} } @article{DezaOnnPokuttaetal.2024, author = {Deza, Antoine and Onn, Shmuel and Pokutta, Sebastian and Pournin, Lionel}, title = {Kissing polytopes}, volume = {38}, journal = {SIAM Journal on Discrete Mathematics}, number = {4}, doi = {10.1137/24M1640859}, year = {2024}, abstract = {We investigate the following question: How close can two disjoint lattice polytopes contained in a fixed hypercube be? This question stems from various contexts where the minimal distance between such polytopes appears in complexity bounds of optimization algorithms. We provide nearly matching bounds on this distance and discuss its exact computation. We also give similar bounds for disjoint rational polytopes whose binary encoding length is prescribed.}, language = {en} } @article{HartzerRoehrigWolffetal.2022, author = {Hartzer, Jacob and R{\"o}hrig, Olivia and Wolff, Timo and Y{\"u}r{\"u}k, Oğuzhan}, title = {Initial steps in the classification of maximal mediated sets}, journal = {Journal of Symbolic Computation}, year = {2022}, language = {en} } @article{Kerdreuxd'AspremontPokutta2022, author = {Kerdreux, Thomas and d'Aspremont, Alexandre and Pokutta, Sebastian}, title = {Restarting Frank-Wolfe: Faster Rates under H{\"o}lderian Error Bounds}, journal = {Journal of Optimization Theory and Applications}, year = {2022}, language = {en} } @article{CombettesPokutta2023, author = {Combettes, Cyrille and Pokutta, Sebastian}, title = {Revisiting the Approximate Carath{\´e}odory Problem via the Frank-Wolfe Algorithm}, volume = {197}, journal = {Mathematical Programming A}, doi = {10.1007/s10107-021-01735-x}, pages = {191 -- 214}, year = {2023}, language = {en} } @article{GelssIssagaliKornhuber2024, author = {Gelß, Patrick and Issagali, Aizhan and Kornhuber, Ralf}, title = {Fredholm integral equations for function approximation and the training of neural networks}, volume = {6}, journal = {SIAM Journal on Mathematics of Data Science}, number = {4}, doi = {10.1137/23M156642X}, year = {2024}, language = {en} } @article{Stengl2024, author = {Stengl, Steven-Marian}, title = {An alternative formulation of the quantum phase estimation using projection-based tensor decompositions}, volume = {23}, journal = {Quantum Information Processing}, doi = {10.1007/s11128-024-04347-4}, year = {2024}, language = {en} } @article{Vu‐HanSunkaraBermudez‐Schettinoetal.2025, author = {Vu-Han, Tu-Lan and Sunkara, Vikram and Bermudez-Schettino, Rodrigo and Schwechten, Jakob and Runge, Robin and Perka, Carsten and Winkler, Tobias and Pokutta, Sebastian and Weiß, Claudia and Pumberger, Matthias}, title = {Feature Engineering for the Prediction of Scoliosis in 5q-Spinal Muscular Atrophy}, volume = {16}, journal = {Journal of Cachexia, Sarcopenia and Muscle}, number = {1}, doi = {10.1002/jcsm.13599}, pages = {e13599}, year = {2025}, language = {en} } @inproceedings{KeraIshiharaKambeetal.2024, author = {Kera, Hiroshi and Ishihara, Yuki and Kambe, Yuta and Vaccon, Tristan and Yokoyama, Kazuhiro}, title = {Learning to Compute Gr\"obner Bases}, booktitle = {Proceedings of the Conference on Neural Information Processing Systems}, year = {2024}, language = {en} } @inproceedings{KumanoKeraYamasaki2024, author = {Kumano, Soichiro and Kera, Hiroshi and Yamasaki, Toshihiko}, title = {Wide Two-Layer Networks can Learn from Adversarial Perturbations}, booktitle = {Proceedings of the Conference on Neural Information Processing Systems}, year = {2024}, language = {en} } @inproceedings{TroppensBesanconWilkenetal.2025, author = {Troppens, Hannah and Besan{\c{c}}on, Mathieu and Wilken, St. Elmo and Pokutta, Sebastian}, title = {Mixed-Integer Optimization for Loopless Flux Distributions in Metabolic Networks}, volume = {338}, booktitle = {23rd International Symposium on Experimental Algorithms (SEA 2025)}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik}, doi = {10.4230/LIPIcs.SEA.2025.26}, pages = {26:1 -- 26:18}, year = {2025}, language = {en} } @inproceedings{GłuchTuranNagarajanetal.2025, author = {Głuch, Grzegorz and Turan, Berkant and Nagarajan, Sai Ganesh and Pokutta, Sebastian}, title = {The good, the bad and the ugly: watermarks, transferable attacks and adversarial defenses}, booktitle = {1st Workshop on GenAI Watermarking, collocated with ICLR 2025}, year = {2025}, language = {en} } @inproceedings{HollenderMaystreNagarajan2025, author = {Hollender, Alexandros and Maystre, Gilbert and Nagarajan, Sai Ganesh}, title = {The Complexity of Two-Team Polymatrix Games with Independent Adversaries}, booktitle = {13th International Conference on Learning Representations (ICLR 2025)}, arxiv = {http://arxiv.org/abs/2409.07398}, year = {2025}, abstract = {Adversarial multiplayer games are an important object of study in multiagent learning. In particular, polymatrix zero-sum games are a multiplayer setting where Nash equilibria are known to be efficiently computable. Towards understanding the limits of tractability in polymatrix games, we study the computation of Nash equilibria in such games where each pair of players plays either a zero-sum or a coordination game. We are particularly interested in the setting where players can be grouped into a small number of teams of identical interest. While the three-team version of the problem is known to be PPAD-complete, the complexity for two teams has remained open. Our main contribution is to prove that the two-team version remains hard, namely it is CLS-hard. Furthermore, we show that this lower bound is tight for the setting where one of the teams consists of multiple independent adversaries. On the way to obtaining our main result, we prove hardness of finding any stationary point in the simplest type of non-convex-concave min-max constrained optimization problem, namely for a class of bilinear polynomial objective functions.}, language = {en} } @inproceedings{BesanconPokuttaWirth2025, author = {Besan{\c{c}}on, Mathieu and Pokutta, Sebastian and Wirth, Elias}, title = {The Pivoting Framework: Frank-Wolfe Algorithms with Active Set Size Control}, volume = {258}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {271 -- 279}, year = {2025}, language = {en} } @inproceedings{MartinezRubioRouxCriscitielloetal.2025, author = {Mart{\´i}nez-Rubio, David and Roux, Christophe and Criscitiello, Christopher and Pokutta, Sebastian}, title = {Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties}, volume = {258}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {280 -- 288}, year = {2025}, language = {en} } @inproceedings{SadikuWagnerPokutta2025, author = {Sadiku, Shpresim and Wagner, Moritz and Pokutta, Sebastian}, title = {GSE: Group-wise sparse and explainable adversarial attacks}, booktitle = {13th International Conference on Learning Representations (ICLR 2025)}, arxiv = {http://arxiv.org/abs/2311.17434}, year = {2025}, language = {en} } @article{WirthPenaPokutta2025, author = {Wirth, Elias and Pena, Javier and Pokutta, Sebastian}, title = {Correction: Accelerated affine-invariant convergence rates of the Frank-Wolfe algorithm with open-loop step-sizes}, volume = {214}, journal = {Mathematical Programming}, doi = {10.1007/s10107-025-02214-3}, pages = {941 -- 942}, year = {2025}, language = {en} } @inproceedings{RouxZimmerPokutta2025, author = {Roux, Christophe and Zimmer, Max and Pokutta, Sebastian}, title = {On the byzantine-resilience of distillation-based federated learning}, booktitle = {13th International Conference on Learning Representations (ICLR 2025)}, arxiv = {http://arxiv.org/abs/2402.12265}, year = {2025}, abstract = {Federated Learning (FL) algorithms using Knowledge Distillation (KD) have received increasing attention due to their favorable properties with respect to privacy, non-i.i.d. data and communication cost. These methods depart from transmitting model parameters and instead communicate information about a learning task by sharing predictions on a public dataset. In this work, we study the performance of such approaches in the byzantine setting, where a subset of the clients act in an adversarial manner aiming to disrupt the learning process. We show that KD-based FL algorithms are remarkably resilient and analyze how byzantine clients can influence the learning process. Based on these insights, we introduce two new byzantine attacks and demonstrate their ability to break existing byzantine-resilient methods. Additionally, we propose a novel defence method which enhances the byzantine resilience of KD-based FL algorithms. Finally, we provide a general framework to obfuscate attacks, making them significantly harder to detect, thereby improving their effectiveness.}, language = {en} } @inproceedings{SadikuWagnerNagarajanetal.2025, author = {Sadiku, Shpresim and Wagner, Moritz and Nagarajan, Sai Ganesh and Pokutta, Sebastian}, title = {S-CFE: Simple Counterfactual Explanations}, volume = {258}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {172 -- 180}, year = {2025}, language = {en} } @inproceedings{BestuzhevaGleixnerAchterberg2023, author = {Bestuzheva, Ksenia and Gleixner, Ambros and Achterberg, Tobias}, title = {Efficient Separation of RLT Cuts for Implicit and Explicit Bilinear Products}, volume = {13904}, booktitle = {Integer Programming and Combinatorial Optimization. IPCO 2023.}, publisher = {Springer, Cham}, doi = {10.1007/978-3-031-32726-1_2}, pages = {14 -- 28}, year = {2023}, abstract = {The reformulation-linearization technique (RLT) is a prominent approach to constructing tight linear relaxations of non-convex continuous and mixed-integer optimization problems. The goal of this paper is to extend the applicability and improve the performance of RLT for bilinear product relations. First, a method for detecting bilinear product relations implicitly contained in mixed-integer linear programs is developed based on analyzing linear constraints with binary variables, thus enabling the application of bilinear RLT to a new class of problems. Our second contribution addresses the high computational cost of RLT cut separation, which presents one of the major difficulties in applying RLT efficiently in practice. We propose a new RLT cutting plane separation algorithm which identifies combinations of linear constraints and bound factors that are expected to yield an inequality that is violated by the current relaxation solution. A detailed computational study based on implementations in two solvers evaluates the performance impact of the proposed methods.}, language = {en} } @inproceedings{MexiBertholdGleixneretal.2023, author = {Mexi, Gioni and Berthold, Timo and Gleixner, Ambros and Nordstr{\"o}m, Jakob}, title = {Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning}, volume = {280}, booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik}, doi = {10.4230/LIPIcs.CP.2023.27}, pages = {27:1 -- 27:19}, year = {2023}, abstract = {Conflict analysis has been successfully generalized from Boolean satisfiability (SAT) solving to mixed integer programming (MIP) solvers, but although MIP solvers operate with general linear inequalities, the conflict analysis in MIP has been limited to reasoning with the more restricted class of clausal constraint. This is in contrast to how conflict analysis is performed in so-called pseudo-Boolean solving, where solvers can reason directly with 0-1 integer linear inequalities rather than with clausal constraints extracted from such inequalities. In this work, we investigate how pseudo-Boolean conflict analysis can be integrated in MIP solving, focusing on 0-1 integer linear programs (0-1 ILPs). Phrased in MIP terminology, conflict analysis can be understood as a sequence of linear combinations and cuts. We leverage this perspective to design a new conflict analysis algorithm based on mixed integer rounding (MIR) cuts, which theoretically dominates the state-of-the-art division-based method in pseudo-Boolean solving. We also report results from a first proof-of-concept implementation of different pseudo-Boolean conflict analysis methods in the open-source MIP solver SCIP. When evaluated on a large and diverse set of 0-1 ILP instances from MIPLIB2017, our new MIR-based conflict analysis outperforms both previous pseudo-Boolean methods and the clause-based method used in MIP. Our conclusion is that pseudo-Boolean conflict analysis in MIP is a promising research direction that merits further study, and that it might also make sense to investigate the use of such conflict analysis to generate stronger no-goods in constraint programming.}, language = {en} } @inproceedings{MartinezRubioWirthPokutta2023, author = {Mart{\´i}nez-Rubio, David and Wirth, Elias and Pokutta, Sebastian}, title = {Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond}, volume = {195}, booktitle = {Proceedings of Machine Learning Research}, pages = {1 -- 35}, year = {2023}, abstract = {It has recently been shown that ISTA, an unaccelerated optimization method, presents sparse updates for the ℓ1-regularized undirected personalized PageRank problem (Fountoulakis et al., 2019), leading to cheap iteration complexity and providing the same guarantees as the approximate personalized PageRank algorithm (APPR) (Andersen et al., 2006). In this work, we design an accelerated optimization algorithm for this problem that also performs sparse updates, providing an affirmative answer to the COLT 2022 open question of Fountoulakis and Yang (2022). Acceleration provides a reduced dependence on the condition number, while the dependence on the sparsity in our updates differs from the ISTA approach. Further, we design another algorithm by using conjugate directions to achieve an exact solution while exploiting sparsity. Both algorithms lead to faster convergence for certain parameter regimes. Our findings apply beyond PageRank and work for any quadratic objective whose Hessian is a positive-definite 푀-matrix.}, language = {en} }