TY - JOUR A1 - Gleixner, Ambros A1 - Hendel, Gregor A1 - Gamrath, Gerald A1 - Achterberg, Tobias A1 - Bastubbe, Michael A1 - Berthold, Timo A1 - Christophel, Philipp M. A1 - Jarck, Kati A1 - Koch, Thorsten A1 - Linderoth, Jeff A1 - Lübbecke, Marco A1 - Mittelmann, Hans A1 - Ozyurt, Derya A1 - Ralphs, Ted A1 - Salvagnin, Domenico A1 - Shinano, Yuji T1 - MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library JF - Mathematical Programming Computation N2 - 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. Y1 - 2021 U6 - https://doi.org/10.1007/s12532-020-00194-3 VL - 13 IS - 3 SP - 443 EP - 490 ER - TY - JOUR A1 - Anzt, H. A1 - Bach, F. A1 - Druskat, S. A1 - Löffler, F. A1 - Loewe, A. A1 - Renard, B. Y. A1 - Seemann, G. A1 - Struck, A. A1 - Achhammer, E. A1 - Appell, F. A1 - Bader, M. A1 - Brusch, L. A1 - Busse, C. A1 - Chourdakis, G. A1 - Dabrowski, P. W. A1 - Ebert, P. A1 - Flemisch, B. A1 - Friedl, S. A1 - Fritzsch, B. A1 - Funk, M. D. A1 - Gast, V. A1 - Goth, F. A1 - Grad, J.-N. A1 - Hermann, Sibylle A1 - Hohmann, F. A1 - Janosch, S. A1 - Kutra, D. A1 - Linxweiler, J. A1 - Muth, T. A1 - Peters-Kottig, Wolfgang A1 - Rack, F. A1 - Raters, F. H. C. A1 - Rave, S. A1 - Reina, G. A1 - Reißig, M. A1 - Ropinski, T. A1 - Schaarschmidt, J. A1 - Seibold, H. A1 - Thiele, J. P. A1 - Uekermann, B. A1 - Unger, S. A1 - Weeber, R. T1 - 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] JF - F1000Research N2 - 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. KW - Sustainable Software Development KW - Research Software Y1 - 2020 U6 - https://doi.org/10.12688/f1000research.23224.1 IS - 9:295 ER - TY - GEN A1 - Lenz, Ralf A1 - Serrano, Felipe T1 - Tight Convex Relaxations for the Expansion Planning Problem N2 - Secure energy transport is considered as highly relevant for the basic infrastructure of nowadays society and economy. To satisfy increasing demands and to handle more diverse transport situations, operators of energy networks regularly expand the capacity of their network by building new network elements, known as the expansion planning problem. A key constraint function in expansion planning problems is a nonlinear and nonconvex potential loss function. In order to improve the algorithmic performance of state-of-the-art MINLP solvers, this paper presents an algebraic description for the convex envelope of this function. Through a thorough computational study, we show that this tighter relaxation tremendously improve the performance of the MINLP solver SCIP on a large test set of practically relevant instances for the expansion planning problem. In particular, the results show that our achievements lead to an improvement of the solver performance for a development version by up to 58%. T3 - ZIB-Report - 21-05 KW - Convex envelopes KW - Mixed-Integer Nonlinear Programming KW - Expansion planning of energy networks Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81459 SN - 1438-0064 ER - TY - JOUR A1 - Csizmadia, Zsolt A1 - Berthold, Timo T1 - The confined primal integral: a measure to benchmark heuristic MINLP solvers against global MINLP solvers JF - Mathematical Programming N2 - It is a challenging task to fairly compare local solvers and heuristics against each other and against global solvers. How does one weigh a faster termination time against a better quality of the found solution? In this paper, we introduce the confined primal integral, a new performance measure that rewards a balance of speed and solution quality. It emphasizes the early part of the solution process by using an exponential decay. Thereby, it avoids that the order of solvers can be inverted by choosing an arbitrarily large time limit. We provide a closed analytic formula to compute the confined primal integral a posteriori and an incremental update formula to compute it during the run of an algorithm. For the latter, we show that we can drop one of the main assumptions of the primal integral, namely the knowledge of a fixed reference solution to compare against. Furthermore, we prove that the confined primal integral is a transitive measure when comparing local solves with different final solution values. Finally, we present a computational experiment where we compare a local MINLP solver that uses certain classes of cutting planes against a solver that does not. Both versions show very different tendencies w.r.t. average running time and solution quality, and we use the confined primal integral to argue which of the two is the preferred setting. Y1 - 2020 U6 - https://doi.org/10.1007/s10107-020-01547-5 ER - TY - JOUR A1 - Gamrath, Gerald A1 - Berthold, Timo A1 - Salvagnin, Domenico T1 - An exploratory computational analysis of dual degeneracy in mixed-integer programming JF - EURO Journal on Computational Optimization N2 - Dual degeneracy, i.e., the presence of multiple optimal bases to a linear programming (LP) problem, heavily affects the solution process of mixed integer programming (MIP) solvers. Different optimal bases lead to different cuts being generated, different branching decisions being taken and different solutions being found by primal heuristics. Nevertheless, only a few methods have been published that either avoid or exploit dual degeneracy. The aim of the present paper is to conduct a thorough computational study on the presence of dual degeneracy for the instances of well-known public MIP instance collections. How many instances are affected by dual degeneracy? How degenerate are the affected models? How does branching affect degeneracy: Does it increase or decrease by fixing variables? Can we identify different types of degenerate MIPs? As a tool to answer these questions, we introduce a new measure for dual degeneracy: the variable–constraint ratio of the optimal face. It provides an estimate for the likelihood that a basic variable can be pivoted out of the basis. Furthermore, we study how the so-called cloud intervals—the projections of the optimal face of the LP relaxations onto the individual variables—evolve during tree search and the implications for reducing the set of branching candidates. Y1 - 2020 U6 - https://doi.org/10.1007/s13675-020-00130-z IS - 8 SP - 241 EP - 246 ER - TY - CHAP A1 - Shinano, Yuji A1 - Tateiwa, N. A1 - Nakamura, S. A1 - Yoshida, A. A1 - Yasuda, M. A1 - Kaji, S. A1 - Fujisawa, K. T1 - Massive Parallelization for Finding Shortest Lattice Vectors Based on Ubiquity Generator Framework T2 - 2020 SC20: International Conference for High Performance Computing, Networking, Storage and Analysis (SC) N2 - Lattice-based cryptography has received attention as a next-generation encryption technique, because it is believed to be secure against attacks by classical and quantum computers. Its essential security depends on the hardness of solving the shortest vector problem (SVP). In the cryptography, to determine security levels, it is becoming significantly more important to estimate the hardness of the SVP by high-performance computing. In this study, we develop the world’s first distributed and asynchronous parallel SVP solver, the MAssively Parallel solver for SVP (MAP-SVP). It can parallelize algorithms for solving the SVP by applying the Ubiquity Generator framework, which is a generic framework for branch-and-bound algorithms. The MAP-SVP is suitable for massive-scale parallelization, owing to its small memory footprint, low communication overhead, and rapid checkpoint and restart mechanisms. We demonstrate its performance and scalability of the MAP-SVP by using up to 100,032 cores to solve instances of the Darmstadt SVP Challenge. Y1 - 2020 U6 - https://doi.org/10.1109/SC41405.2020.00064 SP - 834 EP - 848 ER - TY - JOUR A1 - Pokutta, Sebastian A1 - Spiegel, Christoph A1 - Zimmer, Max T1 - Deep Neural Network Training with Frank-Wolfe N2 - This paper studies the empirical efficacy and benefits of using projection-free first-order methods in the form of Conditional Gradients, a.k.a. Frank-Wolfe methods, for training Neural Networks with constrained parameters. We draw comparisons both to current state-of-the-art stochastic Gradient Descent methods as well as across different variants of stochastic Conditional Gradients. In particular, we show the general feasibility of training Neural Networks whose parameters are constrained by a convex feasible region using Frank-Wolfe algorithms and compare different stochastic variants. We then show that, by choosing an appropriate region, one can achieve performance exceeding that of unconstrained stochastic Gradient Descent and matching state-of-the-art results relying on L2-regularization. Lastly, we also demonstrate that, besides impacting performance, the particular choice of constraints can have a drastic impact on the learned representations. Y1 - 2020 ER - TY - JOUR A1 - Cryille W., Combettes A1 - Spiegel, Christoph A1 - Pokutta, Sebastian T1 - Projection-Free Adaptive Gradients for Large-Scale Optimization N2 - The complexity in large-scale optimization can lie in both handling the objective function and handling the constraint set. In this respect, stochastic Frank-Wolfe algorithms occupy a unique position as they alleviate both computational burdens, by querying only approximate first-order information from the objective and by maintaining feasibility of the iterates without using projections. In this paper, we improve the quality of their first-order information by blending in adaptive gradients. We derive convergence rates and demonstrate the computational advantage of our method over the state-of-the-art stochastic Frank-Wolfe algorithms on both convex and nonconvex objectives. The experiments further show that our method can improve the performance of adaptive gradient algorithms for constrained optimization. Y1 - 2020 ER - TY - JOUR A1 - Ramin, Elham A1 - Bestuzheva, Ksenia A1 - Gargalo, Carina A1 - Ramin, Danial A1 - Schneider, Carina A1 - Ramin, Pedram A1 - Flores-Alsina, Xavier A1 - Andersen, Maj M. A1 - Gernaey, Krist V. T1 - Incremental design of water symbiosis networks with prior knowledge: The case of an industrial park in Kenya JF - Science of the Total Environment N2 - 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. Y1 - 2021 U6 - https://doi.org/https://doi.org/10.1016/j.scitotenv.2020.141706 VL - 751 ER - TY - CHAP A1 - Pfetsch, Marc A1 - Pokutta, Sebastian T1 - IPBoost – Non-Convex Boosting via Integer Programming T2 - Proceedings of ICML Y1 - 2020 N1 - URL of the Code: https://www2.mathematik.tu-darmstadt.de/~pfetsch/ipboost.html N1 - URL of the Slides: https://app.box.com/s/8dpvmls88suouy11bkpwufhu7iiz6dxl N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2020/02/13/ipboost-abstract.html ER - TY - CHAP A1 - Pokutta, Sebastian A1 - Singh, M. A1 - Torrico, A. T1 - On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness T2 - Proceedings of ICML Y1 - 2020 N1 - URL of the Poster: https://app.box.com/s/24vbh1s2vib11upqyepzen3lzdl13skr N1 - URL of the Slides: https://app.box.com/s/fmjxhfdpiqubm28upf563ohy8t8fgl3a N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2020/06/03/unreasonable-abstract.html N1 - https://www.youtube.com/watch?v=VB1e0HrDmVo ER - TY - CHAP A1 - Diakonikolas, Jelena A1 - Carderera, Alejandro A1 - Pokutta, Sebastian T1 - Locally Accelerated Conditional Gradients T2 - Proceedings of AISTATS Y1 - 2020 N1 - URL of the Code: https://colab.research.google.com/drive/1ejjfCan7xnEhWWJXCIzb03CwQRG9iW_O N1 - URL of the PDF: http://proceedings.mlr.press/v108/diakonikolas20a/diakonikolas20a.pdf N1 - URL of the Slides: https://app.box.com/s/gphkhapso7d1vrfnzqykkb3vx0agxh8w N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2019/07/04/LaCG-abstract.html N1 - https://slideslive.com/38930107/locally-accelerated-conditional-gradients?ref=account-folder-52123-folders ER - TY - JOUR A1 - Anari, N. A1 - Haghtalab, N. A1 - Naor, S. A1 - Pokutta, Sebastian A1 - Singh, M. A1 - Torrico, A. T1 - Structured Robust Submodular Maximization: Offline and Online Algorithms JF - INFORMS Journal on Computing Y1 - 2020 ER - TY - CHAP A1 - Combettes, Cyrille W. A1 - Pokutta, Sebastian T1 - Boosting Frank-Wolfe by Chasing Gradients T2 - Proceedings of ICML Y1 - 2020 N1 - Additional Note: github code: https://github.com/cyrillewcombettes/boostfw N1 - URL of the Code: https://colab.research.google.com/drive/1TSOVjDFF1X2ADBo_adHLsUVrblSutRKw N1 - URL of the Slides: https://app.box.com/s/wwj247r5d456q0778p9b9y1jm6txuifb N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2020/03/16/boostFW.html N1 - https://www.youtube.com/watch?v=BfyV0C5FRbE ER - TY - CHAP A1 - Mortagy, Hassan A1 - Gupta, Swati A1 - Pokutta, Sebastian T1 - Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization T2 - Proceedings of NeurIPS Y1 - 2020 N1 - URL of the Code: https://github.com/pokutta/Walking-in-the-Shadow N1 - URL of the Poster: https://app.box.com/s/y266djezdjdidsswaopvdcnsnkp8774i N1 - URL of the Slides: https://app.box.com/s/wjhpe4nh8kv5pw6vl5jbp902v3mksivs ER - TY - CHAP A1 - Pokutta, Sebastian T1 - Restarting Algorithms: Sometimes there is Free Lunch T2 - Proceedings of CPAIOR Y1 - 2020 N1 - URL of the Slides: https://app.box.com/s/8ps8bhjv2phhy182xn55iurk9t3o1xc3 N1 - https://www.youtube.com/watch?v=v3Xzoda2_gQ ER - TY - CHAP A1 - Carderera, Alejandro A1 - Diakonikolas, Jelena A1 - Lin, Cheuk Yin A1 - Pokutta, Sebastian T1 - Parameter-free Locally Accelerated Conditional Gradients T2 - ICML 2021 N2 - Projection-free conditional gradient (CG) methods are the algorithms of choice for constrained optimization setups in which projections are often computationally prohibitive but linear optimization over the constraint set remains computationally feasible. Unlike in projection-based methods, globally accelerated convergence rates are in general unattainable for CG. However, a very recent work on Locally accelerated CG (LaCG) has demonstrated that local acceleration for CG is possible for many settings of interest. The main downside of LaCG is that it requires knowledge of the smoothness and strong convexity parameters of the objective function. We remove this limitation by introducing a novel, Parameter-Free Locally accelerated CG (PF-LaCG) algorithm, for which we provide rigorous convergence guarantees. Our theoretical results are complemented by numerical experiments, which demonstrate local acceleration and showcase the practical improvements of PF-LaCG over non-accelerated algorithms, both in terms of iteration count and wall-clock time. Y1 - 2021 ER - TY - JOUR A1 - Bienenstock, Daniel A1 - Muñoz, Gonzalo A1 - Pokutta, Sebastian T1 - Principled Deep Neural Network Training through Linear Programming N2 - Deep Learning has received significant attention due to its impressive performance in many state-of-the-art learning tasks. Unfortunately, while very powerful, Deep Learning is not well understood theoretically and in particular only recently results for the complexity of training deep neural networks have been obtained. In this work we show that large classes of deep neural networks with various architectures (e.g., DNNs, CNNs, Binary Neural Networks, and ResNets), activation functions (e.g., ReLUs and leaky ReLUs), and loss functions (e.g., Hinge loss, Euclidean loss, etc) can be trained to near optimality with desired target accuracy using linear programming in time that is exponential in the input data and parameter space dimension and polynomial in the size of the data set; improvements of the dependence in the input dimension are known to be unlikely assuming P≠NP, and improving the dependence on the parameter space dimension remains open. In particular, we obtain polynomial time algorithms for training for a given fixed network architecture. Our work applies more broadly to empirical risk minimization problems which allows us to generalize various previous results and obtain new complexity results for previously unstudied architectures in the proper learning setting. Y1 - 2018 ER - TY - CHAP A1 - Kerdreux, Thomas A1 - d'Aspremont, Alexandre A1 - Pokutta, Sebastian T1 - Projection-Free Optimization on Uniformly Convex Sets T2 - To Appear in Proceedings of AISTATS Y1 - 2020 ER - TY - JOUR A1 - Carderera, Alejandro A1 - Pokutta, Sebastian T1 - Second-order Conditional Gradient Sliding N2 - 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. Y1 - 2020 ER - TY - JOUR A1 - Kerdreux, Thomas A1 - d'Aspremont, Alexandre A1 - Pokutta, Sebastian T1 - Local and Global Uniform Convexity Conditions N2 - 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. Y1 - 2021 ER - TY - JOUR A1 - Bärmann, Andreas A1 - Martin, Alexander A1 - Pokutta, Sebastian A1 - Schneider, Oskar T1 - An Online-Learning Approach to Inverse Optimization Y1 - 2018 ER - TY - CHAP A1 - Parczyk, Olaf A1 - Pokutta, Sebastian A1 - Spiegel, Christoph A1 - Szabó, Tibor T1 - New Ramsey Multiplicity Bounds and Search Heuristics T2 - Discrete Mathematics Days N2 - We study two related problems concerning the number of monochromatic cliques in two-colorings of the complete graph that go back to questions of Erdős. Most notably, we improve the 25-year-old upper bounds of Thomason on the Ramsey multiplicity of K4 and K5 and we settle the minimum number of independent sets of size 4 in graphs with clique number at most 4. Motivated by the elusiveness of the symmetric Ramsey multiplicity problem, we also introduce an off-diagonal variant and obtain tight results when counting monochromatic K4 or K5 in only one of the colors and triangles in the other. The extremal constructions for each problem turn out to be blow-ups of a finite graph and were found through search heuristics. They are complemented by lower bounds and stability results established using Flag Algebras, resulting in a fully computer-assisted approach. More broadly, these problems lead us to the study of the region of possible pairs of clique and independent set densities that can be realized as the limit of some sequence of graphs. Y1 - 2022 ER - TY - GEN A1 - Bestuzheva, Ksenia A1 - Gleixner, Ambros A1 - Vigerske, Stefan T1 - A Computational Study of Perspective Cuts N2 - The benefits of cutting planes based on the perspective function are well known for many specific classes of mixed-integer nonlinear programs with on/off structures. However, we are not aware of any empirical studies that evaluate their applicability and computational impact over large, heterogeneous test sets in general-purpose solvers. This paper provides a detailed computational study of perspective cuts within a linear programming based branch-and-cut solver for general mixed-integer nonlinear programs. Within this study, we extend the applicability of perspective cuts from convex to nonconvex nonlinearities. This generalization is achieved by applying a perspective strengthening to valid linear inequalities which separate solutions of linear relaxations. The resulting method can be applied to any constraint where all variables appearing in nonlinear terms are semi-continuous and depend on at least one common indicator variable. Our computational experiments show that adding perspective cuts for convex constraints yields a consistent improvement of performance, and adding perspective cuts for nonconvex constraints reduces branch-and-bound tree sizes and strengthens the root node relaxation, but has no significant impact on the overall mean time. T3 - ZIB-Report - 21-07 KW - perspective cuts, mixed-integer nonlinear programming, nonconvex optimization, computational study Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81821 SN - 1438-0064 ER - TY - JOUR A1 - Kamčev, Nina A1 - Spiegel, Christoph T1 - Another note on intervals in the Hales-Jewett theorem JF - Electronic Journal of Combinatorics N2 - The Hales-Jewett Theorem states that any r-colouring of [m]ⁿ contains a monochromatic combinatorial line if n is large enough. Shelah's proof of the theorem implies that for m = 3 there always exists a monochromatic combinatorial line whose set of active coordinates is the union of at most r intervals. For odd r, Conlon and Kamčev constructed r–colourings for which it cannot be fewer than r intervals. However, we show that for even r and large n, any r–colouring of [3]ⁿ contains a monochromatic combinatorial line whose set of active coordinates is the union of at most r−1 intervals. This is optimal and extends a result of Leader and Räty for r=2. Y1 - 2022 U6 - https://doi.org/10.37236/6730 VL - 29 IS - 1 SP - P1.62 ER - TY - JOUR A1 - Hunkenschröder, Christoph A1 - Pokutta, Sebastian A1 - Weismantel, Robert T1 - Optimizing a low-dimensional convex function over a high-dimensional cub JF - SIAM Journal on Optimization Y1 - 2022 ER - TY - CHAP A1 - Wäldchen, Stephan A1 - Huber, Felix A1 - Pokutta, Sebastian T1 - Training Characteristic Functions with Reinforcement Learning: XAI-methods Play Connect Four T2 - Proceedings of the International Conference on Machine Learning Y1 - 2022 ER - TY - CHAP A1 - Tsuji, Kazuma A1 - Tanaka, Ken'ichiro A1 - Pokutta, Sebastian T1 - Pairwise Conditional Gradients without Swap Steps and Sparser Kernel Herding T2 - Proceedings of the International Conference on Machine Learning Y1 - 2022 ER - TY - JOUR A1 - Roux, Christophe A1 - Pokutta, Sebastian A1 - Wirth, Elias A1 - Kerdreux, Thomas T1 - Efficient Online-Bandit Strategies for Minimax Learning Problems N2 - Several learning problems involve solving min-max problems, e.g., empirical distributional robust learning [Namkoong and Duchi, 2016, Curi et al., 2020] or learning with non-standard aggregated losses [Shalev- Shwartz and Wexler, 2016, Fan et al., 2017]. More specifically, these problems are convex-linear problems where the minimization is carried out over the model parameters w ∈ W and the maximization over the empirical distribution p ∈ K of the training set indexes, where K is the simplex or a subset of it. To design efficient methods, we let an online learning algorithm play against a (combinatorial) bandit algorithm. We argue that the efficiency of such approaches critically depends on the structure of K and propose two properties of K that facilitate designing efficient algorithms. We focus on a specific family of sets Sn,k encompassing various learning applications and provide high-probability convergence guarantees to the minimax values. Y1 - 2021 ER - TY - CHAP A1 - Bestuzheva, Ksenia A1 - Gleixner, Ambros A1 - Völker, Helena T1 - Strengthening SONC Relaxations with Constraints Derived from Variable Bounds T2 - Proceedings of the Hungarian Global Optimization Workshop HUGO 2022 N2 - 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. Y1 - 2022 SP - 41 EP - 44 ER - TY - JOUR A1 - Kossen, Tabea A1 - Hirzel, Manuel A. A1 - Madai, Vince I. A1 - Boenisch, Franziska A1 - Hennemuth, Anja A1 - Hildebrand, Kristian A1 - Pokutta, Sebastian A1 - Sharma, Kartikey A1 - Hilbert, Adam A1 - Sobesky, Jan A1 - Galinovic, Ivana A1 - Khalil, Ahmed A. A1 - Fiebach, Jochen B. A1 - Frey, Dietmar T1 - Towards Sharing Brain Images: Differentially Private TOF-MRA Images with Segmentation Labels Using Generative Adversarial Networks JF - Frontiers in Artificial Intelligence N2 - Sharing labeled data is crucial to acquire large datasets for various Deep Learning applications. In medical imaging, this is often not feasible due to privacy regulations. Whereas anonymization would be a solution, standard techniques have been shown to be partially reversible. Here, synthetic data using a Generative Adversarial Network (GAN) with differential privacy guarantees could be a solution to ensure the patient's privacy while maintaining the predictive properties of the data. In this study, we implemented a Wasserstein GAN (WGAN) with and without differential privacy guarantees to generate privacy-preserving labeled Time-of-Flight Magnetic Resonance Angiography (TOF-MRA) image patches for brain vessel segmentation. The synthesized image-label pairs were used to train a U-net which was evaluated in terms of the segmentation performance on real patient images from two different datasets. Additionally, the Fréchet Inception Distance (FID) was calculated between the generated images and the real images to assess their similarity. During the evaluation using the U-Net and the FID, we explored the effect of different levels of privacy which was represented by the parameter ϵ. With stricter privacy guarantees, the segmentation performance and the similarity to the real patient images in terms of FID decreased. Our best segmentation model, trained on synthetic and private data, achieved a Dice Similarity Coefficient (DSC) of 0.75 for ϵ = 7.4 compared to 0.84 for ϵ = ∞ in a brain vessel segmentation paradigm (DSC of 0.69 and 0.88 on the second test set, respectively). We identified a threshold of ϵ <5 for which the performance (DSC <0.61) became unstable and not usable. Our synthesized labeled TOF-MRA images with strict privacy guarantees retained predictive properties necessary for segmenting the brain vessels. Although further research is warranted regarding generalizability to other imaging modalities and performance improvement, our results mark an encouraging first step for privacy-preserving data sharing in medical imaging. Y1 - 2022 U6 - https://doi.org/https://doi.org/10.3389/frai.2022.813842 ER - TY - CHAP A1 - Criado, Francisco A1 - Martínez-Rubio, David A1 - Pokutta, Sebastian T1 - Fast Algorithms for Packing Proportional Fairness and its Dual T2 - Proceedings of the Conference on Neural Information Processing Systems N2 - 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. Y1 - 2022 VL - 36 ER - TY - GEN A1 - Chmiela, Antonia A1 - Muñoz, Gonzalo A1 - Serrano, Felipe T1 - On the implementation and strengthening of intersection cuts for QCQPs N2 - The generation of strong linear inequalities for QCQPs has been recently tackled by a number of authors using the intersection cut paradigm - a highly studied tool in integer programming whose flexibility has triggered these renewed efforts in non-linear settings. In this work, we consider intersection cuts using the recently proposed construction of maximal quadratic-free sets. Using these sets, we derive closed-form formulas to compute intersection cuts which allow for quick cut-computations by simply plugging-in parameters associated to an arbitrary quadratic inequality being violated by a vertex of an LP relaxation. Additionally, we implement a cut-strengthening procedure that dates back to Glover and evaluate these techniques with extensive computational experiments. KW - Intersection cuts KW - QCQPs KW - Quadratic-free sets Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-79994 ER - TY - JOUR A1 - Yokoyama, Ryohei A1 - Shinano, Yuji A1 - Wakayama, Yuki A1 - Wakui, Tetsuya T1 - Model reduction by time aggregation for optimal design of energy supply systems by an MILP hierarchical branch and bound method JF - Energy N2 - Mixed-integer linear programming (MILP) methods have been applied widely to optimal design of energy supply systems in consideration of multi-period operation. A hierarchical MILP method has been proposed to solve such optimal design problems efficiently. An original problem has been solved by dividing it into a relaxed optimal design problem at the upper level and optimal operation problems which are independent of one another at the lower level. In addition, some strategies have been proposed to enhance the computation efficiency furthermore. In this paper, a method of reducing model by time aggregation is proposed as a novel strategy to search design candidates efficiently in the relaxed optimal design problem at the upper level. In addition, the previous strategies are modified in accordance with the novel strategy. This method is realized only by clustering periods and averaging energy demands for clustered periods, while it guarantees to derive the optimal solution. Thus, it may decrease the computation time at the upper level. Through a case study on the optimal design of a gas turbine cogeneration system, it is clarified how the model reduction is effective to enhance the computation efficiency in comparison and combination with the modified previous strategies. Y1 - 2019 U6 - https://doi.org/https://doi.org/10.1016/j.energy.2019.04.066 VL - 181 SP - 782 EP - 792 ER - TY - CHAP A1 - Chmiela, Antonia A1 - Muñoz, Gonzalo A1 - Serrano, Felipe T1 - On the implementation and strengthening of intersection cuts for QCQPs T2 - Integer Programming and Combinatorial Optimization: 22nd International Conference, IPCO 2021 N2 - The generation of strong linear inequalities for QCQPs has been recently tackled by a number of authors using the intersection cut paradigm - a highly studied tool in integer programming whose flexibility has triggered these renewed efforts in non-linear settings. In this work, we consider intersection cuts using the recently proposed construction of maximal quadratic-free sets. Using these sets, we derive closed-form formulas to compute intersection cuts which allow for quick cut-computations by simply plugging-in parameters associated to an arbitrary quadratic inequality being violated by a vertex of an LP relaxation. Additionally, we implement a cut-strengthening procedure that dates back to Glover and evaluate these techniques with extensive computational experiments. Y1 - 2021 U6 - https://doi.org/10.1007/978-3-030-73879-2_10 VL - 22 SP - 134 EP - 147 ER - TY - JOUR A1 - Carderera, Alejandro A1 - Pokutta, Sebastian A1 - Schütte, Christof A1 - Weiser, Martin T1 - CINDy: Conditional gradient-based Identification of Non-linear Dynamics – Noise-robust recovery JF - Journal of Computational and Applied Mathematics N2 - Governing equations are essential to the study of nonlinear dynamics, often enabling the prediction of previously unseen behaviors as well as the inclusion into control strategies. The discovery of governing equations from data thus has the potential to transform data-rich fields where well-established dynamical models remain unknown. This work contributes to the recent trend in data-driven sparse identification of nonlinear dynamics of finding the best sparse fit to observational data in a large library of potential nonlinear models. We propose an efficient first-order Conditional Gradient algorithm for solving the underlying optimization problem. In comparison to the most prominent alternative algorithms, the new algorithm shows significantly improved performance on several essential issues like sparsity-induction, structure-preservation, noise robustness, and sample efficiency. We demonstrate these advantages on several dynamics from the field of synchronization, particle dynamics, and enzyme chemistry. Y1 - 2021 ER - TY - GEN A1 - Bestuzheva, Ksenia A1 - Chmiela, Antonia A1 - Müller, Benjamin A1 - Serrano, Felipe A1 - Vigerske, Stefan A1 - Wegscheider, Fabian T1 - Global Optimization of Mixed-Integer Nonlinear Programs with SCIP 8.0 N2 - For over ten years, the constraint integer programming framework SCIP has been extended by capabilities for the solution of convex and nonconvex mixed-integer nonlinear programs (MINLPs). With the recently published version~8.0, these capabilities have been largely reworked and extended. This paper discusses the motivations for recent changes and provides an overview of features that are particular to MINLP solving in SCIP. Further, difficulties in benchmarking global MINLP solvers are discussed and a comparison with several state-of-the-art global MINLP solvers is provided. T3 - ZIB-Report - 23-01 Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-89348 SN - 1438-0064 ER - TY - JOUR A1 - Nohadani, Omid A1 - Sharma, Kartikey T1 - Optimization under Connected Uncertainty JF - INFORMS Journal on Optimization N2 - Robust optimization methods have shown practical advantages in a wide range of decision-making applications under uncertainty. Recently, their efficacy has been extended to multiperiod settings. Current approaches model uncertainty either independent of the past or in an implicit fashion by budgeting the aggregate uncertainty. In many applications, however, past realizations directly influence future uncertainties. For this class of problems, we develop a modeling framework that explicitly incorporates this dependence via connected uncertainty sets, whose parameters at each period depend on previous uncertainty realizations. To find optimal here-and-now solutions, we reformulate robust and distributionally robust constraints for popular set structures and demonstrate this modeling framework numerically on broadly applicable knapsack and portfolio-optimization problems. Y1 - 2022 U6 - https://doi.org/10.1287/ijoo.2021.0067 VL - 4 IS - 3 SP - 326 EP - 346 ER - TY - CHAP A1 - Rué Perna, Juanjo A1 - Spiegel, Christoph T1 - The Rado Multiplicity Problem in Vector Spaces Over Finite Fields T2 - Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications, EUROCOMB’23 Y1 - 2023 U6 - https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-108 SP - 784 EP - 789 ER - TY - JOUR A1 - Combettes, Cyrille A1 - Pokutta, Sebastian T1 - Revisiting the Approximate Carathéodory Problem via the Frank-Wolfe Algorithm JF - Mathematical Programming Y1 - 2023 U6 - https://doi.org/10.1007/s10107-021-01735-x VL - 197 SP - 191 EP - 214 ER - TY - GEN A1 - Hosoda, Junko A1 - Maher, Stephen J. A1 - Shinano, Yuji A1 - Villumsen, Jonas Christoffer T1 - Location, transshipment and routing: An adaptive transportation network integrating long-haul and local vehicle routing N2 - 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. T3 - ZIB-Report - 21-12 Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-83438 ER - TY - GEN A1 - Eifler, Leon A1 - Gleixner, Ambros T1 - Safe and Verified Gomory Mixed Integer Cuts in a Rational MIP Framework N2 - This paper is concerned with the exact solution of mixed-integer programs (MIPs) over the rational numbers, i.e., without any roundoff errors and error tolerances. Here, one computational bottleneck that should be avoided whenever possible is to employ large-scale symbolic computations. Instead it is often possible to use safe directed rounding methods, e.g., to generate provably correct dual bounds. In this work, we continue to leverage this paradigm and extend an exact branch-and-bound framework by separation routines for safe cutting planes, based on the approach first introduced by Cook, Dash, Fukasawa, and Goycoolea in 2009. Constraints are aggregated safely using approximate dual multipliers from an LP solve, followed by mixed-integer rounding to generate provably valid, although slightly weaker inequalities. We generalize this approach to problem data that is not representable in floating-point arithmetic, add routines for controlling the encoding length of the resulting cutting planes, and show how these cutting planes can be verified according to the VIPR certificate standard. Furthermore, we analyze the performance impact of these cutting planes in the context of an exact MIP framework, showing that we can solve 21.5% more instances and reduce solving times by 26.8% on the MIPLIB 2017 benchmark test set. T3 - ZIB-Report - 23-09 KW - Mixed integer programming, Exact computation, Rational arithmetic, Cutting Planes, Symbolic Computations, Certificate of correctness Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-90159 SN - 1438-0064 ER - TY - JOUR A1 - Bestuzheva, Ksenia A1 - Gleixner, Ambros A1 - Vigerske, Stefan T1 - A Computational Study of Perspective Cuts JF - Mathematical Programming Computation N2 - The benefits of cutting planes based on the perspective function are well known for many specific classes of mixed-integer nonlinear programs with on/off structures. However, we are not aware of any empirical studies that evaluate their applicability and computational impact over large, heterogeneous test sets in general-purpose solvers. This paper provides a detailed computational study of perspective cuts within a linear programming based branch-and-cut solver for general mixed-integer nonlinear programs. Within this study, we extend the applicability of perspective cuts from convex to nonconvex nonlinearities. This generalization is achieved by applying a perspective strengthening to valid linear inequalities which separate solutions of linear relaxations. The resulting method can be applied to any constraint where all variables appearing in nonlinear terms are semi-continuous and depend on at least one common indicator variable. Our computational experiments show that adding perspective cuts for convex constraints yields a consistent improvement of performance, and adding perspective cuts for nonconvex constraints reduces branch-and-bound tree sizes and strengthens the root node relaxation, but has no significant impact on the overall mean time. Y1 - 2023 U6 - https://doi.org/10.1007/s12532-023-00246-4 VL - 15 SP - 703 EP - 731 ER - TY - CHAP A1 - Bestuzheva, Ksenia A1 - Gleixner, Ambros A1 - Achterberg, Tobias T1 - Efficient Separation of RLT Cuts for Implicit and Explicit Bilinear Products T2 - Integer Programming and Combinatorial Optimization. IPCO 2023. N2 - 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. Y1 - 2023 U6 - https://doi.org/10.1007/978-3-031-32726-1_2 VL - 13904 SP - 14 EP - 28 PB - Springer, Cham ER - TY - GEN A1 - Eifler, Leon A1 - Gleixner, Ambros A1 - Pulaj, Jonad T1 - A Safe Computational Framework for Integer Programming applied to Chvátal's Conjecture N2 - 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á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átal's conjecture holds for all downsets whose union of sets contains seven elements or less. T3 - ZIB-Report - 21-35 KW - exact rational mixed integer programming KW - extremal combinatorics Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-84444 SN - 1438-0064 ER - TY - CHAP A1 - Sofranac, Boro A1 - Gleixner, Ambros A1 - Pokutta, Sebastian T1 - An Algorithm-Independent Measure of Progress for Linear Constraint Propagation T2 - 27th International Conference on Principles and Practice of Constraint Programming (CP 2021) N2 - 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. Y1 - 2021 U6 - https://doi.org/10.4230/LIPIcs.CP.2021.52 VL - 210 SP - 52:1 EP - 52:17 ER - TY - JOUR A1 - Hendel, Gregor A1 - Anderson, Daniel A1 - Le Bodic, Pierre A1 - Pfetsch, Marc T1 - Estimating the Size of Branch-And-Bound Trees JF - INFORMS Journal on Computing N2 - 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. Y1 - 2021 U6 - https://doi.org/10.1287/ijoc.2021.1103 ER - TY - JOUR A1 - Eifler, Leon A1 - Gleixner, Ambros A1 - Pulaj, Jonad T1 - A Safe Computational Framework for Integer Programming applied to Chvátal's Conjecture JF - ACM Transactions on Mathematical Software N2 - 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á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átal's conjecture holds for all downsets whose union of sets contains seven elements or less. Y1 - 2022 U6 - https://doi.org/10.1145/3485630 VL - 48 IS - 2 ER - TY - CHAP A1 - Breuer, Thomas A1 - Bussieck, Michael A1 - Cao, Karl-Kien A1 - Fiand, Fred A1 - Gils, Hans-Christian A1 - Gleixner, Ambros A1 - Khabi, Dmitry A1 - Kempke, Nils A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Wetzel, Manuel T1 - BEAM-ME: Accelerating Linear Energy Systems Models by a Massively Parallel Interior Point Method T2 - NIC Symposium 2020 Y1 - 2020 VL - 50 SP - 345 EP - 352 ER - TY - CHAP A1 - Chmiela, Antonia A1 - Gleixner, Ambros A1 - Lichocki, Pawel A1 - Pokutta, Sebastian T1 - Online Learning for Scheduling MIP Heuristics T2 - Integration of Constraint Programming, Artificial Intelligence, and Operations Research N2 - Mixed Integer Programming (MIP) is NP-hard, and yet modern solvers often solve large real-world problems within minutes. This success can partially be attributed to heuristics. Since their behavior is highly instance-dependent, relying on hard-coded rules derived from empirical testing on a large heterogeneous corpora of benchmark instances might lead to sub-optimal performance. In this work, we propose an online learning approach that adapts the application of heuristics towards the single instance at hand. We replace the commonly used static heuristic handling with an adaptive framework exploiting past observations about the heuristic’s behavior to make future decisions. In particular, we model the problem of controlling Large Neighborhood Search and Diving – two broad and complex classes of heuristics – as a multi-armed bandit problem. Going beyond existing work in the literature, we control two different classes of heuristics simultaneously by a single learning agent. We verify our approach numerically and show consistent node reductions over the MIPLIB 2017 Benchmark set. For harder instances that take at least 1000 seconds to solve, we observe a speedup of 4%. Y1 - 2023 U6 - https://doi.org/10.1007/978-3-031-33271-5_8 VL - 13884 SP - 114 EP - 123 PB - Springer, Cham ER - TY - JOUR A1 - Šofranac, Boro A1 - Gleixner, Ambros A1 - Pokutta, Sebastian T1 - An Algorithm-independent Measure of Progress for Linear Constraint Propagation JF - Constraints Y1 - 2022 U6 - https://doi.org/10.1007/s10601-022-09338-9 VL - 27 SP - 432 EP - 455 ER - TY - JOUR A1 - Eifler, Leon A1 - Gleixner, Ambros T1 - Safe and Verified Gomory Mixed Integer Cuts in a Rational MIP Framework JF - SIAM Journal on Optimization N2 - This paper is concerned with the exact solution of mixed-integer programs (MIPs) over the rational numbers, i.e., without any roundoff errors and error tolerances. Here, one computational bottleneck that should be avoided whenever possible is to employ large-scale symbolic computations. Instead it is often possible to use safe directed rounding methods, e.g., to generate provably correct dual bounds. In this work, we continue to leverage this paradigm and extend an exact branch-and-bound framework by separation routines for safe cutting planes, based on the approach first introduced by Cook, Dash, Fukasawa, and Goycoolea in 2009. Constraints are aggregated safely using approximate dual multipliers from an LP solve, followed by mixed-integer rounding to generate provably valid, although slightly weaker inequalities. We generalize this approach to problem data that is not representable in floating-point arithmetic, add routines for controlling the encoding length of the resulting cutting planes, and show how these cutting planes can be verified according to the VIPR certificate standard. Furthermore, we analyze the performance impact of these cutting planes in the context of an exact MIP framework, showing that we can solve 21.5% more instances and reduce solving times by 26.8% on the MIPLIB 2017 benchmark test set. Y1 - 2023 ER - TY - JOUR A1 - Eifler, Leon A1 - Gleixner, Ambros T1 - A Computational Status Update for Exact Rational Mixed Integer Programming JF - Integer Programming and Combinatorial Optimization: 22th International Conference, IPCO 2021 N2 - 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. Y1 - 2021 U6 - https://doi.org/10.1007/978-3-030-73879-2_12 ER - TY - JOUR A1 - Eifler, Leon A1 - Gleixner, Ambros T1 - A computational status update for exact rational mixed integer programming JF - Mathematical Programming N2 - 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. Y1 - 2022 U6 - https://doi.org/10.1007/s10107-021-01749-5 PB - Springer ER - TY - CHAP A1 - Chmiela, Antonia A1 - Khalil, Elias B. A1 - Gleixner, Ambros A1 - Lodi, Andrea A1 - Pokutta, Sebastian T1 - Learning to Schedule Heuristics in Branch and Bound T2 - Thirty-fifth Conference on Neural Information Processing Systems, NeurIPS 2021 N2 - Primal heuristics play a crucial role in exact solvers for Mixed Integer Programming (MIP). While solvers are guaranteed to find optimal solutions given sufficient time, real-world applications typically require finding good solutions early on in the search to enable fast decision-making. While much of MIP research focuses on designing effective heuristics, the question of how to manage multiple MIP heuristics in a solver has not received equal attention. Generally, solvers follow hard-coded rules derived from empirical testing on broad sets of instances. Since the performance of heuristics is instance-dependent, using these general rules for a particular problem might not yield the best performance. In this work, we propose the first data-driven framework for scheduling heuristics in an exact MIP solver. By learning from data describing the performance of primal heuristics, we obtain a problem-specific schedule of heuristics that collectively find many solutions at minimal cost. We provide a formal description of the problem and propose an efficient algorithm for computing such a schedule. Compared to the default settings of a state-of-the-art academic MIP solver, we are able to reduce the average primal integral by up to 49% on a class of challenging instances. Y1 - 2021 ER - TY - JOUR A1 - Šofranac, Boro A1 - Gleixner, Ambros A1 - Pokutta, Sebastian T1 - Accelerating domain propagation: An efficient GPU-parallel algorithm over sparse matrices JF - Parallel Computing N2 - • 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. Y1 - 2022 U6 - https://doi.org/10.1016/j.parco.2021.102874 VL - 109 SP - 102874 ER - TY - CHAP A1 - Sofranac, Boro A1 - Gleixner, Ambros A1 - Pokutta, Sebastian T1 - Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse Matrices T2 - 2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3) N2 - 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. Y1 - 2020 U6 - https://doi.org/10.1109/IA351965.2020.00007 N1 - URL of the Slides: https://app.box.com/s/qy0pjmhtbm7shk2ypxjxlh2sj4nudvyu N1 - URL of the Abstract: http://www.pokutta.com/blog/research/2020/09/20/gpu-prob.html SP - 1 EP - 11 ER - TY - JOUR A1 - Bonami, Pierre A1 - Gleixner, Ambros A1 - Linderoth, Jeff A1 - Misener, Ruth T1 - Designing and Implementing Algorithms for Mixed-Integer Nonlinear Optimization (Dagstuhl Seminar 18081) JF - Dagstuhl Reports N2 - Mathematical models for optimal decisions often require both nonlinear and discrete components. These mixed-integer nonlinear programs (MINLP) may be used to optimize the energy use of large industrial plants, integrate renewable sources into energy networks, design biological and biomedical systems, and address numerous other applications of societal importance. The first MINLP algorithms and software were designed by application engineers. While these efforts initially proved useful, scientists, engineers, and practitioners have realized that a transformational shift in technology will be required for MINLP to achieve its full potential. MINLP has transitioned to a forefront position in computer science, with researchers actively developing MINLP theory, algorithms, and implementations. Even with their concerted effort, algorithms and available software are often unable to solve practically-sized instances of these important models. Current obstacles include characterizing the computability boundary, effectively exploiting known optimization technologies for specialized classes of MINLP, and effectively using logical formulas holistically throughout algorithms. Y1 - 2018 U6 - https://doi.org/10.4230/DagRep.8.2.64 VL - 8 IS - 2 SP - 64 EP - 87 ER - TY - JOUR A1 - Witzig, Jakob A1 - Berthold, Timo T1 - Conflict Analysis for MINLP JF - INFORMS Journal on Computing N2 - The generalization of MIP techniques to deal with nonlinear, potentially non-convex, constraints have been a fruitful direction of research for computational MINLP in the last decade. In this paper, we follow that path in order to extend another essential subroutine of modern MIP solvers towards the case of nonlinear optimization: the analysis of infeasible subproblems for learning additional valid constraints. To this end, we derive two different strategies, geared towards two different solution approaches. These are using local dual proofs of infeasibility for LP-based branch-and-bound and the creation of nonlinear dual proofs for NLP-based branch-and-bound, respectively. We discuss implementation details of both approaches and present an extensive computational study, showing that both techniques can significantly enhance performance when solving MINLPs to global optimality. Y1 - 2021 U6 - https://doi.org/10.1287/ijoc.2020.1050 VL - 33 IS - 2 SP - 421 EP - 435 ER - TY - CHAP A1 - Chmiela, Antonia A1 - Muñoz, Gonzalo A1 - Serrano, Felipe T1 - Monoidal strengthening and unique lifting in MIQCPs T2 - Integer Programming and Combinatorial Optimization. IPCO 2023. N2 - Using the recently proposed maximal quadratic-free sets and the well-known monoidal strengthening procedure, we show how to improve inter- section cuts for quadratically-constrained optimization problems by exploiting integrality requirements. We provide an explicit construction that allows an efficient implementation of the strengthened cuts along with computational results showing their improvements over the standard intersection cuts. We also show that, in our setting, there is unique lifting which implies that our strengthening procedure is generating the best possible cut coefficients for the integer variables. Y1 - 2023 U6 - https://doi.org/10.1007/978-3-031-32726-1_7 VL - 13904 SP - 87 EP - 99 ER - TY - THES A1 - Francobaldi, Matteo T1 - Learning to Use Local Cuts N2 - 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. KW - Mathematical Programming KW - Machine Learning KW - Artificial Intelligence Y1 - 2021 ER - TY - CHAP A1 - Martínez-Rubio, David A1 - Wirth, Elias A1 - Pokutta, Sebastian T1 - Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond T2 - Proceedings of Machine Learning Research N2 - 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. Y1 - 2023 UR - https://proceedings.mlr.press/v195/martinez-rubio23a/martinez-rubio23a.pdf VL - 195 SP - 1 EP - 35 ER - TY - CHAP A1 - Parczyk, Olaf A1 - Pokutta, Sebastian A1 - Spiegel, Christoph A1 - Szabó, Tibor T1 - Fully Computer-assisted Proofs in Extremal Combinatorics T2 - Proceedings of the AAAI Conference on Artificial Intelligence N2 - We present a fully computer-assisted proof system for solving a particular family of problems in Extremal Combinatorics. Existing techniques using Flag Algebras have proven powerful in the past, but have so far lacked a computational counterpart to derive matching constructive bounds. We demonstrate that common search heuristics are capable of finding constructions far beyond the reach of human intuition. Additionally, the most obvious downside of such heuristics, namely a missing guarantee of global optimality, can often be fully eliminated in this case through lower bounds and stability results coming from the Flag Algebra approach. To illustrate the potential of this approach, we study two related and well-known problems in Extremal Graph Theory that go back to questions of Erdős from the 60s. Most notably, we present the first major improvement in the upper bound of the Ramsey multiplicity of the complete graph on 4 vertices in 25 years, precisely determine the first off-diagonal Ramsey multiplicity number, and settle the minimum number of independent sets of size four in graphs with clique number strictly less than five. Y1 - 2023 U6 - https://doi.org/10.1609/aaai.v37i10.26470 VL - 37 IS - 10 SP - 12482 EP - 12490 ER - TY - CHAP A1 - Wirth, Elias A1 - Pokutta, Sebastian T1 - Conditional Gradients for the Approximately Vanishing Ideal T2 - Proceedings of The 25th International Conference on Artificial Intelligence and Statistics N2 - The vanishing ideal of a set of points X is the set of polynomials that evaluate to 0 over all points x in X and admits an efficient representation by a finite set of polynomials called generators. To accommodate the noise in the data set, we introduce the Conditional Gradients Approximately Vanishing Ideal algorithm (CGAVI) for the construction of the set of generators of the approximately vanishing ideal. The constructed set of generators captures polynomial structures in data and gives rise to a feature map that can, for example, be used in combination with a linear classifier for supervised learning. In CGAVI, we construct the set of generators by solving specific instances of (constrained) convex optimization problems with the Pairwise Frank-Wolfe algorithm (PFW). Among other things, the constructed generators inherit the LASSO generalization bound and not only vanish on the training but also on out-sample data. Moreover, CGAVI admits a compact representation of the approximately vanishing ideal by constructing few generators with sparse coefficient vectors. Y1 - 2022 UR - https://proceedings.mlr.press/v151/wirth22a.html VL - 151 SP - 2191 EP - 2209 ER - TY - JOUR A1 - Kerdreux, Thomas A1 - Roux, Christophe A1 - d'Aspremont, Alexandre A1 - Pokutta, Sebastian T1 - Linear Bandits on Uniformly Convex Sets JF - Journal of Machine Learning Research N2 - Linear bandit algorithms yield O~(n√T) pseudo-regret bounds on compact convex action sets K⊂Rn and two types of structural assumptions lead to better pseudo-regret bounds. When K is the simplex or an ℓp ball with p∈]1,2], there exist bandits algorithms with O~(√n√T) pseudo-regret bounds. Here, we derive bandit algorithms for some strongly convex sets beyond ℓp balls that enjoy pseudo-regret bounds of O~(√n√T), which answers an open question from [BCB12, §5.5.]. Interestingly, when the action set is uniformly convex but not necessarily strongly convex, we obtain pseudo-regret bounds with a dimension dependency smaller than O(√n). However, this comes at the expense of asymptotic rates in T varying between O(√T) and O(T). Y1 - 2021 UR - https://www.jmlr.org/papers/v22/21-0277.html VL - 22 IS - 284 SP - 1 EP - 23 ER - TY - CHAP A1 - Martínez-Rubio, David A1 - Pokutta, Sebastian T1 - Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties T2 - Proceedings of Thirty Sixth Conference on Learning Theory N2 - We propose a globally-accelerated, first-order method for the optimization of smooth and (strongly or not) geodesically-convex functions in a wide class of Hadamard manifolds. We achieve the same convergence rates as Nesterov’s accelerated gradient descent, up to a multiplicative geometric penalty and log factors. Crucially, we can enforce our method to stay within a compact set we define. Prior fully accelerated works \emph{resort to assuming} that the iterates of their algorithms stay in some pre-specified compact set, except for two previous methods of limited applicability. For our manifolds, this solves the open question in (Kim and Yang, 2022) about obtaining global general acceleration without iterates assumptively staying in the feasible set.In our solution, we design an accelerated Riemannian inexact proximal point algorithm, which is a result that was unknown even with exact access to the proximal operator, and is of independent interest. For smooth functions, we show we can implement the prox step inexactly with first-order methods in Riemannian balls of certain diameter that is enough for global accelerated optimization. Y1 - 2023 UR - https://proceedings.mlr.press/v195/martinez-rubio23a.html VL - 195 SP - 359 EP - 393 ER - TY - GEN A1 - Eifler, Leon A1 - Gleixner, Ambros T1 - A Computational Status Update for Exact Rational Mixed Integer Programming N2 - 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. T3 - ZIB-Report - 21-04 Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-81298 SN - 1438-0064 ER - TY - GEN A1 - Bestuzheva, Ksenia A1 - Gleixner, Ambros A1 - Völker, Helena T1 - Strengthening SONC Relaxations with Constraints Derived from Variable Bounds N2 - 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. T3 - ZIB-Report - 22-23 Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-88306 SN - 1438-0064 ER - TY - JOUR A1 - Müller, Benjamin A1 - Muñoz, Gonzalo A1 - Gasse, Maxime A1 - Gleixner, Ambros A1 - Lodi, Andrea A1 - Serrano, Felipe T1 - On generalized surrogate duality in mixed-integer nonlinear programming JF - Mathematical Programming N2 - The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global ϵ-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solvers can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In this work, we exploit this fact and make use of a nonconvex relaxation obtained via aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in an MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm’s ability to generate strong dual bounds through extensive computational experiments. Y1 - 2022 U6 - https://doi.org/10.1007/s10107-021-01691-6 VL - 192 IS - 1 SP - 89 EP - 118 ER - TY - GEN A1 - Bestuzheva, Ksenia A1 - Völker, Helena A1 - Gleixner, Ambros T1 - Strengthening SONC Relaxations with Constraints Derived from Variable Bounds N2 - 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. Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-89510 SN - 1438-0064 ER - TY - JOUR A1 - Gemander, Patrick A1 - Chen, Wei-Kun A1 - Weninger, Dieter A1 - Gottwald, Leona A1 - Gleixner, Ambros T1 - Two-row and two-column mixed-integer presolve using hashing-based pairing methods JF - EURO Journal on Computational Optimization N2 - In state-of-the-art mixed-integer programming solvers, a large array of reduction techniques are applied to simplify the problem and strengthen the model formulation before starting the actual branch-and-cut phase. Despite their mathematical simplicity, these methods can have significant impact on the solvability of a given problem. However, a crucial property for employing presolve techniques successfully is their speed. Hence, most methods inspect constraints or variables individually in order to guarantee linear complexity. In this paper, we present new hashing-based pairing mechanisms that help to overcome known performance limitations of more powerful presolve techniques that consider pairs of rows or columns. Additionally, we develop an enhancement to one of these presolve techniques by exploiting the presence of set-packing structures on binary variables in order to strengthen the resulting reductions without increasing runtime. We analyze the impact of these methods on the MIPLIB 2017 benchmark set based on an implementation in the MIP solver SCIP. Y1 - 2020 U6 - https://doi.org/10.1007/s13675-020-00129-6 VL - 8 IS - 3-4 SP - 205 EP - 240 ER - TY - JOUR A1 - Devriendt, Jo A1 - Gleixner, Ambros A1 - Nordström, Jakob T1 - Learn to Relax: Integrating 0-1 Integer Linear Programming with Pseudo-Boolean Conflict-Driven Search JF - Constraints N2 - Conflict-driven pseudo-Boolean solvers optimize 0-1 integer linear programs by extending the conflict-driven clause learning (CDCL) paradigm from SAT solving. Though pseudo-Boolean solvers have the potential to be exponentially more efficient than CDCL solvers in theory, in practice they can sometimes get hopelessly stuck even when the linear programming (LP) relaxation is infeasible over the reals. Inspired by mixed integer programming (MIP), we address this problem by interleaving incremental LP solving with cut generation within the conflict-driven pseudo-Boolean search. This hybrid approach, which for the first time combines MIP techniques with full-blown conflict analysis operating directly on linear inequalities using the cutting planes method, significantly improves performance on a wide range of benchmarks, approaching a "best-of-both-worlds" scenario between SAT-style conflict-driven search and MIP-style branch-and-cut. Y1 - 2021 U6 - https://doi.org/10.1007/s10601-020-09318-x VL - 26 SP - 26 EP - 55 ER - TY - JOUR A1 - Gelß, Patrick A1 - Klus, Stefan A1 - Knebel, Sebastian A1 - Shakibaei, Zarin A1 - Pokutta, Sebastian T1 - Low-Rank Tensor Decompositions of Quantum Circuits JF - Journal of Computational Physics N2 - Quantum computing is arguably one of the most revolutionary and disruptive technologies of this century. Due to the ever-increasing number of potential applications as well as the continuing rise in complexity, the development, simulation, optimization, and physical realization of quantum circuits is of utmost importance for designing novel algorithms. We show how matrix product states (MPSs) and matrix product operators (MPOs) can be used to express certain quantum states, quantum gates, and entire quantum circuits as low-rank tensors. This enables the analysis and simulation of complex quantum circuits on classical computers and to gain insight into the underlying structure of the system. We present different examples to demonstrate the advantages of MPO formulations and show that they are more efficient than conventional techniques if the bond dimensions of the wave function representation can be kept small throughout the simulation. Y1 - 2022 ER - TY - JOUR A1 - Riedel, Jerome A1 - Gelß, Patrick A1 - Klein, Rupert A1 - Schmidt, Burkhard T1 - WaveTrain: a Python Package for Numerical Quantum Mechanics of Chain-like Systems Based on Tensor Trains JF - The Journal of Chemical Physics N2 - WaveTrain is an open-source software for numerical simulations of chain-like quantum systems with nearest-neighbor (NN) interactions only. The Python package is centered around tensor train (TT, or matrix product) format representations of Hamiltonian operators and (stationary or time-evolving) state vectors. It builds on the Python tensor train toolbox Scikit_tt, which provides efficient construction methods and storage schemes for the TT format. Its solvers for eigenvalue problems and linear differential equations are used in WaveTrain for the time-independent and time-dependent Schrödinger equations, respectively. Employing efficient decompositions to construct low-rank representations, the tensor-train ranks of state vectors are often found to depend only marginally on the chain length N. This results in the computational effort growing only slightly more than linearly with N, thus mitigating the curse of dimensionality. As a complement to the classes for full quantum mechanics, WaveTrain also contains classes for fully classical and mixed quantum–classical (Ehrenfest or mean field) dynamics of bipartite systems. The graphical capabilities allow visualization of quantum dynamics “on the fly,” with a choice of several different representations based on reduced density matrices. Even though developed for treating quasi-one-dimensional excitonic energy transport in molecular solids or conjugated organic polymers, including coupling to phonons, WaveTrain can be used for any kind of chain-like quantum systems, with or without periodic boundary conditions and with NN interactions only. The present work describes version 1.0 of our WaveTrain software, based on version 1.2 of scikit_tt, both of which are freely available from the GitHub platform where they will also be further developed. Moreover, WaveTrain is mirrored at SourceForge, within the framework of the WavePacket project for numerical quantum dynamics. Worked-out demonstration examples with complete input and output, including animated graphics, are available. Y1 - 2023 U6 - https://doi.org/10.1063/5.0147314 VL - 158 IS - 16 SP - 164801 ER - TY - JOUR A1 - Gelß, Patrick A1 - Klein, Rupert A1 - Matera, Sebastian A1 - Schmidt, Burkhard T1 - Solving the time-independent Schrödinger equation for chains of coupled excitons and phonons using tensor trains JF - The Journal of Chemical Physics N2 - We demonstrate how to apply the tensor-train format to solve the time-independent Schrödinger equation for quasi-one-dimensional excitonic chain systems with and without periodic boundary conditions. The coupled excitons and phonons are modeled by Fröhlich–Holstein type Hamiltonians with on-site and nearest-neighbor interactions only. We reduce the memory consumption as well as the computational costs significantly by employing efficient decompositions to construct low-rank tensor-train representations, thus mitigating the curse of dimensionality. In order to compute also higher quantum states, we introduce an approach that directly incorporates the Wielandt deflation technique into the alternating linear scheme for the solution of eigenproblems. Besides systems with coupled excitons and phonons, we also investigate uncoupled problems for which (semi-)analytical results exist. There, we find that in the case of homogeneous systems, the tensor-train ranks of state vectors only marginally depend on the chain length, which results in a linear growth of the storage consumption. However, the central processing unit time increases slightly faster with the chain length than the storage consumption because the alternating linear scheme adopted in our work requires more iterations to achieve convergence for longer chains and a given rank. Finally, we demonstrate that the tensor-train approach to the quantum treatment of coupled excitons and phonons makes it possible to directly tackle the phenomenon of mutual self-trapping. We are able to confirm the main results of the Davydov theory, i.e., the dependence of the wave packet width and the corresponding stabilization energy on the exciton–phonon coupling strength, although only for a certain range of that parameter. In future work, our approach will allow calculations also beyond the validity regime of that theory and/or beyond the restrictions of the Fröhlich–Holstein type Hamiltonians. Y1 - 2022 U6 - https://doi.org/10.1063/5.0074948 VL - 156 IS - 2 SP - 024109 ER - TY - JOUR A1 - Bienstock, Daniel A1 - Muñoz, Gonzalo A1 - Pokutta, Sebastian T1 - Principled Deep Neural Network Training Through Linear Programming JF - Discrete Optimization N2 - 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. Y1 - 2023 U6 - https://doi.org/10.1016/j.disopt.2023.100795 VL - 49 ER - TY - JOUR A1 - Kevin-Martin, Aigner A1 - Bärmann, Andreas A1 - Braun, Kristin A1 - Liers, Frauke A1 - Pokutta, Sebastian A1 - Schneider, Oskar A1 - Sharma, Kartikey A1 - Tschuppik, Sebastian T1 - Data-driven Distributionally Robust Optimization over Time JF - INFORMS Journal on Optimization N2 - Stochastic optimization (SO) is a classical approach for optimization under uncertainty that typically requires knowledge about the probability distribution of uncertain parameters. Because the latter is often unknown, distributionally robust optimization (DRO) provides a strong alternative that determines the best guaranteed solution over a set of distributions (ambiguity set). In this work, we present an approach for DRO over time that uses online learning and scenario observations arriving as a data stream to learn more about the uncertainty. Our robust solutions adapt over time and reduce the cost of protection with shrinking ambiguity. For various kinds of ambiguity sets, the robust solutions converge to the SO solution. Our algorithm achieves the optimization and learning goals without solving the DRO problem exactly at any step. We also provide a regret bound for the quality of the online strategy that converges at a rate of O(log T/T−−√), where T is the number of iterations. Furthermore, we illustrate the effectiveness of our procedure by numerical experiments on mixed-integer optimization instances from popular benchmark libraries and give practical examples stemming from telecommunications and routing. Our algorithm is able to solve the DRO over time problem significantly faster than standard reformulations. Y1 - 2023 U6 - https://doi.org/10.1287/ijoo.2023.0091 VL - 5 IS - 4 SP - 376 EP - 394 ER - TY - CHAP A1 - Mexi, Gioni A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Nordström, Jakob T1 - Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning T2 - 29th International Conference on Principles and Practice of Constraint Programming (CP 2023) N2 - 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. Y1 - 2023 U6 - https://doi.org/10.4230/LIPIcs.CP.2023.27 VL - 280 SP - 27:1 EP - 27:19 PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik ER - TY - GEN A1 - Eifler, Leon A1 - Nicolas-Thouvenin, Jules A1 - Gleixner, Ambros T1 - Combining Precision Boosting with LP Iterative Refinement for Exact Linear Optimization N2 - 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. T3 - ZIB-Report - 23-26 Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-92573 SN - 1438-0064 ER - TY - JOUR A1 - Eifler, Leon A1 - Nicolas-Thouvenin, Jules A1 - Gleixner, Ambros T1 - Combining Precision Boosting with LP Iterative Refinement for Exact Linear Optimization N2 - 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. Y1 - 2023 ER - TY - CHAP A1 - Carderera, Alejandro A1 - Pokutta, Sebastian A1 - Mathieu, Besançon T1 - Simple steps are all you need: Frank-Wolfe and generalized self-concordant functions T2 - Thirty-fifth Conference on Neural Information Processing Systems, NeurIPS 2021 N2 - 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. Y1 - 2021 ER - TY - JOUR A1 - Mathieu, Besançon A1 - Carderera, Alejandro A1 - Pokutta, Sebastian T1 - FrankWolfe.jl: a high-performance and flexible toolbox for Frank-Wolfe algorithms and Conditional Gradients JF - INFORMS Journal on Computing N2 - 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. Y1 - 2022 U6 - https://doi.org/10.1287/ijoc.2022.1191 VL - 34 IS - 5 SP - 2383 EP - 2865 ER - TY - JOUR A1 - Besançon, Mathieu A1 - Anjos, Miguel F. A1 - Brotcorne, Luce T1 - Complexity of near-optimal robust versions of multilevel optimization problems JF - Optimization Letters N2 - 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. Y1 - 2021 U6 - https://doi.org/10.1007/s11590-021-01754-9 VL - 15 IS - 8 SP - 2597 EP - 2610 ER - TY - CHAP A1 - MacDonald, Jan A1 - Besançon, Mathieu A1 - Pokutta, Sebastian T1 - Interpretable Neural Networks with Frank-Wolfe: Sparse Relevance Maps and Relevance Orderings T2 - Proceedings of the International Conference on Machine Learning Y1 - 2022 ER - TY - GEN A1 - Bestuzheva, Ksenia A1 - Besançon, Mathieu A1 - Chen, Wei-Kun A1 - Chmiela, Antonia A1 - Donkiewicz, Tim A1 - van Doornmalen, Jasper A1 - Eifler, Leon A1 - Gaul, Oliver A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Gottwald, Leona A1 - Graczyk, Christoph A1 - Halbig, Katrin A1 - Hoen, Alexander A1 - Hojny, Christopher A1 - van der Hulst, Rolf A1 - Koch, Thorsten A1 - Lübbecke, Marco A1 - Maher, Stephen J. A1 - Matter, Frederic A1 - Mühmer, Erik A1 - Müller, Benjamin A1 - Pfetsch, Marc E. A1 - Rehfeldt, Daniel A1 - Schlein, Steffan A1 - Schlösser, Franziska A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Sofranac, Boro A1 - Turner, Mark A1 - Vigerske, Stefan A1 - Wegscheider, Fabian A1 - Wellner, Philipp A1 - Weninger, Dieter A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 8.0 N2 - 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. T3 - ZIB-Report - 21-41 KW - Constraint integer programming KW - Linear programming KW - Mixed-integer linear programming KW - Mixed-integer nonlinear programming KW - Optimization solver KW - Branch-and-cut KW - Branch-and-price KW - Column generation KW - Parallelization KW - Mixed-integer semidefinite programming Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-85309 SN - 1438-0064 ER - TY - JOUR A1 - Designolle, Sébastien A1 - Besançon, Mathieu A1 - Iommazzo, Gabriele A1 - Knebel, Sebastian A1 - Gelß, Patrick A1 - Pokutta, Sebastian T1 - Improved Local Models and New Bell Inequalities Via Frank-Wolfe Algorithms JF - Physical Review Research N2 - 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. Y1 - 2023 U6 - https://doi.org/10.1103/PhysRevResearch.5.043059 VL - 5 SP - 043059 ER - TY - JOUR A1 - Bestuzheva, Ksenia A1 - Chmiela, Antonia A1 - Müller, Benjamin A1 - Serrano, Felipe A1 - Vigerske, Stefan A1 - Wegscheider, Fabian T1 - Global Optimization of Mixed-Integer Nonlinear Programs with SCIP 8.0 JF - Journal of Global Optimization N2 - For over ten years, the constraint integer programming framework SCIP has been extended by capabilities for the solution of convex and nonconvex mixed-integer nonlinear programs (MINLPs). With the recently published version 8.0, these capabilities have been largely reworked and extended. This paper discusses the motivations for recent changes and provides an overview of features that are particular to MINLP solving in SCIP. Further, difficulties in benchmarking global MINLP solvers are discussed and a comparison with several state-of-the-art global MINLP solvers is provided. Y1 - 2023 U6 - https://doi.org/10.1007/s10898-023-01345-1 ER - TY - JOUR A1 - Kruser, Jacqueline M. A1 - Sharma, Kartikey A1 - Holl, Jane L. A1 - Nohadani, Omid T1 - Identifying Patterns of Medical Intervention in Acute Respiratory Failure: A Retrospective Observational Study JF - Critical Care Explorations Y1 - 2023 U6 - https://doi.org/10.1097/CCE.0000000000000984 VL - 5 IS - 10 SP - p e0984 ER - TY - CHAP A1 - Mexi, Gioni A1 - Besançon, Mathieu A1 - Bolusani, Suresh A1 - Chmiela, Antonia A1 - Hoen, Alexander A1 - Gleixner, Ambros T1 - Scylla: a matrix-free fix-propagate-and-project heuristic for mixed-integer optimization T2 - Proceedings of Conference of the Society for Operations Research in Germany Y1 - 2023 ER - TY - CHAP A1 - Wirth, Elias A1 - Kerdreux, Thomas A1 - Pokutta, Sebastian T1 - Acceleration of Frank-Wolfe Algorithms with Open Loop Step-sizes T2 - Proceedings of International Conference on Artificial Intelligence and Statistics Y1 - 2023 ER - TY - CHAP A1 - Zimmer, Max A1 - Spiegel, Christoph A1 - Pokutta, Sebastian T1 - How I Learned to Stop Worrying and Love Retraining T2 - Proceedings of International Conference on Learning Representations Y1 - 2023 ER - TY - CHAP A1 - Combettes, P. L. A1 - Woodstock, Zev T1 - signal recovery from inconsistent nonlinear observations T2 - Proceedings of ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) Y1 - 2022 ER - TY - JOUR A1 - Bestuzheva, Ksenia A1 - Besançon, Mathieu A1 - Chen, Wei-Kun A1 - Chmiela, Antonia A1 - Donkiewicz, Tim A1 - Doornmalen, Jasper A1 - Eifler, Leon A1 - Gaul, Oliver A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Gottwald, Leona A1 - Graczyk, Christoph A1 - Halbig, Katrin A1 - Hoen, Alexander A1 - Hojny, Christopher A1 - Hulst, Rolf A1 - Koch, Thorsten A1 - Lübbecke, Marco A1 - Maher, Stephen J. A1 - Matter, Frederic A1 - Mühmer, Erik A1 - Müller, Benjamin A1 - Pfetsch, Marc A1 - Rehfeldt, Daniel A1 - Schlein, Steffan A1 - Schlösser, Franziska A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Sofranac, Boro A1 - Turner, Mark A1 - Vigerske, Stefan A1 - Wegscheider, Fabian A1 - Wellner, Philipp A1 - Weninger, Dieter A1 - Witzig, Jakob T1 - Enabling research through the SCIP optimization suite 8.0 JF - ACM Transactions on Mathematical Software N2 - The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. The focus of this article is on the role of the SCIP Optimization Suite in supporting research. SCIP’s main design principles are discussed, followed by a presentation of the latest performance improvements and developments in version 8.0, which serve both as examples of SCIP’s application as a research tool and as a platform for further developments. Furthermore, this article gives an overview of interfaces to other programming and modeling languages, new features that expand the possibilities for user interaction with the framework, and the latest developments in several extensions built upon SCIP. Y1 - 2023 U6 - https://doi.org/10.1145/3585516 VL - 49 IS - 2 SP - 1 EP - 21 ER - TY - JOUR A1 - Besançon, Mathieu A1 - Garcia, Joaquim Dias A1 - Legat, Benoît A1 - Sharma, Akshay T1 - Flexible Differentiable Optimization via Model Transformations JF - INFORMS Journal on Computing N2 - We introduce DiffOpt.jl, a Julia library to differentiate through the solution of optimization problems with respect to arbitrary parameters present in the objective and/or constraints. The library builds upon MathOptInterface, thus leveraging the rich ecosystem of solvers and composing well with modeling languages like JuMP. DiffOpt offers both forward and reverse differentiation modes, enabling multiple use cases from hyperparameter optimization to backpropagation and sensitivity analysis, bridging constrained optimization with end-to-end differentiable programming. DiffOpt is built on two known rules for differentiating quadratic programming and conic programming standard forms. However, thanks to its ability to differentiate through model transformations, the user is not limited to these forms and can differentiate with respect to the parameters of any model that can be reformulated into these standard forms. This notably includes programs mixing affine conic constraints and convex quadratic constraints or objective function. Y1 - 2023 U6 - https://doi.org/10.1287/ijoc.2022.0283 ER - TY - JOUR A1 - Eifler, Leon A1 - Gleixner, Ambros T1 - A computational status update for exact rational mixed integer programming JF - Mathematical Programming N2 - 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. Y1 - 2023 U6 - https://doi.org/10.1007/s10107-021-01749-5 VL - 197 SP - 793 EP - 812 ER - TY - CHAP A1 - Criscitiello, Christopher A1 - Martínez-Rubio, David A1 - Boumal, Nicolas T1 - Open problem: polynomial linearly-convergent method for g-convex optimization? T2 - Proceedings of Thirty Sixth Conference on Learning Theory, PMLR Y1 - 2023 UR - https://proceedings.mlr.press/v195/criscitiello23b.html VL - 195 SP - 5950 EP - 5956 ER - TY - JOUR A1 - Pokutta, Sebastian T1 - The Frank-Wolfe algorithm: a short introduction JF - Jahresbericht der Deutschen Mathematiker-Vereinigung Y1 - 2023 ER - TY - CHAP A1 - Zimmer, Max A1 - Spiegel, Christoph A1 - Pokutta, Sebastian T1 - Sparse Model Soups T2 - Proceedings of International Conference on Learning Representations Y1 - 2024 ER - TY - JOUR A1 - Designolle, Sébastien A1 - Iommazzo, Gabriele A1 - Besançon, Mathieu A1 - Knebel, Sebastian A1 - Gelß, Patrick A1 - Pokutta, Sebastian T1 - Improved local models and new Bell inequalities via Frank-Wolfe algorithms JF - Physical Review Research N2 - 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. Y1 - 2023 U6 - https://doi.org/10.1103/PhysRevResearch.5.043059 VL - 5 SP - 043059 ER - TY - JOUR A1 - Liberti, Leo A1 - Iommazzo, Gabriele A1 - Lavor, Carlile A1 - Maculan, Nelson T1 - Cycle-based formulations in distance geometry JF - Open Journal of Mathematical Optimization N2 - The distance geometry problem asks to find a realization of a given simple edge-weighted graph in a Euclidean space of given dimension , where the edges are realized as straight segments of lengths equal (or as close as possible) to the edge weights. The problem is often modelled as a mathematical programming formulation involving decision variables that determine the position of the vertices in the given Euclidean space. Solution algorithms are generally constructed using local or global nonlinear optimization techniques. We present a new modelling technique for this problem where, instead of deciding vertex positions, the formulations decide the length of the segments representing the edges in each cycle in the graph, projected in every dimension. We propose an exact formulation and a relaxation based on a Eulerian cycle. We then compare computational results from protein conformation instances obtained with stochastic global optimization techniques on the new cycle-based formulation and on the existing edge-based formulation. While edge-based formulations take less time to reach termination, cycle-based formulations are generally better on solution quality measures. Y1 - 2023 U6 - https://doi.org/10.5802/ojmo.18 VL - 4 ER - TY - CHAP A1 - Gasse, Maxime A1 - Bowly, Simon A1 - Cappart, Quentin A1 - Charfreitag, Jonas A1 - Charlin, Laurent A1 - Chételat, Didier A1 - Chmiela, Antonia A1 - Dumouchelle, Justin A1 - Gleixner, Ambros A1 - Kazachkov, Aleksandr M. A1 - Khalil, Elias A1 - Lichocki, Pawel A1 - Lodi, Andrea A1 - Lubin, Miles A1 - Maddison, Chris J. A1 - Christopher, Morris A1 - Papageorgiou, Dimitri J. A1 - Parjadis, Augustin A1 - Pokutta, Sebastian A1 - Prouvost, Antoine A1 - Scavuzzo, Lara A1 - Zarpellon, Giulia A1 - Yang, Linxin A1 - Lai, Sha A1 - Wang, Akang A1 - Luo, Xiaodong A1 - Zhou, Xiang A1 - Huang, Haohan A1 - Shao, Shengcheng A1 - Zhu, Yuanming A1 - Zhang, Dong A1 - Quan, Tao A1 - Cao, Zixuan A1 - Xu, Yang A1 - Huang, Zhewei A1 - Zhou, Shuchang A1 - Binbin, Chen A1 - Minggui, He A1 - Hao, Hao A1 - Zhiyu, Zhang A1 - Zhiwu, An A1 - Kun, Mao T1 - The Machine Learning for Combinatorial Optimization Competition (ML4CO): results and insights T2 - Proceedings of Conference on Neural Information Processing Systems Y1 - 2022 ER - TY - CHAP A1 - Búi, M. N. A1 - Combettes, P. L. A1 - Woodstock, Zev T1 - block-activated algorithms for multicomponent fully nonsmooth minimization T2 - Proceedings of ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) Y1 - 2022 ER - TY - JOUR A1 - Bolusani, Suresh A1 - Ralphs, Ted K. T1 - a framework for generalized Benders' decomposition and its applications to multilevel optimization JF - Mathematical Programming Y1 - 2022 ER - TY - JOUR A1 - Wilken, St. Elmo A1 - Besançon, Mathieu A1 - Kratochvíl, Miroslav A1 - Kuate, Chilperic Armel Foko A1 - Trefois, Christophe A1 - Gu, Wei A1 - Ebenhöh, Oliver T1 - Interrogating the effect of enzyme kinetics on metabolism using differentiable constraint-based models JF - Metabolic Engineering Y1 - 2022 ER - TY - JOUR A1 - Combettes, P. L. A1 - Woodstock, Zev T1 - a variational inequality model for the construction of signals from inconsistent nonlinear equations JF - SIAM Journal on Imaging Sciences Y1 - 2022 ER - TY - CHAP A1 - Wirth, Elias A1 - Kera, A1 - Pokutta, Sebastian T1 - Approximate Vanishing Ideal Computations at Scale T2 - Proceedings of International Conference on Learning Representations Y1 - 2023 ER - TY - GEN A1 - Prause, Felix T1 - A Multi-Swap Heuristic for Rolling Stock Rotation Planning with Predictive Maintenance N2 - We present a heuristic solution approach for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). The task of this problem is to assign a sequence of trips to each of the vehicles and to schedule their maintenance such that all trips can be operated. Here, the health states of the vehicles are considered to be random variables distributed by a family of probability distribution functions, and the maintenance services should be scheduled based on the failure probability of the vehicles. The proposed algorithm first generates a solution by solving an integer linear program and then heuristically improves this solution by applying a local search procedure. For this purpose, the trips assigned to the vehicles are split up and recombined, whereby additional deadhead trips can be inserted between the partial assignments. Subse- quently, the maintenance is scheduled by solving a shortest path problem in a state-expanded version of a space-time graph restricted to the trips of the individual vehicles. The solution approach is tested and evaluated on a set of test instances based on real-world timetables. T3 - ZIB-Report - 23-29 KW - Rolling stock rotation planning KW - Predictive maintenance KW - Heuristic KW - State-expanded graph model KW - Integer linear program Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-93133 SN - 1438-0064 ER - TY - GEN A1 - Prause, Felix A1 - Borndörfer, Ralf T1 - Construction of a Test Library for the Rolling Stock Rotation Problem with Predictive Maintenance N2 - We describe the development of a test library for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). Our approach involves the utilization of genuine timetables from a private German railroad company. The generated instances incorporate probability distribution functions for modeling the health states of the vehicles and the considered trips possess varying degradation functions. RSRP-PdM involves assigning trips to a fleet of vehicles and scheduling their maintenance based on their individual health states. The goal is to minimize the total costs consisting of operational costs and the expected costs associated with vehicle failures. The failure probability is dependent on the health states of the vehicles, which are assumed to be random variables distributed by a family of probability distributions. Each distribution is represented by the parameters characterizing it and during the operation of the trips, these parameters get altered. Our approach incorporates non-linear degradation functions to describe the inference of the parameters but also linear ones could be applied. The resulting instances consist of the timetables of the individual lines that use the same vehicle type. Overall, we employ these assumptions and utilize open-source data to create a library of instances with varying difficulty. Our approach is vital for evaluating and comparing algorithms designed to solve the RSRP-PdM. T3 - ZIB-Report - 23-20 KW - Rolling Stock Rotation Planning KW - Predictive Maintenance KW - Test Library Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-91734 SN - 1438-0064 ER - TY - GEN A1 - Prause, Felix A1 - Borndörfer, Ralf A1 - Grimm, Boris A1 - Tesch, Alexander T1 - Approximating the RSRP with Predictive Maintenance N2 - We study the solution of the rolling stock rotation problem with predictive maintenance (RSRP-PM) by an iterative refinement approach that is based on a state-expanded event-graph. In this graph, the states are parameters of a failure distribution, and paths correspond to vehicle rotations with associated health state approximations. An optimal set of paths including maintenance can be computed by solving an integer linear program. Afterwards, the graph is refined and the procedure repeated. An associated linear program gives rise to a lower bound that can be used to determine the solution quality. Computational results for two instances derived from real world timetables of a German railway company are presented. The results show the effectiveness of the approach and the quality of the solutions. T3 - ZIB-Report - 23-04 KW - Rolling Stock Rotation Planning KW - Predictive Maintenance KW - Integer Linear Programming KW - Heuristic KW - Lower Bound Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-89531 SN - 1438-0064 ER - TY - GEN A1 - Gahururu, Deborah A1 - Hintermüller, Michael A1 - Stengl, Steven-Marian A1 - Surowiec, Thomas M. T1 - Generalized Nash equilibrium problems with partial differential operators: theory, algorithms, and risk aversion T2 - Non-smooth and Complementarity-based Distributed Parameter Systems: Simulation and Hierarchical Optimization Y1 - 2022 ER - TY - CHAP A1 - Martínez-Rubio, David A1 - Roux, Christophe A1 - Criscitiello, Christopher A1 - Pokutta, Sebastian T1 - Accelerated Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties T2 - Proceedings of Optimization for Machine Learning (NeurIPS Workshop OPT 2023) Y1 - 2023 ER - TY - CHAP A1 - Martínez-Rubio, David A1 - Pokutta, Sebastian T1 - Accelerated Riemannian optimization: Handling constraints with a prox to bound geometric penalties T2 - Proceedings of Optimization for Machine Learning (NeurIPS Workshop OPT 2022) Y1 - 2022 ER - TY - JOUR A1 - Hunkenschröder, Christoph A1 - Pokutta, Sebastian A1 - Weismantel, Robert T1 - Optimizing a low-dimensional convex function over a high-dimensional cube JF - SIAM Journal on Optimization Y1 - 2022 ER - TY - CHAP A1 - Thuerck, Daniel A1 - Sofranac, Boro A1 - Pfetsch, Marc A1 - Pokutta, Sebastian T1 - Learning cuts via enumeration oracles T2 - Proceedings of Conference on Neural Information Processing Systems Y1 - 2023 ER - TY - GEN A1 - Iommazzo, Gabriele A1 - D'Ambrosio, Claudia A1 - Frangioni, Antonio A1 - Liberti, Leo T1 - Algorithm configuration problem T2 - Encyclopedia of Optimization Y1 - 2022 ER - TY - GEN A1 - Binkowski, Felix A1 - Kullig, Julius A1 - Betz, Fridtjof A1 - Zschiedrich, Lin A1 - Walther, Andrea A1 - Wiersig, Jan A1 - Burger, Sven T1 - Source code and simulation results: Computing eigenfrequency sensitivities near exceptional points T2 - Zenodo Y1 - 2024 U6 - https://doi.org/10.5281/zenodo.10715639 SP - doi: 10.5281/zenodo.10715639 ER - TY - CHAP A1 - Sharma, Kartikey A1 - Hendrych, Deborah A1 - Besançon, Mathieu A1 - Pokutta, Sebastian T1 - Network Design for the Traffic Assignment Problem with Mixed-Integer Frank-Wolfe T2 - Proceedings of INFORMS Optimization Society Conference Y1 - 2024 ER - TY - GEN A1 - Bolusani, Suresh A1 - Besançon, Mathieu A1 - Bestuzheva, Ksenia A1 - Chmiela, Antonia A1 - Dionísio, João A1 - Donkiewicz, Tim A1 - van Doornmalen, Jasper A1 - Eifler, Leon A1 - Ghannam, Mohammed A1 - Gleixner, Ambros A1 - Graczyk, Christoph A1 - Halbig, Katrin A1 - Hedtke, Ivo A1 - Hoen, Alexander A1 - Hojny, Christopher A1 - van der Hulst, Rolf A1 - Kamp, Dominik A1 - Koch, Thorsten A1 - Kofler, Kevin A1 - Lentz, Jurgen A1 - Manns, Julian A1 - Mexi, Gioni A1 - Mühmer, Erik A1 - E. Pfetsch, Marc A1 - Schlösser, Franziska A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Turner, Mark A1 - Vigerske, Stefan A1 - Weninger, Dieter A1 - Xu, Liding T1 - The SCIP Optimization Suite 9.0 N2 - The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming framework SCIP. This report discusses the enhancements and extensions included in the SCIP Optimization Suite 9.0. The updates in SCIP 9.0 include improved symmetry handling, additions and improvements of nonlinear handlers and primal heuristics, a new cut generator and two new cut selection schemes, a new branching rule, a new LP interface, and several bug fixes. The SCIP Optimization Suite 9.0 also features new Rust and C++ interfaces for SCIP, new Python interface for SoPlex, along with enhancements to existing interfaces. The SCIP Optimization Suite 9.0 also includes new and improved features in the LP solver SoPlex, the presolving library PaPILO, the parallel framework UG, the decomposition framework GCG, and the SCIP extension SCIP-SDP. These additions and enhancements have resulted in an overall performance improvement of SCIP in terms of solving time, number of nodes in the branch-and-bound tree, as well as the reliability of the solver. T3 - ZIB-Report - 24-02-29 KW - Constraint integer programming KW - Linear programming KW - Mixed-integer linear programming KW - Mixed-integer nonlinear programming KW - Optimization solver KW - Branch-and-cut KW - Branch-and-price KW - Column generation KW - Parallelization KW - Mixed-integer semidefinite programming Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-95528 SN - 1438-0064 ER - TY - JOUR A1 - Kreimeier, Timo A1 - Pokutta, Sebastian A1 - Walther, Andrea A1 - Woodstock, Zev T1 - On a Frank-Wolfe approach for abs-smooth functions JF - Optimization Methods and Software Y1 - U6 - https://doi.org/10.1080/10556788.2023.2296985 ER - TY - JOUR A1 - Chmiela, Antonia A1 - Muñoz, Gonzalo A1 - Serrano, Felipe T1 - On the implementation and strengthening of intersection cuts for QCQPs JF - Mathematical Programming B Y1 - 2023 U6 - https://doi.org/10.1007/s10107-022-01808-5 VL - 197 SP - 549 EP - 586 ER - TY - CHAP A1 - Ghannam, Mohammed A1 - Gleixner, Ambros T1 - Hybrid genetic search for dynamic vehicle routing with time windows T2 - Proceedings of Conference of the Society for Operations Research in Germany Y1 - 2023 ER - TY - JOUR A1 - Designolle, Sébastien A1 - Vértesi, Tamás A1 - Pokutta, Sebastian T1 - Symmetric multipartite Bell inequalities via Frank-Wolfe algorithms JF - Physics Review A N2 - In multipartite Bell scenarios, we study the nonlocality robustness of the Greenberger-Horne-Zeilinger (GHZ) state. When each party performs planar measurements forming a regular polygon, we exploit the symmetry of the resulting correlation tensor to drastically accelerate the computation of (i) a Bell inequality via Frank-Wolfe algorithms and (ii) the corresponding local bound. The Bell inequalities obtained are facets of the symmetrized local polytope and they give the best-known upper bounds on the nonlocality robustness of the GHZ state for three to ten parties. Moreover, for four measurements per party, we generalize our facets and hence show, for any number of parties, an improvement on Mermin's inequality in terms of noise robustness. We also compute the detection efficiency of our inequalities and show that some give rise to the activation of nonlocality in star networks, a property that was only shown with an infinite number of measurements. Y1 - 2024 U6 - https://doi.org/10.1103/PhysRevA.109.022205 VL - 109 IS - 2 ER - TY - JOUR A1 - Donati, Luca A1 - Fackeldey, Konstantin A1 - Weber, Marcus T1 - Augmented ant colony algorithm for virtual drug discovery JF - Journal of Mathematical Chemistry N2 - Docking is a fundamental problem in computational biology and drug discovery that seeks to predict a ligand’s binding mode and affinity to a target protein. However, the large search space size and the complexity of the underlying physical interactions make docking a challenging task. Here, we review a docking method, based on the ant colony optimization algorithm, that ranks a set of candidate ligands by solving a minimization problem for each ligand individually. In addition, we propose an augmented version that takes into account all energy functions collectively, allowing only one minimization problem to be solved. The results show that our modification outperforms in accuracy and efficiency. Y1 - 2023 U6 - https://doi.org/10.1007/s10910-023-01549-6 VL - 62 SP - 367 EP - 385 ER - TY - JOUR A1 - Deza, Antoine A1 - Pokutta, Sebastian A1 - Pournin, Lionel T1 - The complexity of geometric scaling JF - Operations Research Letters Y1 - 2024 U6 - https://doi.org/10.1016/j.orl.2023.11.010 VL - 52 SP - 107057 ER - TY - JOUR A1 - Binkowski, Felix A1 - Kullig, Julius A1 - Betz, Fridtjof A1 - Zschiedrich, Lin A1 - Walther, Andrea A1 - Wiersig, Jan A1 - Burger, Sven T1 - Computing eigenfrequency sensitivities near exceptional points JF - Phys. Rev. Research Y1 - 2024 U6 - https://doi.org/10.1103/PhysRevResearch.6.023148 VL - 6 SP - 023148 ER - TY - JOUR A1 - Tjusila, Gennesaret A1 - Besançon, Mathieu A1 - Turner, Mark A1 - Koch, Thorsten T1 - How Many Clues To Give? A Bilevel Formulation For The Minimum Sudoku Clue Problem JF - Operations Research Letters N2 - 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. Y1 - 2024 U6 - https://doi.org/10.1016/j.orl.2024.107105 VL - 54 SP - 107105 ER - TY - CHAP A1 - Prause, Felix T1 - A Multi-Swap Heuristic for Rolling Stock Rotation Planning with Predictive Maintenance T2 - Proceedings of the 11th International Network Optimization Conference (INOC), Dublin, Ireland, March 11-23, 2024 N2 - We present a heuristic solution approach for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). The task of this problem is to assign a sequence of trips to each of the vehicles and to schedule their maintenance such that all trips can be operated. Here, the health states of the vehicles are considered to be random variables distributed by a family of probability distribution functions, and the maintenance services should be scheduled based on the failure probability of the vehicles. The proposed algorithm first generates a solution by solving an integer linear program and then heuristically improves this solution by applying a local search procedure. For this purpose, the trips assigned to the vehicles are split up and recombined, whereby additional deadhead trips can be inserted between the partial assignments. Subsequently, the maintenance is scheduled by solving a shortest path problem in a state-expanded version of a space-time graph restricted to the trips of the individual vehicles. The solution approach is tested and evaluated on a set of test instances based on real-world timetables. Y1 - 2024 U6 - https://doi.org/10.48786/inoc.2024.11 SP - 58 EP - 63 ER - TY - THES A1 - Pedersen, Jaap T1 - Multiperiod Optimal Power Flow Problem In Distribution System Planning N2 - Growing demand, distributed generation, such as renewable energy sources (RES), and the increasing role of storage systems to mitigate the volatility of RES on a medium voltage level, push existing distribution grids to their limits. Therefore, necessary network expansion needs to be evaluated to guarantee a safe and reliable electricity supply in the future taking these challenges into account. This problem is formulated as an optimal power flow (OPF) problem which combines network expansion, volatile generation and storage systems, minimizing network expansion and generation costs. As storage systems introduce a temporal coupling into the system, a multiperiod OPF problem is needed and analysed in this thesis. To reduce complexity, the network expansion problem is represented in a continuous nonlinear programming formulation by using fundamental properties of electrical engeneering. This formulation is validated succesfully against a common mixed integer programming approach on a 30 and 57 bus network with respect to solution and computing time. As the OPF problem is, in general, a nonconvex, nonlinear problem and, thus, hard to solve, convex relaxations of the power flow equations have gained increasing interest. Sufficient conditions are represented which guarantee exactness of a second-order cone (SOC) relaxation of an operational OPF in radial networks. In this thesis, these conditions are enhanced for the network expansion planning problem. Additionally, nonconvexities introduced by the choice of network expansion variables are relaxed by using McCormick envelopes. These relaxations are then applied on the multiperiod OPF and compared to the original problem on a 30 and a 57 bus network. In particular, the computational time is decreased by an order up to 10^2 by the SOC relaxation while it provides either an exact solution or a sufficient lower bound on the original problem. Finally, a sensitivity study is performed on weights of network expansion costs showing strong dependency of both the solution of performed expansion and solution time on the chosen weights. KW - multiperiod optimal power flow, distribution network planning, battery storage Y1 - 2020 ER - TY - CHAP A1 - Wäldchen, Stephan A1 - Sharma, Kartikey A1 - Turan, Berkant A1 - Zimmer, Max A1 - Pokutta, Sebastian T1 - Interpretability Guarantees with Merlin-Arthur Classifiers T2 - Proceedings of International Conference on Artificial Intelligence and Statistics N2 - 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. Y1 - 2024 ER - TY - JOUR A1 - Braun, Gábor A1 - Guzmán, Cristóbal A1 - Pokutta, Sebastian T1 - Corrections to “Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory” JF - IEEE Transactions on Information Theory N2 - This note closes a gap in the proof of Theorem VI.3 from the article “Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory” (2017). Y1 - 2024 U6 - https://doi.org/10.1109/TIT.2024.3357200 VL - 70 IS - 7 SP - 5408 EP - 5409 ER - TY - CHAP A1 - Mexi, Gioni A1 - Shamsi, Somayeh A1 - Besançon, Mathieu A1 - Bodic, Pierre T1 - Probabilistic Lookahead Strong Branching via a Stochastic Abstract Branching Model T2 - Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2024 N2 - Strong Branching (SB) is a cornerstone of all modern branching rules used in the Branch-and-Bound (BnB) algorithm, which is at the center of Mixed-Integer Programming solvers. In its full form, SB evaluates all variables to branch on and then selects the one producing the best relaxation, leading to small trees, but high runtimes. State-of-the-art branching rules therefore use SB with working limits to achieve both small enough trees and short run times. So far, these working limits have been established empirically. In this paper, we introduce a theoretical approach to guide how much SB to use at each node within the BnB. We first define an abstract stochastic tree model of the BnB algorithm where the geometric mean dual gains of all variables follow a given probability distribution. This model allows us to relate expected dual gains to tree sizes and explicitly compare the cost of sampling an additional SB candidate with the reward in expected tree size reduction. We then leverage the insight from the abstract model to design a new stopping criterion for SB, which fits a distribution to the dual gains and, at each node, dynamically continues or interrupts SB. This algorithm, which we refer to as Probabilistic Lookahead Strong Branching, improves both the tree size and runtime over MIPLIB instances, providing evidence that the method not only changes the amount of SB, but allocates it better. Y1 - 2024 U6 - https://doi.org/10.1007/978-3-031-60599-4_4 VL - 14743 ER - TY - JOUR A1 - Eifler, Leon A1 - Gleixner, Ambros T1 - Safe and verified Gomory mixed integer cuts in a rational MIP framework JF - SIAM Journal on Optimization N2 - This paper is concerned with the exact solution of mixed-integer programs (MIPs) over the rational numbers, i.e., without any roundoff errors and error tolerances. Here, one computational bottleneck that should be avoided whenever possible is to employ large-scale symbolic computations. Instead it is often possible to use safe directed rounding methods, e.g., to generate provably correct dual bounds. In this work, we continue to leverage this paradigm and extend an exact branch-and-bound framework by separation routines for safe cutting planes, based on the approach first introduced by Cook, Dash, Fukasawa, and Goycoolea in 2009 [INFORMS J. Comput., 21 (2009), pp. 641–649]. Constraints are aggregated safely using approximate dual multipliers from an LP solve, followed by mixed-integer rounding to generate provably valid, although slightly weaker inequalities. We generalize this approach to problem data that is not representable in floating-point arithmetic, add routines for controlling the encoding length of the resulting cutting planes, and show how these cutting planes can be verified according to the VIPR certificate standard. Furthermore, we analyze the performance impact of these cutting planes in the context of an exact MIP framework, showing that we can solve 21.5% more instances to exact optimality and reduce solving times by 26.8% on the MIPLIB 2017 benchmark test set. Y1 - 2024 U6 - https://doi.org/10.1137/23M156046X VL - 34 IS - 1 ER - TY - CHAP A1 - Hoen, Alexander A1 - Oertel, Andy A1 - Gleixner, Ambros A1 - Nordström, Jakob T1 - Certifying MIP-based presolve reductions for 0-1 integer linear programs T2 - Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2024 N2 - It is well known that reformulating the original problem can be crucial for the performance of mixed-integer programming (MIP) solvers. To ensure correctness, all transformations must preserve the feasibility status and optimal value of the problem, but there is currently no established methodology to express and verify the equivalence of two mixed-integer programs. In this work, we take a first step in this direction by showing how the correctness of MIP presolve reductions on – integer linear programs can be certified by using (and suitably extending) the VeriPB tool for pseudo-Boolean proof logging. Our experimental evaluation on both decision and optimization instances demonstrates the computational viability of the approach and leads to suggestions for future revisions of the proof format that will help to reduce the verbosity of the certificates and to accelerate the certification and verification process further. Y1 - 2024 U6 - https://doi.org/10.1007/978-3-031-60597-0_20 VL - 14742 ER - TY - JOUR A1 - Prause, Felix A1 - Borndörfer, Ralf A1 - Grimm, Boris A1 - Tesch, Alexander T1 - Approximating rolling stock rotations with integrated predictive maintenance JF - Journal of Rail Transport Planning & Management N2 - We study the solution of the rolling stock rotation problem with predictive maintenance (RSRP-PdM) by an iterative refinement approach that is based on a state-expanded event-graph. In this graph, the states are parameters of a failure distribution, and paths correspond to vehicle rotations with associated health state approximations. An optimal set of paths including maintenance can be computed by solving an integer linear program. Afterwards, the graph is refined and the procedure repeated. An associated linear program gives rise to a lower bound that can be used to determine the solution quality. Computational results for six instances derived from real-world timetables of a German railway company are presented. The results show the effectiveness of the approach and the quality of the solutions. Y1 - 2024 U6 - https://doi.org/10.1016/j.jrtpm.2024.100434 VL - 30 SP - 100434 ER - TY - JOUR A1 - Prause, Felix A1 - Borndörfer, Ralf T1 - An Iterative Refinement Approach for the Rolling Stock Rotation Problem with Predictive Maintenance N2 - The rolling stock rotation problem with predictive maintenance (RSRP-PdM) involves the assignment of trips to a fleet of vehicles with integrated maintenance scheduling based on the predicted failure probability of the vehicles. These probabilities are determined by the health states of the vehicles, which are considered to be random variables distributed by a parameterized family of probability distribution functions. During the operation of the trips, the corresponding parameters get updated. In this article, we present a dual solution approach for RSRP-PdM and generalize a linear programming based lower bound for this problem to families of probability distribution functions with more than one parameter. For this purpose, we define a rounding function that allows for a consistent underestimation of the parameters and model the problem by a state-expanded event-graph in which the possible states are restricted to a discrete set. This induces a flow problem that is solved by an integer linear program. We show that the iterative refinement of the underlying discretization leads to solutions that converge from below to an optimal solution of the original instance. Thus, the linear relaxation of the considered integer linear program results in a lower bound for RSRP-PdM. Finally, we report on the results of computational experiments conducted on a library of test instances. Y1 - 2024 ER - TY - JOUR A1 - Gebhard, Oliver A1 - Hahn-Klimroth, Max A1 - Penschuck, Manuel A1 - Rolvien, Maurice A1 - Scarlett, Jonathan A1 - Tan, Nelvin A1 - Parczyk, Olaf T1 - Near optimal sparsity-constrained group testing: improved bounds JF - IEEE Transactions on Information Theory Y1 - 2022 ER - TY - CHAP A1 - Martínez-Rubio, David A1 - Roux, Christophe A1 - Pokutta, Sebastian T1 - Convergence and trade-offs in riemannian gradient descent and riemannian proximal point T2 - Proceedings of International Conference on Machine Learning Y1 - 2024 ER - TY - JOUR A1 - Hahn-Klimroth, Max A1 - Person, Yury A1 - Parczyk, Olaf T1 - Minimum degree conditions for containing an r-regular r-connected subgraph JF - European Journal of Combinatorics Y1 - 2024 ER - TY - CHAP A1 - Mundinger, Konrad A1 - Pokutta, Sebastian A1 - Spiegel, Christoph A1 - Zimmer, Max T1 - Extending the Continuum of Six-Colorings T2 - Proceedings of Discrete Mathematics Days Y1 - 2024 ER - TY - JOUR A1 - Mundinger, Konrad A1 - Pokutta, Sebastian A1 - Spiegel, Christoph A1 - Zimmer, Max T1 - Extending the Continuum of Six-Colorings JF - Geombinatorics Quarterly Y1 - 2024 ER - TY - JOUR A1 - Parczyk, Olaf A1 - Pokutta, Sebastian A1 - Spiegel, Christoph A1 - Szabó, Tibor T1 - New Ramsey multiplicity bounds and search heuristics JF - Foundations of Computational Mathematics Y1 - 2024 ER - TY - JOUR A1 - Böttcher, Julia A1 - Sgueglia, Amedeo A1 - Skokan, Jozef A1 - Parczyk, Olaf T1 - Triangles in randomly perturbed graphs JF - Combinatorics, Probability and Computing Y1 - 2022 ER - TY - JOUR A1 - Allen, Peter A1 - Pfenninger, Vincent A1 - Parczyk, Olaf T1 - Resilience for tight Hamiltonicity JF - Combinatorial Theory Y1 - 2024 ER - TY - CHAP A1 - Pauls, Jan A1 - Zimmer, Max A1 - Kelly, Una M A1 - Schwartz, Martin A1 - Saatchi, Sassan A1 - Ciais, Philippe A1 - Pokutta, Sebastian A1 - Brandt, Martin A1 - Gieseke, Fabian T1 - Estimating canopy height at scale T2 - Proceedings of International Conference on Machine Learning Y1 - 2024 ER - TY - JOUR A1 - Gupta, Pranshu A1 - Hamann, Fabian A1 - Müyesser, Alp A1 - Sgueglia, Amedeo A1 - Parczyk, Olaf T1 - A general approach to transversal versions of Dirac-type theorems JF - Bulletin of the London Mathematical Society Y1 - 2023 ER - TY - CHAP A1 - Hendrych, Deborah A1 - Besançon, Mathieu A1 - Pokutta, Sebastian T1 - Solving the optimal experiment design problem with mixed-integer convex methods T2 - Proceedings of Symposium on Experimental Algorithms Y1 - 2024 ER - TY - JOUR A1 - Prause, Felix A1 - Borndörfer, Ralf A1 - Grimm, Boris A1 - Tesch, Alexander T1 - Approximating rolling stock rotations with integrated predictive maintenance JF - Journal of Rail Transport Planning & Management Y1 - 2024 ER - TY - JOUR A1 - Barros, Gabriel F. A1 - Cavalar, Bruno P. A1 - Mota, Guilherme O. A1 - Parczyk, Olaf T1 - Anti-Ramsey threshold of cycles for sparse graphs JF - Discrete Applied Mathematics Y1 - 2022 ER - TY - JOUR A1 - Kohayakawa, Yoshiharu A1 - Mota, Guilherme O. A1 - Schnitzer, Jakob A1 - Parczyk, Olaf T1 - Anti-Ramsey threshold of complete graphs for sparse graphs JF - Discrete Mathematics Y1 - 2023 ER - TY - CHAP A1 - Kiem, Aldo A1 - Pokutta, Sebastian A1 - Spiegel, Christoph T1 - The 4-color Ramsey multiplicity of triangles T2 - Proceedings of Discrete Mathematics Days Y1 - 2024 ER - TY - CHAP A1 - Kiem, Aldo A1 - Pokutta, Sebastian A1 - Spiegel, Christoph T1 - Categorification of Flag Algebras T2 - Proceedings of Discrete Mathematics Days Y1 - 2024 ER - TY - CHAP A1 - Ghannam, Mohammed A1 - Mexi, Gioni A1 - Lam, Edward A1 - Gleixner, Ambros T1 - Branch and price for the length-constrained cycle partition problem T2 - Proceedings of INFORMS Optimization Society Conference Y1 - 2024 ER - TY - JOUR A1 - Bolusani, Suresh A1 - Besançon, Mathieu A1 - Gleixner, Ambros A1 - Berthold, Timo A1 - D'Ambrosio, Claudia A1 - Muñoz, Gonzalo A1 - Paat, Joseph A1 - Thomopulos, Dimitri T1 - The MIP workshop 2023 computational competition on reoptimization JF - Mathematical Programming Computation N2 - 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. Y1 - 2024 U6 - https://doi.org/10.1007/s12532-024-00256-w VL - 16 SP - 255 EP - 266 ER - TY - JOUR A1 - Carderera, Alejandro A1 - Besançon, Mathieu A1 - Pokutta, Sebastian T1 - Scalable Frank-Wolfe on generalized self-concordant functions via simple steps JF - SIAM Journal on Optimization Y1 - 2024 U6 - https://doi.org/10.1137/23M1616789 VL - 34 IS - 3 ER - TY - CHAP A1 - Eifler, Leon A1 - Witzig, Jakob A1 - Gleixner, Ambros T1 - Branch and cut for partitioning a graph into a cycle of clusters T2 - Combinatorial Optimization. ISCO 2024 N2 - 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. Y1 - 2024 U6 - https://doi.org/10.1007/978-3-031-60924-4_8 VL - 14594 ER -