Month: July 2018

Efficient Algorithms for Flow over Time Evacuation Planning Problems with Lane Reversal Strategy

  • Stephan Dempe
  • Tanka Nath Dhamala
  • Urmila Pyakurel
    • Categories Applications - OR and Management Sciences, Network Optimization

    The contraflow techniques have widely been effective in evacuation planning research. We present effcient algorithms to solve the evacuation network flow problems, namely, the maximum, earliest arrival, quickest and lex-maximum dynamic contraflow problems having constant attributes and their generalizations with partial contraflow recon guration. Moreover, the contraflow models with inflow dependent and load dependent transit times … Read more

    A Note on “A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs”

  • Austin Buchanan
  • Hamidreza Validi
    • Categories Combinatorial Optimization, Integer Programming

    In the paper “A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs” (Networks 39(1):53–60, 2002), Williams introduced an extended formulation for the spanning tree polytope of a planar graph. This formulation is remarkably small (using only $O(n)$ variables and constraints) and remarkably strong (defining an integral polytope). In this note, … Read more

    Data-Driven Distributionally Robust Chance-Constrained Optimization with Wasserstein Metric

  • Ran Ji
  • Miguel A. Lejeune
    • Categories Robust Optimization, Second-Order Cone Programming, Stochastic Programming Tags , ,

    We study distributionally robust chance-constrained programming (DRCCP) optimization problems with data-driven Wasserstein ambiguity sets. The proposed algorithmic and reformulation framework applies to distributionally robust optimization problems subjected to individual as well as joint chance constraints, with random right-hand side and technology vector, and under two types of uncertainties, called uncertain probabilities and continuum of realizations. … Read more

    A Unified Characterization of Nonlinear Scalarizing Functionals in Optimization

  • Gemayqzel Bouza
  • Christiane Tammer
  • Ernest Quintana
    • Categories Convex and Nonsmooth Optimization, Global Optimization, Nonlinear Optimization Tags , , , ,

    Over the years, several classes of scalarization techniques in optimization have been introduced and employed in deriving separation theorems, optimality conditions and algorithms. In this paper, we study the relationships between some of those classes in the sense of inclusion. We focus on three types of scalarizing functionals (by Hiriart-Urruty, Drummond and Svaiter, Gerstewitz) and … Read more

    First-order methods for the impatient: support identification in finite time with convergent Frank-Wolfe variants

  • Immanuel M. Bomze
  • Francesco Rinaldi
  • Samuel Rota Bulo
    • Categories Constrained Nonlinear Optimization Tags , , ,

    In this paper, we focus on the problem of minimizing a non-convex function over the unit simplex. We analyze two well-known and widely used variants of the Frank-Wolfe algorithm and first prove global convergence of the iterates to stationary points both when using exact and Armijo line search. Then we show that the algorithms identify … Read more

    Fast robust shortest path computations

  • Christoph Hansknecht
  • Alexander Richter
  • Sebastian Stiller
    • Categories Network Optimization Tags , ,

    We develop a fast method to compute an optimal robust shortest path in large networks like road networks, a fundamental problem in traffic and logistics under uncertainty. In the robust shortest path problem we are given an $s$-$t$-graph $D(V,A)$ and for each arc a nominal length $c(a)$ and a maximal increase $d(a)$ of its length. … Read more

    The SCIP Optimization Suite 6.0

  • Michael Bastubbe
  • Leon Eifler
  • Tristan Gally
  • Gerald Gamrath
  • Ambros Gleixner
  • Robert Lion Gottwald
  • Gregor Hendel
  • Christopher Hojny
  • Thorsten Koch
  • Marco E. Lübbecke
  • Stephen J. Maher
  • Matthias Miltenberger
  • Marc E. Pfetsch
  • Felipe Serrano
  • Matthias Walter
  • Jakob Witzig
  • Benjamin Müller
  • Christian Puchert
  • Daniel Rehfeldt
  • Franziska Schlösser
  • Christoph Schubert
  • Yuji Shinano
  • Merlin Viernickel
  • Fabian Wegscheider
  • Jonas T. Witt
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , , , , , , , , ,

    The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 6.0 of the SCIP Optimization Suite. Besides performance improvements of the MIP and MINLP core achieved by new primal heuristics and a new selection criterion … Read more