Bin packing

Mix.install([
  {:fixpoint, path: Path.join(System.get_env("HOME"), "projects/cpsolver")}
  #:fixpoint
])

Samples and runner

alias CPSolver.Search.VariableSelector, as: Strategy
alias CPSolver.Examples.BinPacking.UpperBound
gecode_doc_example =
  %{
    capacity: 100,
    weights: [
      99,98,95,95,95,94,94,91,88,87,86,85,76,74,73,71,68,60,55,54,51,
      45,42,40,39,39,36,34,33,32,32,31,31,30,29,26,26,23,21,21,21,19,
      18,18,16,15,5,5,4,1
    ]
  }

t60_00 = %{
  capacity: 1000,
  weights: [495,474,473,472,466,450,445,444,439,430,419,414,410,395,372,370,
    366,366,366,363,361,357,355,351,350,350,347,320,315,307,303,299,
    298,298,292,288,287,283,275,275,274,273,273,272,272,271,269,269,
    268,263,262,261,259,258,255,254,252,252,252,251]
}

t120_00 = %{
  capacity: 1000,
  weights: [
    497,497,495,485,480,478,474,473,472,470,466,450,446,445,445,444,
    439,434,430,420,419,414,412,410,407,405,400,397,395,376,372,370,
    366,366,366,366,366,363,363,362,361,357,357,356,356,355,352,351,
    350,350,350,347,336,333,329,325,320,315,314,313,307,303,302,301,
    299,298,298,298,295,294,292,290,288,287,283,282,282,276,275,275,
    274,273,273,272,272,271,271,269,269,268,267,267,266,263,263,262,
    262,261,260,259,259,259,258,256,255,254,254,254,253,253,253,253,
    252,252,252,252,251,251,250,250]  
}

instance_200_items =
  %{
    capacity: 100,
    weights: [
    100,99,99,97,97,97,94,93,92,92,91,89,89,88,88,88,88,87,87,86,
    86,86,86,86,85,84,83,83,82,81,81,81,81,80,80,79,79,79,78,78,77,
    77,77,76,76,76,75,74,74,73,73,73,73,72,72,72,72,72,71,71,69,69,
    68,67,67,66,66,66,66,64,64,64,64,63,63,62,61,61,61,60,60,59,59,
    57,56,56,56,55,55,55,54,54,53,53,52,52,52,51,50,50,50,49,49,49,
    49,47,47,46,46,46,46,46,46,45,45,45,45,44,44,42,41,40,40,40,39,
    39,38,38,38,38,38,38,37,37,36,36,36,36,34,34,34,34,34,34,31,31,
    31,30,30,30,30,30,29,29,27,27,27,26,24,24,23,22,22,22,22,22,20,
    18,17,17,17,16,16,15,15,14,14,14,13,13,12,11,11,11,10,10,8,8,
    8,6,6,5,5,4,4,3,3,3,1,1
    ]
  }

falkenauer_u120_00 = %{
  weights: [98, 98, 98, 96, 96, 94, 93, 93, 92, 91, 91, 90, 87, 86, 85, 85, 84, 84, 84, 84,
 84, 83, 83, 82, 82, 81, 80, 80, 80, 79, 79, 78, 78, 78, 78, 76, 74, 74, 73, 73,
 73, 73, 72, 71, 70, 70, 70, 69, 69, 69, 67, 66, 64, 62, 62, 60, 60, 59, 58, 58,
 58, 57, 57, 57, 57, 55, 55, 55, 50, 49, 49, 49, 47, 46, 46, 45, 45, 44, 44, 43,
 43, 43, 43, 42, 42, 42, 42, 42, 41, 41, 41, 39, 39, 38, 38, 38, 37, 36, 36, 36,
 35, 33, 33, 33, 32, 32, 30, 30, 30, 29, 28, 27, 27, 26, 25, 25, 24, 23, 23, 20],
 capacity: 120
}

trucks1 = %{
  weights: [
    39417, 42900, 44929, 6558, 37891, 35, 257, 2197, 36544, 1228, 5224, 18880, 7169, 1010, 8569, 
    1512, 27091, 457, 2003, 1822, 23, 765, 22081, 1021, 8833, 7676, 
    2391, 5112, 906, 4174, 43, 1311, 3065, 4487, 2975, 3175, 1414, 
    1057, 12, 15503, 6059, 65, 1065, 135, 4586, 6527, 265, 1921, 24, 
    4772, 531, 417, 24548, 453, 139, 
    41, 178, 184, 24988, 54, 10698, 5485, 2430, 21, 6629, 
    4039, 10448, 16725, 21401, 6457, 13506
  ],
  capacity: 45000
}

trucks2 = %{
  weights: 
  [
    60, 60, 32, 19, 27, 1, 1, 4, 52, 3, 4, 32, 6, 2, 14, 3, 47, 2, 2, 4,
    1, 1, 38, 2, 15, 6, 3, 8, 3, 4, 1, 4, 5, 7, 8, 8, 4, 2, 1, 39,
    10, 1, 1, 1, 5, 17, 1, 4, 1, 8, 1, 1, 19, 2, 1, 1, 1, 1, 20, 1,
    18, 15, 2, 1, 7, 7, 28, 12, 32, 6, 19
  ],
  capacity: 60
}

runner =
  fn %{capacity: capacity, weights: weights} = _instance, opts ->
    CPSolver.Examples.BinPacking.solve(weights, capacity,
     opts
    )
  end

processes_before = :erlang.processes() |> length()

{instance, threads, upper_bound, timeout} = 

#{instance_200_items, 4, nil, :timer.minutes(10)}

# {gecode_doc_example, 8, nil, :timer.minutes(5)}

#{falkenauer_u120_00, 3, nil, :timer.minutes(15)}

#{trucks1, 4, nil, :timer.minutes(5)}

#{trucks2, 4, nil, :timer.minutes(5)}

{t60_00, 4, nil, :timer.minutes(60 * 10)}

{t120_00, 4, nil, :timer.minutes(60)}

search = {:first_fail, :indomain_max} 
# {Strategy.afc({:afc_size_min, 0.75}, &List.first/1), :indomain_max}
runner.(instance, 
  [
    timeout: timeout,
    upper_bound: upper_bound || 
      UpperBound.first_fit_decreasing(instance.weights, instance.capacity),
    space_threads: threads,
    ## stop_on: {:max_solutions, 1}
    #search: search
  ]
)

processes_after = :erlang.processes() |> length()

stray_processes = processes_after - processes_before