Ksenia Bestuzheva

Zuse Institute Berlin

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Trends

Author Order

Document Type

Co-Authors

Ambros Gleixner

Zuse Institute Berlin

Stefan Vigerske

Zuse Institute Berlin

Thorsten Koch

Zuse Institute Berlin

Christopher Hojny

Eindhoven University of Technology

Yuji Shinano

Zuse Institute Berlin

Antonia Chmiela

Zuse Institute Berlin

Marc E. Pfetsch

Technical University of Darmstadt

Fabian Wegscheider

Zuse Institute Berlin

Benjamin Müller

Fraunhofer Institute for Building Physics

Leon Eifler

Zuse Institute Berlin

Cooperative Institutions

Zuse Institute Berlin

Technische Universität Berlin

Technical University of Denmark

Friedrich-Alexander-Universität Erlangen-Nürnberg

RWTH Aachen University

Osys Technology

Technical University of Darmstadt

Center for Discrete Mathematics and Theoretical Computer Science

John Wiley & Sons (United States)

Universität Trier

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Field

Enabling Research through the SCIP Optimization Suite 8.0

ACM Transactions on Mathematical Software (2023)

Ksenia Bestuzheva Mathieu Besançon Wei‐Kun Chen Antonia Chmiela Tim Donkiewicz

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 .

Presentation (obstetrics)

10.1145/3585516

Cite

Citations (33)

Strengthening SONC Relaxations with Constraints Derived from Variable Bounds

arXiv (Cornell University) (2022)

Ksenia Bestuzheva Ambros Gleixner Helena Völker

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.

10.48550/arxiv.2211.05518

Cite

Citations (0)

The SCIP Optimization Suite 7.0

Gerald Gamrath Daniel Anderson Ksenia Bestuzheva Wei‐Kun Chen Leon Eifler

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming frame- work SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies mixed-integer linear op- timization problems and can be used stand-alone or integrated into SCIP via a presolver plugin. SCIP 7.0 provides additional support for decomposition algorithms. Besides im- provements in the Benders’ decomposition solver of SCIP, user-defined decomposition structures can be read, which are used by the automated Benders’ decomposition solver and two primal heuristics. Additionally, SCIP 7.0 comes with a tree size estimation that is used to predict the completion of the overall solving process and potentially trigger restarts. Moreover, substantial performance improvements of the MIP core were achieved by new developments in presolving, primal heuristics, branching rules, conflict analysis, and symmetry handling. Last, not least, the report presents updates to other components and extensions of the SCIP Optimization Suite, in particular, the LP solver SoPlex and the mixed-integer semidefinite programming solver SCIP-SDP.

Solver

Heuristics

Source

Cite

Citations (164)

A Computational Study of Perspective Cuts

arXiv (Cornell University) (2021)

Ksenia Bestuzheva Ambros Gleixner Stefan Vigerske

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.

Solver

Branch and cut

Linear programming relaxation

Tree (set theory)

Benchmark (surveying)

10.48550/arxiv.2103.09573

Cite

Citations (0)

State-of-the-art Methods for Pseudo-Boolean Solving with SCIP

arXiv (Cornell University) (2025)

Gioni Mexi Dominik Kamp Yuji Shinano Shanwen Pu Alexander Hoen

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.

10.48550/arxiv.2501.03390

Cite

Citations (0)

The SCIP Optimization Suite 9.0

arXiv (Cornell University) (2024)

Suresh Bolusani Mathieu Besançon Ksenia Bestuzheva Antonia Chmiela João Dionísio

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming (CIP) 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.

Solver

Heuristics

Python

10.48550/arxiv.2402.17702

Cite

Citations (90)

Invex optimization revisited

Journal of Global Optimization (2018)

Ksenia Bestuzheva Hassan Hijazi

Karush–Kuhn–Tucker conditions

Global Optimization

Interior point method

10.1007/s10898-018-0650-1

Cite

Citations (6)

Global optimization of mixed-integer nonlinear programs with SCIP 8

Journal of Global Optimization (2023)

Ksenia Bestuzheva Antonia Chmiela Benjamin Müller Felipe Serrano Stefan Vigerske

Abstract 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.

Global Optimization

Benchmarking

10.1007/s10898-023-01345-1

Cite

Citations (17)

The SCIP Optimization Suite 8.0

arXiv (Cornell University) (2021)

Ksenia Bestuzheva Mathieu Besançon Wei‐Kun Chen Antonia Chmiela Tim Donkiewicz

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.

Heuristics

Plug-in

10.48550/arxiv.2112.08872

Cite

Citations (10)

SCIP8: rethinking nonlinear constraint representation and recent progress

HAL (Le Centre pour la Communication Scientifique Directe) (2022)

Mathieu Besançon Ksenia Bestuzheva Wei‐Kun Chen Antonia Chmiela Tim Donkiewicz

Representation

Source

Cite

Citations (0)