I have an optimization problem that I am solving with CP-SAT and I am using the Python interface. Moreover, I know a good feasible solution coming from a heuristic and I want the solver to start its search from this solution.
How can I achieve this? Ideally, I would like to specify the initial value right after defining the variable, and not after the model is constructed. Is there a way to do it like this?
I tried with the AddHint() method but it is not clear to me what it does exactly: the solver just ignores the hint and finds another initial solution. I also found the thread here but it remains unanswered.
As a minimal working example, consider the optimization problem:
$ \max\limits_{(x, y) \in \Bbb Z^2 \cap [0, 10]^2 } \{x \: | \: x + y = 10 \}.$
The code implementation is the following:
from ortools.sat.python import cp_model
class SolutionPrinter(cp_model.CpSolverSolutionCallback):
"""Print intermediate solutions."""
def __init__(self, x):
cp_model.CpSolverSolutionCallback.__init__(self)
self._solution_count = 1
self.x = x
def on_solution_callback(self):
"""Called at each new solution."""
print("Solution " + str(self._solution_count) + " ---> " + str(self.Value(self.x)) )
print("")
self._solution_count += 1
model = cp_model.CpModel()
x = model.NewIntVar(0, 10, "x")
y = model.NewIntVar(0, 10, "y")
# Maximize x
model.Maximize(x)
# Hint
model.AddHint(x, 1)
solver = cp_model.CpSolver()
printer = SolutionPrinter(x)
solver.Solve(model, printer)
print(f"x = {solver.Value(x)} and y = {solver.Value(y)}")
The output here is
Solution 1 ---> 10
x = 10 and y = 0
Instead, it should find that $y = 9$ makes $(x, y)$ feasible and print that
Solution 1 ---> 1
and only then keep looking.
EDIT: Based on the suggestion of @LaurentPerron, I added the options
solver.parameters.log_search_progress = True
solver.parameters.num_search_workers = 1
solver.log_callback = print
but this returns
Starting CP-SAT solver v9.6.2534
Parameters: log_search_progress: true num_search_workers: 1
Initial optimization model '': (model_fingerprint: 0x871bcff12da75473)
#Variables: 2 (#ints:1 in objective)
- 2 in [0,10]
Starting presolve at 0.00s
The solution hint is complete and is feasible.
[ExtractEncodingFromLinear] #potential_supersets=0 #potential_subsets=0
#at_most_one_encodings=0 #exactly_one_encodings=0 #unique_terms=0 #multiple_terms=0 #literals=0 time=1e-06s
[Symmetry] Graph for symmetry has 2 nodes and 0 arcs.
[Symmetry] Symmetry computation done. time: 4.9e-06 dtime: 1.2e-07
[Probing] deterministic_time: 0 (limit: 1) wall_time: 1.1e-06 (0/0)
[DetectDuplicateConstraints] #duplicates=0 #without_enforcements=0 time=6e-06s
[DetectDominatedLinearConstraints] #relevant_constraints=0 #work_done=0 #num_inclusions=0 #num_redundant=0 time=3.7e-06s
[ProcessSetPPC] #relevant_constraints=0 #num_inclusions=0 work=0 time=7e-07s
[FindBigLinearOverlap] #blocks=0 #saved_nz=0 #linears=0 #work_done=0/1e+09 time=6e-07s
[MergeClauses] #num_collisions=0 #num_merges=0 #num_saved_literals=0 work=0/100000000 time=4e-07s
[ExpandObjective] #propagations=0 #entries=0 #tight_variables=0 #tight_constraints=0 #expands=0 #issues=0 time=5.4e-06s
Presolve summary:
- 0 affine relations were detected.
- rule 'objective: variable not used elsewhere' was applied 1 time.
- rule 'presolve: 2 unused variables removed.' was applied 1 time.
- rule 'presolve: iteration' was applied 1 time.
Presolved optimization model '': (model_fingerprint: 0xfc4715b25d7c8ae9)
#Variables: 0 ( in objective)
Preloading model.
#Bound 0.00s best:-inf next:[10,10] initial_domain
[Symmetry] Graph for symmetry has 0 nodes and 0 arcs.
Starting to load the model at 0.00s
Starting sequential search at 0.00s
#1 0.00s best:10 next:[] fixed_bools:0/0
Solution 1 ---> 10
#Done 0.00s
CpSolverResponse summary:
status: OPTIMAL
objective: 10
best_bound: 10
integers: 1
booleans: 0
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 1
restarts: 0
lp_iterations: 0
walltime: 0.0025853
usertime: 0.0025854
deterministic_time: 0
gap_integral: 0
solution_fingerprint: 0x2a5128eb91a71559
x = 10 and y = 0
Thus, the problem still remains.
