Network Optimization

On the Single-Multi-Commodity Gap: Lifting Single- to Multicommodity Flow Instances

  • Felix P. Broesamle
  • Stefan Nickel
    • Categories Applications - OR and Management Sciences, Linear Programming, Network Optimization Tags , , , , ,

    Benchmark instances for multicommodity flow problems frequently lack the structural nuances of real-world networks or fail to maintain a rigorous mathematical relationship with their single-commodity counterparts. This paper introduces a formal meta-generation framework that addresses these limitations by lifting single-commodity minimum-cost flow instances into the multicommodity space while strictly preserving the underlying network topology, capacity … Read more

    Finding Minimal Discretizations in Dynamic Discretization Discovery for Continuous-Time Service Network Design

  • Tom Wüllner
  • Alexander Helber
    • Categories Combinatorial Optimization, Network Optimization, Transportation Tags , , ,

    The dynamic discretization discovery framework is a powerful tool for solving network design problems with a temporal component by iteratively refining a time-discretized model. Existing approaches refine the time discretization in ways that guarantee eventual termination. However, refinement choices are not unique, and better choices can yield smaller and easier-to-solve time-discretized models. We pose the … Read more

    Water network design and operation optimization: Leveraging approximations

  • Sourabh Kumar Choudhary
  • Santanu S. Dey
  • Nikolaos Sahinidis
    • Categories Network Optimization Tags , ,

    This study concerns the optimal design and operation of produced water and urban water networks. The optimization formulations of these problems have inherent nonconvexity, making them hard to solve. We address a key source of nonconvexity and difficulty in solving these problems: the representation of frictional pressure changes across network nodes using nonlinear constraints, typically … Read more

    Risk-Averse Stochastic User Equilibrium on Uncertain Transportation Networks

  • Wencheng Bao
  • Chrysafis Vogiatzis
  • Eleftheria Kontou
    • Categories Network Optimization, Robust Optimization, Transportation Tags , , , , ,

    Extreme weather events, like flooding, disrupt urban transportation networks by reducing speeds and capacities, and by closing roadways. These hazards create regime-dependent uncertainty in link performance and travel-time distribution tails, challenging conventional traffic assignment that relies on the expectation of cost or mean excess of cost summation. This study develops a risk- and ambiguity-aware traffic … Read more

    Potential-Based Flows – An Overview

  • Marc E. Pfetsch
  • Martin Schmidt
  • Martin Skutella
  • Johannes Thürauf
    • Categories Energy, Network Optimization

    Potential-based flows provide an algebraic way to model static physical flows in networks, for example, in gas, water, and lossless DC power networks. The flow on an arc in the network depends on the difference of the potentials at its end-nodes, possibly in a nonlinear way. Potential-based flows have several nice properties like uniqueness and … Read more

    The Generalized Group Steiner Tree Problem with Logical Side Constraints

  • Chrysafis Vogiatzis
    • Categories Network Optimization Tags , , ,

    In this work, we study a recent extension to the well-known Steiner tree problem: the Generalized Group Steiner Tree problem with logical side constraints. In this variant, we aim to identify a tree of minimum total cost, that spans a given set of groups of nodes, like in the traditional Group Steiner Tree problem. However, … Read more

    Exact Decentralized Optimization via Explicit $\ell_1$ Consensus Penalties

  • Hong Wang
    • Categories Network Optimization, Nonlinear Optimization Tags ,

    Consensus optimization enables autonomous agents to solve joint tasks through peer-to-peer exchanges alone. Classical decentralized gradient descent is appealing for its minimal state but fails to achieve exact consensus with fixed stepsizes unless additional trackers or dual variables are introduced. We revisit penalty methods and introduce a decentralized two-layer framework that couples an outer penalty-continuation … Read more

    generalizing the successive shortest path algorithm to solve the multi-objective assignment problem

  • Antonio Sedeño-Noda
    • Categories Multi-Criteria Optimization, Network Optimization, Other Topics Tags , ,

    We introduce a novel characterization of the efficient solutions to the Multi-objective Assignment Problem (MAP), relying solely on Network Flow theory. This result establishes that the set of efficient assignments restricted to the first $k$ origin-destination pairs in the associated bipartite graph can be derived incrementally from the efficient solutions corresponding to the first $k-1$ … Read more

    Column Generation for Generalized Min-Cost Flows with Losses

  • Jonas Alker
  • Marc E. Pfetsch
    • Categories Combinatorial Optimization, Linear Programming, Network Optimization Tags ,

    The generalized flow problem deals with flows through a network with losses or gains along the arcs. Motivated by energy networks, this paper concentrates on the case with losses along cycles. Such networks can become extremely large, mostly because they are considered over large time horizons. We therefore develop a column generation approach for a … Read more

    Effective Solution Algorithms for Bulk-Robust Optimization Problems

  • Christoph Buchheim
  • Enrico Malaguti
  • Michele Monaci
  • Paolo Paronuzzi
  • Pia Schreynemackers
    • Categories 0-1 Programming, Network Optimization, Robust Optimization Tags , , , ,

    Bulk-robust optimization is a recent paradigm for addressing problems in which the structure of a system is affected by uncertainty. It considers the case in which a finite and discrete set of possible failure scenarios is known in advance, and the decision maker aims to activate a subset of available resources of minimum cost so … Read more