Every optimization problem has a corresponding verification problem that checks whether a given optimal solution is in fact optimal. In the literature, there are a lot of such ways to verify optimality for a given solution, for example, the branch-and-bound tree. To simplify this task, optimality certificates were introduced for convex mixed-integer nonlinear programs, and it was shown that the sizes of the certificates are bounded in terms of the number of integer variables. We introduce an algorithm to compute the certificates and conduct computational experiments. Through the experiments, we show that the optimality certificates can be surprisingly small. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This work was supported by the Deutsche Forschungsgemeinschaft [CRC 154 Subproject A05, CRC 154 Subproject B07, and SFB Transregio 154], the Bundesministerium für Wirtschaft und Energie. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0099 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0099 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

We consider dynamic gas transport optimization problems, which lead to large-scale and nonconvex mixed-integer nonlinear optimization problems (MINLPs) on graphs. Usually, the resulting instances are too challenging to be solved by state-of-the-art MINLP solvers. In this paper, we use graph decompositions to obtain multiple optimization problems on smaller blocks, which can be solved in parallel and may result in simpler classes of optimization problems because not every block necessarily contains mixed-integer or nonlinear aspects. For achieving feasibility at the interfaces of the several blocks, we employ a tailored consensus-based penalty alternating direction method. Our numerical results show that such decomposition techniques can outperform the baseline approach of just solving the overall MINLP from scratch. However, a complete answer to the question of how to decompose MINLPs on graphs in dependence of the given model is still an open topic for future research. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by Deutsche Forschungsgemeinschaft [Grant TRR 154].

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 .

Abstract We propose an exact global solution method for bilevel mixed-integer optimization problems with lower-level integer variables and including nonlinear terms such as, e.g., products of upper-level and lower-level variables. Problems of this type are extremely challenging as a single-level reformulation suitable for off-the-shelf solvers is not available in general. In order to solve these problems to global optimality, we enhance an approximative projection-based algorithm for mixed-integer linear bilevel programming problems from the literature to become exact under one additional assumption. This assumption still allows for discrete and continuous leader and follower variables on both levels, but forbids continuous upper-level variables to appear in lower-level constraints and thus ensures that a bilevel optimum is attained. In addition, we extend our exact algorithm to make it applicable to a wider problem class. This setting allows nonlinear constraints and objective functions on both levels under certain assumptions, but still requires that the lower-level problem is convex in its continuous variables. We also discuss computational experiments on modified library instances.

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.