Technical Report 2001-017

Experiments with Iterative Improvement Algorithms on Completely Unimodal Hypercubes

Henrik Björklund, Viktor Petersson, and Sergei Vorobyov

August 2001


Completely unimodal (i.e., having a unique local minimum on every face) numberings of many-dimensional hypercubes are abstract versions of different optimization problems, like linear programming, decision problems for games, and abstract optimization problems. In this paper we investigate and compare the behaviors of seven iterative improvement algorithms:

1) the Greedy Single Switch Algorithm (GSSA),

2) the Random Single Switch Algorithm (RSSA),

3) the All Profitable Switches Algorithm (APSA),

4) the Random Multiple Switches Algorithm (RMSA),

5) Kalai-Ludwig's Randomized Algorithm (KLRA),

6) Weighted Random Multiple Switch Algorithm (WRMSA),

7) Weighted Greedy Multiple Switch Algorithm (WGMSA).

Our experiments were conducted on all completely unimodal four-dimensional hypercubes and on randomly generated hypercubes of dimensions up to sixteen, Hamiltonian (presumably corresponding to hard problem instances) and non-Hamiltonian.

Local-search improvement algorithms 1 and 2 have been investigated earlier, but number 3, 4, 5, 6, and 7 probably not. Algorithm 5 (first time used for completely unimodal hypercubes in this paper) is the only algorithm with the known subexponential expected worst-case running time. However, the algorithms 1, 3, 4, 6, 7 demonstrate superior behaviors compared to the other two investigated algorithms. This suggests that further theoretical and experimental studies of these algorithms should be carried out.

Available as PDF (236 kB)

Download BibTeX entry.