(Mixed) Integer Nonlinear Programming

Small and Strong Formulations for Unions of Convex Sets from the Cayley Embedding

  • Juan Pablo Vielma
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming

    There is often a significant trade-off between formulation strength and size in mixed integer programming (MIP). When modeling convex disjunctive constraints (e.g. unions of convex sets), adding auxiliary continuous variables can sometimes help resolve this trade-off. However, standard formulations that use such auxiliary continuous variables can have a worse-than-expected computational effectiveness, which is often attributed … Read more

    MIP-Based Instantaneous Control of Mixed-Integer PDE-Constrained Gas Transport Problems

  • Martin Gugat
  • Günter Leugering
  • Martin Schmidt
  • Mathias Sirvent
  • David Wintergerst
  • Alexander Martin
    • Categories (Mixed) Integer Nonlinear Programming, Optimization of Systems modeled by PDEs, Systems governed by Differential Equations Optimization Tags , , , ,

    We study the transient optimization of gas transport networks including both discrete controls due to switching of controllable elements and nonlinear fluid dynamics described by the system of isothermal Euler equations, which are partial differential equations in time and 1-dimensional space. This combination leads to mixed-integer optimization problems subject to nonlinear hyperbolic partial differential equations … Read more

    Lifted Polymatroid Inequalities for Mean-Risk Optimization with Indicator Variables

  • Alper Atamturk
  • Hyemin Jeon
    • Categories (Mixed) Integer Nonlinear Programming, Stochastic Programming Tags , , , ,

    We investigate a mixed 0-1 conic quadratic optimization problem with indicator variables arising in mean-risk optimization. The indicator variables are often used to model non-convexities such as fixed charges or cardinality constraints. Observing that the problem reduces to a submodular function minimization for its binary restriction, we derive three classes of strong convex valid inequalities … Read more

    Error bounds for monomial convexification in polynomial optimization

  • Warren Adams
  • Akshay Gupte
  • Yibo Xu
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory Tags , , , , ,

    Convex hulls of monomials have been widely studied in the literature, and monomial convexifications are implemented in global optimization software for relaxing polynomials. However, there has been no study of the error in the global optimum from such approaches. We give bounds on the worst-case error for convexifying a monomial over subsets of $[0,1]^n$. This … Read more

    Dantzig Wolfe decomposition and objective function convexification for binary quadratic problems: the cardinality constrained quadratic knapsack case

  • Alberto Ceselli
  • Lucas Létocart
  • Emiliano Traversi
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Quadratic Programming Tags , , ,

    The purpose of this paper is to provide strong reformulations for binary quadratic problems. We propose a first methodological analysis on a family of reformulations combining Dantzig-Wolfe decomposition and Quadratic Convex Reformulation principles. As a representative case study, we apply them to a cardinality constrained quadratic knapsack problem, providing extensive experimental insights. We show that … Read more

    Complex Number Formulation and Convex Relaxations for Aircraft Conflict Resolution

  • Hassan L. Hijazi
  • David Rey
    • Categories (Mixed) Integer Nonlinear Programming, Airline Optimization, Global Optimization Applications Tags , , , ,

    We present a novel complex number formulation along with tight convex relaxations for the aircraft conflict resolution problem. Our approach combines both speed and heading control and provides global optimality guarantees despite non-convexities in the feasible region. As a side result, we present a new characterization of the conflict separation condition in the form of … Read more

    The SCIP Optimization Suite 4.0

  • Tobias Fischer
  • Tristan Gally
  • Gerald Gamrath
  • Ambros Gleixner
  • Robert Lion Gottwald
  • Gregor Hendel
  • Thorsten Koch
  • Marco E. Lübbecke
  • Stephen J. Maher
  • Matthias Miltenberger
  • Marc E. Pfetsch
  • Felipe Serrano
  • Dieter Weninger
  • Jakob Witzig
  • Benjamin Müller
  • Christian Puchert
  • Daniel Rehfeldt
  • Sebastian Schenker
  • Robert Schwarz
  • Yuji Shinano
  • Jonas T. Witt
    • Categories (Mixed) Integer Nonlinear Programming, Optimization Software and Modeling Systems Tags , ,

    The SCIP Optimization Suite is a powerful collection of optimization software that consists of the branch-cut-and-price framework and mixed-integer programming solver SCIP, the linear programming solver SoPlex, the modeling language Zimpl, the parallelization framework UG, and the generic branch-cut-and-price solver GCG. Additionally, it features the extensions SCIP-Jack for solving Steiner tree problems, PolySCIP for solving … Read more

    Conic relaxation approaches for equal deployment problems

  • Safia Kedad-Sidhoum
  • Tim J. Mullin
  • Satoko Moriguchi
  • Makoto Yamashita
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming

    An important problem in the breeding of livestock, crops, and forest trees is the optimum of selection of genotypes that maximizes genetic gain. The key constraint in the optimal selection is a convex quadratic constraint that ensures genetic diversity, therefore, the optimal selection can be cast as a second-order cone programming (SOCP) problem. Yamashita et … Read more

    Exact Methods for Recursive Circle Packing

  • Ambros Gleixner
  • Stephen J. Maher
  • João Pedro Pedroso
  • Benjamin Müller
    • Categories (Mixed) Integer Nonlinear Programming

    Packing rings into a minimum number of rectangles is an optimization problem which appears naturally in the logistics operations of the tube industry. It encompasses two major difficulties, namely the positioning of rings in rectangles and the recursive packing of rings into other rings. This problem is known as the Recursive Circle Packing Problem (RCPP). … Read more

    Simultaneous convexification of bilinear functions over polytopes with application to network interdiction

  • Danial Davarnia
  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Network Optimization

    We study the simultaneous convexification of graphs of bilinear functions that contain bilinear products between variables x and y, where x belongs to a general polytope and y belongs to a simplex. We propose a constructive procedure to obtain a linear description of the convex hull of the resulting set. This procedure can be applied … Read more