The paper presents an account of the experimental study of five different algorithms for the Completely Unimodal Pseudoboolean Function (CUPBF) Optimization. CUPBFs satisfy the Hirsch's conjecture, but are not known (although conjectured) to be polynomial. We summarize known and new upper and lower bounds, describe methods of random CUPBFs generation, and use them to compare the algorithms.
Available as Postscript (909 kB)
Download BibTeX entry.