Theorems Supporting r-flip Search for Pseudo-Boolean Optimization

Bahram Alidaee, Gary Kochenberger and Haibo Wang
Additional contact information
Bahram Alidaee: University of Mississippi, USA
Gary Kochenberger: University of Colorado Denver, USA
Haibo Wang: Texas A&M International University, USA

International Journal of Applied Metaheuristic Computing (IJAMC), 2010, vol. 1, issue 1, 93-109

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.

Date: 2010
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 4018/jamc.2010102605 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jamc00:v:1:y:2010:i:1:p:93-109

Access Statistics for this article

International Journal of Applied Metaheuristic Computing (IJAMC) is currently edited by Peng-Yeng Yin

More articles in International Journal of Applied Metaheuristic Computing (IJAMC) from IGI Global
Bibliographic data for series maintained by Journal Editor ().