Solving mixed-integer nonlinear programs (MINLPs) is hard in theory and practice. Decomposing the nonlinear and the integer part seems promising from a computational point of view. In general, however, no bounds on the objective value gap can be guaranteed and iterative procedures with potentially many subproblems are necessary. The situation is different for mixed-integer optimal … Read more
We consider the combination of a network design and graph partitioning model in a multilevel framework for determining the optimal network expansion and the optimal zonal configuration of zonal pricing electricity markets, which is an extension of the model discussed in [25] that does not include a network design problem. The two classical discrete optimization … Read more
Here we present a center-cut algorithm for convex mixed-integer nonlinear programming (MINLP) that can either be used as a primal heuristic or as a deterministic solution technique. Like many other algorithms for convex MINLP, the center-cut algorithm constructs a linear approximation of the original problem. The main idea of the algorithm is to use the … Read more
We apply the basic principles underlying combinatorial integral approximation methods for mixed-integer optimal control with ordinary differential equations in general, and the sum-up rounding algorithm specifically, to optimization problems with partial differential equation (PDE) constraints. By doing so, we identify two possible generalizations that are applicable to problems involving PDE constraints with mesh-dependent integer variables, … Read more
We study quadratic optimization with semi-continuous variables and an M-matrix, i.e., PSD with non-positive off-diagonal entries. This structure arises in image segmentation, portfolio optimization, as well as a substructure of general quadratic optimization problems. We prove, under mild assumptions, that the minimization problem is solvable in polynomial time by showing its equivalence to a submodular … Read more
In this paper, we present two new methods for solving convex mixed-integer nonlinear programming problems based on the outer approximation method. The first method is inspired by the level method and uses a regularization technique to reduce the step size when choosing new integer combinations. The second method combines ideas from both the level method … Read more
We consider the problem of characterizing the convex hull of the graph of a bilinear function $f$ on the $n$-dimensional unit cube $[0,1]^n$. Extended formulations for this convex hull are obtained by taking subsets of the facets of the Boolean Quadric Polytope (BQP). Extending existing results, we propose the systematic study of properties of $f$ … Read more
This article describes new features and enhanced algorithms made available in version 5.0 of the SCIP Optimization Suite. In its central component, the constraint integer programming solver SCIP, remarkable performance improvements have been achieved for solving mixed-integer linear and nonlinear programs. On MIPs, SCIP 5.0 is about 41 % faster than SCIP 4.0 and over … Read more
We develop a mixed-integer optimal control model with partial differential equation (PDE) constraints for gas transport networks, designed for controlling extreme state transitions, such as flow reversals. Our model shows how to combine binary compressor controls with PDE flow models. We model the flow of gas using a variant of the Euler equations, which we … Read more
We consider a bound for the maximum-entropy sampling problem (MESP) that is based on solving a max-det problem over a relaxation of the Boolean Quadric Polytope (BQP). This approach to MESP was first suggested by Christoph Helmberg over 15 years ago, but has apparently never been further elaborated or computationally investigated. We find that the … Read more