Local search¶
A compiled diagram answers questions about a model; a local search finds solutions to problems
that are too large to compile. Every search of pyaicad runs the same loop. It starts from a random
assignment, and at each iteration destroys some variables (frees them) and repairs them (picks
new values that satisfy the constraints as well as it can), until it finds a solution or reaches
a limit. The searches differ only in how they repair:
BeliefPropagationSearchrepairs with belief propagation on the diagrams of the constraints, from uniform probabilities. It needs nothing but the problem.NeuralPriorSearchandNeuralPriorBPSearchstart from the predictions of a trained network (see Training a network; full build).
A local search finds solutions but cannot prove that there are none: to prove it, compile the model.
A problem family¶
The examples use random graph colourings: a graph with 30 nodes and 3 colours, drawn so that a colouring is known to exist. Generating problems is up to you; the library only sees the models.
import random
import pyaicad as ac
def coloring(rng, nodes, colours, degree):
"""A random feasible graph colouring: hide a colouring, draw edges between nodes of other colours."""
hidden = [rng.randrange(colours) for _ in range(nodes)]
model = ac.Model()
colour = model.int_vars(nodes, domain=range(colours))
pairs = [(i, j) for i in range(nodes) for j in range(i + 1, nodes) if hidden[i] != hidden[j]]
probability = min(1.0, degree * nodes / 2 / len(pairs))
for i, j in pairs:
if rng.random() < probability:
model.add(ac.not_equal(colour[i], colour[j]))
return model
rng = random.Random(0)
problems = [coloring(rng, nodes=30, colours=3, degree=4.0) for _ in range(20)]
print(problems[0])
Model(30 variables, 77 constraints)
Running a search¶
local_search takes a problem (or a list of problems, stepped together as one batch), a search and
its limits. A Limits applies to each problem separately; whichever limit is
reached first stops the search.
limits = ac.Limits(time=5, iterations=300)
search = ac.BeliefPropagationSearch()
results = ac.local_search(problems, search, limits, seed=0)
print(f"destroy everything: solved {sum(r.found for r in results)} of {len(problems)}")
destroy everything: solved 0 of 20
The default search destroys every variable at each iteration, which is a restart from scratch.
with_ makes a copy of a search with some options changed. Destroying only a fraction of the
variables makes it a real local search; destroy chooses which ones: at "random", where the
constraints are violated ("worst"), or around a variable ("related").
for destroy in ("random", "worst", "related"):
variant = search.with_(destroy=destroy, destroy_fraction=0.2)
results = ac.local_search(problems, variant, limits, seed=0)
solved = [r for r in results if r.found]
print(f"destroy {destroy:>8} 20%: solved {len(solved):>2} of {len(problems)}")
destroy random 20%: solved 17 of 20
destroy worst 20%: solved 18 of 20
destroy related 20%: solved 3 of 20
Results¶
A Result carries the assignment when one was found, and how the search went.
best = search.with_(destroy="worst", destroy_fraction=0.2)
result = ac.local_search(problems[0], best, limits, seed=0)
print(result.status.value, "after", result.iterations, "iterations")
if result.found:
assert problems[0].check(result.assignment)
feasible after 37 iterations