Constraint for distance between two circles

[Joonas Palonen]

Hello,

I am working on a circle bin packing problem and using OR-Tools 9.6 and CP-SAT solver.

The goal is to pack N circular items into M pallets, that can have varying sizes. The objective function is to minimize the total area of the pallets used. I am having troube with implementing a constraint that enforces no overlap on two circles, which is formulated by the following formula:

Currently my implementation is following:

Is it possible to implement the constraint that enforces no overlap in OR-Tools?

Thanks,

Joonas

[Joonas Palonen]

And to be more accurate, this is the problematic part in the code now

[Joonas Palonen]

Apparently the image with whole code is not loading, so trying again.

[Laurent Perron]

answered in the next mail.

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/130658ea-6fe8-4c84-a675-8513bb5753aan%40googlegroups.com.

[watchdogs132]

You need to do something like this (https://github.com/google/or-tools/blob/main/examples/python/spread_robots_sat.py#L68-L77) for the LHS. 

[Joonas Palonen]

Great! This looks promising.

Thanks Laurent!

[youssef kaichouh]

Why not see ur area as a grid

--

[Joonas Palonen]

I got my implementation working with your advices. Currently my code is working nicely for smaller cases, but when I increase the item size, the solving process takes an infeasible amount of time. Can you spot any obvious places or ways I could improve my performance or reudce the amount of variables created during the search.

"""

Bounds

"""

order['all_items'] = list(range(len(group)))

# Upper bound for number of bins (each stack in own pallet) and pallet for each size option.

order['all_pallets'] = list(range(len(group)*len(order['palletDims'])))

order['pallet_dimensions'] = []

order['pallet_costs'] = []

for dims in order['palletDims']:

for i in range(len(group)):

        order['pallet_costs'].append(dims[2])

        order['pallet_dimensions'].append((dims[0],dims[1]))

"""

Variables

"""

model = cp_model.CpModel()

# x[i, b] = 1 if item i is packed in pallet b.

x = {}

for i in order['all_items']:

    for b in order['all_pallets']:

      x[i, b] = model.NewBoolVar(f'x_{i}_{b}')

# y[j] = 1 if pallet b is used

y = {}

for b in order['all_pallets']:

    y[b] = model.NewBoolVar('y[%i]' % (b))

# Center X and Y coodinates for stack i in pallet b

cx = {}

cy = {}

for b in order['all_pallets']:

    cx[b] = [ model.NewIntVar(0+stack._radius, order['pallet_dimensions'][b][0]-stack._radius,

f'cx.{i}_{b}') for i, stack in enumerate(group) ]

    cy[b] = [ model.NewIntVar(0+stack._radius, order['pallet_dimensions'][b][1]-stack._radius,

f'cy.{i}_{b}') for i, stack in enumerate(group) ]

"""

Constaints

"""

# Each item must be in exactly one pallet.

for i, stack in enumerate(group):

    model.Add(sum(x[i, b] for b in order['all_pallets']) == 1)

# Pallet size constraint, the area of packed stacks cannot exceed the pallet area.

for b in order['all_pallets']:

    model.Add( sum(x[(i, b)] * stack.area for i, stack in enumerate(group)) <= y[b] * order['pallet_costs'][b] )

       

# Enforce no overlap on stack items

for b in order['all_pallets']:

for i in range(len(group) - 1):

        for j in range(i + 1, len(group)):

            # Compute the distance on each dimension between stack i and stack j.

            x_diff = model.NewIntVar(-order['pallet_dimensions'][b][0], order['pallet_dimensions'][b][0],

f'x_diff{i}')

            y_diff = model.NewIntVar(-order['pallet_dimensions'][b][1], order['pallet_dimensions'][b][1],

f'y_diff{i}')

            model.Add(x_diff == cx[b][i] - cx[b][j])

            model.Add(y_diff == cy[b][i] - cy[b][j])

            # Compute the square of the previous differences.

            x_diff_sq = model.NewIntVar(0, order['pallet_dimensions'][b][0]**2, f'x_diff_sq{i}')

            y_diff_sq = model.NewIntVar(0, order['pallet_dimensions'][b][1]**2, f'y_diff_sq{i}')

            model.AddMultiplicationEquality(x_diff_sq, x_diff, x_diff)

            model.AddMultiplicationEquality(y_diff_sq, y_diff, y_diff)

            # Compute the stack1 and 2 sum of radius'

          rad = model.NewIntVar(0, order['pallet_dimensions'][b][0], f'rad_{i}')

            model.Add( rad == ((group[i]._radius * x[(i,b)]) + (group[j]._radius * x[(j,b)])) )

            rad_sq = model.NewIntVar(0, order['pallet_costs'][b], f'rad_sq{i}')

            model.AddMultiplicationEquality(rad_sq, rad, rad)

            # Enforce distance between stack i and j be equal or over to the sum of their radius

            # (x1-x2)^2 + (y1-y2)^2 >= d^2

            model.Add( x_diff_sq + y_diff_sq >= rad_sq )

"""

Objective

"""

# Minimize the combined total area of the pallets

model.Minimize( sum([ y[b] * order['pallet_costs'][b] for b in order['all_pallets'] ]) )

"""

Solve

"""

solver = cp_model.CpSolver()

solver.parameters.num_search_workers = 8

status = solver.Solve(model)

Big thanks,

[Laurent Perron]

you should set the log to see what is happening.

solver.parameters.log_search_progress = True

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/869a1698-30a7-46f1-9d8e-d3c3ea88f86en%40googlegroups.com.

[Joonas Palonen]

The logging process doesn't really tell me anything, whether there is someting wrong or if some step can be improved. Can you spot something out of the ordinary? Or give some explanations on how the solving process could be interpreted.

Log:

Starting CP-SAT solver v9.6.2534
Parameters: log_search_progress: true num_search_workers: 8

Initial optimization model '': (model_fingerprint: 0xd26401b870dc8921)
#Variables: 3010 (#bools:10 in objective)
  - 110 Booleans in [0,1]
  - 900 in [-800,800]
  - 450 in [0,800]
  - 1350 in [0,640000]
  - 200 in [200,600]
#kIntProd: 1350
#kLinear1: 20
#kLinear2: 180
#kLinear3: 1800
#kLinearN: 20 (#terms: 210)

Starting presolve at 0.01s
[ExtractEncodingFromLinear] #potential_supersets=10 #potential_subsets=450 #at_most_one_encodings=0 #exactly_one_encodings=0 #unique_terms=0 #multiple_terms=0 #literals=0 time=0.0003023s
[Probing] deterministic_time: 0.0001641 (limit: 1) wall_time: 0.0094835 (110/110)
[Probing]  - new binary clause: 100
[Probing] implications and bool_or (work_done=2240).
[DetectDuplicateConstraints] #duplicates=0 #without_enforcements=0 time=0.0114144s
[DetectDominatedLinearConstraints] #relevant_constraints=1990 #work_done=18924 #num_inclusions=180 #num_redundant=180 time=0.0021236s
[ProcessSetPPC] #relevant_constraints=20 #num_inclusions=0 work=520 time=0.0036634s
[FindBigLinearOverlap] #blocks=0 #saved_nz=0 #linears=10 #work_done=110/1e+09 time=6.77e-05s
[MergeClauses] #num_collisions=0 #num_merges=0 #num_saved_literals=0 work=0/100000000 time=5.02e-05s
[Probing] deterministic_time: 0.0001641 (limit: 1) wall_time: 0.0060081 (110/110)
[Probing]  - new binary clause: 100
[Probing] implications and bool_or (work_done=2240).
[DetectDuplicateConstraints] #duplicates=0 #without_enforcements=0 time=0.0065744s
[DetectDominatedLinearConstraints] #relevant_constraints=1810 #work_done=16584 #num_inclusions=0 #num_redundant=0 time=0.0009908s
[ProcessSetPPC] #relevant_constraints=20 #num_inclusions=0 work=520 time=0.0023885s
[FindBigLinearOverlap] #blocks=0 #saved_nz=0 #linears=10 #work_done=110/1e+09 time=4.77e-05s
[MergeClauses] #num_collisions=0 #num_merges=0 #num_saved_literals=0 work=0/100000000 time=1.96e-05s
[ExpandObjective] #propagations=0 #entries=6660 #tight_variables=2980 #tight_constraints=1360 #expands=0 #issues=0 time=0.0012759s

Presolve summary:
  - 900 affine relations were detected.
  - rule 'TODO dual: only one blocking constraint?' was applied 8160 times.
  - rule 'TODO dual: only one unspecified blocking constraint?' was applied 60 times.
  - rule 'affine: new relation' was applied 900 times.
  - rule 'int_prod: divide product by constant factor' was applied 450 times.
  - rule 'int_square: reduced target domain.' was applied 1350 times.
  - rule 'linear inclusion: subset + singleton is equality' was applied 180 times.
  - rule 'linear with partial amo: constant coeff' was applied 10 times.
  - rule 'linear: divide by GCD' was applied 450 times.
  - rule 'linear: positive equal one' was applied 10 times.
  - rule 'linear: reduced variable domains' was applied 1350 times.
  - rule 'linear: reduced variable domains in derived constraint' was applied 180 times.
  - rule 'linear: remapped using affine relations' was applied 1800 times.
  - rule 'linear: simplified rhs' was applied 1090 times.
  - rule 'presolve: 0 unused variables removed.' was applied 1 time.
  - rule 'presolve: iteration' was applied 2 times.
  - rule 'variables: canonicalize affine domain' was applied 900 times.

Presolved optimization model '': (model_fingerprint: 0x120ea2c96bef2432)
#Variables: 3010 (#bools:10 in objective)
  - 110 Booleans in [0,1]
  - 180 in [-400,0]
  - 720 in [-400,400]
  - 450 in [0,1][4]
  - 450 in [0,2]
  - 900 in [0,160000]
  - 200 in [200,600]
#kExactlyOne: 10 (#literals: 100)
#kIntProd: 1350
#kLinear3: 1800
#kLinearN: 10 (#terms: 110)

Preloading model.
#Bound   0.28s best:inf   next:[0,6400000] initial_domain
#Model   0.29s var:3010/3010 constraints:3170/3170

Starting search at 0.29s with 8 workers.
6 full problem subsolvers: [default_lp, no_lp, max_lp, core, reduced_costs, pseudo_costs]
1 first solution subsolver: [random_0]
7 incomplete subsolvers: [feasibility_pump, rins_lns_default, rens_lns_default, rnd_var_lns_default, rnd_cst_lns_default, graph_var_lns_default, graph_cst_lns_default]
3 helper subsolvers: [synchronization_agent, neighborhood_helper, update_gap_integral]
#Bound   0.37s best:inf   next:[640000,6400000] bool_core num_cores:1 [core:9 mw:1 d:0] assumptions:2 depth:4 fixed_bools:0/125
#Bound   0.37s best:inf   next:[1280000,6400000] bool_core num_cores:2 [core:2 mw:1 d:4] assumptions:1 depth:5 fixed_bools:0/130
#1       3.19s best:5120000 next:[1280000,4480000] rens_lns_default_incomplete(d=0.50 s=10 t=0.10 p=0.00) [presolve]
#2       4.45s best:2560000 next:[1280000,1920000] graph_var_lns_default(d=0.50 s=14 t=0.10 p=0.00)
#3       5.91s best:1920000 next:[1280000,1280000] graph_var_lns_default(d=0.45 s=40 t=0.10 p=0.50)
#Model  86.43s var:3009/3010 constraints:3170/3170
#Model 109.60s var:3006/3010 constraints:3168/3170
#Model 133.99s var:3001/3010 constraints:3164/3170
#Model 225.04s var:3000/3010 constraints:3164/3170
#Model 326.22s var:2999/3010 constraints:3164/3170
#Model 332.38s var:2988/3010 constraints:3156/3170
#Model 417.47s var:2983/3010 constraints:3152/3170
#Model 548.63s var:2982/3010 constraints:3152/3170
#Model 618.58s var:2979/3010 constraints:3150/3170
#Model 645.35s var:2878/3010 constraints:3062/3170 compo:2678,100,100
#Model 653.63s var:2778/3010 constraints:3017/3170 compo:2678,100
#Model 668.36s var:2678/3010 constraints:2972/3170
#Model 762.67s var:2636/3010 constraints:2940/3170
#Done  765.50s bool_core num_cores:3 [core:1 mw:1 d:5] assumptions:1 depth:5 fixed_bools:0/35139
#Done  765.50s core

Sub-solver search statistics:
  'default_lp':
    Search statistics:
      booleans: 12'098
      conflicts: 52'203
      branches: 348'304
      binary_propagations: 28'931'819
      integer_propagations: 12'240'833
      restarts: 262
    LP statistics:
      final dimension: 1943 rows, 3010 columns, 5456 entries with magnitude in [8.248720e-04, 1.000000e+00]
      total number of simplex iterations: 270'967
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 99'650
      managed constraints: 12'175
      merged constraints: 33'302
      shortened constraints: 9'078
      split constraints: 8
      coefficient strenghtenings: 32'711
      num simplifications: 21'990
      total cuts added: 8'475 (out of 61'607 calls)
        - 'CG_KB': 57
        - 'CG_KL': 6
        - 'CG_R': 1'603
        - 'CG_RB': 1'128
        - 'CG_RBP': 781
        - 'IB': 3'230
        - 'MIR_1_F': 171
        - 'MIR_1_KB': 17
        - 'MIR_1_R': 101
        - 'MIR_1_RB': 9
        - 'MIR_1_RBP': 7
        - 'MIR_2_F': 79
        - 'MIR_2_KB': 18
        - 'MIR_2_R': 102
        - 'MIR_2_RB': 13
        - 'MIR_2_RBP': 13
        - 'MIR_3_F': 39
        - 'MIR_3_KB': 30
        - 'MIR_3_R': 131
        - 'MIR_3_RB': 28
        - 'MIR_3_RBP': 19
        - 'MIR_4_F': 50
        - 'MIR_4_KB': 20
        - 'MIR_4_KL': 2
        - 'MIR_4_R': 81
        - 'MIR_4_RB': 17
        - 'MIR_4_RBP': 27
        - 'MIR_5_F': 20
        - 'MIR_5_KB': 8
        - 'MIR_5_KL': 1
        - 'MIR_5_R': 23
        - 'MIR_5_RB': 4
        - 'MIR_5_RBP': 9
        - 'MIR_6_F': 8
        - 'MIR_6_KB': 2
        - 'MIR_6_KL': 2
        - 'MIR_6_R': 13
        - 'MIR_6_RB': 5
        - 'MIR_6_RBP': 6
        - 'SquareLower': 139
        - 'SquareUpper': 8
        - 'ZERO_HALF_F': 11
        - 'ZERO_HALF_KB': 32
        - 'ZERO_HALF_R': 312
        - 'ZERO_HALF_RB': 48
        - 'ZERO_HALF_RBP': 45

  'no_lp':
    Search statistics:
      booleans: 30'902
      conflicts: 258'858
      branches: 12'411'067
      binary_propagations: 383'432'302
      integer_propagations: 263'910'400
      restarts: 1'506

  'max_lp':
    Search statistics:
      booleans: 6'776
      conflicts: 36'770
      branches: 146'614
      binary_propagations: 16'386'235
      integer_propagations: 6'909'457
      restarts: 240
    LP statistics:
      final dimension: 2267 rows, 3010 columns, 6277 entries with magnitude in [2.402811e-02, 1.000000e+00]
      total number of simplex iterations: 75'183
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 63'787
        - #DUAL_FEASIBLE: 2'990
      managed constraints: 13'441
      merged constraints: 29'146
      shortened constraints: 6'379
      coefficient strenghtenings: 13'498
      num simplifications: 10'905
      total cuts added: 11'739 (out of 64'765'544 calls)
        - 'CG_KB': 338
        - 'CG_KL': 3
        - 'CG_R': 1'118
        - 'CG_RB': 970
        - 'CG_RBP': 568
        - 'Clique': 90
        - 'IB': 1'573
        - 'MIR_1_F': 66
        - 'MIR_1_KB': 7
        - 'MIR_1_KL': 1
        - 'MIR_1_R': 53
        - 'MIR_1_RB': 6
        - 'MIR_1_RBP': 6
        - 'MIR_2_F': 29
        - 'MIR_2_KB': 5
        - 'MIR_2_R': 47
        - 'MIR_2_RB': 19
        - 'MIR_2_RBP': 9
        - 'MIR_3_F': 34
        - 'MIR_3_KB': 8
        - 'MIR_3_R': 78
        - 'MIR_3_RB': 32
        - 'MIR_3_RBP': 28
        - 'MIR_4_F': 9
        - 'MIR_4_KB': 6
        - 'MIR_4_KL': 2
        - 'MIR_4_R': 55
        - 'MIR_4_RB': 38
        - 'MIR_4_RBP': 39
        - 'MIR_5_F': 9
        - 'MIR_5_KB': 18
        - 'MIR_5_KL': 3
        - 'MIR_5_R': 44
        - 'MIR_5_RB': 11
        - 'MIR_5_RBP': 9
        - 'MIR_6_F': 3
        - 'MIR_6_KB': 9
        - 'MIR_6_R': 21
        - 'MIR_6_RB': 6
        - 'MIR_6_RBP': 6
        - 'SquareLower': 5'903
        - 'SquareUpper': 8
        - 'ZERO_HALF_F': 3
        - 'ZERO_HALF_KB': 51
        - 'ZERO_HALF_R': 288
        - 'ZERO_HALF_RB': 96
        - 'ZERO_HALF_RBP': 14

  'core':
    Search statistics:
      booleans: 35'139
      conflicts: 200'359
      branches: 13'659'576
      binary_propagations: 489'127'480
      integer_propagations: 285'233'205
      restarts: 228

  'reduced_costs':
    Search statistics:
      booleans: 11'809
      conflicts: 49'073
      branches: 190'319
      binary_propagations: 17'379'006
      integer_propagations: 8'106'910
      restarts: 246
    LP statistics:
      final dimension: 1865 rows, 3010 columns, 5225 entries with magnitude in [1.581139e-02, 1.000000e+00]
      total number of simplex iterations: 91'442
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 90'944
        - #DUAL_FEASIBLE: 2'239
      managed constraints: 12'279
      merged constraints: 16'408
      shortened constraints: 196
      coefficient strenghtenings: 3'326
      num simplifications: 1'684
      total cuts added: 8'570 (out of 99'357'942 calls)
        - 'CG_KB': 16
        - 'CG_KL': 16
        - 'CG_R': 113
        - 'CG_RB': 26
        - 'CG_RBP': 18
        - 'Clique': 92
        - 'IB': 1'409
        - 'MIR_1_R': 23
        - 'MIR_2_R': 10
        - 'MIR_3_KL': 3
        - 'MIR_3_R': 8
        - 'MIR_4_R': 4
        - 'MIR_5_R': 3
        - 'MIR_6_R': 2
        - 'SquareLower': 6'752
        - 'SquareUpper': 1
        - 'ZERO_HALF_KB': 6
        - 'ZERO_HALF_KL': 20
        - 'ZERO_HALF_R': 36
        - 'ZERO_HALF_RB': 12

  'pseudo_costs':
    Search statistics:
      booleans: 9'492
      conflicts: 21'202
      branches: 175'713
      binary_propagations: 7'633'644
      integer_propagations: 5'297'962
      restarts: 246
    LP statistics:
      final dimension: 1984 rows, 3010 columns, 5529 entries with magnitude in [5.000000e-03, 1.000000e+00]
      total number of simplex iterations: 76'163
      total num cut propagation: 0
      num solves:
        - #OPTIMAL: 71'434
        - #DUAL_FEASIBLE: 4'494
      managed constraints: 12'784
      merged constraints: 37'394
      shortened constraints: 10'601
      coefficient strenghtenings: 21'867
      num simplifications: 23'604
      total cuts added: 13'076 (out of 82'483'298 calls)
        - 'CG_KB': 162
        - 'CG_KL': 19
        - 'CG_R': 1'721
        - 'CG_RB': 1'022
        - 'CG_RBP': 537
        - 'Clique': 145
        - 'IB': 3'086
        - 'MIR_1_F': 173
        - 'MIR_1_KB': 2
        - 'MIR_1_R': 75
        - 'MIR_1_RB': 20
        - 'MIR_1_RBP': 1
        - 'MIR_2_F': 87
        - 'MIR_2_KB': 17
        - 'MIR_2_R': 81
        - 'MIR_2_RB': 15
        - 'MIR_2_RBP': 10
        - 'MIR_3_F': 84
        - 'MIR_3_KB': 42
        - 'MIR_3_KL': 1
        - 'MIR_3_R': 217
        - 'MIR_3_RB': 52
        - 'MIR_3_RBP': 54
        - 'MIR_4_F': 73
        - 'MIR_4_KB': 19
        - 'MIR_4_R': 154
        - 'MIR_4_RB': 33
        - 'MIR_4_RBP': 67
        - 'MIR_5_F': 43
        - 'MIR_5_KB': 17
        - 'MIR_5_KL': 2
        - 'MIR_5_R': 55
        - 'MIR_5_RB': 13
        - 'MIR_5_RBP': 23
        - 'MIR_6_F': 9
        - 'MIR_6_KB': 10
        - 'MIR_6_KL': 1
        - 'MIR_6_R': 22
        - 'MIR_6_RB': 5
        - 'MIR_6_RBP': 12
        - 'SquareLower': 4'538
        - 'SquareUpper': 1
        - 'ZERO_HALF_KB': 44
        - 'ZERO_HALF_KL': 1
        - 'ZERO_HALF_R': 233
        - 'ZERO_HALF_RB': 49
        - 'ZERO_HALF_RBP': 29


