CODEWITHSUNDEEP
or-toolscp-sat
S.M.
S.M.

Reputation: 13

OR-Tools CP-SAT hint completeness is lost after presolve

I am using ortools.sat.python.cp_model (version 9.9) to solve some kind of JSSP. I have heuristics that find me (possibly infeasible) solutions. I test the solutions, choose the best one and use add_hint() to give them to my CpModel.

I set

solver.parameters.max_time_in_seconds = 3
solver.parameters.log_search_progress = True
solver.parameters.fix_variables_to_their_hinted_value = False

and call solver.solve() Now those lines appear in the output:

The return of solver.solve() is also the status UNKNOWN.

As I understand this, the solver checks my hints, recognize them as feasible solution but still ends without knowing that the problem is feasible. Is there an explanation and a way to change that behavior or is this a bug?

Upvotes: 1

Views: 122

Answers (1)

Laurent Perron
Laurent Perron

Reputation: 11064

Upgrade the version of or-tools.

It has been much improved in 9.11 and mostly fixed in the upcoming 9.12.

This is what I get with the current code:

Preloading model.
#Bound   1.54s best:inf   next:[526660,2.57698038e+11] initial_domain
The solution hint is incomplete: 374 out of 6974 non fixed variables hinted.
#Model   1.54s var:6974/6974 constraints:20008/20008

Starting search at 1.55s with 12 workers.
8 full problem subsolvers: [core, default_lp, fixed, max_lp, no_lp, quick_restart, quick_restart_no_lp, reduced_costs]
4 first solution subsolvers: [fj(2), fs_random, fs_random_no_lp]
14 interleaved subsolvers: [feasibility_pump, graph_arc_lns, graph_cst_lns, graph_dec_lns, graph_var_lns, ls, ls_lin, rins/rens, rnd_cst_lns, rnd_var_lns, scheduling_intervals_lns, scheduling_precedences_lns, scheduling_resource_windows_lns, scheduling_time_window_lns]
3 helper subsolvers: [neighborhood_helper, synchronization_agent, update_gap_integral]

#1       2.58s best:891360 next:[526660,891359] default_lp [hint]

Update

I have fixed the code:

Preloading model.
#Bound   1.51s best:inf   next:[526660,2.57698038e+11] initial_domain
#1       1.51s best:891360 next:[526660,891359] complete_hint
#Model   1.51s var:6974/6974 constraints:20008/20008

Starting search at 1.52s with 12 workers.
8 full problem subsolvers: [core, default_lp, fixed, max_lp, no_lp, quick_restart, quick_restart_no_lp, reduced_costs]
4 first solution subsolvers: [fj(2), fs_random, fs_random_no_lp]
14 interleaved subsolvers: [feasibility_pump, graph_arc_lns, graph_cst_lns, graph_dec_lns, graph_var_lns, ls, ls_lin, rins/rens, rnd_cst_lns, rnd_var_lns, scheduling_intervals_lns, scheduling_precedences_lns, scheduling_resource_windows_lns, scheduling_time_window_lns]
3 helper subsolvers: [neighborhood_helper, synchronization_agent, update_gap_integral]

#2       2.15s best:567660 next:[526660,567659] graph_var_lns (d=5.00e-01 s=10 t=0.10 p=0.00 stall=0 h=auto_l0)

Upvotes: 1

Related Questions