We consider the NP-hard problem of minimizing a separable concave quadratic function over the integral points in a polyhedron, and we denote by D the largest absolute value of the subdeterminants of the constraint matrix. In this paper we give an algorithm that finds an epsilon-approximate solution for this problem by solving a number of … Read more
Partial outer convexification is a relaxation technique for MIOCPs being constrained by time-dependent differential equations. Sum-Up-Rounding algorithms allow to approximate feasible points of the relaxed, convexified continuous problem with binary ones that are feasible up to an arbitrarily small $\delta > 0$. We show that this approximation property holds for ODEs and semilinear PDEs under … Read more
Approximation algorithms like sum-up rounding that allow to compute integer-valued approximations of the continuous controls in a weak$^*$ sense have attracted interest recently. They allow to approximate (optimal) feasible solutions of continuous relaxations of mixed-integer control problems (MIOCPs) with integer controls arbitrarily close. To this end, they use compactness properties of the underlying state equation, … Read more
In addition to sparsity, practitioners of statistics and machine learning often wish to promote additional structures in their variable selection process to incorporate prior knowledge. Borrowing the modeling power of linear systems with binary variables, many of such structures can be faithfully modeled as so-called affine sparsity constraints (ASC). In this note we study conditions … Read more
As an alternative to traditional integer programming (IP), decision diagrams (DDs) provide a new solution technology for discrete problems based on their combinatorial structure and dynamic programming representation. While the literature mainly focuses on the competitive aspects of DDs as a stand-alone solver, we investigate their complementary role by studying IP techniques that can be … Read more
This paper studies mathematical programming formulations for solving optimization problems with piecewise polynomial (PWP) constraint functions. We elaborate on suitable polynomial bases as a means of efficiently representing PWPs in mathematical programs, comparing and drawing connections between the monomial basis, the Bernstein basis, and B-splines. The theory is presented for both continuous and semi-continuous PWPs. … Read more
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