% example data
bin_demands(b1,[3*glass, 4*plastic, 1*steel, 4*wood, 2*copper]).
bin_demands(b2,[6*glass, 8*plastic, 2*steel, 8*wood, 4*copper]).
bin_demands(c1,[32*glass,44*plastic,11*steel,44*wood,230*copper]).
bin_demands(d1,[132*glass,414*plastic,1001*steel,414*wood,230*copper]).
% pack 3 bin types with 5 types of commodities
bin_types([red,green,blue]).
commodities([glass, plastic, steel, wood, copper]).
% define a bin with constraints
bin(Type, Contents, Total):-
Type::integer(1,3), % enumeration of 3 bin types
{Red == (Type==1), Green == (Type==2), Blue == (Type==3)}, % true if bin the designated colour
Binsize::integer(1,4), % bin capacity, colour dependent
{Binsize == Red*3 + Blue*1 + Green*4}, % "conditional" expression
Contents=[Glass,Plastic,Steel,Wood,Copper], Contents::integer(0,_),
Total::integer(1,_), % % bin contains Total items (at least 1)
{Total == Glass + Plastic + Steel + Wood + Copper, Total =< Binsize},
{(Wood >= 1) -> (Plastic >= 1)}, % wood requires plastic
{Glass * Copper == 0}, % glass excludes copper
{Copper * Plastic == 0}, % copper excludes plastic
{Blue -> (Wood + Plastic == 0)}, % blue bin -> no plastc or wood
{Red -> ((0==Steel + Plastic) and (Wood=<1))}, % red bin -> no steel or plastic, no more than 1 wood
{Green -> ((0==Glass + Steel) and (Wood=<2))}. % green bin -> no steel or plastic, no more than 2 wood
setup_bins_(Items,Total,Contents) :-
commodities(Names),
get_bin_items_(Names,Items,Contents,0,Total).
get_bin_items_([],_,[],Total,Total).
get_bin_items_([N|Names],ItemsList,[C|Counts],Acc,Total):-
(memberchk(C*N,ItemsList) -> NewAcc is Acc+C ; NewAcc=Acc),
get_bin_items_(Names,ItemsList,Counts,NewAcc,Total).
% reduce result for output
accumulate_bins_([],[],Total,Total).
accumulate_bins_([bin(T,C,L)|BinsRaw],Bins,Acc,Total) :- !,
accumulate_bins_([1*bin(T,C,L)|BinsRaw],Bins,Acc,Total).
accumulate_bins_([0*_|BinsRaw],Bins,Acc,Total) :- !,
accumulate_bins_(BinsRaw,Bins,Acc,Total).
accumulate_bins_([N*B,B|BinsRaw],Bins,Acc,Total) :- !,
N1 is N+1,
accumulate_bins_([N1*B|BinsRaw],Bins,Acc,Total).
accumulate_bins_([N*bin(T,Contents,_)|BinsRaw],[N*Bin|Bins],Acc,Total) :-
bin_types(BTs), nth1(T,BTs,Type),
commodities(Names), format_commodities_(Names,Contents,Comms),
Bin =.. [Type|Comms], !,
AccN is Acc+N,
accumulate_bins_(BinsRaw,Bins,AccN,Total).
format_commodities_([],[],[]).
format_commodities_([N|Names],[Count|Contents],[Count*N|Comms]) :- Count>0, !,
format_commodities_(Names,Contents,Comms).
format_commodities_([_|Names],[_|Contents],Comms) :-
format_commodities_(Names,Contents,Comms).
% For example:
% ?- pack_bins([3*glass, 4*plastic, 1*steel, 4*wood, 2*copper],Bins,Required).
% Bins = [1*red(2*copper), 1*red(3*glass), 2*green(2*plastic, 2*wood), 1*blue(1*steel)],
% Required = 5.
%
pack_bins(Items,Bins,Required) :-
setup_bins_(Items,Total,ItemsRaw), % process input
bin_load_(Total,ItemsRaw,BinsRaw), % add a bin (further add on backtracking)
bins_ordered_(BinsRaw), % order bins to break symmetry
enum_bins_(BinsRaw), !, % enumerate bin type and contents - single solution
accumulate_bins_(BinsRaw,Bins,0,Required). % format for output
bin_load_(0, [0,0,0,0,0], []).
bin_load_(Total, Amounts, [bin(Type,Contents,Size)|Bins]) :-
bin(Type,Contents,Size), % new bin
{T == Total - Size, T>=0}, % decrease total by bin capacity
subtract_clp(Amounts, Contents, Residual), % decrease each commodity using bin contents
bin_load_(T, Residual, Bins). % repeat until feasible solution exists
bins_ordered_([_]) :- !.
bins_ordered_([X,Y|Xs]) :- order_bins_(X,Y), bins_ordered_([Y|Xs]).
order_bins_(bin(T1,_,S1), bin(T2,_,S2)) :-
{(T1<T2) or ((T1==T2) and (S1=<S2))}.
subtract_clp([], [], []).
subtract_clp([X|Xs], [Y|Ys], [Z|Zs]) :-
{Z == X - Y, Z >= 0}, % can't get to -ve items
subtract_clp(Xs,Ys,Zs).
enum_bins_([]).
enum_bins_([bin(T,C,_S)|Bs]):-
enumerate([T|C]),
enum_bins_(Bs).
% For example:
% ?- fastpack_bins([3*glass, 4*plastic, 1*steel, 4*wood, 2*copper],Bins,Required).
% Bins = [1*blue(1*steel), 1*green(2*copper), 1*red(3*glass), 2*green(2*plastic, 2*wood)],
% Required = 5.
%
fastpack_bins(Items,Bins,Required) :-
setup_bins_(Items,_Total,ItemsRaw), % process input
% generate possible load patterns
findall(bin(Type,Contents,Size), (bin(Type, Contents, Size), enumerate([Type|Contents])), BinDefs),
% use ItemsRaw and BinDefs to define linear objective expression and constraints
bins_lin_summation(ItemsRaw,BinDefs,NBins,Obj,Constraints),
lin_minimize(Obj,{Constraints},_Min), % and minimize
accumulate_bins_(NBins,Bins,0,Required). % format for output
bins_lin_summation(Items,BinDefs,NBins,Obj,Constraints) :-
bins_list(BinDefs,Ns,NBins), % lists of pattern counts
sym_sum_list(Ns,Obj), % Objective function is sum of counts
length(Items,TLen), % construct constraint for each type
lin_constraints_bins(0,TLen,Items,BinDefs,Ns,Constraints).
bins_list([],[],[]).
bins_list([Bin|BinDefs],[N|Ns],[N*Bin|NBins]) :-
N::integer(0,_),
bins_list(BinDefs,Ns,NBins).
lin_constraints_bins(T,T,_,_,_,[]) :- !.
lin_constraints_bins(T,TLen,Items,BinDefs,Ns,[LHS==RHS|Constraints]):-
bin_lhs_constraint_(BinDefs,Ns,T,LHS),
nth0(T,Items,RHS),
T1 is T+1,
lin_constraints_bins(T1,TLen,Items,BinDefs,Ns,Constraints).
bin_lhs_constraint_([bin(_,Contents,_)],[N],T, CI*N) :- !,
nth0(T,Contents,CI).
bin_lhs_constraint_([bin(_,Contents,_)|BinDefs],[N|Ns],T, RHS) :-
nth0(T,Contents,CI),
(CI==0
-> bin_lhs_constraint_(BinDefs,Ns,T,RHS)
; RHS = CI*N+RHS1,
bin_lhs_constraint_(BinDefs,Ns,T,RHS1)
).
sym_sum_list([X],X) :- !.
sym_sum_list([X|Xs],X+XS) :-
sym_sum_list(Xs,XS).