Thanks Michael, I understand.
But what it is not clear to me is once I have the type and numbers for
type how to do it:
let's say there's this *data1.csv* having:
ITEM,WEIGHT,ALLOY,BATCH,MOULD
1,85,2502,H27587V,P27795
2,85,2502,H27587V,P27795
3,85,2502,H27587V,P27795
4,85,2502,H27587V,P27795
5,63,2502,H27587V,P12396
6,63,2502,H27587V,P12396
7,63,2502,H27587V,P12396
8,63,2502,H27587V,P12396
9,42,2502,H27587V,P27532
10,42,2502,H27587V,P27532
11,42,2502,H27587V,P27532
12,42,2502,H27587V,P27532
13,42,2502,H27587V,P27532
14,78,2502,H27587V,P35495
15,78,2502,H27587V,P35495
16,78,2502,H27587V,P35495
where WEIGHT is the weight I'll use in the bpp example of Andrew Makhorin,
alloy and batch are descriptive and mould is the type.
My code is:
set I;
param w{it in I}, > 0; # Weight of item i (w[i])
param al{it in I}; # Alloy
param ba{it in I} symbolic; # Batch
param mo{it in I} symbolic; # Mould
table tab_items IN "CSV" "data1.csv" :
I <- [ITEM], w ~ WEIGHT, al ~ ALLOY, ba ~ BATCH, mo ~ MOULD;
printf{it in I}: "%d %d %s %s \n", it,w[it],ba[it], mo[it];
set mouldTypes := setof{it in I} mo[it];
# Count the distinct molds
param cmt := card(mouldTypes);
#display mouldTypes;
display cmt;
#param itemCounts{ti in mouldTypes};
param itemCounts{ti in mouldTypes} := sum{i in I: mo[i] = ti} 1;
for {ti in mouldTypes} {
printf "Mould Type: %s, Item Count: %d\n", ti, itemCounts[ti];
}
# total number of items
param m := card(I),>0;
printf "Number of items: %d \n", m;
# Bin capacity
param cmax, > 0;
/* We need to estimate an upper bound of the number of bins sufficient
to contain all items. The number of items m can be used, however, it
is not a good idea. To obtain a more suitable estimation an easy
heuristic is used: we put items into a bin while it is possible, and
if the bin is full, we use another bin. The number of bins used in
this way gives us a more appropriate estimation. */
param z{i in I, j in 1..m} :=
# z[i,j] = 1 if item i is in bin j, otherwise z[i,j] = 0
if i = 1 and j = 1 then 1
# put item 1 into bin 1
else if exists{jj in 1..j-1} z[i,jj] then 0
# if item i is already in some bin, do not put it into bin j
else if sum{ii in 1..i-1} w[ii] * z[ii,j] + w[i] > cmax then 0
# if item i does not fit into bin j, do not put it into bin j
else 1;
# otherwise put item i into bin j
check{i in I}: sum{j in 1..m} z[i,j] = 1;
# each item must be exactly in one bin
check{j in 1..m}: sum{i in I} w[i] * z[i,j] <= cmax;
# no bin must be overflowed
param n := sum{j in 1..m} if exists{i in I} z[i,j] then 1;
/* determine the number of bins used by the heuristic; obviously it is
an upper bound of the optimal solution */
set J := 1..n;
# set of bins
var x{i in I, j in J}, binary;
# x[i,j] = 1 means item i is in bin j
var used{j in J}, binary;
# used[j] = 1 means bin j contains at least one item
s.t. one{i in I}: sum{j in J} x[i,j] = 1;
# each item must be exactly in one bin
s.t. limMax{j in J}: sum{i in I} w[i] * x[i,j] <= cmax * used[j];
# if bin j is used, it must not be overflowed: can't exceed cmax
minimize obj: sum{j in J} used[j];
# objective is to minimize the number of bins used
solve;
data;
param cmax := 300; # max weight
end;
So now I can see that I have 4 type of moulds,
cmt = 4
And each one ha n items:Mould Type: P27795, Item Count: 4
Mould Type: P12396, Item Count: 4
Mould Type: P27532, Item Count: 5
Mould Type: P35495, Item Count: 3
For a total of items:
Number of items: 16
So now I can say I have the params for type:
ti, #typeitemCounts[ti] # number of items for that
type.
Now, what it is not clear to me is: if I want max 2 types of n items for
each bin how to achieve this goal.
e.g in the same bin I can have 2 of P27795 and 2 of P12396 because the
weight is : 85*2+63*2=296<300 and cardinality of #(P27795, P12396) is 2
but I can't have 1 of P12396 and 1 of P12396 and 1 of P27532 because
the weight is 85+63+42=190<300, fine, but the cardinality of #(P27795,
P12396, ) is 3
I tried adding a variable t[ti,j] like Makhorin did for z[i,j] , in this
case meaning 1 when there's a mould type ti in bin j ....but type must be
linked to i, because each item can be of just 1 mould type.
So I tried with a t[ti,i], but in this case it is not bound to bin and I
need this.
So I asked me if I just had to add ti as a third variable in z[i,j,ti] but
in this latter I would get that i can be of each type while each i is just
one type.
Any tips?
Il giorno mer 4 ott 2023 alle ore 20:08 Michael Hennebry <
hennebry@web.cs.ndsu.nodak.edu> ha scritto:
On Sat, 30 Sep 2023, Leonardo Corato wrote:
param m := 6;
param w := 1 50, 2 60, 3 30, 4 40, 5 40, 6 40;
--> param t := 1 A, 2 B , 3 B, 4 C, 5 C, 6 C;
param c := 100;
end;
I have to add a constraint so that the number of types for every bin is
limited to maximum 2.
Each bin can contain a number of the same type of items (i.e. A) or max 2
different types (i.e. A and C).
it is not regarding the number of items, of course, I can have multiple
items.