Eduardo Uchoa

New Lower Bounds for the Vehicle Routing Problem with Simultaneous Pickup and Delivery

  • Luiz Satoru Ochi
  • Anand Subramanian
  • Eduardo Uchoa
    • Categories Branch and Cut Algorithms, Production and Logistics, Transportation Tags , ,

    This work deals with the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD). We propose undirected and directed two-commodity flow formulations, which are based on the one developed by Baldacci, Hadjiconstantinou and Mingozzi for the Capacitated Vehicle Routing Problem. These new formulations are theoretically compared with the one-commodity flow formulation proposed by Dell’Amico, Righini … Read more

    Algorithms over Arc-time Indexed Formulations for Single and Parallel Machine Scheduling Problems

  • Artur Alves Pessoa
  • Marcus Poggi de Aragão
  • Eduardo Uchoa
  • Rosiane Rodrigues
    • Categories Integer Programming, Scheduling Tags , , ,

    This paper presents algorithms for single and parallel identical machine scheduling problems. While the overall algorithm can be viewed as a branch-cut-and-price over a very large extended formulation, a number of auxiliary techniques are necessary to make the column generation effective. Those techniques include a powerful fixing by reduced costs and a new proposed dual … Read more

    Modelling Hop-Constrained and Diameter-Constrained Minimum Spanning Tree Problems as Steiner Tree Problems over Layered Graphs

  • Luís Gouveia
  • Eduardo Uchoa
  • Luidi Simonetti
    • Categories Branch and Cut Algorithms, Network Optimization Tags ,

    The Hop-Constrained Minimum Spanning Tree Problem (HMSTP) is a NP-hard problem arising in the design of centralized telecommunication networks with quality of service constraints. We show that the HMSTP is equivalent to a Steiner Tree Problem (STP) in an adequate layered graph. We prove that the directed cut formulation for the STP defined in the … Read more

    A Robust Branch-Cut-and-Price Algorithm for the Heterogeneous Fleet Vehicle Routing Problem

  • Artur Alves Pessoa
  • Marcus Poggi de Aragão
  • Eduardo Uchoa
    • Categories Combinatorial Optimization, Transportation Tags , ,

    This paper presents a robust branch-cut-and-price algorithm for the Heterogeneous Fleet Vehicle Routing Problem (HFVRP), vehicles may have distinct capacities and costs. The columns in the formulation are associated to q-routes, a relaxation of capacitated elementary routes that makes the pricing problem solvable in pseudo-polynomial time. Powerful new families of cuts are also proposed, which … Read more

    Robust Branch-Cut-and-Price Algorithms for Vehicle Routing Problems

  • Artur Alves Pessoa
  • Marcus Poggi de Aragão
  • Eduardo Uchoa
    • Categories Combinatorial Optimization, Transportation

    This article presents techniques for constructing robust Branch-Cutand-Price algorithms on a number of Vehicle Routing Problem variants. The word “robust” stress the effort of controlling the worst-case complexity of the pricing subproblem, keeping it pseudo-polynomial. Besides summarizing older research on the topic, some promising new lines of investigation are also presented, specially the development of … Read more

    A Robust Branch-Cut-and-Price Algorithm for the Heterogeneous Fleet Vehicle Routing Problem

  • Artur Alves Pessoa
  • Marcus Poggi de Aragão
  • Eduardo Uchoa
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming, Transportation Tags , ,

    This paper presents a robust branch-cut-and-price algorithm for the Heterogeneous Fleet Vehicle Routing Problem (HFVRP), vehicles may have various capacities and fixed costs. The columns in the formulation are associated to $q$-routes, a relaxation of capacitated elementary routes that makes the pricing problem solvable in pseudo-polynomial time. Powerful new families of cuts are also proposed, … Read more

    Robust Branch-Cut-and-Price for the Capacitated Minimum Spanning Tree Problem over a Large Extended Formulation

  • Diogo V. Andrade
  • Ricardo Fukasawa
  • Artur Alves Pessoa
  • Marcus Poggi de Aragão
  • Eduardo Uchoa
  • Jens Lysgaard
    • Categories Cutting Plane Approaches Tags , ,

    This paper presents a robust branch-cut-and-price algorithm for the Capacitated Minimum Spanning Tree Problem (CMST). The variables are associated to $q$-arbs, a structure that arises from a relaxation of the capacitated prize-collecting arborescence probem in order to make it solvable in pseudo-polynomial time. Traditional inequalities over the arc formulation, like Capacity Cuts, are also used. … Read more

    Stabilized Branch-and-cut-and-price for the Generalized Assignment Problem

  • Alexandre Pigatti
  • Marcus Poggi de Aragão
  • Eduardo Uchoa
    • Categories Branch and Cut Algorithms, Meta Heuristics, Scheduling Tags , , ,

    The Generalized Assignment Problem (GAP) is a classic scheduling problem with many applications. We propose a branch-and-cut-and-price for that problem featuring a stabilization mechanism to accelerate column generation convergence. We also propose ellipsoidal cuts, a new way of transforming the exact algorithm into a powerful heuristic, in the same spirit of the cuts recently proposed … Read more

    Reduction Tests for the Prize-Collecting Steiner Problem

  • Eduardo Uchoa
    • Categories Applications - OR and Management Sciences, Integer Programming, Telecommunications Tags , ,

    The Prize-Collecting Steiner Problem (PCSP) is a generalization of the classical Steiner Problem in Graphs (SPG) where instead of terminal vertices that must be necessarily connected, one have profits associated to the vertices that must be balanced against the connection costs. This problem is gaining much attention in the last years due to its practical … Read more

    A Grid-Enabled Distributed Branch-and-Bound Algorithm with

  • Clicia Castro
  • Lucia Drummond
  • Eduardo Uchoa
  • José Viterbo
    • Categories Parallel Algorithms Tags , ,

    This work introduces a distributed branch-and-bound algorithm to be run on computational Grids. Grids are often organized in a hierarchical fashion: clusters of processors connected via high-speed links, while the clusters themselves are geographically distant and connected through slower links. Our algorithm does not employ the usual master-worker paradigm and it considers the hierarchical structure … Read more