Enjoy a 20% Discount on all IGI Global Books Browse Titles

Special Offers
- 20% Discount On All IGI Global Published Book Products Through the Online Bookstore
  In response to rapid inflation and global currency fluctuations, and in our continued effort to make diverse, equitable, and inclusive research more accessible, IGI Global is now offering a 20% discount on hardcover print book and e-book purchases through June 30, 2023, directly on IGI Global’s Online Bookstore. Hosted on the InfoSci^® platform, these titles feature no DRM, no additional cost for multi-user licensing, no embargo of content, full-text PDF & HTML format, and more. Discount is automatically added at checkout.
  Browse Titles
- 20% Discount on All IGI Global E-Book Purchases Through GOBI
  GOBI is currently offering a 20% discount on IGI Global e-Book purchases on GOBI (Publisher Direct), through June 30, 2023. A direct link to GOBI can be found on each book's webpage of the IGI Global Online Bookstore.
  Browse GOBI
- 20% Discount on All IGI Global E-Book Purchases Through OASIS
  OASIS is currently offering a 20% discount on IGI Global e-Book purchases (Publisher Direct) until June 30, 2023. A direct link to OASIS can be found on each book's webpage of the IGI Global Online Bookstore.
  Browse OASIS
- 20% Discount on All IGI Global E-Book Purchases Through Rialto
  Rialto is currently offering a 20% discount on IGI Global e-Book purchases (Publisher Direct) until June 30, 2023.
  Browse Books
- IGI Global E-Book Offer Through Proquest E-Book Central
  Right now, receive Unlimited Multi-User Licensing at the Single User price with no mark-up for all IGI Global e-books acquired on ProQuest's e-Book Central platform until June 30, 2023.
  Browse e-Book Central
- IGI Global e-Book Offer Through EBSCOhost
  Right now, receive Unlimited Multi-User Licensing at the Single User price with no mark-up for all IGI Global e-books acquired on EBSCOhost until June 30, 2023.
  Browse EBSCOhost
- Limited Time Offer: Retrospective Open Access is Discounted 20%
  Access and convert your previously published work through your through your IGI Global Portal Account. For a limited time, IGI Global is offering a 20% discount on all Retrospective Open Access conversions through June 30, 2023.
  Learn More
Books
- - Books by Subject
  - Business, Administration, & Management
  - Scientific, Technical, & Medical (STM)
  - Education
  - Books by Field
Journals
- - Journals
  - OnDemand Journal Articles
  - Journals by Subject
  - Business, Administration, & Management
  - Scientific, Technical, & Medical (STM)
  - Education
  - Journals by Field
e-Collections
Open Access
Publish with Us
Resources
- - Instructors
  - Course Adoption
  - Teaching Cases
  - K-12 Online Learning Collection
  - Authors and Editors
  - eEditorial Discovery^® System
  - Peer Review Process
  - Ethics and Malpractice
  - COPE Membership
  - Fair Use Policy
  - Open Access Publishing
  - FAQ
Catalogs
About Us
Newsroom

Theorems Supporting r-flip Search for Pseudo-Boolean Optimization

Bahram Alidaee, Gary Kochenberger, Haibo Wang

Source Title: International Journal of Applied Metaheuristic Computing (IJAMC) 1(1)

DOI: 10.4018/jamc.2010102605

OnDemand:

(Individual Articles)

Available

$29.50

Current Special Offers

No Current Special Offers

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 . 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: