(Mixed) Integer Nonlinear Programming

Think co(mpletely )positive ! Matrix properties, examples and a clustered bibliography on copositive optimization

  • Immanuel M. Bomze
  • Werner Schachinger
  • Gabriele Uchida
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Linear, Cone and Semidefinite Programming

    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

    Exact Approaches to Multi-Level Vertical Orderings

  • Markus Chimani
  • Philipp Hungerländer
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , ,

    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

    An Outer-Inner Approximation for separable MINLPs

  • Pierre Bonami
  • Hassan L. Hijazi
  • Adam Ouorou
    • Categories (Mixed) Integer Nonlinear Programming Tags ,

    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

    Sampling Decisions in Optimum Experimental Design in the Light of Pontryagin’s Maximum Principle

  • Sebastian Sager
    • Categories (Mixed) Integer Nonlinear Programming, Systems governed by Differential Equations Optimization Tags , ,

    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

    The Symmetric Quadratic Traveling Salesman Problem

  • Anja Fischer
  • Christoph Helmberg
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Polyhedra Tags , , ,

    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

    Inexact solution of NLP subproblems in MINLP

  • L. Min
  • Luis Nunes Vicente
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , ,

    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

    Inexact solution of NLP subproblems in MINLP

  • L. Min
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , ,

    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

    Lifted Inequalities for 0−1 Mixed-Integer Bilinear Covering Sets

  • Kwanghun Chung
  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Global Optimization Theory Tags , ,

    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

    Bound reduction using pairs of linear inequalities

  • Pietro Belotti
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Constrained Nonlinear Optimization Tags , , ,

    We describe a procedure to reduce variable bounds in Mixed Integer Nonlinear Programming (MINLP) as well as Mixed Integer Linear Programming (MILP) problems. The procedure works by combining pairs of inequalities of a linear programming (LP) relaxation of the problem. This bound reduction technique extends the implied bounds procedure used in MINLP and MILP and … Read more

    A compact variant of the QCR method for quadratically constrained quadratic 0-1 programs

  • Laura Galli
  • Adam N. Letchford
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming, Semi-definite Programming

    Quadratic Convex Reformulation (QCR) is a technique that was originally proposed for quadratic 0-1 programs, and then extended to various other problems. It is used to convert non-convex instances into convex ones, in such a way that the bound obtained by solving the continuous relaxation of the reformulated instance is as strong as possible. In … Read more