Solution hint is complete and feasible, but solver status is unkown

[Yifei Shi]

Hi, I'm using ortools 9.3.10497, and sometimes I encounter with the problem that even solution hint is already complete and feasible, but the solver can't find a feasible solution more than 10 mins after presolve is finished, using 8 workers. Here is solver log, any suggestions how to deal with this situation? Thanks for the help!

Starting CP-SAT solver v9.3.10497
Parameters: max_time_in_seconds: 900 log_search_progress: true
Setting number of workers to 8
Initial optimization model '':
#Variables: 34258 (#bools:248 in objective)
  - 491 different domains in [0,120] with a largest complexity of 1.
  - 31 constants in {0,1,2,3,5,8,12,14,16,18,20,21,23,24,25,28,30,35,52,58}
#kBoolOr: 53 (#enforced: 48) (#literals: 5)
#kInterval: 32843 (#enforced: 32242)
#kLinMax: 473
#kLinear1: 23209 (#enforced: 23135)
#kLinear2: 34711 (#enforced: 32901)
#kLinear3: 1211 (#enforced: 1176)
#kLinear: 258 (#enforced: 258)
#kLinearN: 1706 (#enforced: 886) (#terms: 36382)
#kNoOverlap: 266 (#intervals: 31884, #optional: 31468)
Starting presolve at 0.04s
The solution hint is complete and is feasible.
[ExtractEncodingFromLinear] #potential_supersets=821 #potential_subsets=0 #at_most_one_encodings=0 #exactly_one_encodings=0 #unique_terms=0 #multiple_terms=0 #literals=0 time=0.000378s
[Probing] deterministic_time: 0.113129 (limit: 1) wall_time: 12.1782 (33140/33140)
[Probing]  - new fixed Boolean: 2219 (11130/33140)
[Probing]  - new integer holes: 2
[Probing]  - new integer bounds: 9
[Probing]  - new binary clause: 84139
[SAT presolve] num removable Booleans: 13334 / 34320
[SAT presolve] num trivial clauses: 1471
[SAT presolve] [0s] clauses:6176 literals:21217 vars:3958 one_side_vars:2176 simple_definition:422 singleton_clauses:0
[SAT presolve] [0.0004951s] clauses:4746 literals:13614 vars:3958 one_side_vars:2176 simple_definition:1087 singleton_clauses:0
[SAT presolve] [0.00210346s] clauses:4746 literals:13614 vars:3958 one_side_vars:2176 simple_definition:1087 singleton_clauses:0
[MaxClique] Merged 1304(2780 literals) into 1302(2777 literals) at_most_ones.
[DetectDuplicateConstraints] #duplicates=188 time=0.00282542s
[DetectDominatedLinearConstraints] #relevant_constraints=467 #work_done=3668 #num_inclusions=141 #num_redundant=0 time=0.00334936s
[DetectOverlappingColumns] #processed_columns=0 #work_done=0 #nz_reduction=0 time=0.00214951s
[ProcessSetPPC] #relevant_constraints=5881 #num_inclusions=11 work=107469 time=0.00267949s
[Symmetry] Graph for symmetry has 112959 nodes and 196460 arcs.
[Symmetry] Symmetry computation done. time: 0.0268836 dtime: 0.0526757
[Symmetry] #generators: 185, average support size: 59.9892
[Symmetry] The model contains 170 duplicate constraints !
[Symmetry] 4303 orbits with sizes: 12,8,6,6,6,6,6,6,6,6,...
[Symmetry] Num fixable by binary propagation in orbit: 1 / 12
[Symmetry] Num fixable by intersecting at_most_one with orbits: 3 largest_orbit: 12
[Symmetry] Found orbitope of size 37 x 2
[Probing] deterministic_time: 0.0841749 (limit: 1) wall_time: 9.7095 (33142/33142)
[Probing]  - new fixed Boolean: 8 (11141/33142)
[Probing]  - new binary clause: 75591
[SAT presolve] num removable Booleans: 13376 / 34320
[SAT presolve] num trivial clauses: 0
[SAT presolve] [0s] clauses:4732 literals:13579 vars:3946 one_side_vars:2171 simple_definition:1082 singleton_clauses:0
[SAT presolve] [0.000237888s] clauses:4732 literals:13579 vars:3946 one_side_vars:2171 simple_definition:1082 singleton_clauses:0
[SAT presolve] [0.00182902s] clauses:4732 literals:13579 vars:3946 one_side_vars:2171 simple_definition:1082 singleton_clauses:0
[DetectDuplicateConstraints] #duplicates=19 time=0.00249105s
[DetectDominatedLinearConstraints] #relevant_constraints=418 #work_done=3320 #num_inclusions=132 #num_redundant=0 time=0.0032453s
[DetectOverlappingColumns] #processed_columns=0 #work_done=0 #nz_reduction=0 time=0.00214328s
[ProcessSetPPC] #relevant_constraints=4569 #num_inclusions=0 work=98077 time=0.00225166s
[Symmetry] Graph for symmetry has 112833 nodes and 196208 arcs.
[Symmetry] Symmetry computation done. time: 0.0279985 dtime: 0.0525665
[Symmetry] #generators: 184, average support size: 59.837
[Symmetry] The model contains 170 duplicate constraints !
[Symmetry] 4299 orbits with sizes: 12,8,6,6,6,6,6,6,6,6,...
[Symmetry] Num fixable by binary propagation in orbit: 1 / 12
[Symmetry] Num fixable by intersecting at_most_one with orbits: 3 largest_orbit: 12
[Symmetry] Found orbitope of size 37 x 2
Presolve summary:
  - 2205 affine relations were detected.
  - rule 'TODO linear2: contains a Boolean.' was applied 82 times.
  - rule 'affine: new relation' was applied 2205 times.
  - rule 'at_most_one: duplicate literals' was applied 11 times.
  - rule 'at_most_one: removed literals' was applied 7 times.
  - rule 'at_most_one: transformed into max clique.' was applied 1 time.
  - rule 'at_most_one: x and not(x)' was applied 27 times.
  - rule 'bool_and: always false' was applied 3 times.
  - rule 'bool_and: fixed literals' was applied 2 times.
  - rule 'bool_and: non-reified.' was applied 62 times.
  - rule 'bool_or: always true' was applied 1734 times.
  - rule 'bool_or: fixed literals' was applied 62 times.
  - rule 'bool_or: implications' was applied 58 times.
  - rule 'bool_or: only one literal' was applied 739 times.
  - rule 'bool_or: removed enforcement literal' was applied 6590 times.
  - rule 'deductions: 7365 stored' was applied 1 time.
  - rule 'duplicate: merged rhs of linear constraint' was applied 77 times.
  - rule 'duplicate: removed constraint' was applied 207 times.
  - rule 'enforcement literal not used' was applied 12 times.
  - rule 'exactly_one: duplicate literals' was applied 44 times.
  - rule 'exactly_one: removed literals' was applied 351 times.
  - rule 'exactly_one: satisfied' was applied 2 times.
  - rule 'exactly_one: size one' was applied 4 times.
  - rule 'exactly_one: size two' was applied 2 times.
  - rule 'exactly_one: x and not(x)' was applied 59 times.
  - rule 'false enforcement literal' was applied 26742 times.
  - rule 'lin_max: all Booleans.' was applied 209 times.
  - rule 'lin_max: converted to equality' was applied 264 times.
  - rule 'lin_max: removed exprs' was applied 81 times.
  - rule 'lin_max: target domain reduced' was applied 93 times.
  - rule 'linear1: is boolean implication' was applied 6679 times.
  - rule 'linear2: implied ax + by = cte has only one solution' was applied 6 times.
  - rule 'linear: always true' was applied 26299 times.
  - rule 'linear: empty' was applied 7518 times.
  - rule 'linear: enforcement literal in expression' was applied 2 times.
  - rule 'linear: expand small ax + by != cte' was applied 1 time.
  - rule 'linear: extracted enforcement literal' was applied 18 times.
  - rule 'linear: fixed or dup variables' was applied 34465 times.
  - rule 'linear: infeasible' was applied 435 times.
  - rule 'linear: negative clause' was applied 12 times.
  - rule 'linear: negative reified and' was applied 9 times.
  - rule 'linear: positive at most one' was applied 10 times.
  - rule 'linear: positive clause' was applied 11 times.
  - rule 'linear: positive equal one' was applied 820 times.
  - rule 'linear: reduced variable domains' was applied 7536 times.
  - rule 'linear: remapped using affine relations' was applied 54506 times.
  - rule 'linear: simplified rhs' was applied 1292 times.
  - rule 'linear: small Boolean expression' was applied 1532 times.
  - rule 'no_overlap: merged constraints' was applied 1 time.
  - rule 'no_overlap: removed absent intervals' was applied 150 times.
  - rule 'no_overlap: split into disjoint components' was applied 108 times.
  - rule 'objective: variable not used elsewhere' was applied 15 times.
  - rule 'presolve: 11171 unused variables removed.' was applied 1 time.
  - rule 'presolve: iteration' was applied 2 times.
  - rule 'setppc: bool_or in at_most_one.' was applied 11 times.
  - rule 'symmetry: fixed to false in general orbit' was applied 6 times.
  - rule 'true enforcement literal' was applied 7865 times.
  - rule 'variables with 2 values: create encoding literal' was applied 49 times.
  - rule 'variables with 2 values: new affine relation' was applied 49 times.
  - rule 'variables: canonicalize domain' was applied 13 times.
  - rule 'variables: detect fully reified value encoding' was applied 10 times.
  - rule 'variables: detect half reified value encoding' was applied 35 times.
  - rule 'variables: removable enforcement literal' was applied 4 times.