Solutions found per subsolver:
  'graph_var_lns_default': 2
  'rens_lns_default_incomplete': 1

Objective bounds found per subsolver:
  'bool_core': 2
  'initial_domain': 1

Improving variable bounds shared per subsolver:
  'default_lp': 2
  'no_lp': 459
  'pseudo_costs': 57
  'reduced_costs': 6

Clauses shared per subsolver:
  'default_lp': 1
  'max_lp': 1
  'no_lp': 86
  'pseudo_costs': 4

CpSolverResponse summary:
status: OPTIMAL
objective: 1920000
best_bound: 1920000
integers: 3014
booleans: 12098
conflicts: 52203
branches: 348304
propagations: 28931819
integer_propagations: 12240833
restarts: 262
lp_iterations: 270967
walltime: 766.332
usertime: 766.332
deterministic_time: 309.457
gap_integral: 22.66
solution_fingerprint: 0x3c08bab27c94f8de

[Joonas Palonen]

Interestingly, the output of that solving process says to be optimal, but the item placements actually have items on top of eachother (interesing parts bolded in the output below). For pallets 1 and 2 all stacks are placed on the same coordinates, but pallet 3 is perfect. And this is done in one calculation.

Pallet 1 (800x800)

        Stack 6: (400x1000)
                Reel 5: {'_id': 5, '_ordNum': 'testi7', '_horizontal': False, '_width': 500, '_length': 4000, '_diameter': 400, '_x': 400, '_y': 200, '_z': 0}
                Reel 20: {'_id': 20, '_ordNum': 'testi7', '_horizontal': False, '_width': 500, '_length': 4000, '_diameter': 400, '_x': 400, '_y': 200, '_z': 500}
        Stack 8: (400x1000)
                Reel 17: {'_id': 17, '_ordNum': 'testi7', '_horizontal': False, '_width': 500, '_length': 4000, '_diameter': 400, '_x': 400, '_y': 200, '_z': 0}
                Reel 19: {'_id': 19, '_ordNum': 'testi7', '_horizontal': False, '_width': 500, '_length': 4000, '_diameter': 400, '_x': 400, '_y': 200, '_z': 500}
        Stack 10: (400x1000)
                Reel 16: {'_id': 16, '_ordNum': 'testi7', '_horizontal': False, '_width': 500, '_length': 4000, '_diameter': 400, '_x': 400, '_y': 200, '_z': 0}
                Reel 18: {'_id': 18, '_ordNum': 'testi7', '_horizontal': False, '_width': 500, '_length': 4000, '_diameter': 400, '_x': 400, '_y': 200, '_z': 500}
