Network Optimization

Complete mixed integer linear programming formulations for modularity density based clustering

  • Alberto Costa
  • Lin Xuan Foo
  • Tsan Sheng Ng
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Nonlinear Optimization

    Modularity density maximization is a clustering method that improves some issues of the commonly-used modularity maximization approach. Recently, some Mixed-Integer Linear Programming (MILP) reformulations have been proposed in the literature for the modularity density maximization problem, but they require as input the solution of a set of auxiliary binary Non-Linear Programs (NLPs). These can become … Read more

    A Branch-and-Price Algorithm for the Vehicle Routing Problem with Roaming Delivery Locations

  • Oya Ekin Karasan
  • Gizem Ozbaygin
  • Martin Savelsbergh
  • Hande Yaman
    • Categories Integer Programming, Network Optimization, Transportation Tags , , , ,

    We study the vehicle routing problem with roaming delivery locations in which the goal is to find a least-cost set of delivery routes for a fleet of capacitated vehicles and in which a customer order has to be delivered to the trunk of the customer’s car during the time that the car is parked at … Read more

    Exact algorithms for bi-objective ring tree problems with reliability measures

  • Alessandro Hill
  • Silvia Schwarze
    • Categories Branch and Cut Algorithms, Multi-Criteria Optimization, Network Optimization Tags , , , , ,

    We introduce bi-objective models for ring tree network design with a focus on network reliability within telecommunication applications. Our approaches generalize the capacitated ring tree problem (CRTP) which asks for a partially reliable topology that connects customers with different security requirements to a depot node by combined ring and tree graphs. While the CRTP aims … Read more

    A Benders decomposition based framework for solving cable trench problems

  • Hatice Calik
  • Markus Leitner
  • Martin Luipersbeck
    • Categories Integer Programming, Network Optimization Tags , , ,

    In this work, we present an algorithmic framework based on Benders decomposition for the Capacitated p-Cable Trench Problem with Covering. We show that our approach can be applied to most variants of the Cable Trench Problem (CTP) that have been considered in the literature. The proposed algorithm is augmented with a stabilization procedure to accelerate … Read more

    Improving Benders decomposition via a non-linear cut selection procedure

  • R.S. Camargo
  • F. M. S. Lima
  • G. Miranda
    • Categories Applications - OR and Management Sciences, Cutting Plane Approaches, Network Optimization

    A non-linear lifting procedure is proposed to generate high density Benders cuts. The new denser cuts cover more master problem variables than traditional Benders cuts, shortening the required number of iterations to reach optimality, and speeding up the Benders decomposition algorithm. To lessen the intricacy stemmed from the non-linearity, a simple outer approximation lineariza- tion … Read more

    A dual-ascent-based branch-and-bound framework for the prize-collecting Steiner tree and related problems

  • Markus Leitner
  • Ivana Ljubić
  • Martin Luipersbeck
  • Markus Sinnl
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags , , , ,

    In this work we present a branch-and-bound (B&B) framework for the asymmetric prize-collecting Steiner tree problem (APCSTP). Several well-known network design problems can be transformed to the APCSTP, including the Steiner tree problem (STP), prize-collecting Steiner tree problem (PCSTP), maximum-weight connected subgraph problem (MWCS) and the node-weighted Steiner tree problem (NWSTP). The main component of … Read more

    Lagrangian and Branch-and-Cut Approaches for Upgrading Spanning Tree Problems

  • Eduardo Alvarez-Miranda
  • Markus Sinnl
    • Categories Branch and Cut Algorithms, Network Optimization, Telecommunications

    Problems aiming at finding budget constrained optimal upgrading schemes to improve network performance have received attention over the last two decades. In their general setting, these problems consist of designing a network and, simultaneously, allocating (limited) upgrading resources in order to enhance the performance of the designed network. In this paper we address two particular … Read more

    Risk Averse Shortest Path Interdiction

  • Siqian Shen
  • Yongjia Song
    • Categories 0-1 Programming, Network Optimization, Stochastic Programming

    We consider a Stackelberg game in a network, where a leader minimizes the cost of interdicting arcs and a follower seeks the shortest distance between given origin and destination nodes under uncertain arc traveling cost. In particular, we consider a risk-averse leader, who aims to keep high probability that the follower’s traveling distance is longer … Read more

    An O(nm) time algorithm for finding the min length directed cycle in a graph

  • James B. Orlin
  • Antonio Sedeño-Noda
    • Categories Graphs and Matroids, Network Optimization, Optimization Software and Modeling Systems Tags , ,

    In this paper, we introduce an $O(nm)$ time algorithm to determine the minimum length directed cycle in a directed network with $n$ nodes and $m$ arcs and with no negative length directed cycles. This result improves upon the previous best time bound of $O(nm + n^2 \log\log n)$. Our algorithm first determines the cycle with … Read more

    ExtraPush for Convex Smooth Decentralized Optimization over Directed Networks

  • Wotao Yin
  • Jinshan Zeng
    • Categories Network Optimization, Nonlinear Optimization Tags , , , ,

    In this note, we extend the existing algorithms Extra and subgradient-push to a new algorithm ExtraPush for convex consensus optimization over a directed network. When the network is stationary, we propose a simplified algorithm called Normalized ExtraPush. These algorithms use a fixed step size like in Extra and accept the column-stochastic mixing matrices like in … Read more