In this paper, we examine a mixed integer linear programming (MIP) reformulation for mixed integer bilinear problems where each bilinear term involves the product of a nonnegative integer variable and a nonnegative continuous variable. This reformulation is obtained by first replacing a general integer variable with its binary expansion and then using McCormick envelopes to … Read more
Due to its versatility, copositive optimization receives increasing interest in the Operational Research community, and is a rapidly expanding and fertile field of research. It is a special case of conic optimization, which consists of minimizing a linear function over a cone subject to linear constraints. The diversity of copositive formulations in different domains of … Read more
Copositive optimization is a quickly expanding scientific research domain with wide-spread applications ranging from global nonconvex problems in engineering to NP-hard combinatorial optimization. It falls into the category of conic programming (optimizing a linear functional over a convex cone subject to linear constraints), namely the cone of all completely positive symmetric nxn matrices, and its … Read more
We present a semide nite programming (SDP) approach for the problem of ordering vertices of a layered graph such that the edges of the graph are drawn as vertical as possible. This Multi-Level Vertical Ordering (MLVO) problem is a quadratic ordering problem and conceptually related to the well-studied problem of Multi-Level Crossing Minimization (MLCM). In contrast … Read more
A common structure in convex mixed-integer nonlinear programs is additively separable nonlinear functions consisting of a sum of univariate functions. In the presence of such structures, we propose three improvements to the classical Outer Approximation algorithms that exploit separability. The first improvement is a simple extended formulation. The second a refined outer approximation. Finally, the … Read more
Optimum Experimental Design (OED) problems are optimization problems in which an experimental setting and decisions on when to measure – the so-called sampling design – are to be determined such that a follow-up parameter estimation yields accurate results for model parameters. In this paper we use the interpretation of OED as optimal control problems with … Read more
In the quadratic traveling salesman problem a cost is associated with any three nodes traversed in succession. This structure arises, e.g., if the succession of two edges represents energetic conformations, a change of direction or a possible change of transportation means. In the symmetric case, costs do not depend on the direction of traversal. We … Read more
In the context of convex mixed-integer nonlinear programming (MINLP), we investigate how the outer approximation method and the generalized Benders decomposition method are affected when the respective NLP subproblems are solved inexactly. We show that the cuts in the corresponding master problems can be changed to incorporate the inexact residuals, still rendering equivalence and finiteness … Read more
In the context of convex mixed-integer nonlinear programming (MINLP), we investigate how the outer approximation method and the generalized Benders decomposition method are affected when the respective NLP subproblems are solved inexactly. We show that the cuts in the corresponding master problems can be changed to incorporate the inexact residuals, still rendering equivalence and finiteness … Read more
In this paper, we study 0-1 mixed-integer bilinear covering sets. We derive several families of facet-defining inequalities via sequence-independent lifting techniques. We then show that these sets have polyhedral structures that are similar to those of certain fixed-charge single-node flow sets. As a result, we obtain new facet-defining inequalities for these sets that generalize well-known … Read more