Pallet 2 (800x800)
        Stack 2: (400x1000)
                Reel 11: {'_id': 11, '_ordNum': 'testi7', '_horizontal': False, '_width': 500, '_length': 4000, '_diameter': 400, '_x': 200, '_y': 400, '_z': 0}
                Reel 14: {'_id': 14, '_ordNum': 'testi7', '_horizontal': False, '_width': 500, '_length': 4000, '_diameter': 400, '_x': 200, '_y': 400, '_z': 500}
        Stack 4: (400x1000)
                Reel 2: {'_id': 2, '_ordNum': 'testi7', '_horizontal': False, '_width': 500, '_length': 4000, '_diameter': 400, '_x': 200, '_y': 400, '_z': 0}
                Reel 3: {'_id': 3, '_ordNum': 'testi7', '_horizontal': False, '_width': 500, '_length': 4000, '_diameter': 400, '_x': 200, '_y': 400, '_z': 500}
        Stack 5: (400x1000)
                Reel 6: {'_id': 6, '_ordNum': 'testi7', '_horizontal': False, '_width': 500, '_length': 4000, '_diameter': 400, '_x': 200, '_y': 400, '_z': 0}
                Reel 7: {'_id': 7, '_ordNum': 'testi7', '_horizontal': False, '_width': 500, '_length': 4000, '_diameter': 400, '_x': 200, '_y': 400, '_z': 500}
