mercredi 29 septembre 2010

Getting all the solutions with google solver

Laurent explained to me how to get all the solutions in a more elegant way than with collectors and assignment. Here is the trick for the Dudeney problem:

while solver.NextSolution():
print nb

What I still have to discover is:
- How to get the fix point after each post in the python model ?
- How to implement a search (at least variable/value heuristic) in python ?
- How to make LNS and defining a fragment from python ?

3 commentaires:

  1. Some answer:
    Fix point: add constraint inside a decision Builder.

    Thus how to define tree search:

    Here is a simple decision builder around one var:
    class MyDecisionBuilder(object):
    def __init__(self, var):
    self.__var = var

    def Next(self, solver):
    if not self.__var.Bound():
    value = self.__var.Min()
    decision = solver.AssignVariableValue(self.__var, value)
    return decision
    return None

    You could use the same Next method to add your constraints there

    Define LNS:

    class MyLNS(object):
    def __init__(self):
    self.__current = 0

    def InitFragment(self):
    self.__current = 0

    def NextFragment(self, fragment, values):
    while self.__current < len(values):
    if values[self.__current] == 1:
    self.__current += 1
    return True
    self.__current += 1

    Thus in a fragment, you append the index of the variables you want to release.
    Values gives you the number of variables and the value in the current solution of these variables.

    Here is how it is called:

    def testCallbackLNS(self):
    solver = pywrapcp.Solver('testCallbackLNS')
    x = [solver.BoolVar('x_%d' % i) for i in range(0, 10)]
    lns = solver.LNSOperator(x, MyLNS())
    solution = solver.Assignment()
    for v in x:
    solution.SetValue(v, 1)
    obj_var = solver.Sum(x)
    objective = solver.Minimize(obj_var, 1)
    collector = solver.LastSolutionCollector(solution)
    inner_db = solver.Phase(x, solver.CHOOSE_FIRST_UNBOUND,

    db = solver.LocalSearchPhase(solution, lns, inner_db, None)
    solver.Solve(db, [objective, collector])
    for v in x:
    self.assertEqual(0, collector.solution(0).Value(v))

  2. Thank you again Laurent!
    I will try to format this in a nice way on examples.

  3. I have committed a shortcut on SolutionCollectors

    for i in range(collector.solution_count()):
    nbsol = collector.Value(i, nb)
    print nbsol

    You can get directly the saved value of 'nb' in the ith stored solution.