/* 

  Cutting stock example in Picat.

  Winston "Operations Research", page 570.
  """
  Woodco sells 3-ft, 5-ft, and 9-ft pieces of lumber. W:s customers demand
  25 3-ft, 20 5-ft and 15 9-ft boards. ... by cutting up 17-ft boards.
  """

  The different ways of cutting a 17-ft board:
               
  Combination  3-ft   5-ft   9-ft   waste
  1             5     0      0       2
  2             4     1      0       0
  3             2     2      0       1
  4             2     0      1       2
  5             1     1      1       0
  6             0     3      0       2


  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


% import util.
import cp.


main => go.


go =>

  cuts(Cuts),  
  NumCuts = Cuts.length,
  combinations(Combinations),
  NumComb = Combinations.length,

  demand(Demand),

  % decision variables
  X = new_list(NumComb),
  X :: 0..1000,

  TotalSum #= sum(X),

  foreach(I in 1..NumComb)
    X[I] #>= 0
  end,
  foreach(J in 1..NumCuts)
     sum([Combinations[I,J]*X[I] : I in 1..NumComb]) #>= Demand[J]
  end,

  solve($[min(TotalSum)], X),

  println(totalSum=TotalSum),
  println(x=X),
  nl.

%
% Data
%

combinations(Combinations) => 
  Combinations = 
  [[5, 0, 0],
   [4, 1, 0],
   [2, 2, 0],
   [2, 0, 1],
   [1, 1, 1],
   [0, 3, 0]].

cuts(Cuts) => Cuts = [3,5,9].
demand(Demand) => Demand = [25, 20, 15].