Speeding up the time to find a first solution

[S. K.]

Hi,

I have a rather complex flexible job shop problem that takes ages to find a first solution.

I tried playing around with some of the solver parameters like

random_seed: 3
max_presolve_iterations: 2
cp_model_probing_level: 4
num_search_workers: 14
use_optimization_hints: true
search_branching: PORTFOLIO_WITH_QUICK_RESTART_SEARCH
hint_conflict_limit: 75000

#extra_subsolvers: 'probing' 

#random_branches_ratio: 0.02

But nothing really speeds up the process.

Any tips or ideas what else I could try?

The first solution does not necessarily have to be near to an optimal solution. I just need a solution to kickstart another even bigger model that contains this model.

I'm currently using ortools version: 9.8.3296.

I uploaded the proto text file of the model as a zip-archive here: proto_model

This is the log from the solver:
max_time_in_seconds: 1200
random_seed: 4
log_search_progress: true
log_subsolver_statistics: false
max_presolve_iterations: 2
cp_model_probing_level: 4
num_search_workers: 14
use_optimization_hints: true
search_branching: PORTFOLIO_WITH_QUICK_RESTART_SEARCH
hint_conflict_limit: 75000


Starting CP-SAT solver v9.8.3296
Parameters: random_seed: 4 use_optimization_hints: true max_time_in_seconds: 1200 log_search_progress: true search_branching: PORTFOLIO_WITH_QUICK_RESTART_SEARCH num_search_workers: 14 cp_model_probing_level: 4 max_presolve_iterations: 2 hint_conflict_limit: 75000 log_subsolver_statistics: false

Initial optimization model '': (model_fingerprint: 0x1d3e568978e7c40e)
#Variables: 109'558 (#ints: 28 in objective)
  - 22'489 Booleans in [0,1]
  - 276 different domains in [-10000000,18053978414400] with a largest complexity of 1.
  - 4 constants in {1,2,3,12}
#kBoolOr: 8'719 (#enforced: 1'436) (#literals: 8'719)
#kCircuit: 14
#kCumulative: 24 (#intervals: 18705, #optional: 18705, #variable_sizes: 18705)
#kEmpty: 2
#kIntDiv: 96
#kIntProd: 21'105
#kInterval: 28'370 (#enforced: 21'105) (#fixed: 7265)
#kLinMax: 592 (#expressions: 1'272)
#kLinear1: 26'992 (#enforced: 26'868)
#kLinear2: 300'366 (#enforced: 299'998 #multi: 17'325)
#kLinear3: 21'317 (#enforced: 21'200)
#kLinearN: 1'737 (#enforced: 170) (#terms: 55'187)
#kNoOverlap: 482 (#intervals: 51694, #optional: 44429, #variable_sizes: 44429, #fixed_intervals: 7265)

Starting presolve at 0.10s
  6.14e-02s  0.00e+00d  [DetectDominanceRelations]
  1.35e+00s  0.00e+00d  [PresolveToFixPoint] #num_loops=5 #num_dual_strengthening=2
  4.88e-03s  0.00e+00d  [ExtractEncodingFromLinear] #potential_supersets=1'340
  7.45e+00s  3.02e-01d  [Probe] #probed=56'031 #fixed_bools=27 #new_bounds=1'312 #equiv=17 #new_binary_clauses=9'851
  3.67e-03s  0.00e+00d  [MaxClique]
  6.39e-02s  0.00e+00d  [DetectDominanceRelations]
  3.13e-01s  0.00e+00d  [PresolveToFixPoint] #num_loops=4 #num_dual_strengthening=2
  6.68e-02s  0.00e+00d  [DetectDuplicateConstraints] #duplicates=738 #without_enforcements=375
  2.93e-02s  0.00e+00d  [DetectDifferentVariables] #different=7
  2.39e-02s  5.16e-04d  [DetectDominatedLinearConstraints] #relevant_constraints=66'671
  1.84e-02s  2.60e-05d  [ProcessSetPPC] #relevant_constraints=1'341
  4.46e-03s  0.00e+00d  [FindAlmostIdenticalLinearConstraints]
  5.31e-03s  5.19e-03d  [FindBigHorizontalLinearOverlap] #linears=163
  2.33e-02s  1.34e-02d  [FindBigVerticalLinearOverlap]
  7.28e-03s  6.00e-08d  [MergeClauses]
  3.84e-02s  0.00e+00d  [DetectDominanceRelations]
  2.08e-01s  0.00e+00d  [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
  3.81e-02s  0.00e+00d  [DetectDominanceRelations]
  2.07e-01s  0.00e+00d  [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
[SAT presolve] num removable Booleans: 2 / 9482
[SAT presolve] num trivial clauses: 0
[SAT presolve] [0s] clauses:354 literals:712 vars:600 one_side_vars:576 simple_definition:23 singleton_clauses:0
[SAT presolve] [5.329e-05s] clauses:354 literals:708 vars:600 one_side_vars:576 simple_definition:24 singleton_clauses:0
[SAT presolve] [0.000297292s] clauses:348 literals:696 vars:598 one_side_vars:578 simple_definition:20 singleton_clauses:0
  7.11e+00s  2.94e-01d  [Probe] #probed=55'750 #new_bounds=14 #equiv=18 #new_binary_clauses=8'518
  4.88e-03s  0.00e+00d  [MaxClique] Merged 348(696 literals) into 315(663 literals) at_most_ones.
  3.87e-02s  0.00e+00d  [DetectDominanceRelations]
  2.11e-01s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
  6.66e-02s  0.00e+00d  [DetectDuplicateConstraints] #duplicates=4 #without_enforcements=375
  2.96e-02s  0.00e+00d  [DetectDifferentVariables] #different=7
  2.43e-02s  5.16e-04d  [DetectDominatedLinearConstraints] #relevant_constraints=66'670
  1.82e-02s  2.78e-05d  [ProcessSetPPC] #relevant_constraints=1'632
  4.40e-03s  0.00e+00d  [FindAlmostIdenticalLinearConstraints]
  5.28e-03s  5.19e-03d  [FindBigHorizontalLinearOverlap] #linears=163
  2.34e-02s  1.34e-02d  [FindBigVerticalLinearOverlap]
  4.63e-03s  0.00e+00d  [MergeClauses]
  3.84e-02s  0.00e+00d  [DetectDominanceRelations]
  2.09e-01s  0.00e+00d  [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
  2.55e-02s  0.00e+00d  [ExpandObjective] #entries=1'851'806 #tight_variables=17'513 #tight_constraints=1'590

Presolve summary:
  - 4729 affine relations were detected.
  - rule 'TODO dual: add implied bound' was applied 1'288 times.
  - rule 'TODO dual: make linear1 equiv' was applied 292 times.
  - rule 'TODO dual: only one blocking constraint?' was applied 6'102 times.
  - rule 'TODO dual: only one blocking enforced constraint?' was applied 1'288 times.
  - rule 'TODO dual: only one unspecified blocking constraint?' was applied 114 times.
  - rule 'TODO duplicate: identical constraint with different enforcements' was applied 750 times.
  - rule 'TODO linear1: appear in only one extra 2-var constraint' was applied 146 times.
  - rule 'affine: new relation' was applied 4'729 times.
  - rule 'at_most_one: transformed into max clique.' was applied 1 time.
  - rule 'bool_and: x => x' was applied 1'306 times.
  - rule 'bool_or: always true' was applied 8'719 times.
  - rule 'bool_or: only one literal' was applied 77 times.
  - rule 'bool_or: removed enforcement literal' was applied 4 times.
  - rule 'circuit: degree 2' was applied 8 times.
  - rule 'circuit: fixed singleton arcs.' was applied 13 times.
  - rule 'circuit: fully specified.' was applied 1 time.
  - rule 'circuit: removed false arcs.' was applied 37 times.
  - rule 'circuit: set literal to false.' was applied 74 times.
  - rule 'cumulative: max profile is always under the min capacity' was applied 13 times.
  - rule 'deductions: 26965 stored' was applied 1 time.
  - rule 'dual: add implication' was applied 16 times.
  - rule 'dual: enforced equivalence' was applied 648 times.
  - rule 'dual: fix variable' was applied 21'741 times.
  - rule 'dual: make encoding equiv' was applied 12 times.
  - rule 'dual: reduced domain' was applied 646 times.
  - rule 'duplicate: merged rhs of linear constraint' was applied 15 times.
  - rule 'duplicate: removed constraint' was applied 742 times.
  - rule 'enforcement: false literal' was applied 62'477 times.
  - rule 'enforcement: literal not used' was applied 14 times.
  - rule 'enforcement: true literal' was applied 298'847 times.
  - rule 'exactly_one: removed literals' was applied 1'385 times.
  - rule 'exactly_one: size two' was applied 60 times.
  - rule 'incompatible linear: add implication' was applied 566 times.
  - rule 'int_abs: converted to equality' was applied 11 times.
  - rule 'int_abs: propagate domain from x to abs(x)' was applied 11 times.
  - rule 'int_abs: unused target' was applied 12 times.
  - rule 'int_div: linearize positive division with a constant divisor' was applied 96 times.
  - rule 'int_div: updated domain of target in target = X / cte' was applied 96 times.
  - rule 'int_prod: constant product' was applied 12'236 times.
  - rule 'int_prod: expanded product with Boolean var' was applied 8'782 times.
  - rule 'int_prod: removed constant expressions.' was applied 12'239 times.
  - rule 'int_square: reduced target domain.' was applied 118 times.
  - rule 'intervals: removed unused interval' was applied 4'674 times.
  - rule 'lin_max: canonicalize target using gcd' was applied 18 times.
  - rule 'lin_max: converted to equality' was applied 99 times.
  - rule 'lin_max: divising by gcd' was applied 18 times.
  - rule 'lin_max: removed exprs' was applied 99 times.
  - rule 'lin_max: rewrite with precedences' was applied 15 times.
  - rule 'lin_max: target domain reduced' was applied 680 times.
  - rule 'lin_max: unused affine target' was applied 381 times.
  - rule 'linear1: always true' was applied 1 time.
  - rule 'linear2: implied ax + by = cte has only one solution' was applied 626 times.
  - rule 'linear: always true' was applied 221'781 times.
  - rule 'linear: divide by GCD' was applied 1'195 times.
  - rule 'linear: empty' was applied 845 times.
  - rule 'linear: enforcement literal in expression' was applied 34 times.
  - rule 'linear: fixed or dup variables' was applied 235'487 times.
  - rule 'linear: infeasible' was applied 77 times.
  - rule 'linear: positive equal one' was applied 1'400 times.
  - rule 'linear: reduced variable domains' was applied 4'436 times.
  - rule 'linear: remapped using affine relations' was applied 10'855 times.
  - rule 'linear: simplified rhs' was applied 299'417 times.
  - rule 'linear: singleton column' was applied 7 times.
  - rule 'linear: small Boolean expression' was applied 2 times.
  - rule 'linear: tightened into equality' was applied 1 time.
  - rule 'no_overlap: merged constraints' was applied 1 time.
  - rule 'no_overlap: no intervals' was applied 17 times.
  - rule 'no_overlap: removed absent intervals' was applied 313 times.
  - rule 'no_overlap: split into disjoint components' was applied 289 times.
  - rule 'objective: variable not used elsewhere' was applied 13 times.
  - rule 'presolve: 60606 unused variables removed.' was applied 1 time.
  - rule 'presolve: iteration' was applied 2 times.
  - rule 'variables with 2 values: create encoding literal' was applied 531 times.
  - rule 'variables with 2 values: new affine relation' was applied 531 times.
  - rule 'variables: canonicalize affine domain' was applied 20 times.
  - rule 'variables: detect fully reified value encoding' was applied 6 times.
  - rule 'variables: detect half reified value encoding' was applied 13'521 times.
  - rule 'variables: removable enforcement literal' was applied 73 times.

Presolved optimization model '': (model_fingerprint: 0x9a8dbb59f2e9107b)
#Variables: 44'308 (#bools: 1 #ints: 14 in objective)
  - 9'432 Booleans in [0,1]
  - 467 different domains in [-13144,2392697493450] with a largest complexity of 3.
  - 1 constants in {1}
#kAtMostOne: 12 (#literals: 57)
#kBoolAnd: 566 (#enforced: 566) (#literals: 1'132)
#kCircuit: 13
#kCumulative: 11 (#intervals: 8384, #optional: 8384, #variable_sizes: 8384)
#kExactlyOne: 1'337 (#literals: 8'654)
#kIntProd: 87
#kInterval: 11'463 (#enforced: 8'782) (#fixed: 2592)
#kLinMax: 74 (#expressions: 148)
#kLinear1: 10'677 (#enforced: 10'677)
#kLinear2: 69'091 (#enforced: 11'456)
#kLinear3: 8'871 (#enforced: 8'782)
#kLinearN: 164 (#terms: 8'825)
#kNoOverlap: 177 (#intervals: 20635, #optional: 17954, #variable_sizes: 18043, #fixed_intervals: 2592)

Preloading model.
#Bound  18.18s best:inf   next:[1,1262]   initial_domain
#Model  18.27s var:44307/44308 constraints:102543/102543

Starting search at 18.27s with 14 workers.
10 full problem subsolvers: [core, default_lp, fixed, lb_tree_search, max_lp, no_lp, pseudo_costs, quick_restart, quick_restart_no_lp, reduced_costs]
3 first solution subsolvers: [fj_long_default, fj_short_default, fs_random]
16 incomplete subsolvers: [feasibility_pump, graph_arc_lns, graph_cst_lns, graph_dec_lns, graph_var_lns, rins/rens, rnd_cst_lns, rnd_var_lns, routing_full_path_lns, routing_path_lns, routing_random_lns, scheduling_intervals_lns, scheduling_precedences_lns, scheduling_resource_windows_lns, scheduling_time_window_lns, violation_ls]
3 helper subsolvers: [neighborhood_helper, synchronization_agent, update_gap_integral]

[Laurent Perron]

try 9.10, feasibility jumps has been improved a lot.

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/9257f629-8e8a-49a9-890b-bc486377baa0n%40googlegroups.com.

[grego...@gmail.com]

From reduction of a model after presolve it seems that you modeled also impossible cases. It is possible that some variants were left after presolve that are hard to identify by a solver but you can find it with your knowledge of a problem. Finding of independent subproblems always help. Circuit constraint is very pricey, it always helped me avoid it and use some simpler alternative.

[S. K.]

I upgraded to 9.10, and at the moment, I don't notice any difference. Maybe the slightest bit faster.

I also tried to reduce the domains of some variables, but that did nothing.

Regarding the circuit constraint:

The part of my code which uses the AddCircuit constraint looks like this (simplified).
I need this part, because I need to know which job follows which job on a machine. With this information I calculate a transition/setup time, that I use another part of the code where I calculate the jobs total duration, etc.

I'm not sure how to remodel this to lose the AddCircuit constraint without losing the knowledge of which job follows which.

# Transition times and transition costs using a circuit constraint.

self.switch_literals = dict() # indexed by (machine_id, i,j) # []

self.total_cost = []

for machine_id in self.all_machines:

print(f'machine_id: {machine_id}')

machine_starts = starts_per_machines[machine_id]

machine_ends = ends_per_machines[machine_id]

machine_presences = presences_per_machines[machine_id]

machine_resources = resources_per_machines[machine_id]

machine_materials = materials_per_machines[machine_id]

machine_ranks = ranks_per_machines[machine_id]

intervals = intervals_per_machines[machine_id]

arcs = []

num_machine_tasks = len(machine_starts)

all_machine_tasks = range(num_machine_tasks)

collect_j = []

for i in all_machine_tasks:

# Initial arc from the dummy node (0) to a task.

start_lit = self.model.NewBoolVar('start_lit %i on machine %i' % (i, machine_id))

self.all_variables.append(start_lit)

arcs.append([0, i + 1, start_lit])

# If this task is the first, set both rank and start to 0.

self.model.Add(machine_ranks[i] == 0).OnlyEnforceIf(start_lit)

# Final arc from an arc to the dummy node.

final_arc = self.model.NewBoolVar('final_arc %i on machine %i' % (i, machine_id))

self.all_variables.append(final_arc)

arcs.append([i + 1, 0, final_arc])

# Self arc if the task is not performed.

arcs.append([i + 1, i + 1, machine_presences[i].Not()])

self.model.Add(machine_ranks[i] == -1).OnlyEnforceIf(machine_presences[i].Not())

# Compute the transition time if task j is the successor of task i.

parts_i = machine_starts[i].Name().split('_')

job_id_i, task_id_i, alt_id_i = int(parts_i[1][1:]), int(parts_i[2][1:]), int(parts_i[3][1:])

self.model.Add(self.add_time_trans[job_id_i, task_id_i, alt_id_i ] == 0).OnlyEnforceIf(start_lit)

for j in all_machine_tasks:

if i == j:

continue

lit = self.model.NewBoolVar('%i follows %i on machine %i' % (j, i, machine_id))

self.all_variables.append(lit)

arcs.append([i + 1, j + 1, lit])

self.model.AddImplication(lit, machine_presences[i])

self.model.AddImplication(lit, machine_presences[j])

# Maintain rank incrementally.

self.model.Add(machine_ranks[j] == machine_ranks[i] + 1).OnlyEnforceIf(lit)

# for solution hinting

self.switch_literals[(machine_id, i,j)] = lit

####

# Start of computing transition time

# Transition time is the duration time of the setup of task j

# The duration is needed for the part above and split_intervals_setter_Einspindler and split_intervals_setter_Rundtakt

# Compute the transition time if task j is the successor of task i.

parts_j = machine_starts[j].Name().split('_')

job_id_j, task_id_j, alt_id_j = int(parts_j[1][1:]), int(parts_j[2][1:]), int(parts_j[3][1:])

transition_time = self.ruestzeiten_werkzeugliste_id.loc[int(parts_i[1][1:])+1, int(parts_j[1][1:])+1]

if machine_materials[i] != machine_materials[j]:

materialfaktor = materialwechsel.loc[machine_materials[i], machine_materials[j]]# 3 #ruestzeiten

else:

materialfaktor = 0

# simplified for this example

additional_time = transition_time + materialfaktor

# End of computing transition time

####

# We add the

self.model.Add(machine_starts[j] >= machine_ends[i]).OnlyEnforceIf(lit)

# TEMP

#self.model.Add(machine_starts[j] <= machine_ends[i] + 0 + (max_distance_per_machine[machine_id]+90)*24).OnlyEnforceIf(lit)

if arcs:

self.model.AddCircuit(arcs)

[grego...@gmail.com]

Can you try it without circuits to see whether it finds a solution fast?

I see that you create arc for every possibility. When you know order of tasks or that some tasks cannot directly follow you can ignore impossible arcs.

Since you care about feasible solution you can extend every task by worst setup time. This way you can remove circuits. Another possibility can be express setup time by shortest possible distance between two tasks when present on same machine with two constraints for both orientations - much faster than circuit but still reduction in number of considered possibilities is welcomed.

[Laurent Perron]

THe problem seems really hard.

It took 10 hours with 32 workers to find the first solution.

The (incomplete) hint does not seem to help at all. If I fix all hinted variables to their value, it is still hard.

The best thing you can do is improve the hint.

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/df89700d-bd91-41d4-a99d-710efd241962n%40googlegroups.com.

[Laurent Perron]

note:  

random_seed: 3
max_presolve_iterations: 2: why limit it?
cp_model_probing_level: 4 -> no effect IMO
num_search_workers: 14 -> OK
use_optimization_hints: true -> OK
search_branching: PORTFOLIO_WITH_QUICK_RESTART_SEARCH -> make no sense with multiple workers
hint_conflict_limit: 75000 -> OK, but hint is of low quality

#extra_subsolvers: 'probing' 

#random_branches_ratio: 0.02

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