Exterior Path Relinking for Zero-One Optimization

Exterior Path Relinking for Zero-One Optimization

Fred Glover (ECEE, School of Engineering & Science, University of Colorado, Boulder, CO, USA)
Copyright: © 2014 |Pages: 8
DOI: 10.4018/ijamc.2014070101
OnDemand PDF Download:
No Current Special Offers


Path relinking (PR) maintains a reference set of elite and diverse solutions, and generates new solutions between and beyond initiating and guiding solutions selected from this set as a foundation for an evolutionary solution process. However, in spite of the widespread application of path relinking in combinatorial optimization, almost all PR implementations only consider the between-form of PR. This note discusses the beyond-form of path relinking, which is called Exterior Path Relinking, and focuses on its relevance for diversification strategies in binary optimization. Finally, this work also observes how to combine the Exterior (beyond) and Interior (between) forms of path relinking.
Article Preview

1. Introduction

Path relinking (PR) creates combinations of solutions by a process of generating paths between selected points in neighborhood space. The approach, as first suggested in Glover (1989) and then formalized and given the path relinking name in Glover and Laguna (1993), takes advantage of the path interpretation of solution combinations as a foundation for numerous applications in combinatorial optimization, as illustrated in the work of Reeves and Yamada (1998), Laguna and Marti (1999), Laguna and Marti (2003), Piñana et al. (2004), Ghamlouche, Crainic, and Gendreau (2004), James, Rego and Glover (2005), Glover, Ho and Gendreau (2006), Zhang and Lai (2006), Yagiura, Ibaraki and Glover (2006), Yagiura et al. (2007), Resende et al. (2010), Vallada and Ruiz (2010), Marti et al. (2011), Marinakis and Marinaki (2012), Ribeiro and Resende (2012), Wang et al. (2012), Marti and Sandoy (2012), Lai et al. (2013), Duarte, Martí and Gortazar (2013), Rahimi-Vahed et al. (2013), and Marti, Resende and Ribeiro (2013).

However, the principles of path relinking are somewhat broader than those employed in most of its implementations, and offer strategies for combinatorial and non-linear optimization that have not been fully examined. To clarify these aspects of PR we begin by reviewing a few observations from Glover (1996) that express the basic themes of path relinking and at the same time highlight the relevance of strategies that to date remain unexplored.

The character of paths generated by PR is easily specified by reference to attribute-based memory, as used in tabu search. In particular, it is only necessary to select moves in a neighborhood space that perform the following simple function: upon starting from an initiating solution, the moves must progressively introduce attributes contributed by a guiding solution (or reduce the distance between attributes of the initiating and guiding solutions). The process invites variation by interchanging the roles of the initiating and guiding solutions, inducing each to move simultaneously toward the other as a way of generating combinations. (When the goal for combining the solutions can be expressed as an optimization model, algorithmic processes may appropriately be incorporated to generate the moves.)

Complete Article List

Search this Journal:
Volume 13: 4 Issues (2022): 2 Released, 2 Forthcoming
Volume 12: 4 Issues (2021)
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing