Theorems Supporting r-flip Search for Pseudo-Boolean Optimization

Theorems Supporting r-flip Search for Pseudo-Boolean Optimization

Bahram Alidaee (University of Mississippi, USA), Gary Kochenberger (University of Colorado Denver, USA) and Haibo Wang (Texas A&M International University, USA)
Copyright: © 2010 |Pages: 17
DOI: 10.4018/jamc.2010102605

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

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:
Reset
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2020): 1 Released, 3 Forthcoming
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