convex minlp

Automatic Reformulations for Convex Mixed-Integer Nonlinear Optimization: Perspective and Separability

  • Meenarli Sharma
  • Ashutosh Mahajan
    • Categories (Mixed) Integer Nonlinear Programming, Optimization Software and Modeling Systems Tags , , , ,

    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 disjunctive cut strengthening technique for convex MINLP

  • Jan Kronqvist
  • Ruth Misener
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , ,

    Generating polyhedral outer approximations and solving mixed-integer linear relaxations remains one of the main approaches for solving convex mixed-integer nonlinear programming (MINLP) problems. There are several algorithms based on this concept, and the efficiency is greatly affected by the tightness of the outer approximation. In this paper, we present a new framework for strengthening cutting … Read more

    Linearization and Parallelization Schemes for Convex Mixed-Integer Nonlinear Optimization

  • Meenarli Sharma
  • Prashant Palkar
  • Ashutosh Mahajan
    • Categories (Mixed) Integer Nonlinear Programming, Parallel Algorithms Tags , , , ,

    We develop and test linearization and parallelization schemes for convex mixed-integer nonlinear programming. Several linearization approaches are proposed for LP/NLP based branch-and-bound. Some of these approaches strengthen the linear approximation to nonlinear constraints at the root node and some at the other branch-and-bound nodes. Two of the techniques are specifically applicable to commonly found univariate … Read more

    On the Relation between the Extended Supporting Hyperplane Algorithm and Kelley’s Cutting Plane Algorithm

  • Ambros Gleixner
  • Felipe Serrano
  • Robert Schwarz
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization Tags , ,

    Recently, Kronqvist et al.rediscovered the supporting hyperplane algorithm of Veinott and demonstrated its computational benefits for solving convex mixed-integer nonlinear programs. In this paper we derive the algorithm from a geometric point of view. This enables us to show that the supporting hyperplane algorithm is equivalent to Kelley’s cutting plane algorithm applied to a particular … Read more

    Outer Approximation With Conic Certificates For Mixed-Integer Convex Problems

  • Chris Coey
  • Miles Lubin
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming, Optimization Software Benchmark Tags , ,

    A mixed-integer convex (MI-convex) optimization problem is one that becomes convex when all integrality constraints are relaxed. We present a branch-and-bound LP outer approximation algorithm for an MI-convex problem transformed to MI-conic form. The polyhedral relaxations are refined with K* cuts} derived from conic certificates for continuous primal-dual conic subproblems. Under the assumption that all … Read more

    A Center-Cut Algorithm for Quickly Obtaining Feasible Solutions and Solving Convex MINLP Problems

  • David E. Bernal Neira
  • Andreas Lundell
  • Tapio Westerlund
  • Jan Kronqvist
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , ,

    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

    Using Regularization and Second Order Information in Outer Approximation for Convex MINLP

  • David E. Bernal Neira
  • Ignacio E. Grossmann
  • Jan Kronqvist
    • Categories (Mixed) Integer Nonlinear Programming Tags , ,

    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

    Orbital shrinking

  • Matteo Fischetti
  • Leo Liberti
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , , , ,

    Symmetry plays an important role in optimization. The usual approach to cope with symmetry in discrete optimization is to try to eliminate it by introducing artificial symmetry-breaking conditions into the problem, and/or by using an ad-hoc search strategy. In this paper we argue that symmetry is instead a beneficial feature that we should preserve and … Read more