Theorems Supporting r-flip Search for Pseudo-Boolean Optimization

View Sample PDF

Author(s): Bahram Alidaee (University of Mississippi, USA), Gary Kochenberger (University of Colorado Denver, USA)and Haibo Wang (Texas A&M International University, USA)
Copyright: 2012
Pages: 20
Source title: Modeling, Analysis, and Applications in Metaheuristic Computing: Advancements and Trends
Source Author(s)/Editor(s): Peng-Yeng Yin (Ming Chuan University, Taiwan)
DOI: 10.4018/978-1-4666-0270-0.ch016

Keywords: Algorithms / Artificial Intelligence / Computer Science & IT / Information Science Reference

Purchase

View Theorems Supporting r-flip Search for Pseudo-Boolean Optimization on the publisher's website for pricing and purchasing information.

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.

The IRMA Community

Research IRM

Theorems Supporting r-flip Search for Pseudo-Boolean Optimization

Purchase

Abstract

Related Content

IRMA Sponsors