| Article ID: | iaor2013254 |
| Volume: | 7 |
| Issue: | 1 |
| Start Page Number: | 79 |
| End Page Number: | 87 |
| Publication Date: | Jan 2013 |
| Journal: | Optimization Letters |
| Authors: | Kammerdiner Alla, Pasiliao Eduardo |
| Keywords: | programming: assignment, graphs, combinatorial optimization |
We study local optima of combinatorial optimization problems. We show that a local search algorithm can be represented as a digraph and apply recent results for spanning forests of a diagraph. We establish a correspondence between the number of local optima and the algebraic multiplicities of eigenvalues of digraph laplacians. We apply our finding to the three‐dimensional assignment problem.