Artur Alves Pessoa

Solving bilevel combinatorial optimization as bilinear min-max optimization via a branch-and-cut algorithm

  • Artur Alves Pessoa
  • Michael Poss
  • Marcos Costa Roboredo
    • Categories Branch and Cut Algorithms Tags , , ,

    In this paper, we propose a generic branch-and -cut algorithm for a special class of bi-level combinatorial optimization problems. Namely, we study such problems that can be reformulated as bilinear min-max combinatorial optimization problems. We show that the reformulation can be efficiently solved by a branch-and-cut algorithm whose cuts represent the inner maximization feasibility set. … Read more

    A Branch-and-Bound Algorithm for the Close-Enough Traveling Salesman Problem

  • Walton Coutinho
  • Artur Alves Pessoa
  • Anand Subramanian
  • Roberto do Nascimento
    • Categories Combinatorial Optimization, Second-Order Cone Programming

    This paper deals with the Close-Enough Traveling Salesman Problem (CETSP). In the CETSP, rather than visiting the vertex (customer) itself, the salesman must visit a specific region containing such vertex. To solve this problem, we propose a simple yet effective exact algorithm, based on Branch-and-Bound and Second Order Cone Programming (SOCP). The proposed algorithm was … Read more

    Exact algorithms for the Traveling Salesman Problem with Draft Limits

  • Maria Battarra
  • Artur Alves Pessoa
  • Anand Subramanian
  • Eduardo Uchoa
    • Categories Branch and Cut Algorithms, Integer Programming Tags , , , ,

    This paper deals with the Traveling Salesman Problem (TSP) with Draft Limits (TSPDL), which is a variant of the well-known TSP in the context of maritime transportation. In this recently proposed problem, draft limits are imposed due to restrictions on the port infrastructures. Exact algorithms based on three mathematical formulations are proposed and their performance … Read more

    Algorithms for the Cross-dock Door Assignment Problem

  • Daniel Cardoso da Silva
  • Monique Guignard
  • Peter M. Hahn
  • Artur Alves Pessoa
    • Categories Applications - OR and Management Sciences, Approximation Algorithms, Transportation Tags , , ,

    In a cross-dock facility, goods are moved by forklift from incoming truck platforms (strip doors) to temporary holding areas and then to outgoing truck platforms (stack doors) or directly from strip doors to stack doors. Costs within the cross-dock may be minimized by appropriate assignment of strip doors to incoming trucks and stack doors to … Read more

    The Time Dependent Traveling Salesman Problem: Polyhedra and Algorithm

  • Hernan Abeledo
  • Ricardo Fukasawa
  • Artur Alves Pessoa
  • Eduardo Uchoa
    • Categories Branch and Cut Algorithms, Polyhedra Tags ,

    The Time Dependent Traveling Salesman Problem (TDTSP) is a generalization of the classical Traveling Salesman Problem (TSP), where arc costs depend on their position in the tour with respect to the source node. While TSP instances with thousands of vertices can be solved routinely, there are very challenging TDTSP instances with less than 100 vertices. … 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

    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

    An Improved Algorithm for the Generalized Quadratic Assignment Problem

  • Monique Guignard
  • Peter M. Hahn
  • Artur Alves Pessoa
  • Yi-Rong Zhu
    • Categories 0-1 Programming, Combinatorial Optimization Tags , ,

    In the Generalized Quadratic Assignment Problem (GQAP), given M facilities and N locations, one must assign each facility to one location so as to satisfy the given facility space requirements, minimizing the sum of installation and facility interaction costs. In this paper, we propose a new Lagrangean relaxation and a lower bounding procedure for 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, 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