The Steiner Problem in Graphs (SPG) is defined as follows. Given an undirected graph G = (V, E), positive edge costs c and a set T ⊆ V of terminal nodes, find a connected subgraph (V ′ , E ′ )...
Dual-Ascent Distribuído para Multicast com Restrição de Saltos (2008)
Marcelo Santos, Eduardo Uchoa, Luidi Simonetti
The directed Steiner Problem consists in finding a minimum cost tree that reaches a subset of nodes of a graph from a root node r. It is frequently used to model the multicast routing problem. The...
Uchoa, Eduardo, Fukasawa, Ricardo, Lysgaard, Jens, Pessoa, Artur, Poggi De Aragão, Marcus, Andrade, Diego
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...
Departamento de Engenharia Eletrica, Pontifcia Universidade Catolica do Rio (2007)
Ricardo Fukasawa, Marcus Vinicius, Eduardo Uchoa
A pervasive problem in freight railroad operations is to determine a feasible ow of cars to meet the required demands within a certain period of time. In this work we present a method to determine an...
Abstract: Consider the problem of routing the electrical connections among two large terminal sets in circuit layout. A realistic model for this problem is given by the vertex-disjoint packing of two...
Marcus Poggi de Arag~ao (2007)
Isabel Rosseti, Celso C. Ribeiro, Eduardo Uchoa, Renato F. Werneck
Let G = (V; E) be a connected undirected graph, where V is the set of nodes and E denotes the set of edges. Given a non-negative weight function w: E! IR + associated with its edges and a subset
Uchoa, Eduardo, Fukasawa, Ricardo, Lysgaard, Jens, Pessoa, Artur, Poggi De Aragão, Marcus, Andrade, Diogo
nullThis 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...
Solving Routing Problems with Branch-Cut-and-Price (2005)
Dep. De Informática, Católica Rio Janeiro, Eduardo Uchoa
The Capacitated Vehicle Routing Problem (CVRP) is the most basic variant of a vehicle routing problem: homogeneous fleet, single depot, only deliveries, no time-windows, and a one-dimensional...
Reduction Tests for the Prize-Collecting Steiner Problem (2005)
This article introduces a proper redefinition of the concept of bottleneck Steiner distance for the Prize-Collecting Steiner Problem. This allows the application of reduction tests known to be...
Stabilized Branch-and-cutand-price for the Generalized Assignment Problem (2005)
The Generalized Assignment Problem (GAP) is a classic scheduling problem with many applications. We propose a branch-and-cut-andprice for that problem featuring a stabilization mechanism to...
Robust branch-and-cut-and-price for the capacitated vehicle routing problem (2003)
Ricardo Fukasawa, Marcelo Reis, Eduardo Uchoa, Ricardo Fukasawa, ...
During the eigthies and early nineties, the best exact algorithms for the Capacitated Vehicle Routing Problem (CVRP) utilized lower bounds obtained by Lagrangean relaxation or column generation....
Integer Program Reformulation for Robust Branch-and-Cut-and-Price Algorithms (2003)
Since cut and column generation were established as two of the most important techniques in integer programming, researchers have looked for ways of combining them into a robust...
Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem (2003)
Ricardo Fukasawa, Jens Lysgaard, Marcelo Reis, Marcus Poggi, Aragão Marcelo Reis, ...
The best exact algorithms for the capacitated Vehicle Routing Problem (CVRP) have been based on either branch-and-cut or Lagrangean relaxation/column generation. This paper presents an algorithm that...
Robust branch-and-cut-and-price for the capacitated vehicle routing problem (2003)
Ricardo Fukasawa, Jens Lysgaard, Marcelo Reis, Eduardo Uchoa, Renato F. Werneck
Abstract. The best exact algorithms for the Capacitated Vehicle Routing Problem (CVRP) have been based on either branch-and-cut or Lagrangean relaxation/column generation. This paper presents an...
New benchmark instances for the Steiner problem in graphs (2001)
Isabel Rosseti, Celso C. Ribeiro, Eduardo Uchoa, Renato F. Werneck
Abstract. We propose in this work 50 new test instances for the Steiner problem in graphs. These instances are characterized by large integrality gaps (between the optimal integer solution and that...
A hybrid GRASP with perturbations for the Steiner problem in graphs (2001)
Celso C. Ribeiro, Eduardo Uchoa, Renato F. Werneck
We propose and describe a hybrid GRASP with weight perturbations and adaptive pathrelinking heuristic (HGP+PR) for the Steiner problem in graphs. In this multi-start approach, the greedy randomized...
Hybrid local search for the Steiner problem in graphs (2001)
Celso C. Ribeiro, Eduardo Uchoa, Renato F. Werneck
Let G = (V; E) be a connected undirected graph, where V is the set of nodes and E denotes the set of edges. Given a non-negative weight function w: E! IR + associated with its edges and a subset
A hybrid GRASP with perturbations for the Steiner problem in graphs (2001)
Celso C. Ribeiro, Eduardo Uchoa, F. Werneck
Abstract. We propose and describe a hybrid GRASP with weight perturbations and adaptive path-relinking heuristic (HGP+PR) for the Steiner problem in graphs. In this multi-start approach, the greedy...
A hybrid GRASP with perturbations for the Steiner problem in graphs (2001)
Celso C. Ribeiro, Eduardo Uchoa, F. Werneck
Abstract. We propose and describe a hybrid GRASP with weight perturbations and adaptive path-relinking heuristic (HGP-PR) for the Steiner problem in graphs. In this multi-start approach, the greedy...
New Benchmark Instances for the Steiner Problem in Graphs (2001)
Isabel Rosseti Marcus, Marcus Poggi, Aragão Celso, C. Ribeiro, Eduardo Uchoa, Renato F. Werneck
This paper proposes three new series of benchmark instances that will hopefully lead to a better assessment of exact and approximate algorithms for the SPG. Even though some of them are somewhat...
Hybrid Local Search for the Steiner Problem in Graphs (2001)
Celso C. Ribeiro, Marcus Poggi, Aragão Celso, C. Ribeiro, Eduardo Uchoa, ...
Introduction Let G =(V,E) be a connected undirected graph, where V is the set of nodes and E denotes the set of edges. Given a non-negative weight function w : E IR + associated with its edges and a...
Celso C. Ribeiro, Eduardo Uchoa, Renato F. Werneck
We propose and describe a hybrid GRASP with weight perturbations and adaptive path-relinking heuristic (HGP-PR) for the Steiner problem in graphs. In this multi-start approach, the greedy randomized...
Preprocessing Steiner problems from VLSI layout (1999)
Abstract: VLSI layout applications yield instances of the Steiner tree problem over grid graphs with holes, which are considered hard to be solved by current methods. In particular, preprocessing...
Preprocessing Steiner problems from VLSI layout (1999)
Eduardo Uchoa, Celso C. Ribeiro
VLSI layout applications yield instances of the Steiner tree problem over grid graphs with holes, which are considered hard to be solved by current methods. In particular, preprocessing techniques...
Vertex-Disjoint Packing of Two Steiner Trees: Polyhedra and Branch-and-Cut (1999)
. Consider the problem of routing the electrical connections among two large terminal sets in circuit layout. A realistic model for this problem is given by the vertex-disjoint packing of two Steiner...
Preprocessing Steiner Problems from VLSI Layout (1999)
: VLSI layout applications yield instances of the Steiner tree problem over grid graphs with holes, which are considered hard to be solved by current methods. In particular, preprocessing techniques...
Vertex-Disjoint Packing of Two Steiner Trees: Polyhedra and Branch-and-Cut (1999)
. Consider the problem of routing the electrical connections among two large terminal sets in circuit layout. A realistic model for this problem is given by the vertex-disjoint packing of two Steiner...
The γ-Connected Assignment Problem (1998)
Given a graph and costs of assigning to each vertex one of K different colors, we want to find a minimum cost assignment such that no color induces a subgraph with more than a given number (γ_k) of...
The gamma-Connected Assignment Problem (1998)
Given a graph and costs of assigning to each vertex one of k different colors, we want to find a minimum cost assignment such that no color q induces a subgraph with more than a given number (fl q )...
Uchoa, Eduardo, Fukasawa, Ricardo, Lysgaard, Jens, Pessoa, Artur, Poggi De Aragão, Marcus, Andrade, Diogo
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...
A facility location and installation of resources model for level of repair analysis
Brick, Eduardo Siqueira, Uchoa, Eduardo
The Level of Repair Analysis - LORA - is an analytic methodology aimed at determining: (i) the optimal location of facilities that compose a maintenance structure; (ii) the quantity of required...