Linear programming (LP) relaxations are widely employed in exact solution methods for multilinear programs (MLP). One example is the family of Recursive McCormick Linearization (RML) strategies, where bilinear products are substituted for artificial variables, which deliver a relaxation of the original problem when introduced together with concave and convex envelopes. In this article, we introduce … Read more
We propose an algorithm for solving bilevel problems with mixed-integer convex-quadratic upper level as well as convex-quadratic and continuous lower level. The method is based on a classic branch-and-bound procedure, where branching is performed on the integer constraints and on the complementarity constraints resulting from the KKT reformulation of the lower-level problem. However, instead of … Read more
In this paper, a new method for computing an enclosure of the nondominated set of multiobjective mixed-integer problems without any convexity requirements is presented. In fact, our criterion space method makes use of piecewise linear relaxations in order to bypass the nonconvexity of the original problem. The method chooses adaptively which level of relaxation is … Read more
In this paper, we consider piecewise polyhedral relaxations (PPRs) of multilinear optimization problems over axis-parallel hyper-rectangular partitions of their domain. We improve formulations for PPRs by linking components that are commonly modeled independently in the literature. Numerical experiments with ALPINE, an open-source software for global optimization that relies on piecewise approximations of functions, show that … Read more
For the fast approximate solution of Mixed-Integer Non-Linear Programs (MINLPs) arising in the context of Mixed-Integer Optimal Control Problems (MIOCPs) a decomposition algorithm exists that solves a sequence of three comparatively less hard subproblems to determine an approximate MINLP solution. In this work, we propose a problem formulation for the second algorithm stage that is … Read more
Tight reformulations of combinatorial optimization problems like Convex Mixed-Integer Nonlinear Programs (MINLPs) enable one to solve these problems faster by obtaining tight bounds on the optimal value. We consider two techniques for reformulation: perspective reformulation and separability detection. We develop routines for the automatic detection of problem structures suitable for these reformulations and implement new … Read more
A central goal for multi-objective optimization problems is to compute their nondominated sets. In most cases these sets consist of infinitely many points and it is not a practical approach to compute them exactly. One solution to overcome this problem is to compute an enclosure, a special kind of coverage, of the nondominated set. One … Read more
We present a branch-and-prune procedure for discrete Nash equilibrium problems with a convex description of each player’s strategy set. The derived pruning criterion does not require player convexity, but only strict convexity of some player’s objective function in a single variable. If satisfied, it prunes choices for this variable by stating activity of certain constraints. … Read more
We investigate the optimal piecewise linear interpolation of the bivariate product xy over rectangular domains. More precisely, our aim is to minimize the number of simplices in the triangulation underlying the interpolation, while respecting a prescribed approximation error. First, we show how to construct optimal triangulations consisting of up to five simplices. Using these as … Read more
In this paper, we establish a polynomial equivalence between tree ensemble optimization and optimization of multilinear functions over the Cartesian product of simplices. We use this insight to derive new formulations for tree ensemble optimization problems and to obtain new convex hull results for multilinear polytopes. A computational experiment on multi-commodity transportation problems with costs … Read more