(Mixed) Integer Nonlinear Programming

Strong formulations for quadratic optimization with M-matrices and semi-continuous variables

  • Alper Atamturk
  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , ,

    We study quadratic optimization with semi-continuous variables and an M-matrix, i.e., PSD with non-positive off-diagonal entries. This structure arises in image segmentation, portfolio optimization, as well as a substructure of general quadratic optimization problems. We prove, under mild assumptions, that the minimization problem is solvable in polynomial time by showing its equivalence to a submodular … 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

    Extended formulations for convex hulls of some bilinear functions

  • Akshay Gupte
  • Thomas Kalinowski
  • Fabian Rigterink
  • Hamish Waterer
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Polyhedra Tags , , ,

    We consider the problem of characterizing the convex hull of the graph of a bilinear function $f$ on the $n$-dimensional unit cube $[0,1]^n$. Extended formulations for this convex hull are obtained by taking subsets of the facets of the Boolean Quadric Polytope (BQP). Extending existing results, we propose the systematic study of properties of $f$ … Read more

    The SCIP Optimization Suite 5.0

  • Leon Eifler
  • Tristan Gally
  • Gerald Gamrath
  • Ambros Gleixner
  • Robert Lion Gottwald
  • Gregor Hendel
  • Christopher Hojny
  • Thorsten Koch
  • Matthias Miltenberger
  • Marc E. Pfetsch
  • Felipe Serrano
  • Dieter Weninger
  • Jakob Witzig
  • Patrick Gemander
  • Benjamin Müller
  • Christian Puchert
  • Daniel Rehfeldt
  • Franziska Schlösser
  • Yuji Shinano
  • Merlin Viernickel
  • Stefan Vigerske
  • Jonas T. Witt
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , , , , , , , ,

    This article describes new features and enhanced algorithms made available in version 5.0 of the SCIP Optimization Suite. In its central component, the constraint integer programming solver SCIP, remarkable performance improvements have been achieved for solving mixed-integer linear and nonlinear programs. On MIPs, SCIP 5.0 is about 41 % faster than SCIP 4.0 and over … Read more

    Mixed-Integer PDE-Constrained Optimal Control of Gas Networks

  • Mirko Hahn
  • Sven Leyffer
  • Victor M. Zavala
    • Categories (Mixed) Integer Nonlinear Programming, Optimization of Systems modeled by PDEs, Systems governed by Differential Equations Optimization Tags , , ,

    We develop a mixed-integer optimal control model with partial differential equation (PDE) constraints for gas transport networks, designed for controlling extreme state transitions, such as flow reversals. Our model shows how to combine binary compressor controls with PDE flow models. We model the flow of gas using a variant of the Euler equations, which we … Read more

    Maximum-Entropy Sampling and the Boolean Quadric Polytope

  • Kurt M. Anstreicher
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming, Statistics Tags , ,

    We consider a bound for the maximum-entropy sampling problem (MESP) that is based on solving a max-det problem over a relaxation of the Boolean Quadric Polytope (BQP). This approach to MESP was first suggested by Christoph Helmberg over 15 years ago, but has apparently never been further elaborated or computationally investigated. We find that the … Read more

    Granularity in nonlinear mixed-integer optimization

  • Christoph Neumann
  • Oliver Stein
  • Nathan Sudermann-Merx
    • Categories (Mixed) Integer Nonlinear Programming

    We study a deterministic technique to check the existence of feasible points for mixed-integer nonlinear optimization problems which satisfy a structural requirement that we call granularity. We show that solving certain purely continuous optimization problems and rounding their optimal points leads to feasible points of the original mixed-integer problem, as long as the latter is … Read more

    Sparse principal component analysis and its l1-relaxation

  • Santanu S. Dey
  • Rahul Mazumder
  • Marco Molinaro
  • Guanyi Wang
    • Categories (Mixed) Integer Nonlinear Programming, Data-Mining

    Principal component analysis (PCA) is one of the most widely used dimensionality reduction methods in scientific data analysis. In many applications, for additional interpretability, it is desirable for the factor loadings to be sparse, that is, we solve PCA with an additional cardinality (l0) constraint. The resulting optimization problem is called the sparse principal component … Read more

    Network-based Approximate Linear Programming for Discrete Optimization

  • Andre Augusto Cire
  • Selvaprabu Nadarajah
    • Categories (Mixed) Integer Nonlinear Programming, Dynamic Programming, Linear Programming Tags , ,

    We develop a new class of approximate linear programs (ALPs) that project the high-dimensional value function of dynamic programs onto a class of basis functions, each defined as a network that represents aggregrations over the state space. The resulting ALP is a minimum-cost flow problem over an extended variable space that synchronizes flows across multiple … Read more

    A partial outer convexification approach to control transmission lines

  • Simone Göttlich
  • Andreas Potschka
  • Claus Teuber
    • Categories (Mixed) Integer Nonlinear Programming, Optimization of Systems modeled by PDEs Tags , ,

    In this paper we derive an efficient optimization approach to calculate optimal controls of electric transmission lines. These controls consist of time-dependent inflows and switches that temporarily disable single arcs or whole subgrids to reallocate the flow inside the system. The aim is then to find the best energy input in terms of boundary controls … Read more