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 - 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 - 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 - 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 - 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 - 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 - Abbas, Amira A1 - Ambainis, Andris A1 - Augustino, Brandon A1 - Bärtschi, Andreas A1 - Buhrman, Harry A1 - Coffrin, Carleton A1 - Cortiana, Giorgio A1 - Dunjko, Vedran A1 - Egger, Daniel J. A1 - Elmegreen, Bruce G. A1 - Franco, Nicola A1 - Fratini, Filippo A1 - Fuller, Bryce A1 - Gacon, Julien A1 - Gonciulea, Constantin A1 - Gribling, Sander A1 - Gupta, Swati A1 - Hadfield, Stuart A1 - Heese, Raoul A1 - Kircher, Gerhard A1 - Kleinert, Thomas A1 - Koch, Thorsten A1 - Korpas, Georgios A1 - Lenk, Steve A1 - Marecek, Jakub A1 - Markov, Vanio A1 - Mazzola, Guglielmo A1 - Mensa, Stefano A1 - Mohseni, Naeimeh A1 - Nannicini, Giacomo A1 - O’Meara, Corey A1 - Tapia, Elena Peña A1 - Pokutta, Sebastian A1 - Proissl, Manuel A1 - Rebentrost, Patrick A1 - Sahin, Emre A1 - Symons, Benjamin C. B. A1 - Tornow, Sabine A1 - Valls, Víctor A1 - Woerner, Stefan A1 - Wolf-Bauwens, Mira L. A1 - Yard, Jon A1 - Yarkoni, Sheir A1 - Zechiel, Dirk A1 - Zhuk, Sergiy A1 - Zoufal, Christa T1 - Challenges and opportunities in quantum optimization JF - Nature Reviews Physics Y1 - 2024 U6 - https://doi.org/10.1038/s42254-024-00770-9 SN - 2522-5820 VL - 6 SP - 718 EP - 735 PB - Springer Science and Business Media LLC 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 - 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 - Š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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 -