Mauricio G.C. Resende We describe FORTRAN subroutines for network flow optimization using an interior point network flow algorithm. We provide FORTRAN and C language drivers, as well as C language functions that, together with the subroutines, make up PDNET (Portugal, Resende, Veiga, and Júdice, 2000). The algorithm is described in detail and its implementation is outlined. Usage of … Read more
This paper presents an annotated bibliography of greedy randomized adaptive search procedures (GRASP). The bibliography is current up to early 2004. The bibliography contains: background material; tutorials and surveys; enhancements to the basic method; hybrid methods; software; parallel GRASP; graph theory; quadratic and other assignment problems; location, layout, and cutting; covering, clustering, packing, and partitioning; … Read more
A Greedy Randomized Adaptive Search Procedure (GRASP) is a metaheuristic for combinatorial optimization. It usually consists of a construction procedure based on a greedy randomized algorithm and local search. Path-relinking is an intensification strategy that explores trajectories that connect high quality solutions. We analyze two parallel strategies for GRASP with path-relinking and propose a criterion … Read more
This document contains references related to GRASP (greedy randomized adaptive search procedure) that have either appeared in the literature or as technical reports. If you are aware of any uncited reference, incorrectly cited reference, or update to a cited reference, please contact Mauricio G. C. Resende at the address given at the end of this … Read more
A greedy randomized adaptive search procedure (GRASP) is a multi-start metaheuristic which applies local search to starting solutions generated by a greedy randomized construction procedure. Until recently, most implementations of GRASP assumed independence of its iterations, thus making no use of memory structures. Path-relinking is an intensification strategy which explores trajectories between elite solutions. Using … Read more
Dynamic shortest path algorithms update the shortest paths to take into account a change in an edge weight. This paper describes a new technique that allows the reduction of heap sizes used by several dynamic shortest path algorithms. For unit weight change, the updates can be done without heaps. These reductions almost always reduce the … Read more
We present a multistart heuristic for the uncapacitated facility location problem, based on a very successful method we originally developed for the P-median problem. We show extensive empirical evidence to the effectiveness of our algorithm in practice. For most benchmarks instances in the literature, we obtain solutions that are either optimal or a fraction of … Read more
We present a new implementation of a widely used swap-based local search procedure for the P-median problem, proposed in 1968 by Teitz and Bart. Our method produces the same output as the best alternatives described in the literature and, even though it does not have a better worst-case complexity, it can be significantly faster in … Read more
Given N customers and a set F of M potential facilities, the P-median problem consists in finding a subset of F with P facilities such that the cost of serving all customers is minimized. This is a well-known NP-complete problem with important applications in location science and classification (clustering). We present a multistart hybrid heuristic … Read more
Intra-domain traffic engineering aims to make more efficient use of network resources within an autonomous system. Interior Gateway Protocols such as OSPF (Open Shortest Path First) and IS-IS (Intermediate System-Intermediate System) are commonly used to select the paths along which traffic is routed within an autonomous system. These routing protocols direct traffic based on link … Read more