Binary constraints on one additional variable can create exponential ascents for local search

David A. Cohen, Peter G. Jeavons, Artem Kaznatcheev +2

Local search in combinatorial optimisation can be viewed as an uphill climb on a corresponding fitness landscape, where the assignments visited by a strict local search follow an a…