Presolved optimization model '':
#Variables: 20940 (#bools:233 in objective)
  - 231 different domains in [0,119] with a largest complexity of 2.
#kBoolAnd: 1251 (#enforced: 1251) (#literals: 1290)
#kBoolOr: 3442 (#literals: 10999)
#kExactlyOne: 748 (#literals: 20097)
#kInterval: 22254 (#enforced: 21554)
#kLinear1: 646 (#enforced: 646)
#kLinear2: 418
#kLinearN: 378 (#enforced: 378) (#terms: 1702)
#kNoOverlap: 102 (#intervals: 21344, #optional: 21166)
Preloading model.
[Symmetry] Graph for symmetry has 99392 nodes and 196078 arcs.
[Symmetry] Symmetry computation done. time: 0.0254153 dtime: 0.0515854
[Symmetry] #generators: 183, average support size: 59.7923
[Symmetry] The model contains 122 duplicate constraints !
[Symmetry] Found orbitope of size 37 x 2
#Bound  22.74s best:inf   next:[45,1137]  initial_domain
Starting Search at 22.77s with 8 workers.
6 full subsolvers: [default_lp, fixed, no_lp, max_lp, core, reduced_costs]
Interleaved subsolvers: [feasibility_pump, rnd_var_lns_default, rnd_cst_lns_default, graph_var_lns_default, graph_cst_lns_default, scheduling_time_window_lns_default, scheduling_random_lns_default, rins_lns_default, rens_lns_default]
#Bound  41.03s best:inf   next:[60,1137]  reduced_costs
Sub-solver search statistics:
  'max_lp':
     LP statistics:
       final dimension: 4009 rows, 20997 columns, 107788 entries with magnitude in [1.520280e-02, 1.000000e+00]
       total number of simplex iterations: 328914
       num solves:
         - #OPTIMAL: 35109
         - #DUAL_UNBOUNDED: 785
         - #DUAL_FEASIBLE: 23484
       managed constraints: 15763
       merged constraints: 36688
       shortened constraints: 37
       coefficient strenghtenings: 76
       total cuts added: 25308 (out of 61982 calls)
         - 'CG': 1584
         - 'IB': 3577
         - 'MIR_1': 1525
         - 'MIR_1_K': 10
         - 'MIR_2': 1524
         - 'MIR_2_K': 1
         - 'MIR_3': 579
         - 'MIR_4': 608
         - 'MIR_5': 269
         - 'MIR_6': 196
         - 'NoOverlapCompletionTime': 77
         - 'NoOverlapCompletionTimeMirror': 8
         - 'NoOverlapEnergy_opt': 17
         - 'NoOverlapEnergy_opt_energy': 6
         - 'NoOverlapEnergy_opt_lifted': 3676
         - 'NoOverlapEnergy_opt_lifted_energy': 2414
         - 'ZERO_HALF': 973
         - 'clique': 8264
  'reduced_costs':
     LP statistics:
       final dimension: 2131 rows, 20997 columns, 48498 entries with magnitude in [1.326189e-02, 1.000000e+00]
       total number of simplex iterations: 188175
       num solves:
         - #OPTIMAL: 39933
         - #DUAL_UNBOUNDED: 179
         - #DUAL_FEASIBLE: 10867
       managed constraints: 16334
       merged constraints: 16586
       shortened constraints: 1
       coefficient strenghtenings: 107
       total cuts added: 13879 (out of 30451 calls)
         - 'CG': 749
         - 'IB': 1757
         - 'MIR_1': 736
         - 'MIR_1_K': 4
         - 'MIR_2': 817
         - 'MIR_3': 375
         - 'MIR_4': 337
         - 'MIR_5': 154
         - 'MIR_6': 102
         - 'NoOverlapCompletionTime': 41
         - 'NoOverlapCompletionTimeMirror': 3
         - 'NoOverlapEnergy_opt': 9
         - 'NoOverlapEnergy_opt_energy': 1
         - 'NoOverlapEnergy_opt_lifted': 2395
         - 'NoOverlapEnergy_opt_lifted_energy': 1410
         - 'ZERO_HALF': 589
         - 'clique': 4400
