Reference Hub11
Theorems Supporting r-flip Search for Pseudo-Boolean Optimization

Theorems Supporting r-flip Search for Pseudo-Boolean Optimization

Bahram Alidaee, Gary Kochenberger, Haibo Wang
Copyright: © 2010 |Volume: 1 |Issue: 1 |Pages: 17
ISSN: 1947-8283|EISSN: 1947-8291|ISSN: 1947-8283|EISBN13: 9781616929664|EISSN: 1947-8291|DOI: 10.4018/jamc.2010102605
Cite Article Cite Article

MLA

Alidaee, Bahram, et al. "Theorems Supporting r-flip Search for Pseudo-Boolean Optimization." IJAMC vol.1, no.1 2010: pp.93-109. http://doi.org/10.4018/jamc.2010102605

APA

Alidaee, B., Kochenberger, G., & Wang, H. (2010). Theorems Supporting r-flip Search for Pseudo-Boolean Optimization. International Journal of Applied Metaheuristic Computing (IJAMC), 1(1), 93-109. http://doi.org/10.4018/jamc.2010102605

Chicago

Alidaee, Bahram, Gary Kochenberger, and Haibo Wang. "Theorems Supporting r-flip Search for Pseudo-Boolean Optimization," International Journal of Applied Metaheuristic Computing (IJAMC) 1, no.1: 93-109. http://doi.org/10.4018/jamc.2010102605

Export Reference

Mendeley
Favorite Full-Issue Download

Abstract

Modern metaheuristic methodologies rely on well defined neighborhood structures and efficient means for evaluating potential moves within these structures. Move mechanisms range in complexity from simple 1-flip procedures where binary variables are “flipped” one at a time, to more expensive, but more powerful, r-flip approaches where “r” variables are simultaneously flipped. These multi-exchange neighborhood search strategies have proven to be effective approaches for solving a variety of combinatorial optimization problems. In this paper, we present a series of theorems based on partial derivatives that can be readily adopted to form the essential part of r-flip heuristic search methods for Pseudo-Boolean optimization. To illustrate the use of these results, we present preliminary results obtained from four simple heuristics designed to solve a set of Max 3-SAT problems.

Request Access

You do not own this content. Please login to recommend this title to your institution's librarian or purchase it from the IGI Global bookstore.