Integer Programming

Combinatorial Integral Approximation for Mixed-Integer PDE-Constrained Optimization Problems

  • Mirko Hahn
  • Sebastian Sager
    • Categories (Mixed) Integer Nonlinear Programming, Optimization of Systems modeled by PDEs, Systems governed by Differential Equations Optimization Tags , , ,

    We apply the basic principles underlying combinatorial integral approximation methods for mixed-integer optimal control with ordinary differential equations in general, and the sum-up rounding algorithm specifically, to optimization problems with partial differential equation (PDE) constraints. By doing so, we identify two possible generalizations that are applicable to problems involving PDE constraints with mesh-dependent integer variables, … Read more

    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

    Robust Optimal Discrete Arc Sizing for Tree-Shaped Potential Networks

  • Martin Robinius
  • Lars Schewe
  • Martin Schmidt
  • Johannes Thürauf
  • Detlef Stolten
  • Lara Welder
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering, Robust Optimization Tags , , , , ,

    We consider the problem of discrete arc sizing for tree-shaped potential networks with respect to infinitely many demand scenarios. This means that the arc sizes need to be feasible for an infinite set of scenarios. The problem can be seen as a strictly robust counterpart of a single-scenario network design problem, which is shown to … Read more

    Optimal Black Start Allocation for Power System Restoration

  • Shmuel Oren
  • Deepak Rajan
  • Georgios Patsakis
  • Jennifer Rios
    • Categories (Mixed) Integer Linear Programming, Energy Tags , ,

    Equipment failures, operator errors, natural disasters and cyber-attacks can and have caused extended blackouts of the electric grid. Even though such events are rare, preparedness for them is critical because extended power outages endanger human lives, compromise national security, or result in economic losses of billions of dollars. Since most of the generating units cannot … Read more

    Least cost influence propagation in (social) networks

  • Matteo Fischetti
  • Michael Kahr
  • Markus Leitner
  • Michele Monaci
  • Mario Ruthmair
    • Categories Applications - OR and Management Sciences, Integer Programming, Network Optimization Tags , ,

    Influence maximization problems aim to identify key players in (social) networks and are typically motivated from viral marketing. In this work, we introduce and study the Generalized Least Cost Influence Problem (GLCIP) that generalizes many previously considered problem variants and allows to overcome some of their limitations. A formulation that is based on the concept … Read more

    A Notion of Total Dual Integrality for Convex, Semidefinite, and Extended Formulations

  • Marcel K. de Carli Silva
  • Levent Tunçel
    • Categories Combinatorial Optimization, Integer Programming, Linear, Cone and Semidefinite Programming Tags , ,

    Total dual integrality is a powerful and unifying concept in polyhedral combinatorics and integer programming that enables the refinement of geometric min-max relations given by linear programming Strong Duality into combinatorial min-max theorems. The definition of total dual integrality (TDI) revolves around the existence of optimal dual solutions that are integral, and thus naturally applies … Read more

    The Continuous Time Inventory Routing Problem

  • Natashia Boland
  • Felipe Lagos
  • Martin Savelsbergh
    • Categories Integer Programming, Transportation Tags ,

    We consider a continuous time variant of the Inventory Routing Problem in which the maximum quantity that can delivered at a customer depends on the customer’s storage capacity and product inventory at the time of the delivery. We investigate critical components of a dynamic discretization discovery algorithm and demonstrate in an extensive computational study that … Read more

    A polynomial time algorithm for the linearization problem of the QSPP and its applications

  • Hao Hu
  • Renata Sotirov
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    Given an instance of the quadratic shortest path problem (QSPP) on a digraph $G$, the linearization problem for the QSPP asks whether there exists an instance of the linear shortest path problem on $G$ such that the associated costs for both problems are equal for every $s$-$t$ path in $G$. We prove here that the … Read more

    Staircase Compatibility and its Applications in Scheduling and Piecewise Linearization

  • Andreas Bärmann
  • Maximilian Merkert
  • Thorsten Gellermann
  • Oskar Schneider
    • Categories (Mixed) Integer Linear Programming, Polyhedra, Scheduling Tags , , , ,

    We consider the clique problem with multiple-choice constraints (CPMC) and characterize a case where it is possible to give an efficient description of the convex hull of its feasible solutions. This new special case, which we call staircase compatibility, generalizes common properties in several applications and allows for a linear description of the integer feasible … Read more

    Network Models with Unsplittable Node Flows with Application to Unit Train Scheduling

  • Danial Davarnia
  • Jean-Philippe P. Richard
  • Ece Icyuz-Ay
  • Bijan Taslimi
    • Categories Cutting Plane Approaches, Network Optimization, Transportation

    We study network models where flows cannot be split or merged when passing through certain nodes, i.e., for such nodes, each incoming arc flow must be matched to an outgoing arc flow of identical value. This requirement, which we call “no-split no-merge” (NSNM), appears in railroad applications where train compositions can only be modified at … Read more