Integer Programming

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

    Multi-objective Optimization Based Algorithms for Solving Mixed Integer Linear Minimum Multiplicative Programs

  • Hadi Charkhgard
  • Vahid Mahmoodian
  • Yu Zhang
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Global Optimization

    We present two new algorithms for a class of single-objective non-linear optimization problems, the so-called Mixed Integer Linear minimum Multiplicative Programs (MIL-mMPs). This class of optimization problems has a desirable characteristic: a MIL-mMP can be viewed as a special case of the problem of optimization over the efficient set in multi-objective optimization. The proposed algorithms … Read more

    A Solution Framework for Linear PDE-Constrained Mixed-Integer Problems

  • Armin Fügenschuh
  • Sven Leyffer
  • Fabian Gnegel
  • Michael Hagel
  • Marcus Stiemer
    • Categories (Mixed) Integer Linear Programming, Control Applications, Network Optimization Tags , , , , ,

    We present a general numerical solution method for control problems with PDE-defined state variables over a finite set of binary or continuous control variables. We show empirically that a naive approach that applies a numerical discretization scheme to the PDEs (and if necessary a linearization scheme) to derive constraints for a mixed-integer linear program (MILP) … 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

    Polynomial Size IP Formulations of Knapsack May Require Exponentially Large Coefficients

  • Christopher Hojny
    • Categories 0-1 Programming, Integer Programming Tags , ,

    A desirable property of integer formulations is to consist of few inequalities having small coefficients. We show that these targets are conflicting by proving the existence of knapsack sets that need exponentially many inequalities or exponentially large coefficients in any integer formulation. Moreover, we show that there exist undirected graphs such that (in a natural … Read more

    Optimal time-and-level-of-use price setting for an energy retailer

  • Miguel F. Anjos
  • Luce Brotcorne
  • Juan A. Gomez-Herrera
    • Categories (Mixed) Integer Linear Programming, Energy, Game Theory Tags , , , , ,

    This paper presents a novel price setting optimization problem for an energy retailer in the smart grid. In this framework the retailer buys energy from multiple generators via bilateral contracts, and sells it to a population of smart homes using Time-and-Level-of-Use prices (TLOU). TLOU is an energy price structure recently introduced in the literature, where … Read more

    Persistency of Linear Programming Formulations for the Stable Set Problem

  • Elisabeth Rodriguez-Heck
  • Matthias Walter
  • Karl Stickler
  • Stefan Weltge
    • Categories 0-1 Programming, Polyhedra Tags , ,

    The Nemhauser-Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: for every optimal LP solution that assigns integer values to some variables, there exists an optimal integer solution in which these variables retain the same values. While the standard LP … Read more

    Exact Methods for the Traveling Salesman Problem with Drone

  • Roberto Roberti
  • Mario Ruthmair
    • Categories (Mixed) Integer Linear Programming, Dynamic Programming, Transportation Tags , , , ,

    Efficiently handling last-mile deliveries becomes more and more important nowadays. Using drones to support classical vehicles allows improving delivery schedules as long as efficient solution methods to plan last-mile deliveries with drones are available. We study exact solution approaches for some variants of the traveling salesman problem with drone (TSP-D) in which a truck and … Read more