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
}

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

{instance, threads, upper_bound, timeout} = 
#{instance_200_items, 2, nil, :timer.minutes(10)}

#{gecode_doc_example, 3, nil, :timer.minutes(3)}
{falkenauer_u120_00, 3, 63, :timer.hours(10)}
#{t60_00, 3, nil, :timer.minutes(5)}
#{t120_00, 3, 45, :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
  ]
)