Objective bounds found per subsolver:
  'initial_domain': 1
  'reduced_costs': 1
Improving variable bounds shared per subsolver:
  'core': 1
  'max_lp': 2
  'no_lp': 3
Clauses shared per subsolver:
  'core': 42
  'default_lp': 12
  'max_lp': 10
  'no_lp': 10
  'reduced_costs': 1
CpSolverResponse summary:
status: UNKNOWN
objective: 1137
best_bound: 60
booleans: 22173
conflicts: 8880
branches: 309075
propagations: 2298588
integer_propagations: 2559991
restarts: 40946
lp_iterations: 328914
walltime: 900.168
usertime: 900.168
deterministic_time: 684.025
gap_integral: 4775.08

[Laurent Perron]

Please test with 9.7.

--
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/358c54b1-e76e-491e-8299-0bf63dd77f8fn%40googlegroups.com.

[Frederic Didier]

And also, the message "The solution hint is complete and is feasible." is before presolve.

Unfortunately, at this time, not all our presolve transformations preserve the hint correctly.

You might want to try with "keep_all_feasible_solutions_in_presolve:true", if it still doesn't work, you can send us the model and we will try to improve the situation.

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

[Yifei Shi]

Setting keep_all_feasible_solutions_in_presolve to true worked for the example I used. Could you elaborate more on what this parameter does? Thanks a lot!

[Laurent Perron]

It tells the solver not to fix variables when it does not change the optimal.

Sometimes, you can prove that whatever the value of a variable, the optimal objective value is the same. Therefore, you can fix that variable to some value.

This can help the solver tremendously.

So, during presolve, there are opportunities to remove variables.  Unfortunately, if these happen to be hinted, we loose the hint.

I hope I am clear.

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/66ae1fd6-f077-4d76-8c87-95bad5d8e290n%40googlegroups.com.

[Yifei Shi]

That's quite clear, thanks a lot!

[Yifei Shi]

Hi Laurent, 

It occurs to me that in this situation, when there are variables that don't change the optimal, you can fix it to the hinted value, that way you can still simplify the problem while maintaining the hint. Is that possible? Thanks!