Tobias Achterberg
Tobias Achterberg has a total of 22 co-authors. Here are the top co-authors by number of shared publications:
- Ambros Gleixner
Zuse Institute Berlin Takustr. 7 14195 Berlin Germany
3 shared publications - Ksenia Bestuzheva
Zuse Institute Berlin Germany
2 shared publications Ambros Gleixner
1 shared publication- Derya Ozyurt
The Mathworks, Inc., Natick, USA
1 shared publication Dieter Weninger
University Erlangen-Nürnberg, 91054 Erlangen, Germany
1 shared publication- Domenico Salvagnin
University of Padova
1 shared publication
Latest Publications
- 16 July 2024
- Published by Springer Nature in Mathematical Programming
- Vol. 210 (1-2) , 47-74
Efficient separation of RLT cuts for implicit and explicit bilinear terms
- 16 July 2024
- Published by Springer Nature in Mathematical Programming
- Vol. 210 (1-2) , 47-74
Efficient separation of RLT cuts for implicit and explicit bilinear terms
- 22 May 2023
- Published by Springer Nature
- p. 14-28
Efficient Separation of RLT Cuts for Implicit and Explicit Bilinear Products
- 22 May 2023
- Published by Springer Nature
- p. 14-28
Efficient Separation of RLT Cuts for Implicit and Explicit Bilinear Products
- Open Access
Efficient Separation of RLT Cuts for Implicit and Explicit Bilinear Products
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.
Open AccessEfficient Separation of RLT Cuts for Implicit and Explicit Bilinear Products
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.
- Top Cited PapersOpen Access
- 7 January 2021
- Published by Springer Nature in Mathematical Programming Computation
- Vol. 13 (3) , 443-490
MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library
We report on the selection process leading to the sixth version of the Mixed Integer Programming Library, MIPLIB 2017. Selected from an initial pool of 5721 instances, the new MIPLIB 2017 collection consists of 1065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, these sets were compiled using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encode requirements on diversity and balancedness with respect to instance features and performance data.
- 7 January 2021
- Published by Springer Nature in Mathematical Programming Computation
- Vol. 13 (3) , 443-490
Top Cited PapersOpen AccessMIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library
We report on the selection process leading to the sixth version of the Mixed Integer Programming Library, MIPLIB 2017. Selected from an initial pool of 5721 instances, the new MIPLIB 2017 collection consists of 1065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, these sets were compiled using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encode requirements on diversity and balancedness with respect to instance features and performance data.
- Top Cited Papers
- 1 April 2020
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 32 (2) , 473-506
Presolve Reductions in Mixed Integer Programming
Mixed integer programming has become a very powerful tool for modeling and solving real-world planning and scheduling problems, with the breadth of applications appearing to be almost unlimited. A critical component in the solution of these mixed integer programs is a set of routines commonly referred to as presolve. Presolve can be viewed as a collection of preprocessing techniques that reduce the size of and, more importantly, improve the “strength” of the given model formulation, that is, the degree to which the constraints of the formulation accurately describe the underlying polyhedron of integer-feasible solutions. As our computational results will show, presolve is a key factor in the speed with which we can solve mixed integer programs and is often the difference between a model being intractable and solvable, in some cases easily solvable. In this paper we describe the presolve functionality in the Gurobi commercial mixed integer programming code. This includes an overview, or taxonomy of the different methods that are employed, as well as more-detailed descriptions of several of the techniques, with some of them appearing, to our knowledge, for the first time in the literature.
- 1 April 2020
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 32 (2) , 473-506
Top Cited PapersPresolve Reductions in Mixed Integer Programming
Mixed integer programming has become a very powerful tool for modeling and solving real-world planning and scheduling problems, with the breadth of applications appearing to be almost unlimited. A critical component in the solution of these mixed integer programs is a set of routines commonly referred to as presolve. Presolve can be viewed as a collection of preprocessing techniques that reduce the size of and, more importantly, improve the “strength” of the given model formulation, that is, the degree to which the constraints of the formulation accurately describe the underlying polyhedron of integer-feasible solutions. As our computational results will show, presolve is a key factor in the speed with which we can solve mixed integer programs and is often the difference between a model being intractable and solvable, in some cases easily solvable. In this paper we describe the presolve functionality in the Gurobi commercial mixed integer programming code. This includes an overview, or taxonomy of the different methods that are employed, as well as more-detailed descriptions of several of the techniques, with some of them appearing, to our knowledge, for the first time in the literature.