2
$\begingroup$

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.

$\endgroup$
13
  • 1
    $\begingroup$ Please try the same recommendations: log_search_progress:true, num_search_workers:1 and note that your hint is not complete $\endgroup$ Commented May 2, 2023 at 22:16
  • $\begingroup$ @LaurentPerron thanks, will try. However, the incomplete hint was on purpose: in my problem, I want to supply a minimum number of variables after which the remaining ones are completely determined via equality constraints. I was expecting CP SAT to find them easily. Would this change the solution in the link you suggested? $\endgroup$
    – John D
    Commented May 3, 2023 at 0:28
  • $\begingroup$ Have you checked the second part ? Number of workers, which one finds the on solution first ? $\endgroup$ Commented May 3, 2023 at 6:10
  • $\begingroup$ Hi @LaurentPerron. I tried your suggestion but nothing. Please see the modified code. Also, please could you comment on my question above? (the one with the minimum number of variables that determine all of the variables). It is still not clear to me what am I supposed to find. I am a newbie with CP - SAT. $\endgroup$
    – John D
    Commented May 3, 2023 at 18:52
  • $\begingroup$ Yes, the model is so trivial, it is empty after presolve, and unfortunately, presolve does not follow the hint currently. $\endgroup$ Commented May 3, 2023 at 20:06

1 Answer 1

2
$\begingroup$

The hints are actually wrong and infeasible. A good way to check it is to add the parameter fix_variables_to_their_hinted_value:true to the solver before solving.

In your case, it returns INFEASIBLE, thus showing the problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.