GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES: ADVANCES AND APPLICATIONS (2009)
Mauricio G. C, Celso C. Ribeiro
Abstract. GRASP is a multi-start metaheuristic for combinatorial optimization problems, in which each iteration consists basically of two phases: construction and local search. The construction phase...
Scheduling the Brazilian soccer tournament with fairness and broadcast objectives (2008)
Celso C. Ribeiro, Sebastián Urrutia
Abstract. The Brazilian soccer tournament is organized every year by the Brazilian Soccer Confederation. Its major sponsor is TV Globo, the largest media group and television network in Brazil, who...
Referee Assignment in Sports Leagues (2008)
Alexandre R. Duarte, Edward H. Haeusler, Celso C. Ribeiro, Sebastián Urrutia
Optimization in sports is a field of increasing interest. Combinatorial optimization techniques have been applied e.g. to game scheduling and playoff elimination. A common problem usually found in...
GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES (2008)
Mauricio G. C, Celso C. Ribeiro
Abstract. GRASP is a multi-start metaheuristic for combinatorial problems, in which each iteration consists basically of two phases: construction and local search. The construction phase builds a...
A GRASP WITH PATH-RELINKING FOR PRIVATE VIRTUAL CIRCUIT ROUTING (2008)
Mauricio G. C, Celso C. Ribeiro
Abstract. 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....
A Branch-and-Cut Algorithm for the Partition Coloring Problem (2008)
Yuri Frota, Nelson Maculan, Thiago F. Noronha, Celso C. Ribeiro
Let G = (V, E) be an undirected graph, where E is the set of edges and V is the set of vertices. Furthermore, let Q = {Q1,..., Qq} be a partition of V into q subsets such that Q1 ∪... ∪ Qq = V...
Constraint Programming for the Diameter Constrained Minimum Spanning Tree Problem (2008)
Thiago F. Noronha, Andréa C. Santos, Celso C. Ribeiro
Given an undirected connected graph G = (V,E) with a set V of vertices, a set E of edges, and costs cij associated to every edge [i,j] ∈ E, with i < j, the Diameter Minimum Spanning Tree Problem...
PARALLEL GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES (2008)
Mauricio G. C, Celso C. Ribeiro
ABSTRACT. A GRASP (Greedy Randomized Adaptive Search Procedure) is a metaheuristic for producing good-quality solutions of combinatorial optimization problems. It is usually implemented with a...
A branch-and-cut algorithm for scheduling the highly-constrained Chilean soccer tournament (2008)
Thiago F. Noronha, Celso C. Ribeiro, Guillermo Duran, Sebastian Souyris, Andres Weintraub
Abstract. The Chilean soccer championship follows the structure of a compact single round robin tournament. Good schedules are of major importance for the success of the tournament, making them more...
Guillermo Durán, Thiago F. Noronha, Celso C. Ribeiro, Sebastián Souyris, Andrés Weintraub, Santiago Chile
for a real-life highly constrained
Branch-and-Cut for a Real-Life Highly Constrained (2008)
Soccer Tournament Scheduling, Guillermo Durán, Thiago F. Noronha, Celso C. Ribeiro, Sebastián Souyris, Andrés Weintraub
Introduction There are 20 teams in the Chilean soccer first division. They take part in two yearly tournaments: opening and closing. Each tournament is organized in two phases: qualifying and...
Departamento de Ciencia da Computac~ao (2007)
Alexandre Plastino, Celso C. Ribeiro
Recent work on load balancing has confirmed its importance when one wants to achieve good performances during the actual evaluation of parallel database queries. Existing work mostly focuses on the...
A Column Generation Approach to Cell Formation Problems in Cellular Manufacturing (2007)
Brigitte Jaumard, Pascal Labit, Celso C. Ribeiro
Cellular manufacturing is a promising approach for grouping eciency in manufacturing systems. Although this problem has been extensively studied in the literature, very few authors have proposed...
Marcus Fontoura, Carlos J. Lucena, Alexandre Andreatta, Re Andreatta, Srgio E. Carvalho, Celso C. Ribeiro
Currently frameworks are most commonly represented through design diagrams written in standard objectoriented analysis and design languages. However, these design notations do not provide elements...
A framework for SPMD applications with load balancing (2007)
Alexandre Plastino, Celso C. Ribeiro, Noemi Rodriguez, Niteroi Brasil
This work describes SAMBA, a framework for the development of parallel SPMD applications with load balancing. SAMBA contains the structure common to different SPMD applications and a library of...
A Column Generation Approach to Cell Formation Problems in Cellular Manufacturing (2007)
Brigitte Jaumard, Pascal Labit, Celso C. Ribeiro
: Cellular manufacturing is a promising approach for grouping efficiency in manufacturing systems. Although this problem has been extensively studied in the literature, very few authors have proposed...
A GRASP WITH PATH-RELINKING FOR PERMANENT VIRTUAL CIRCUIT ROUTING (2007)
Mauricio G. C, Celso C. Ribeiro
Abstract. 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....
GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES (2007)
Mauricio G. C, Celso C. Ribeiro
Abstract. GRASP is a multi-start metaheuristic for combinatorial problems, in which each iteration consists basically of two phases: construction and local search. The construction phase builds a...
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
A Hybrid Improvement Heuristic for the Bin Packing Problem (2007)
Adriana C. F, Alvim Dario, J. Aloise, Fred Glover, Celso C. Ribeiro, E Do Norte
Given a set of n items with weights wi,i =1,...,n, the bin packing (BP) problem consists of finding
GRASP WITH PATH-RELINKING: RECENT ADVANCES AND APPLICATIONS (2007)
Mauricio G. C, Celso C. Ribeiro
ABSTRACT. Path-relinking is a major enhancement to the basic greedy randomized adaptive search procedure (GRASP), leading to significant improvements in solution time and quality. Path-relinking adds...
Abstract Efficient parallel cooperative implementations of GRASP heuristics (2007)
Celso C. Ribeiro, Isabel Rosseti
We propose a parallel cooperative strategy for the implementation of the GRASP metaheuristic and we illustrate it with a GRASP with path-relinking heuristic for the 2-path network design problem....
Celso C. Ribeiro, Rodrigo F. Toso
Abstract We consider the problem of maintaining a minimum spanning tree of a dynamically changing graph, subject to changes on edge weights. We propose an on-line fully-dynamic algorithm that runs in...
Referee assignment in sports tournaments (2006)
Alexandre R. Duarte, Celso C. Ribeiro, Sebastián Urrutia
Optimization in sports is a field of increasing interest. Some applications have been reviewed by Ribeiro and Urrutia [7]. Combinatorial optimization techniques have been applied e.g. to the...
Scheduling the Brazilian Soccer Championship (2006)
Celso Ribeiro And, Celso C. Ribeiro, Sebastián Urrutia
Introduction The yearly Brazilian Football Championship is the most important sport event in Brazil. It is organized by CBF (the Brazilian Football Confederation) and its major sponsor is TV Globo,...
GRASP with path-relinking: Recent advances and applications (2005)
Abstract: Path-relinking is a major enhancement to the basic greedy randomized adaptive search procedure (GRASP), leading to significant improvements in solution time and quality. Path-relinking adds...
An Efficient Implementation of a Joint Generation Algorithm (2004)
Boros, Endre, Elbassioni, Khaled, Gurvich, Vladimir, Khachiyan, Leonid, Ribeiro, Celso C., Martins, Simone L.
Let $\cC$ be an n-dimensional integral box, and $\pi$ be a monotone property defined over the elements of $\cC$. We consider the problems of incrementally generating jointly the families $\cF_{\pi}$...
Heuristics for the mirrored traveling tournament problem (2004)
Celso C. Ribeiro, Sebastian Urrutia
Abstract. Professional sports leagues are a major economic activity around the world. Teams and leagues do not want to waste their investments in players and structure in consequence of poor...
A hybrid improvement heuristic for the one-dimensional bin packing problem (2004)
Celso C. Ribeiro, Fred Glover, J. Aloise
Abstract. We propose in this work a hybrid improvement procedure for the bin packing problem. This heuristic has several features: the use of lower bounding strategies; the generation of initial...
A TABU SEARCH APPROACH FOR SOLVING A DIFFICULT FOREST HARVESTING MACHINE LOCATION PROBLEM (2004)
Jacques A. Ferl, Département Informatique, Recherche Opérationnelle, Celso C. Ribeiro
Abstract: This paper deals with two main problems in forest harvesting. The first is that of selecting the locations for the machinery to haul logs from the points where they are felled to the...
An Efficient Implementation of a Joint Generation Algorithm (2004)
Boros, Endre, Elbassioni, Khaled, Gurvich, Vladimir, Khachiyan, Leonid, Ribeiro, Celso C., Martins, Simone L.
Let $\cC$ be an n-dimensional integral box, and $\pi$ be a monotone property defined over the elements of $\cC$. We consider the problems of incrementally generating jointly the families $\cF_{\pi}$...
Scheduling workover rigs for onshore oil production (2003)
Dario J. Aloise, Daniel Aloise, Celso C. Ribeiro
Many oil wells in Brazilian onshore fields rely on artificial lift methods. Maintenance services such as cleaning, reinstatement, stimulation and others are essential to these wells. These services...
Strategies for the parallel implementation of metaheuristics (2002)
Van-dat Cung, Simone L. Martins, Celso C. Ribeiro, Catherine Roucairol
Abstract. Parallel implementationsof metaheuristicsappear quite naturally asan effective alternative to speed up the search for approximate solutions of combinatorial optimization problems. They not...
Fred Glover, Celso C. Ribeiro, J. Aloise
Abstract. We propose in this work a hybrid improvement procedure for the bin packing problem, based on the progressive increase of the number of bins used by a possibly feasible solution. This...
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...
Variable Neighborhood Search For The Degree-Constrained Minimum Spanning Tree Problem (2001)
Celso C. Ribeiro, Maurício C. Souza, C. Souza
. Given an undirected graph with weights associated with its edges, the degreeconstrained minimum spanning tree problem consists in finding a minimum spanning tree of the given graph, subject to...
A Path-Based Local Search Heuristic for the (2001)
Capacitated Minimum Spanning, Mauricio C. Souza, Christophe Duhamel, Celso C. Ribeiro
Introduction Let G =(V,E) be a connected undirected graph, where V = {0, 1,...,n} denotes the set of nodes and E is the set of edges. Non-negative integers c e and b i are associated respectively...
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...
GRASP and VNS for Max-Cut (2001)
Paola Festa Pardalos, P. M. Pardalos, Celso C. Ribeiro
Introduction and problem formulation The Max-Cut problem can be stated as follows: Given an undirected graph G =(V,E) and nonnegative weights w ij on the edges (i, j) E, i, j V , find a subset of...
Parallel Computing Environments (2001)
Celso C. Ribeiro, Noemi Rodriguez
Abstract: This article presents a survey of parallel computing environments available for the implementation of parallel algorithms for optimization problems. These parallel environments are composed...
Probability Distribution Of Solution Time In Grasp: An Experimental Investigation (2000)
Renata M. Aiex, Celso C. Ribeiro, C. Ribeiro
. A GRASP (greedy randomized adaptive search procedure) is a multi-start metaheuristic for combinatorial optimization. We study the probability distributions of solution time to a sub-optimal target...
Probability Distribution Of Solution Time In Grasp: An Experimental Investigation (2000)
Renata M. Aiex, Celso C. Ribeiro, C. Ribeiro
. A GRASP (greedy randomized adaptive search procedure) is a multi-start metaheuristic for combinatorial optimization. We study the probability distributions of solution time to a sub-optimal target...
Parallel Cooperative Approaches for the Labor Constrained Scheduling Problem (2000)
V. C. Cavalcante, Celso C. Ribeiro
In this paper we consider the labor constrained scheduling problem (LCSP), in which a set of jobs to be processed is subject to precedence and labor requirement constraints. Each job has a specified...
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...
Sorting Methods for Small Arrays (2000)
Renato F. Werneck, Celso C. Ribeiro
We present and compare four efficient quadratic, comparison-based algorithms for small arrays and (for three of them) almost sorted inputs. In addition to the well-known insertion sort and selection...
Sorting Methods for Small Arrays (2000)
Renato F. Werneck, Celso C. Ribeiro
We present and compare four ecient quadratic, comparison-based algorithms for small arrays and (for three of them) almost sorted inputs. In addition to the well-known insertion sort and selection...
A New Formulation for Scheduling Unrelated Processors under Precedence Constraints (1999)
Nelson Maculan, Celso C. Ribeiro, Cid Carvalho, De Souza, Communicated Catherine Roucairol
Abstract. – We give a new formulation for the problem of task scheduling into unrelated processors under precedence constraints. This formulation has a polynomial number of variables and does not...
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...
Reactive Tabu Search With Path Relinking For The Steiner Problem In Graphs (1999)
Marcelo P. Bastos, Celso C. Ribeiro, C. Ribeiro
. Given an undirected graph with weights associated with its edges, the Steiner tree problem consists in finding a minimum weight subgraph spanning a given subset of nodes (terminals) of the original...
Preprocessing Steiner Problems from VLSI Layout (1999)
Eduardo Uchoa Marcus, 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...
Heuristics For The Phylogeny Problem (1999)
Alexandre A. Andreatta, Celso C. Ribeiro
. A phylogeny is a tree that relates taxonomic units, based on their similarity over a set of characters. The problem of finding a phylogeny with the minimum number of evolutionary steps is one of...
Local Search For The Bin Packing Problem (1999)
Adriana Alvim, Fred S. Glover, Celso C. Ribeiro, DARIO J. ALOISE
. The bin packing problem consists in finding the minimum number of bins of given capacity which are necessary to pack a certain number of itens. In this work, we propose an improvement procedure for...
Greedy Randomized Adaptive Search Procedures For The Steiner Problem In Graphs (1999)
Simone L. Martins, Panos M. Pardalos, Celso C. Ribeiro, C. Ribeiro
. We describe four versions of a Greedy Randomized Adaptive Search Procedure (GRASP) for finding approximate solutions of general instances of the Steiner Problem in Graphs. Di#erent construction and...
Load Balancing Algorithms for SPMD Applications (1999)
Alexandre Plastino, Celso C. Ribeiro, Noemi Rodriguez
. This paper deals with the problem of load balancing in SPMD parallel applications. Based on the study of recent work in the area, we propose a taxonomy that provides a terminology and a framework...
A Tool for SPMD Application Development with Support for Load Balancing (1999)
Alexandre Plastino, Celso C. Ribeiro, Noemi Rodriguez
Introduction According to Quinn [Qui94], the SPMD (Single Program, Multiple Data) parallel programming model is equivalent to data parallelism when associated to MIMD (Multiple Instruction, Multiple...
Greedy Randomized Adaptive Search Procedures For The Steiner Problem In Graphs (1999)
Simone L. Martins, Panos M. Pardalos, Celso C. Ribeiro, C. Ribeiro
. We describe four versions of a Greedy Randomized Adaptive Search Procedure (GRASP) for finding approximate solutions of general instances of the Steiner Problem in Graphs. Different construction...
Algorithm 797: Fortran Subroutines for (1999)
Approximate Solution Of, Celso C. Ribeiro
this article are an implementation of that GRASP
Mauricio G. C, Celso C. Ribeiro
. We survey graph planarization and related problems. We first describe variants and applications of graph planarization. Then we focus on algorithms. We begin by describing the branch-and-cut...
Cooperative Multi-Thread Parallel Tabu Search with an Application to Circuit Partitioning (1998)
. In this work, we propose a cooperative multi-thread parallel tabu search heuristic for the circuit partitioning problem. This procedure is based on the cooperation of multiple search threads. Each...
A Parallel GRASP for the Steiner Problem in Graphs (1998)
Simone L. Martins, Celso C. Ribeiro, Mauricio C. Souza
A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. Given an undirected graph with weights associated with its nodes, the Steiner tree problem...
Mauricio G. C, Celso C. Ribeiro
this article, we survey graph planarization and related problems. In the next section, we describe variants and applications of the basic problem formulated above. Next, we describe the...
An Object-Oriented Framework For Local Search Heuristics (1998)
Alexandre A. Andreatta, Celso C. Ribeiro
: In the study of heuristics for combinatorial problems, it is often important to develop and compare, in a systematic way, different algorithms, strategies, and parameters for the same problem. This...
Reactive GRASP: An Application To A Matrix Decomposition Problem In TDMA Traffic Assignment (1998)
Marcelo Prais, Celso C. Ribeiro, C. Ribeiro
. A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. In this paper, we describe a GRASP for a matrix decomposition problem arising in the context...
Improved Tabu Search For The Steiner Problem In Graphs (1998)
. Given an undirected graph with weights associated with its nodes, the Steiner tree problem consists in finding a minimum weight subgraph spanning a given subset of nodes (terminals) of the original...
A Grasp For Graph Planarization (1997)
. A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. In this paper, we describe a GRASP for the graph planarization problem, extending the...
Alexandre A. Andreatta, Celso C. Ribeiro
: In the study of heuristics for combinatorial problems, it is often important to develop and compare, in a systematic way, different algorithms, strategies, and parameters for the same problem. The...
A Grasp For Graph Planarization (1997)
. A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. In this paper, we describe a GRASP for the graph planarization problem, extending the...
This paper presents parallelization strategies for a tabu search algorithm for the task scheduling problem on heterogeneous processors under task precedence constraints. Parallelization relies...
: We study in this paper different synchronous strategies for the parallel implementation of tabu search on a parallel machine. The task scheduling problem on heterogeneous processors under...
Performance Evaluation of a Parallel Tabu Search Task Scheduling Algorithm (1996)
Stella Porto Applied, F. W. Kitajima, Celso C. Ribeiro
This paper presents the solution quality analysis of a parallel tabu search algorithm for the task scheduling problem on heterogeneous processors under precedence constraints. We evaluate the...
Performance Evaluation of a Parallel Tabu Search Task Scheduling Algorithm (1996)
Stella Porto Applied, F. W. Kitajima, Celso C. Ribeiro
This paper presents the solution quality analysis of a parallel tabu search algorithm for the task scheduling problem on heterogeneous processors under precedence constraints. We evaluate the...
Performance Evaluation of a Parallel Tabu Search Task Scheduling Algorithm (1996)
Stella Porto Applied, F. W. Kitajima, Celso C. Ribeiro
This paper presents the solution quality analysis of a parallel tabu search algorithm for the task scheduling problem on heterogeneous processors under precedence constraints. We evaluate the...
Performance Evaluation of a Parallel Tabu Search Task Scheduling Algorithm (1996)
Stella Porto, F. W. Kitajima, Celso C. Ribeiro
This paper presents the solution quality analysis of a parallel tabu search algorithm for the task scheduling problem on heterogeneous processors under precedence constraints. We evaluate the...
Exploring Load Balancing in Parallel Processing of Recursive Queries (1996)
Sérgio Lifschitz, Alexandre Plastino, Celso C. Ribeiro
. We study a dose-driven dynamic load balancing strategy to evaluate database recursive queries. This proposal aims at obtaining a good workload balance with full use of the available resources, with...
Parallel Strategies for Task Scheduling Algorithms Using PVM (1995)
This paper presents parallelization strategies of a tabu search algorithm for the task scheduling problem on heterogeneous processors under task precedence constraints. Parallelization relies...
This paper presents parallelization strategies for a tabu search algorithm for the task scheduling problem on heterogeneous processors under task precedence constraints. Parallelization relies...
Alexandre Andreatta Celso, Celso C. Ribeiro
The logical test of integrated VLSI circuits is one of the main phases of their design and fabrication. The pseudo-exhaustive approach for the logical test of integrated circuits consists in...
Celso C. Ribeiro, Stella C. S, Porto Celso, C. Ribeiro
Parallel programs may be represented as a set of interrelated sequential tasks. When multiprocessors are used to execute such programs, the parallel portion of the application can be speeded up by an...
A tabu search approach for solving a difficult forest harvesting machine location problem
Legues, Andres Diaz, Ferland, Jacques A., Ribeiro, Celso C., Vera, Jorge R., Weintraub, Andres
An efficient implementation of a VNS/ILS heuristic for a real-life car sequencing problem
Ribeiro, Celso C., Aloise, Daniel, Noronha, Thiago F., Rocha, Caroline, Urrutia, Sebastián
The car sequencing problem consists in sequencing a given set of cars to be produced in a single day. We address one of the variants of this problem, in which the objective of minimizing the number...
Ribeiro, Celso C., Aloise, Daniel, Noronha, Thiago F., Rocha, Caroline, Urrutia, Sebastián
We address a multi-objective version of the car sequencing problem, which consists in sequencing a given set of cars to be produced in a single day, minimizing the number of violations of assembly...