KBKsenia Bestuzheva

Ksenia Bestuzheva

*This is an algorithmically generated author record based on publicly available information.

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


Ksenia Bestuzheva has a total of 56 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Sparsity-driven Aggregation of Mixed Integer Programs

    by Liding Xu, Gioni Mexi, Ksenia Bestuzheva

    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

    by Gioni Mexi, Dominik Kamp, Yuji Shinano, Shanwen Pu, Alexander Hoen, Ksenia Bestuzheva, Christopher Hojny, Matthias Walter, Marc E. Pfetsch, Sebastian Pokutta, et al.

    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.

  • Efficient separation of RLT cuts for implicit and explicit bilinear terms

    by Ksenia Bestuzheva, Ambros Gleixner, Tobias Achterberg


  • Top Cited Papers
    Open Access

    Global optimization of mixed-integer nonlinear programs with SCIP 8

    by Ksenia Bestuzheva, Antonia Chmiela, Benjamin Müller, Felipe Serrano, Stefan Vigerske, Fabian Wegscheider

    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

    A computational study of perspective cuts

    by Ksenia Bestuzheva, Ambros Gleixner, Stefan Vigerske


  • Top Cited Papers
    Open Access

    Enabling Research through the SCIP Optimization Suite 8.0

    by Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, et al.

    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 .


  • Open Access

    Strengthening SONC Relaxations with Constraints Derived from Variable Bounds

    by Ksenia Bestuzheva, Helena Völker, Ambros Gleixner

    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

    by Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, et al.

    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

    by Ksenia Bestuzheva, Antonia Chmiela, Benjamin Müller, Felipe Serrano, Stefan Vigerske, Fabian Wegscheider

    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.