Network Optimization

Transmission and Generation Investment in Electricity Markets: The Effects of Market Splitting and Network Fee Regimes

  • Veronika Grimm
  • Martin Schmidt
  • Alexander Martin
  • Weibelzahl Martin
  • Gregor Zöttl
    • Categories (Mixed) Integer Nonlinear Programming, Finance and Economics, Network Optimization Tags , , , , ,

    We propose an equilibrium model that allows to analyze the long-run impact of the regulatory environment on transmission line expansion by the regulator and investment in generation capacity by private firms in liberalized electricity markets. The model incorporates investment decisions of the transmission operator and private firms in expectation of an energy-only market and cost-based … Read more

    On imposing connectivity constraints in integer programs

  • Austin Buchanan
  • Sergiy Butenko
  • Yiming Wang
    • Categories Combinatorial Optimization, Network Optimization, Polyhedra

    In many network applications, one searches for a connected subset of vertices that exhibits other desirable properties. To this end, this paper studies the connected subgraph polytope of a graph, which is the convex hull of subsets of vertices that induce a connected subgraph. Much of our work is devoted to the study of two … Read more

    Hybrid Constructive Heuristics for the Critical Node Problem

  • Bernardetta Addis
  • Andrea Grosso
  • Roberto Aringhieri
  • Pierre Hosteins
    • Categories Network Optimization Tags , ,

    We consider the Critical Node Problem: given an undirected graph and an integer number K, at most K nodes have to be deleted from the graph in order to minimize a connectivity measure in the residual graph. We combine the basic steps used in common greedy algorithms with some flavour of local search, in order … Read more

    Single-Commodity Robust Network Design with Finite and Hose Demand Sets

  • Valentina Cacchiani
  • Frauke Liers
  • Andrea Lodi
  • Michael Juenger
  • Daniel Schmidt
    • Categories Branch and Cut Algorithms, Network Optimization, Robust Optimization Tags , , ,

    We study a single-commodity Robust Network Design problem (sRND) defined on an undirected graph. Our goal is to determine minimum cost capacities such that any traffic demand from a given uncertainty set can be satisfied by a feasible single-commodity flow. We consider two ways of representing the uncertainty set, either as a finite list of … Read more

    Ship Traffic Optimization for the Kiel Canal

  • Elisabeth Lübbecke
  • Marco E. Lübbecke
  • Rolf H. Möhring
    • Categories Network Optimization, Transportation Tags , , , ,

    We introduce, discuss, and solve a hard practical optimization problem which we call the ship traffic control problem (STCP). Since we plan bi-directional traffic, STCP relates to, and in fact generalizes train timetabling on single-track networks. The objective of finding quickest routes motivates the integration of recent algorithmic ideas from dynamic collision-free routing of automated … Read more

    A Compact Linearisation of Euclidean Single Allocation Hub Location Problems

  • Christoph Buchheim
  • Uwe Clausen
  • J. Fabian Meier
  • Borzou Rostami
    • Categories 0-1 Programming, Network Optimization, Production and Logistics Tags , ,

    Hub location problems are strategic network planning problems. They formalise the challenge of mutually exchanging shipments between a large set of depots. The aim is to choose a set of hubs (out of a given set of possible hubs) and connect every depot to a hub so that the total transport costs for exchanging shipments … Read more

    Parameter-free Sampled Fictitious Play for Solving Deterministic Dynamic Programming Problems

  • Irina S Dolinskaya
  • Marina A. Epelman
  • Esra Sisikoglu
  • Robert L. Smith
    • Categories Dynamic Programming, Network Optimization, Transportation Tags , ,

    To facilitate fast solution of deterministic dynamic programming problems, we present a parameter-free variation of the Sampled Fictitious Play (SFP) algorithm. Its random tie-braking procedure imparts a natural randomness to the algorithm which prevents it from “getting stuck” at a local optimal solution and allows the discovery of an optimal path in a finite number … Read more

    p-facility Huff location problem on networks

  • Rafael Blanquero
  • Emilio Carrizosa
  • Amaya Nogales-Gómez
  • Boglárka Tóth
    • Categories Applications - OR and Management Sciences, Network Optimization Tags , , , , ,

    The p-facility Huff location problem aims at locating facilities on a competitive environment so as to maximize the market share. While it has been deeply studied in the field of continuous location, in this paper we study the p-facility Huff location problem on networks formulated as a Mixed Integer Nonlinear Programming problem that can be … Read more

    New Discoveries of Domination between Traffic Matrices

  • Pengfei Liu
  • Wenguo Yang
    • Categories Network Optimization, Robust Optimization Tags , ,

    A traffic matrix $D_1$ dominates a traffic matrix $D_2$ if any capacity reservation supporting $D_1$ supports $D_2$ as well. We prove that $D_3$ dominates $D_3+ \lambda(D_2-D_1)$ for any $\lambda\geq 0$ if $D_1$ dominates $D_2$. By the property , it is pointed out that the domains supported by different traffic matrices are isomorphic on the extended … Read more

    Efficient approaches for the robust network loading problem

  • Sara Mattia
  • Michael Poss
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Robust Optimization Tags , , , ,

    We consider the Robust Network Loading problem with splittable flows and demands that belong to the budgeted uncertainty set. We compare the optimal solution cost and computational cost of the problem when using static routing, volume routing, affine routing, and dynamic routing. For the first three routing types, we compare the compact formulation with a … Read more