Issue with Solution Hinting

1,838 views
Skip to first unread message

S. K.

unread,
Aug 23, 2021, 9:42:07 AM8/23/21
to or-tools-discuss
The problem I am having is that sometimes the solution hinting works totally fine, and an initial solution (=the exact solution I hint the model) is found very quickly.
And sometimes the solver does not find a solution for a veeeeeery long time.
The way I hint the solutions is the same every time.
Why does it work sometimes and not at all another time?


I am doing a Job Shop scheduling optimization with a multi-objective approach.


Simplified it looks like this:

# Instantiating model
model = cp_model.CpModel()
[adding constraints etc. to the model]
I keep track of all model variables in a list called all_variables.

# Create solver
solver = cp_model.CpSolver()
solver.parameters.log_search_progress = True
solver.parameters.num_search_workers = 16
solver.parameters.max_time_in_seconds = 600
solver.parameters.hint_conflict_limit = 50000
solver.parameters.cp_model_probing_level = 4
solver.parameters.max_presolve_iterations = 12

# Objective 1
model.Minimize(objective_1)

status = solver.Solve(model, solution_callback=solution_printer)

# Hint model with solution from "objective_1 run"
# model._CpModel__model.solution_hint.Clear()
model.Proto().solution_hint.Clear()
inner_hint_count = 0
for (i,v) in enumerate(all_variables):
value = solver.Value(v)
model.AddHint(v, value)
inner_hint_count += 1
print(f'{inner_hint_count} hints successfully added')

# add constraint for objective_1 using the best found objective value
model.Add(objective_1 <= int(solver.ObjectiveValue()))


# Objective 2
model.Minimize(objective_2)

status = solver.Solve(model, solution_callback=solution_printer)

# Hint model with solution from "objective_2 run"
# model._CpModel__model.solution_hint.Clear()
model.Proto().solution_hint.Clear()
inner_hint_count = 0
for (i,v) in enumerate(all_variables):
value = solver.Value(v)
model.AddHint(v, value)
inner_hint_count += 1
print(f'{inner_hint_count} hints successfully added')

# add constraint for objective_2 using the best found objective value
model.Add(objective_2 <= int(solver.ObjectiveValue()))


# Objective 3
model.Minimize(objective_2)

status = solver.Solve(model, solution_callback=solution_printer)

# Hint model with solution from "objective_2 run"
# model._CpModel__model.solution_hint.Clear()
model.Proto().solution_hint.Clear()
inner_hint_count = 0
for (i,v) in enumerate(all_variables):
value = solver.Value(v)
model.AddHint(v, value)
inner_hint_count += 1
print(f'{inner_hint_count} hints successfully added')

# add constraint for objective_2 using the best found objective value
model.Add(objective_2 <= int(solver.ObjectiveValue()))

and so on.
In total I am having 6 different objectives.


I am hinting EVERY variable with a valid solution.






Laurent Perron

unread,
Aug 23, 2021, 9:44:26 AM8/23/21
to or-tools-discuss
We cannot debug this.
Please send us a model where finding a feasible solution is slow.
Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00



--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/3ee5f4a4-ec02-483d-8a68-b2acf8d4eba2n%40googlegroups.com.

Xiang Chen

unread,
Aug 23, 2021, 9:51:05 AM8/23/21
to or-tools...@googlegroups.com
I had a similar problem, the solution was to replace int with round here:

model.Add(objective_1 <= int(solver.ObjectiveValue()))

S. K.

unread,
Aug 23, 2021, 10:12:37 AM8/23/21
to or-tools-discuss
Tried using round instead of int. Makes no difference.

S. K.

unread,
Aug 23, 2021, 10:21:35 AM8/23/21
to or-tools-discuss
Attached the proto file for the model.

The different objectives and their order are below.
In this case hinting the solution from the first objective works fine and the run with the second objective finds an initial solution immediately.
But when I hint the model with the solution found in the second run and minimize the 3rd objective "transition" afterwards, it does not find a solution in an acceptable time.

criteria_order = ['posted_job', 'termin', 'transition', 'starts', 'zeitplan','makespan']
criteria_time = [5*60, 5*60, 10*60, 10*60, 10*60, 10*60]
criteria_objectives = [None]*len(criteria_order)
feasible_solutions = 0
old_variables = []
old_solution = []
old_solver_values = []

for (no_kriterium,kriterium) in enumerate(criteria_order):

solver.parameters.max_time_in_seconds = int(criteria_time[no_kriterium])
#solver.parameters.random_seed = random_seed_int

if kriterium == "makespan":
model_free.Minimize(makespan)
elif kriterium == "transition":
model_free.Minimize(sum(total_cost))
elif kriterium == "starts":
model_free.Minimize(sum(starts))
elif kriterium == "posted_job":
model_free.Minimize(sum(posted_job_starts))
elif kriterium == "termin":
model_free.Minimize(sum(termin))
elif kriterium == "zeitplan":
model_free.Minimize(sum(zeitplan))


solution_printer = SolutionPrinter(makespan, total_cost, starts, posted_job_starts, termin, zeitplan, max_num_solutions, num_jobs, job_ends, job_starts, job_presences, job_durations, job_ranks, jobs)
print(f'\n\n_ _ _ _ _ _ _Solver starts at: {datetime.datetime.now()}_ _ _ _ _ _ _ _\n\n')
status = solver.Solve(model_free, solution_callback=solution_printer) #solver.SolveWithSolutionCallback(model_free, solution_printer)
if print_output:
print('Optimization:')
print(f'status: {solver.StatusName(status)}')
print('End of Solve-section\n')
print(f'\n\n_ _ _ _ _ _ _Solver stops at: {datetime.datetime.now()}_ _ _ _ _ _ _ _\n\n')
#print(solver.ResponseStats())

#----------------------------------------------------------------------------
# Print solution.
if status == cp_model.FEASIBLE or status == cp_model.OPTIMAL:
# print solution
elif status == cp_model.UNKNOWN :
if no_kriterium != len(criteria_order)-1:
print(f"ATTENTION: Optimierung hat in der gegebenen Zeit keine Loesung für Kriterium: {kriterium} gefunden.")
if len(old_solver_values) > 0:
model_free._CpModel__model.solution_hint.Clear()
inner_hint_count = 0
for (i,v) in enumerate(all_variables):
value = old_solver_values[i] # solver.Value(v)
model_free.AddHint(v, value)
inner_hint_count += 1
print(f'{inner_hint_count} old hints successfully added')
else:
model_free.Proto().solution_hint.Clear()
for i in range(len(old_variables)):
model_free.Proto().solution_hint.vars.append(i)
model_free.Proto().solution_hint.values.append(old_solution[i])

'''
model_free._CpModel__model.solution_hint.Clear()
for (i,v) in enumerate(all_variables):
model_free._CpModel__model.solution_hint.vars.append(model_free.GetOrMakeIndex(v))
#value = old_solver.Value(v)
value = old_solver_values[i] # old_solver.Value(v)
model_free._CpModel__model.solution_hint.values.append(value)
'''
print('Old hints successfully added')
continue
else:
if feasible_solutions == 0:
raise ValueError("ERROR: Optimierung hat in der gegebenen Zeit keine Loesung gefunden.")
else:
if len(old_solver_values) > 0:
model_free._CpModel__model.solution_hint.Clear()
inner_hint_count = 0
for (i,v) in enumerate(all_variables):
value = old_solver_values[i] # solver.Value(v)
model_free.AddHint(v, value)
inner_hint_count += 1
print(f'{inner_hint_count} old hints successfully added')
else:
model_free.Proto().solution_hint.Clear()
for i in range(len(old_variables)):
model_free.Proto().solution_hint.vars.append(i)
model_free.Proto().solution_hint.values.append(old_solution[i])

'''
model_free._CpModel__model.solution_hint.Clear()
for (i,v) in enumerate(all_variables):
model_free._CpModel__model.solution_hint.vars.append(model_free.GetOrMakeIndex(v))
#value = old_solver.Value(v)
value = old_solver_values[i] # old_solver.Value(v)
model_free._CpModel__model.solution_hint.values.append(value)
'''
print('Old hints successfully added')
continue
elif status == cp_model.INFEASIBLE:
raise ValueError("ERROR: Optimierungsmodel ist unausfuehrbar / nicht zu loesen.")

print('Adding solution hints...')

'''
model_free.Proto().solution_hint.Clear()
for i in range(len(model.Proto().variables)):
model_free.Proto().solution_hint.vars.append(i)
model_free.Proto().solution_hint.values.append(solver.ResponseProto().solution[i])
print('Hints successfully added')
'''
old_variables = model_free.Proto().variables
old_solution = solver.ResponseProto().solution
old_solver = solver
old_solver_values = []
for v in all_variables:
old_solver_values.append(solver.Value(v))
print('Most recent feasible solutions and solver data saved')

model_free._CpModel__model.solution_hint.Clear()
inner_hint_count = 0
for (i,v) in enumerate(all_variables):
#model_free._CpModel__model.solution_hint.vars.append(model_free.GetOrMakeIndex(v))
value = solver.Value(v)
#model_free._CpModel__model.solution_hint.values.append(value)
model_free.AddHint(v, value)
inner_hint_count += 1
print(f'{inner_hint_count} hints successfully added')



if kriterium == "makespan":
model_free.Add(makespan <= int(solver.ObjectiveValue()))
elif kriterium == "transition":
model_free.Add(sum(total_cost) <= int(solver.ObjectiveValue()))
elif kriterium == "starts":
model_free.Add(sum(starts) <= int(solver.ObjectiveValue()))
elif kriterium == "posted_job":
model_free.Add(sum(posted_job_starts) <= int(solver.ObjectiveValue()))
elif kriterium == "termin":
model_free.Add(sum(termin) <= int(solver.ObjectiveValue()))
elif kriterium == "zeitplan":
model_free.Add(sum(zeitplan) <= int(solver.ObjectiveValue()))

criteria_objectives[no_kriterium] = int(solver.ObjectiveValue())
print(f'Objective Value for {kriterium}: {int(solver.ObjectiveValue())}')



print(f'_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Optimization stops at: {datetime.datetime.now()}_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ')

solution_hinting.pb.txt

Laurent Perron

unread,
Aug 23, 2021, 10:59:21 AM8/23/21
to or-tools-discuss
I have checked. The hint you generate is infeasible.

You need to debug it. Unfortunately, we have little support to help you there.  

I could extract this information:

Hint found infeasible when assigning variable name: "start_j51_t0_a20"
domain: 0
domain: 5
domain: 102
domain: 109
domain: 158
domain: 277
domain: 326
domain: 445
domain: 494
domain: 613
domain: 662
domain: 781
domain: 830
domain: 949
domain: 998
domain: 1117
domain: 1166
domain: 1285
domain: 1334
domain: 1453
domain: 1502
domain: 1621
domain: 1670
domain: 1670
domain: 1695
domain: 1790
domain: 1839
domain: 1958
domain: 2007
domain: 2126
domain: 2175
domain: 2294
domain: 2343
domain: 2462
domain: 2511
domain: 2630
domain: 2679
domain: 2798
domain: 2847
domain: 2934
domain: 3183
domain: 3246
domain: 3279
domain: 3302
domain: 3351
domain: 3470
domain: 3519
domain: 3638
domain: 3687
domain: 3806
domain: 3855
domain: 3974
domain: 4023
domain: 4142
domain: 4191
domain: 4310
domain: 4359
domain: 4478
domain: 4527
domain: 4646
domain: 4695
domain: 4814
domain: 4863
domain: 4982
domain: 5031
domain: 5150
domain: 5199
domain: 5317
domain: 5366
domain: 5485
domain: 5534
domain: 5621
domain: 5726
domain: 5821
domain: 5870
domain: 5989
domain: 6038
domain: 6157
domain: 6206
domain: 6325
domain: 6374
domain: 6493
domain: 6542
domain: 6605
domain: 6638
domain: 6661
domain: 6710
domain: 6829
domain: 6902
domain: 6997
domain: 7046
domain: 7109
domain: 7142
domain: 7165
domain: 7214
domain: 7333
domain: 7382
domain: 7501
domain: 7550
domain: 7669
domain: 7718
domain: 7837
domain: 7886
domain: 8005
domain: 8054
domain: 8173
domain: 8222
domain: 8341
domain: 8390
domain: 8509
domain: 8558
domain: 8677
domain: 8726
domain: 9072
 the value 24

--Laurent

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00


S. K.

unread,
Aug 24, 2021, 1:45:34 AM8/24/21
to or-tools-discuss
1) How did you know that the hint was found infeasible when assigning variable name: "start_j51_t0_a20"?

2) Did you get this information if you run the proto-file alone and the objective is 
model_free.Minimize(sum(posted_job_starts))
Because for the first run it is possible that I hint with an infeasible solution (that is close to a feasible one). And I almost never had problems with that. This time neither, it takes about 10 s and then I get a feasible solution from the solver.

The problems start when I use the definitely feasible solution from the solver that I get from the run with objective 2 (model_free.Minimize(sum(termin)) and hint this solution to the 3rd run with objective 3 (model_free.Minimize(sum(transition))).
And there should be no way that the hint is found infeasible then, because when switching the objective I change nothing on the model and the solution I use to hint is from the solver itself and found feasible the run before....


Maybe I send you another proto-file from the "right moment".

Laurent Perron

unread,
Aug 24, 2021, 2:55:08 AM8/24/21
to or-tools-discuss
1)

I wrote some code that forces the hint to be hard constraints.
To do this, just before presolve, I loop through the hint, and reduce the domain of the variables to the value in the hints.

At this time, I just check that the value is compatible with the domain of the variable, which is not the case.

2) I run this before presolve, and I do not look at the objective. So it it still infeasible.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00


S. K.

unread,
Aug 24, 2021, 5:41:30 AM8/24/21
to or-tools-discuss
1) Okay, nice to know.

2) Yeah, I know. Like I said the model proto file I attached before has hints that could be infeasible, but that never makes any problems. I have problems with what happens afterwards.

I send you 2 more model proto .txt files.

The solution_hinting_posted_job.pb.txt may have some infeasible hints, but still works fine and find feasible solutions for the first objective model.Minimize(sum(posted_job_starts)).
Then I take this (best) feasible solution found by the solver and hint the model with it via
model_free._CpModel__model.solution_hint.Clear()
for (i,v) in enumerate(all_variables):
model_free._CpModel__model.solution_hint.vars.append(model_free.GetOrMakeIndex(v))
#value = old_solver.Value(v)
value = old_solver_values[i] # old_solver.Value(v)
model_free._CpModel__model.solution_hint.values.append(value)

and change the objective to the second objective model.Minimize(sum(termin)).
So now the model can only have feasible hints because there from a solution found by the solver just a second before and suddenly the solver can't find any feasible solutions in an acceptable time (despite hinting EVERY model variable with a feasible value).
The model with the feasible hints and the new objective is in solution_hinting_termin.pb.txt.
productionplanning-main.zip

Frederic Didier

unread,
Aug 24, 2021, 9:40:09 AM8/24/21
to or-tools...@googlegroups.com
I don't know what your code is doing, but in the solution_hinting_termin.pb.txt model you send us, your hint contains duplicate variable entries.
That is, some of your  "append(model_free.GetOrMakeIndex(v))" are pushing the same index.
So it is actually incomplete and probably not doing what you want. 

We will add some validation code to detect this case to help further development.



S. K.

unread,
Aug 24, 2021, 9:48:43 AM8/24/21
to or-tools-discuss
Ah, sorry, I copied the wrong bit.
I am doing the following in the solution hinting part (not model._CpModel__model.solution_hint.vars.append(model.GetOrMakeIndex(v)) ) as I already written in my very first entry:

 model._CpModel__model.solution_hint.Clear()
model.Proto().solution_hint.Clear()
inner_hint_count = 0
for (i,v) in enumerate(all_variables):
#model._CpModel__model.solution_hint.vars.append(model.GetOrMakeIndex(v))
value = solver.Value(v)
#model._CpModel__model.solution_hint.values.append(value)
model.AddHint(v, value)
inner_hint_count += 1
print(f'{inner_hint_count} hints successfully added') 

Frederic Didier

unread,
Aug 24, 2021, 9:51:13 AM8/24/21
to or-tools...@googlegroups.com
I didn't look at your code, just in the proto you sent us, the hint contained duplicate entries, which is probably the source of the issues.
Please double check that you hint at each variable index only once.
I am adding a validation on our side, so if the hint is like this in the future you will get a MODEL_INVALID with hopefully a clear error message.

Frederic Didier

unread,
Aug 24, 2021, 9:54:29 AM8/24/21
to or-tools...@googlegroups.com
More precisely, if you open the text file solution_hinting_termin.pb.txt (it is big) and look at the "solution_hint {" part, you will see stuff like:
vars: 5601
vars: 5602
vars: 5601   // Duplicate
vars: 5604
vars: 5605
vars: 5606
vars: 5601  // Duplicate, etc...


Laurent Perron

unread,
Aug 24, 2021, 10:38:33 AM8/24/21
to or-tools-discuss
The _job example contains infeasible hints: 

Hint found infeasible when assigning variable 'start_j221_t0_a1' with domain[4388,4460][4509,4628][4677,4796][4845,4964][5013,5132][5181,5299][5348,5467][5516,5603][5708,5803][5852,5971][6020,6139][6188,6307][6356,6475][6524,6587][6620,6643][6692,6811][6884,6979][7028,7091][7124,7147][7196,7315][7364,7483][7532,7651][7700,7819][7868,7987][8036,8155][8204,8323][8372,8491][8540,8659][8708,9072] the value 553


The _termin file has valid hints (with duplicated variables). If I force them, the solution is trivial. But if I just use hinting, then the solver has a problem finding a feasible solution.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00


Frederic Didier

unread,
Aug 24, 2021, 11:33:00 AM8/24/21
to or-tools...@googlegroups.com
Yes it seems even with duplicates, the hint should have led to a quick feasible solution, we are still investigating why it doesn't happen.

Frederic Didier

unread,
Aug 24, 2021, 1:51:10 PM8/24/21
to or-tools...@googlegroups.com
Ok, I found why the hint was not properly followed, it was colliding with some code that "detects" a propagation loop and tries to get out of it by taking other decisions.

Not sure how this will be fixed yet, but as a temporary solution, you can fix the code directly by always returning false, or changing the condition to max(10000, 10 * num_vars) for instance, there:

Note that we will probably still mark as invalid model that contains a hint referring to the same variable twice, so you might still want to fix this.


S. K.

unread,
Aug 25, 2021, 2:20:54 AM8/25/21
to or-tools-discuss

Mh, that is really weird.
I double checked everything and I don't see a part where I could accidentally double-hint some variables...

Before changing the objective and hinting the model with the solution found from the solver at the run before I am doing:

#model._CpModel__model.solution_hint.Clear()
model.Proto().solution_hint.Clear()

Is this not correct?
Should I do both commands?  Only the other one? A totally different one?

S. K.

unread,
Aug 25, 2021, 2:28:35 AM8/25/21
to or-tools-discuss
Okay, just so that I get it right.
I would have to download the source code, edit this part and install it from the source on my computer for this to work?

Frederic Didier

unread,
Aug 25, 2021, 4:15:15 AM8/25/21
to or-tools...@googlegroups.com
The clear looks correct, just double check that you don't have duplicates in your "all_variables". 
And yes for the source bit, but you can also wait a bit as we should push a quick fix on the master branch soon.

Laurent Perron

unread,
Aug 25, 2021, 5:05:43 AM8/25/21
to or-tools-discuss
I have pushed the fix on the master branch. No need to patch the code.

I cannot test it as the proto we have has duplicated variables in hints, which is now checked.

If you send us the fixed proto, I can test it locally.

Thanks

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00


grego...@gmail.com

unread,
Aug 25, 2021, 10:31:28 AM8/25/21
to or-tools-discuss
Not yet :-)  Last commit on the master branch is two days old.

Laurent Perron

unread,
Aug 25, 2021, 10:36:23 AM8/25/21
to or-tools-discuss
Indeed :-) done.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00


Reply all
Reply to author
Forward
0 new messages