(Mixed) Integer Nonlinear Programming

A Fast Branch-and-Bound Algorithm for Non-convex Quadratic Integer Optimization Subject To Linear Constraints Using Ellipsoidal Relaxations

  • Christoph Buchheim
  • Marianna De Santis
  • Laura Palagi
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Quadratic Programming

    We propose two exact approaches for non-convex quadratic integer minimization subject to linear constraints where lower bounds are computed by considering ellipsoidal relaxations of the feasible set. In the first approach, we intersect the ellipsoids with the feasible linear subspace. In the second approach we penalize exactly the linear constraints. We investigate the connection between … Read more

    LP formulations for mixed-integer polynomial optimization problems

  • Daniel Bienstock
  • Gonzalo Muñoz
    • Categories (Mixed) Integer Nonlinear Programming, Nonsmooth Optimization Tags

    We present polynomial-time algorithms for constrained optimization problems overwhere the intersection graph of the constraint set has bounded tree-width. In the case of binary variables we obtain exact, polynomial-size linear programming formulations for the problem. In the mixed-integer case with bounded variables we obtain polynomial-size linear programming representations that attain guaranteed optimality and feasibility bounds. … Read more

    Quadratic Cone Cutting Surfaces for Quadratic Programs with On-Off Constraints

  • Hyemin Jeon
  • Jeff Linderoth
  • Andrew J. Miller
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming

    We study the convex hull of a set arising as a relaxation of difficult convex mixed integer quadratic programs (MIQP). We characterize the extreme points of our set and the extreme points of its continuous relaxation. We derive four quadratic cutting surfaces that improve the strength of the continuous relaxation. Each of the cutting surfaces … Read more

    Extended Formulations in Mixed Integer Conic Quadratic Programming

  • Iain Dunning
  • Joey Huchette
  • Juan Pablo Vielma
  • Miles Lubin
    • Categories (Mixed) Integer Nonlinear Programming

    In this paper we consider the use of extended formulations in LP-based algorithms for mixed integer conic quadratic programming (MICQP). Extended formulations have been used by Vielma, Ahmed and Nemhauser (2008) and Hijazi, Bonami and Ouorou (2013) to construct algorithms for MICQP that can provide a significant computational advantage. The first approach is based on … Read more

    Solving Power-Constrained Gas Transportation Problems using an MIP-based Alternating Direction Method

  • Björn Geißler
  • Antonio Morsi
  • Lars Schewe
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Constrained Nonlinear Optimization Tags , , , ,

    We present a solution algorithm for problems from steady-state gas transport optimization. Due to nonlinear and nonconvex physics and engineering models as well as discrete controllability of active network devices, these problems lead to hard nonconvex mixed-integer nonlinear optimization models. The proposed method is based on mixed-integer linear techniques using piecewise linear relaxations of the … Read more

    Convex hull of two quadratic or a conic quadratic and a quadratic inequality

  • Sina Modaresi
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Second-Order Cone Programming Tags , ,

    In this paper we consider an aggregation technique introduced by Yildiran, 2009 to study the convex hull of regions defined by two quadratic or by a conic quadratic and a quadratic inequality. Yildiran shows how to characterize the convex hull of open sets defined by two strict quadratic inequalities using Linear Matrix Inequalities (LMI). We … Read more

    A specialized branch-and-bound algorithm for the Euclidean Steiner tree problem in n-space

  • Marcia Fampa
  • Jon Lee
  • Wendel Melo
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms Tags , , ,

    We present a specialized branch-and-bound (b&b) algorithm for the Euclidean Steiner tree problem (ESTP) in R^n and apply it to a convex mixed-integer nonlinear programming (MINLP) formulation of the problem, presented by Fampa and Maculan. The algorithm contains procedures to avoid difficulties observed when applying a b&b algorithm for general MINLP problems to solve the … Read more

    A Gentle, Geometric Introduction to Copositive Optimization

  • Samuel Burer
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    This paper illustrates the fundamental connection between nonconvex quadratic optimization and copositive optimization—a connection that allows the reformulation of nonconvex quadratic problems as convex ones in a unified way. We intend the paper for readers new to the area, and hence the exposition is largely self-contained. We focus on examples having just a few variables … Read more

    Maximal Covering Location Problems on networks with regional demand

  • Rafael Blanquero
  • Emilio Carrizosa
  • Boglárka Tóth
    • Categories (Mixed) Integer Nonlinear Programming, Facility Planning and Design, Global Optimization Tags , , , ,

    Covering problems are well studied in the Operations Research literature under the assumption that both the set of users and the set of potential facilities are finite. In this paper we address the following variant, which leads to a Mixed Integer Nonlinear Program (MINLP): locations of p facilities are sought along the edges of a … Read more

    On a nonconvex MINLP formulation of the Euclidean Steiner tree problems in n-space

  • Claudia D'Ambrosio
  • Marcia Fampa
  • Jon Lee
  • Stefan Vigerske
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Global Optimization Tags , ,

    The Euclidean Steiner Tree Problem in dimension greater than two is notoriously difficult. The successful methods for exact solution are not based on mathematical-optimization methods — rather, they involve very sophisticated enumeration. There are two types of mathematical-optimization formulations in the literature, and it is an understatement to say that neither scales well enough to … Read more