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)
DOI: 10.4018/978-1-4666-0270-0.ch016
OnDemand PDF Download:
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.
Chapter Preview

Pseudo-Boolean Optimization

Let R be the set of reals, Z the set of integers, and 978-1-4666-0270-0.ch016.m01. For a positive integer n let 978-1-4666-0270-0.ch016.m02. Let 978-1-4666-0270-0.ch016.m03 be a binary vector and 978-1-4666-0270-0.ch016.m04complement of 978-1-4666-0270-0.ch016.m05for 978-1-4666-0270-0.ch016.m06 Define the set of literals to be978-1-4666-0270-0.ch016.m07. Mappings 978-1-4666-0270-0.ch016.m08 are called Pseudo-Boolean functions. Since there is a one-to-one correspondence between subsets of V and the set of binary vectors978-1-4666-0270-0.ch016.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 978-1-4666-0270-0.ch016.m10is a weight associated with the set978-1-4666-0270-0.ch016.m11:

Complete Chapter List

Search this Book: