Issue with Solution Hinting

[S. K.]

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]

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]

I had a similar problem, the solution was to replace int with round here:

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

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEebqRvPHHPWQGHD485cvAHNoV3FozKm6nDnwuWHpvUEkdA%40mail.gmail.com.

[S. K.]

Tried using round instead of int. Makes no difference.

[S. K.]

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()}_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ')

[Laurent Perron]

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

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/d281ca54-b6e2-4ed3-b05e-aa7d88090de1n%40googlegroups.com.

[S. K.]

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]

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

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/d2d8d523-2216-4f4a-9ea0-ade6ef7994dan%40googlegroups.com.

[S. K.]

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.

[Frederic Didier]

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.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/34921ee5-aadb-4eb7-9d89-122210cb2cfdn%40googlegroups.com.

[S. K.]

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]

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.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/b96085c5-c43c-4a04-9187-2000823ca06an%40googlegroups.com.

[Frederic Didier]

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]

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

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABqCn%3Dfq40RPhutspzBYwPK6O3cgn%2B_9gGz3%3D%3DG-bPNw5BgbrQ%40mail.gmail.com.

[Frederic Didier]

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.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeZ8SsLzDx3%3DWk1jChs7_fvS6%3Dbdr1%3DTyUCbL80oSjjw%3Dg%40mail.gmail.com.

[Frederic Didier]

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:

https://github.com/google/or-tools/blob/b37d9c786b69128f3505f15beca09e89bf078a89/ortools/sat/integer.cc#L1155

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.]

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.]

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]

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.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/f20b1641-360a-4c61-90de-dce44bee1282n%40googlegroups.com.

[Laurent Perron]

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

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABqCn%3Df1TKv0tMtC1obYc_OS5%3DoWfu1bUfsbdjaqs_o5bx4Q8A%40mail.gmail.com.

[grego...@gmail.com]

Not yet :-)  Last commit on the master branch is two days old.

[Laurent Perron]

Indeed :-) done.

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

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/1c87987b-3cc3-47e3-a518-acb969bc6b9dn%40googlegroups.com.