15 June 2023 in ACM Transactions on Mathematical Software
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 .
14 December 2023 in Journal of Global Optimization
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.
1 July 2020 in INFORMS Journal on Computing
This paper studies mixed-integer nonlinear programs featuring disjunctive constraints and trigonometric functions and presents a strengthened version of the convex quadratic relaxation of the optimal transmission switching problem. We first characterize the convex hull of univariate quadratic on/off constraints in the space of original variables using perspective functions. We then introduce new tight quadratic relaxations for trigonometric functions featuring variables with asymmetrical bounds. These results are used to further tighten recent convex relaxations introduced for the optimal transmission switching problem in power systems. Using the proposed improvements, along with bound propagation, on 23 medium-sized test cases in the PGLib benchmark library with a relaxation gap of more than 1%, we reduce the gap to less than 1% on five instances. The tightened model has promising computational results when compared with state-of-the-art formulations.
21 August 2023 in Mathematical Programming Computation
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.
12 April 2018 in Journal of Global Optimization
16 July 2024 in Mathematical Programming