outer approximation

A graphical framework for global optimization of mixed-integer nonlinear programs

  • Danial Davarnia
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Applications, Global Optimization Theory Tags , , , , ,

    While mixed-integer linear programming and convex programming solvers have advanced significantly over the past several decades, solution technologies for general mixed-integer nonlinear programs (MINLPs) have yet to reach the same level of maturity. Various problem structures across different application domains remain challenging to model and solve using modern global solvers, primarily due to the lack … Read more

    A Subgradient Projection Method with Outer Approximation for Solving Semidefinite Programming Problems

  • Nagisa Sugishita
  • Miguel F. Anjos
    • Categories Convex Optimization, Semi-definite Programming Tags , ,

    We explore the combination of subgradient projection with outer approximation to solve semidefinite programming problems. We compare several ways to construct outer approximations using the problem structure. The resulting approach enjoys the strengths of both subgradient projection and outer approximation methods. Preliminary computational results on the semidefinite programming relaxations of graph partitioning and max-cut show … Read more

    A Sequential Benders-based Mixed-Integer Quadratic Programming Algorithm

  • Andrea Ghezzi
  • Wim Van Roy
  • Sebastian Sager
  • Moritz Diehl
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Optimization Software Benchmark Tags , , , ,

    For continuous decision spaces, nonlinear programs (NLPs) can be efficiently solved via sequential quadratic programming (SQP) and, more generally, sequential convex programming (SCP). These algorithms linearize only the nonlinear equality constraints and keep the outer convex structure of the problem intact, such as (conic) inequality constraints or convex objective terms. The aim of the presented … Read more

    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

    Projective Cutting Planes for General QP with Indicator Constraints

  • Ulf Friedrich
  • Dennis Kreber
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , ,

    General quadratic optimization problems with linear constraints and additional indicator constraints on the variables are studied. Based on the well-known perspective reformulation for mixed-integer quadratic optimization problems, projective cuts are introduced as new valid inequalities for the general problem. The key idea behind the theory of these cutting planes is the projection of the continuous … 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

    Outer Approximation for Global Optimization of Mixed-Integer Quadratic Bilevel Problems

  • Veronika Grimm
  • Thomas Kleinert
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , , ,

    Bilevel optimization problems have received a lot of attention in the last years and decades. Besides numerous theoretical developments there also evolved novel solution algorithms for mixed-integer linear bilevel problems and the most recent algorithms use branch-and-cut techniques from mixed-integer programming that are especially tailored for the bilevel context. In this paper, we consider MIQP-QP … Read more

    Sample Average Approximation for Stochastic Nonconvex Mixed Integer Nonlinear Programming via Outer Approximation

  • David E. Bernal Neira
  • Kevin C Furman
  • Ignacio E. Grossmann
  • Can Li
    • Categories (Mixed) Integer Nonlinear Programming, Stochastic Programming Tags , , ,

    Stochastic mixed-integer nonlinear programming (MINLP) is a very challenging type of problem. Although there have been recent advances in developing decomposition algorithms to solve stochastic MINLPs, none of the existing algorithms can address stochastic MINLPs with continuous distributions. We propose a sample average approximation-based outer approximation algorithm (SAAOA) that can address nonconvex two-stage stochastic programs … Read more

    Solving Heated Oil Pipeline Problems Via Mixed Integer Nonlinear Programming Approach

  • Yu-Hong Dai
  • Yakui Huang
  • Bo Li
  • Muming Yang
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences Tags , , , , , ,

    It is a crucial problem how to heat oil and save running cost for crude oil transport. This paper strictly formulates such a heated oil pipeline problem as a mixed integer nonlinear programming model. Nonconvex and convex continuous relaxations of the model are proposed, which are proved to be equivalent under some suitable conditions. Meanwhile, … Read more

    A Unified Approach to Mixed-Integer Optimization Problems With Logical Constraints

  • Dimitris Bertsimas
  • Ryan Cory-Wright
  • Jean Pauphilet
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , ,

    We propose a unified framework to address a family of classical mixed-integer optimization problems with logically constrained decision variables, including network design, facility location, unit commitment, sparse portfolio selection, binary quadratic optimization, sparse principal component analysis and sparse learning problems. These problems exhibit logical relationships between continuous and discrete variables, which are usually reformulated linearly … Read more