(Mixed) Integer Nonlinear Programming

Stochastic Dual Dynamic Programming for Multistage Stochastic Mixed-Integer Nonlinear Optimization

  • Shixuan Zhang
  • Xu Andy Sun
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Stochastic Programming Tags , , ,

    In this paper, we study multistage stochastic mixed-integer nonlinear programs (MS-MINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization with \emph{non-Lipschitz-continuous} value functions and multistage stochastic mixed-integer linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient … 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

    Convex Hulls for Non-Convex Mixed-Integer Quadratic Programs with Bounded Variables

  • Laura Galli
  • Adam N. Letchford
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Polyhedra

    We consider non-convex mixed-integer quadratic programs in which all variables are explicitly bounded. Many exact methods for such problems use additional variables, representing products of pairs of original variables. We study the convex hull of feasible solutions in this extended space. Some other approaches use bit representation to convert bounded integer variables into binary variables. … Read more

    Inversion of Convection-Diffusion Equation with Discrete Sources

  • Mirko Hahn
  • Sven Leyffer
  • Bart van Bloemen Waanders
  • Lars Ruthotto
  • Meenarli Sharma
    • Categories (Mixed) Integer Nonlinear Programming, Systems governed by Differential Equations Optimization

    We present a convection-diffusion inverse problem that aims to identify an unknown number of sources and their locations. We model the sources using a binary function, and we show that the inverse problem can be formulated as a large-scale mixed-integer nonlinear optimization problem. We show empirically that current state-of-the-art mixed-integer solvers cannot solve this problem … 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

    The Impact of Neighboring Markets on Renewable Locations, Transmission Expansion, and Generation Investment

  • Jonas Egerer
  • Veronika Grimm
  • Thomas Kleinert
  • Martin Schmidt
  • Gregor Zöttl
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Global Optimization Tags , , , ,

    Many long-term investment planning models for liberalized electricity markets either optimize for the entire electricity system or focus on confined jurisdictions, abstracting from adjacent markets. In this paper, we provide models for analyzing the impact of the interdependencies between a core electricity market and its neighboring markets on key long-run decisions. This we do both … Read more

    On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming

  • Maxime Gasse
  • Ambros Gleixner
  • Andrea Lodi
  • Felipe Serrano
  • Benjamin Müller
  • Gonzalo Muñoz
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Nonlinear Optimization Tags ,

    The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solver can often successfully handle a moderate presence of nonconvexities, which opens … Read more

    On the complexity of binary polynomial optimization over acyclic hypergraphs

  • Alberto Del Pia
  • Silvia Di Gregorio
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , ,

    In this work we advance the understanding of the fundamental limits of computation for Binary Polynomial Optimization (BPO), which is the problem of maximizing a given polynomial function over all binary points. In our main result we provide a novel class of BPO that can be solved efficiently both from a theoretical and computational perspective. … Read more

    Outlier detection in time series via mixed-integer conic quadratic optimization

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

    We consider the problem of estimating the true values of a Wiener process given noisy observations corrupted by outliers. The problem considered is closely related to the Trimmed Least Squares estimation problem, a robust estimation procedure well-studied from a statistical standpoint but poorly understood from an optimization perspective. In this paper we show how to … Read more

    Integrality of Linearizations of Polynomials over Binary Variables using Additional Monomials

  • Christopher Hojny
  • Marc E. Pfetsch
  • Matthias Walter
    • Categories (Mixed) Integer Nonlinear Programming, Polyhedra Tags , ,

    Polynomial optimization problems over binary variables can be expressed as integer programs using a linearization with extra monomials in addition to those arising in the given polynomial. We characterize when such a linearization yields an integral relaxation polytope, generalizing work by Del Pia and Khajavirad (SIAM Journal on Optimization, 2018) and Buchheim, Crama and Rodríguez-Heck … Read more