Pallet 3 (800x800)
        Stack 1: (400x1000)
                Reel 1: {'_id': 1, '_ordNum': 'testi7', '_horizontal': False, '_width': 500, '_length': 4000, '_diameter': 400, '_x': 200, '_y': 200, '_z': 0}
                Reel 4: {'_id': 4, '_ordNum': 'testi7', '_horizontal': False, '_width': 500, '_length': 4000, '_diameter': 400, '_x': 200, '_y': 200, '_z': 500}
        Stack 3: (400x1000)
                Reel 9: {'_id': 9, '_ordNum': 'testi7', '_horizontal': False, '_width': 500, '_length': 4000, '_diameter': 400, '_x': 200, '_y': 600, '_z': 0}
                Reel 12: {'_id': 12, '_ordNum': 'testi7', '_horizontal': False, '_width': 500, '_length': 4000, '_diameter': 400, '_x': 200, '_y': 600, '_z': 500}
        Stack 7: (400x1000)
                Reel 8: {'_id': 8, '_ordNum': 'testi7', '_horizontal': False, '_width': 500, '_length': 4000, '_diameter': 400, '_x': 600, '_y': 200, '_z': 0}
                Reel 15: {'_id': 15, '_ordNum': 'testi7', '_horizontal': False, '_width': 500, '_length': 4000, '_diameter': 400, '_x': 600, '_y': 200, '_z': 500}
        Stack 9: (400x1000)
                Reel 10: {'_id': 10, '_ordNum': 'testi7', '_horizontal': False, '_width': 500, '_length': 4000, '_diameter': 400, '_x': 600, '_y': 600, '_z': 0}
                Reel 13: {'_id': 13, '_ordNum': 'testi7', '_horizontal': False, '_width': 500, '_length': 4000, '_diameter': 400, '_x': 600, '_y': 600, '_z': 500}

[Joonas Palonen]

Hello Laurent!

Only progress I've been able to make is to determine that the bad performance only occurs, when the solver needs to assign more than one pallet to fit all the items. For large amounts of items on a theoretically huge pallet, the execution is fast.

Any ideas on this subject? Or can you spot any mistakes in my code that might cause this behaviour?

Br,

Joonas