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 |Pages: 17
DOI: 10.4018/jamc.2010102605
(Individual Articles)
No Current Special Offers


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.
Article Preview

Pseudo-Boolean Optimization

Let R be the set of reals, Z the set of integers, and jamc.2010102605.m01. For a positive integer n let jamc.2010102605.m02. Let jamc.2010102605.m03 be a binary vector and jamc.2010102605.m04complement of jamc.2010102605.m05for jamc.2010102605.m06 Define the set of literals to bejamc.2010102605.m07. Mappings jamc.2010102605.m08 are called Pseudo-Boolean functions. Since there is a one-to-one correspondence between subsets of V and the set of binary vectorsjamc.2010102605.m09, these functions are set functions. All Pseudo-Boolean functions can be uniquely represented as multi-linear polynomials of the form given below (see (Boros & Hammer, 2002), for a comprehensive discussion) where jamc.2010102605.m10is a weight associated with the setjamc.2010102605.m11:

Complete Article List

Search this Journal:
Volume 15: 1 Issue (2024)
Volume 14: 1 Issue (2023)
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