Network Optimization

Reformulating Linear Programs with Transportation Constraints — with Applications to Workforce Scheduling

  • Tolga Cezik
  • Oktay Gunluk
    • Categories Combinatorial Optimization, Network Optimization Tags , ,

    We study linear programming models that contain transportation constraints in their formulation. Typically, these models have a multi-stage nature and the transportation constraints together with the associated flow variables are used to achieve consistency between consecutive stages. We describe how to reformulate these models by projecting out the flow variables. The reformulation can be more … Read more

    A Mixed Integer Disjunctive Model for Transmission Network Expansion

  • Laura Bahiense
  • Sérgio Granville
  • Gerson C. Oliveira
  • Mario Pereira
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Network Optimization Tags , ,

    The classical non-linear mixed integer formulation of the transmission network expansion problem cannot guarantee finding the optimal solution due to its non-convex nature. We propose an alternative mixed integer linear disjunctive formulation, which has better conditioning properties than the standard disjunctive model. The mixed integer program is solved by a commercial Branch and Bound code, … Read more

    The Robust Shortest Path Problem with Interval Data

  • Oya Ekin Karasan
  • Mustafa C. Pinar
  • Hande Yaman
    • Categories Network Optimization, Robust Optimization, Telecommunications Tags , , ,

    Motivated by telecommunication applications, we investigate the shortest path problem on directed acyclic graphs under arc length uncertainties represented as interval numbers. Using a minimax-regret criterion we define and identify robust paths via mixed-integer programming and exploiting interesting structural properties of the problem. Citation Bilkent University, Department of Industrial Engineering, Technical Report August 2001 Article … Read more

    A GRASP with path-relinking for private virtual circuit routing

  • Mauricio G.C. Resende
  • Celso C. Ribeiro
    • Categories Meta Heuristics, Network Optimization, Telecommunications Tags , , , , , , , ,

    A frame relay service offers virtual private networks to customers by provisioning a set of long-term private virtual circuits (PVCs) between customer endpoints on a large backbone network. During the provisioning of a PVC, routing decisions are made without any knowledge of future requests. Over time, these decisions can cause inefficiencies in the network and … Read more

    A study of preconditioners for network interior point methods

  • Joaquim J. Júdice
  • João Patrício
  • Luis F. Portugal
  • Mauricio G.C. Resende
  • Geraldo Veiga
    • Categories Network Optimization Tags , , , ,

    We study and compare preconditioners available for network interior point methods. We derive upper bounds for the condition number of the preconditioned matrices used in the solution of systems of linear equations defining the algorithm search directions. The preconditioners are tested using PDNET, a state-of-the-art interior point code for the minimum cost network flow problem. … Read more

    Newton Algorithms for Large-Scale Strictly Convex Separable Network Optimization

  • Aleksandar Donev
  • Phillip Duxbury
    • Categories Convex Optimization, Network Optimization Tags ,

    In this work we summarize the basic elements of primal and dual Newton algorithms for network optimization with continuously differentiable (strictly) convex arc cost functions. Both the basic mathematics and implementation are discussed, and hints to important tuning details are made. The exposition assumes that the reader posseses a significant level of prior knowledge in … Read more