Conditional Markov Chain Search for the Simple Plant Location Problem Improves Upper Bounds on Twelve Körkel–Ghosh Instances

Daniel Karapetyan and Boris Goldengorin
Additional contact information
Daniel Karapetyan: University of Essex
Boris Goldengorin: University of Baltimore

A chapter in Optimization Problems in Graph Theory, 2018, pp 123-147 from Springer

Abstract: Abstract We address a family of hard benchmark instances for the Simple Plant Location Problem (also known as the Uncapacitated Facility Location Problem). The recent attempt by Fischetti et al. Manag Sci 63(7): 2146–2162 (2017) to tackle the Körkel–Ghosh instances resulted in seven new optimal solutions and 22 improved upper bounds. We use automated generation of heuristics to obtain a new algorithm for the Simple Plant Location Problem. In our experiments, our new algorithm matched all the previous best known and optimal solutions, and further improved 12 upper bounds, all within shorter time budgets compared to the previous efforts. Our algorithm design process is split into two phases: (1) development of algorithmic components such as local search procedures and mutation operators, and (2) composition of a metaheuristic from the available components. Phase (1) requires human expertise and often can be completed by implementing several simple domain-specific routines known from the literature. Phase (2) is entirely automated by employing the Conditional Markov Chain Search (CMCS) framework. In CMCS, a metaheuristic is flexibly defined by a set of parameters, called configuration. Then the process of composition of a metaheuristic from the algorithmic components is reduced to an optimisation problem seeking the best performing CMCS configuration. We discuss the problem of comparing configurations, and propose a new efficient technique to select the best performing configuration from a large set. To employ this method, we restrict the original CMCS to a simple deterministic case that leaves us with a finite and manageable number of meaningful configurations.

Date: 2018
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-319-94830-0_7

Ordering information: This item can be ordered from
http://www.springer.com/9783319948300

DOI: 10.1007/978-3-319-94830-0_7

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().