Ksenia Bestuzheva
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Ksenia Bestuzheva has a total of 56 co-authors. Here are the top co-authors by number of shared publications:
- Ambros Gleixner
Zuse Institute Berlin Takustr. 7 14195 Berlin Germany
6 shared publications - Stefan Vigerske
GAMS Software GmbH, c/o Zuse Institute Berlin, Berlin, Germany
5 shared publications - Antonia Chmiela
Zuse Institute Berlin
4 shared publications - Benjamin Müller
Zuse Institute Berlin
4 shared publications - Felipe Serrano
COPT GmbH, Berlin, Germany
4 shared publications - Alexander Hoen
Zuse Institute Berlin, 14195 Berlin, Germany
3 shared publications
Latest Publications
- Open Access
Sparsity-driven Aggregation of Mixed Integer Programs
Cutting planes are crucial for the performance of branch-and-cut algorithms for solving mixed-integer programming (MIP) problems, and linear row aggregation has been successfully applied to better leverage the potential of several major families of MIP cutting planes. This paper formulates the problem of finding good quality aggregations as an $\ell_0$-norm minimization problem and employs a combination of the lasso method and iterative reweighting to efficiently find sparse solutions corresponding to good aggregations. A comparative analysis of the proposed algorithm and the state-of-the-art greedy heuristic approach is presented, showing that the greedy heuristic implements a stepwise selection algorithm for the $\ell_0$-norm minimization problem. Further, we present an example where our approach succeeds, whereas the standard heuristic fails to find an aggregation with desired properties. The algorithm is implemented within the constraint integer programming solver SCIP, and computational experiments on the MIPLIB 2017 benchmark show that although the algorithm leads to slowdowns on relatively ``easier'' instances, our aggregation approach decreases the mean running time on a subset of challenging instances and leads to smaller branch-and-bound trees.
Open AccessSparsity-driven Aggregation of Mixed Integer Programs
Cutting planes are crucial for the performance of branch-and-cut algorithms for solving mixed-integer programming (MIP) problems, and linear row aggregation has been successfully applied to better leverage the potential of several major families of MIP cutting planes. This paper formulates the problem of finding good quality aggregations as an $\ell_0$-norm minimization problem and employs a combination of the lasso method and iterative reweighting to efficiently find sparse solutions corresponding to good aggregations. A comparative analysis of the proposed algorithm and the state-of-the-art greedy heuristic approach is presented, showing that the greedy heuristic implements a stepwise selection algorithm for the $\ell_0$-norm minimization problem. Further, we present an example where our approach succeeds, whereas the standard heuristic fails to find an aggregation with desired properties. The algorithm is implemented within the constraint integer programming solver SCIP, and computational experiments on the MIPLIB 2017 benchmark show that although the algorithm leads to slowdowns on relatively ``easier'' instances, our aggregation approach decreases the mean running time on a subset of challenging instances and leads to smaller branch-and-bound trees.
- Open Access
State-of-the-art Methods for Pseudo-Boolean Solving with SCIP
The Pseudo-Boolean problem deals with linear or polynomial constraints with integer coefficients over Boolean variables. The objective lies in optimizing a linear objective function, or finding a feasible solution, or finding a solution that satisfies as many constraints as possible. In the 2024 Pseudo-Boolean competition, solvers incorporating the SCIP framework won five out of six categories it was competing in. From a total of 1,207 instances, SCIP successfully solved 759, while its parallel version FiberSCIP solved 776. Based on the results from the competition, we further enhanced SCIP's Pseudo-Boolean capabilities. This article discusses the results and presents the winning algorithmic ideas.
Open AccessState-of-the-art Methods for Pseudo-Boolean Solving with SCIP
The Pseudo-Boolean problem deals with linear or polynomial constraints with integer coefficients over Boolean variables. The objective lies in optimizing a linear objective function, or finding a feasible solution, or finding a solution that satisfies as many constraints as possible. In the 2024 Pseudo-Boolean competition, solvers incorporating the SCIP framework won five out of six categories it was competing in. From a total of 1,207 instances, SCIP successfully solved 759, while its parallel version FiberSCIP solved 776. Based on the results from the competition, we further enhanced SCIP's Pseudo-Boolean capabilities. This article discusses the results and presents the winning algorithmic ideas.
- 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
- Top Cited PapersOpen Access
- 14 December 2023
- Published by Springer Nature in Journal of Global Optimization
- Vol. 91 (2) , 287-310
Global optimization of mixed-integer nonlinear programs with SCIP 8
For over 10 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.
- 14 December 2023
- Published by Springer Nature in Journal of Global Optimization
- Vol. 91 (2) , 287-310
Top Cited PapersOpen AccessGlobal optimization of mixed-integer nonlinear programs with SCIP 8
For over 10 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.
- Open Access
- 21 August 2023
- Published by Springer Nature in Mathematical Programming Computation
- Vol. 15 (4) , 703-731
A computational study of perspective cuts
- 21 August 2023
- Published by Springer Nature in Mathematical Programming Computation
- Vol. 15 (4) , 703-731
Open AccessA computational study of perspective cuts
- Top Cited PapersOpen Access
- 15 June 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 49 (2) , 1-21
Enabling Research through the SCIP Optimization Suite 8.0
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 .
- 15 June 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 49 (2) , 1-21
Top Cited PapersOpen AccessEnabling Research through the SCIP Optimization Suite 8.0
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 .
- 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
Strengthening SONC Relaxations with Constraints Derived from Variable Bounds
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.
Open AccessStrengthening SONC Relaxations with Constraints Derived from Variable Bounds
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.
- Open Access
Enabling Research through the SCIP Optimization Suite 8.0
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 paper 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. Further, the paper 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.
Open AccessEnabling Research through the SCIP Optimization Suite 8.0
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 paper 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. Further, the paper 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.
- Open Access
Global Optimization of Mixed-Integer Nonlinear Programs with SCIP 8
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.
Open AccessGlobal Optimization of Mixed-Integer Nonlinear Programs with SCIP 8
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.