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

Pseudo-Boolean Optimization

Let R be the set of reals, Z the set of integers, and . For a positive integer n let . Let be a binary vector and complement of for Define the set of literals to be. Mappings are called Pseudo-Boolean functions. Since there is a one-to-one correspondence between subsets of V and the set of binary vectors, 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 is a weight associated with the set:

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): 1 Released, 3 Forthcoming
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