(Mixed) Integer Nonlinear Programming

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

    Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane

  • Alberto Del Pia
  • Robert Hildebrand
  • Robert Weismantel
  • Kevin Zemmer
    • Categories (Mixed) Integer Nonlinear Programming Tags

    We complete the complexity classification by degree of minimizing a polynomial in two variables over the integer points in a polyhedron. Previous work shows that in two variables, optimizing a quadratic polynomial over the integer points in a polyhedral region can be done in polynomial time, while optimizing a quartic polynomial in the same type … Read more

    Fast Algorithms for the Minimum Volume Estimator

  • Selin Damla Ahipasaoglu
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Statistics Tags , ,

    The MVE estimator is an important tool in robust regression and outlier detection in statistics. We develop fast and efficient algorithms for the MVE estimator problem and discuss how they can be implemented efficiently. The novelty of our approach stems from the recent developments in the first-order algorithms for solving the related Minimum Volume Enclosing … Read more

    A Feasible Active Set Method with Reoptimization for Convex Quadratic Mixed-Integer Programming

  • Christoph Buchheim
  • Marianna De Santis
  • Stefano Lucidi
  • Francesco Rinaldi
  • Long Trieu
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , ,

    We propose a feasible active set method for convex quadratic programming problems with non-negativity constraints. This method is specifically designed to be embedded into a branch-and-bound algorithm for convex quadratic mixed integer programming problems. The branch-and-bound algorithm generalizes the approach for unconstrained convex quadratic integer programming proposed by Buchheim, Caprara and Lodi to the presence … Read more

    Constraint Qualification Failure in Action

  • Hassan L. Hijazi
  • Leo Liberti
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming Tags , , , ,

    This note presents a theoretical analysis of disjunctive constraints featuring unbounded variables. In this framework, classical modeling techniques, including big-M approaches, are not applicable. We introduce a lifted second-order cone formulation of such on/off constraints and discuss related constraint qualification issues. A solution is proposed to avoid solvers’ failure. Citation H. L. Hijazi and L.Liberti … Read more