Re: bpp plus type constrain
On Wed, 11 Oct 2023, Leonardo Corato wrote: About the upper bound, I realized the bins could't have been enough, so my first code was a greedy solution: 1 bin per 1 item. Two items per bin would also work. Do you think I should write the full bpp with types, code? Maybe it could help someone. I'm not sure what you are asking. If you are asking whether you should publish your gmpl, why not? It couldn't hurt. BTW you still have not dealt with symmetry. 10 bins can be permuted more than 3 million ways. 15 bins more than a trillion ways. -- Michael henne...@mail.cs.ndsu.nodak.edu "Occasionally irrational explanations are required" -- Luke Roman
Re: bpp plus type constrain
Thank you Michael, I already did, I realized immediately it was a typing
error.
I have to double thank you because you made me understand a thing in which
I was stuck.
About the upper bound, I realized the bins could't have been enough, so my
first code was a greedy solution: 1 bin per 1 item.
I think this could be largely improved, as you showed me, but I still have
to analyze to fully understand your suggestion.
Do you think I should write the full bpp with types, code? Maybe it could
help someone.
Best regards
Il giorno lun 9 ott 2023 alle ore 18:26 Michael Hennebry <
henne...@web.cs.ndsu.nodak.edu> ha scritto:
> On Fri, 6 Oct 2023, Michael Hennebry wrote:
>
> > YY{y in mouldTypes, b in 1..n, i in I: mo[i]==t} y[t, b] >= x[i, b] ;
>
> Oops. A y where a t was needed. The corrected version:
> YY{t in mouldTypes, b in 1..n, i in I: mo[i]==t} y[t, b] >= x[i, b] ;
>
>
>
Re: bpp plus type constrain
On Fri, 6 Oct 2023, Michael Hennebry wrote:
YY{y in mouldTypes, b in 1..n, i in I: mo[i]==t} y[t, b] >= x[i, b] ;
Oops. A y where a t was needed. The corrected version:
YY{t in mouldTypes, b in 1..n, i in I: mo[i]==t} y[t, b] >= x[i, b] ;
--
Michael henne...@mail.cs.ndsu.nodak.edu
"Occasionally irrational explanations are required" -- Luke Roman
Re: bpp plus type constrain
On Fri, 6 Oct 2023, Michael Hennebry wrote: Your estimate of the number of bins necessary could be an underestimate. It does not enforce the only two types in a bin requirement. For larger problems, I think that that would be necessary. I think that all that is needed is another else if: else if exists i1 in 1..i-1 exists i2 in 1..i1 z[i1, j] and z[i2, j] and mo[i1] != mo[i2] != mo[i] != mo[i1] then 0 This could be a rather slow way to do it. I think that, with effort, I could get it down to three levels of loops. -- Michael henne...@mail.cs.ndsu.nodak.edu "Occasionally irrational explanations are required" -- Luke Roman
Re: bpp plus type constrain
Your estimate of the number of bins necessary could be an underestimate. It does not enforce the only two types in a bin requirement. For larger problems, I think that that would be necessary. -- Michael henne...@mail.cs.ndsu.nodak.edu "Occasionally irrational explanations are required" -- Luke Roman
Re: bpp plus type constrain
On Fri, 6 Oct 2023, Leonardo Corato wrote:
As you can see in bin 2 and 3 there are 3 mold types, so sadly s.t. fred is
not limiting to 2
I'd misunderstood.
I'd thought that you want no more than two of a given type.
Using an auxillary array is probably easiest:
y[t, b] == 1 iff bin b has an item of type t.
It need not be binary or have an upper bound.
An upper bound of one would not hurt and might help.
An upper bound of two can be inferred from other constraints.
greg{b in 1..n} sum{t in mouldTypes} y[t, b] <= 2 ;
YY{y in mouldTypes, b in 1..n, i in I: mo[i]==t} y[t, b] >= x[i, b] ;
Without y, I think that O(n*|I|**3) constraints might be necessary.
cube{b in 1..n, i1 in I, i2 in I, i3 in I: i1< i2 < i3 and
mo[i1] != mo[i2] != mo[i3] != moi10] }
x[i1, b] + x[i2, b] + x[i3, b] <= 2 ;
This is the kind of thing I'd be inclined to generate on the fly.
I'm not sure which set is stronger.
They might be equivalent.
Apparently you problems are small enough so that it does not matter much,
but you have rather a lot of symmetry.
That sort of thing plays havoc with branch and bound.
--
Michael henne...@mail.cs.ndsu.nodak.edu
"Occasionally irrational explanations are required" -- Luke Roman
Please do not quote boilerplate.
--
Michael henne...@mail.cs.ndsu.nodak.edu
"Occasionally irrational explanations are required" -- Luke Roman
Re: bpp plus type constrain
Por favor no me envíen más correos, no pertenezco al grupo!!
El El vie, oct. 6, 2023 a la(s) 5:32 p.m., Leonardo Corato
escribió:
> Thank you very much Michael,
> and sorry for missing the maling list and sending the email directly to
> you.
>
> I applied
> s.t. fred{b in 1..n, t in mouldTypes}: sum{i in I: mo[i]==t} x[i, b] <= 2 ;
> doesn't limit the types to max 2.
>
> To check whether s.t. fred worked properly, I added some printf statements
> between solve and data:
>
> solve;
>
>
> printf "Min number of bins used: %d \n", obj;
> for {j in J: sum{i in I} x[i,j] != 0} {
> printf "Bin %d # items: %d - Total weight: %d - Filling %% %d \n", j,
> sum{i in I} x[i,j], sum{i in I} w[i] * x[i,j], sum{i in I} w[i] * x[i,j] /
> cmax * 100 ;
> printf "Item Batch Alloy Mould\n";
> for {i in I: x[i,j]==1} {
> printf "%3d %s%d %s\n",i ,ba[i] ,al[i],mo[i];
> }
> printf "mold types: %d\n", card(setof{i in I: x[i,j]==1} mo[i] );
>
>
> }
>
>
> data;
>
>
> When run, I got:
>
> Min number of bins used: 4
> Bin 1 # items: 4 - Total weight: 254 - Filling % 85
> Item Batch Alloy Mould
> 1 H27587V2502 P27795
> 2 H27587V2502 P27795
> 9 H27587V2502 P27532
> 10 H27587V2502 P27532
> mold types: 2
> Bin 2 # items: 5 - Total weight: 288 - Filling % 96
> Item Batch Alloy Mould
> 5 H27587V2502 P12396
> 6 H27587V2502 P12396
> 11 H27587V2502 P27532
> 12 H27587V2502 P27532
> 15 H27587V2502 P35495
> mold types: 3
> Bin 3 # items: 4 - Total weight: 290 - Filling % 97
> Item Batch Alloy Mould
> 3 H27587V2502 P27795
> 4 H27587V2502 P27795
> 13 H27587V2502 P27532
> 14 H27587V2502 P35495
> mold types: 3
> Bin 4 # items: 3 - Total weight: 204 - Filling % 68
> Item Batch Alloy Mould
> 7 H27587V2502 P12396
> 8 H27587V2502 P12396
> 16 H27587V2502 P35495
> mold types: 2
> Model has been successfully processed
>
> As you can see in bin 2 and 3 there are 3 mold types, so sadly s.t. fred
> is not limiting to 2
> I also tried
> s.t. cardset{j in J}: card(setof{i in I: x[i,j] == 1} mo[i] ) <= 2;
> which is the same I used in printfs to check how many type of items are
> in every bin j, but it seems that this expression can't be used inside an
> s.t.
>
>
> Il giorno gio 5 ott 2023 alle ore 21:28 Michael Hennebry <
> henne...@web.cs.ndsu.nodak.edu> ha scritto:
>
>> I'm assuming the your e-mail was intended for the list.
>> I'm quoting most of it because the list does not have it.
>>
>> In either case, forget about what I wrote.
>> GMPL is more powerful than I remembered.
>>
>> I think the desired constraint is
>> fred{b in 1..n, t in mouldTypes} sum{i in I: mo[i]==t} x[i, b] <= 2 ;
>> The above two lines are duplicated at an appropriate point.
>> I did not add anything else.
>>
>> On Thu, 5 Oct 2023, Leonardo Corato wrote:
>>
>> > 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
Re: bpp plus type constrain
Thank you very much Michael,
and sorry for missing the maling list and sending the email directly to you.
I applied
s.t. fred{b in 1..n, t in mouldTypes}: sum{i in I: mo[i]==t} x[i, b] <= 2 ;
doesn't limit the types to max 2.
To check whether s.t. fred worked properly, I added some printf statements
between solve and data:
solve;
printf "Min number of bins used: %d \n", obj;
for {j in J: sum{i in I} x[i,j] != 0} {
printf "Bin %d # items: %d - Total weight: %d - Filling %% %d \n", j,
sum{i in I} x[i,j], sum{i in I} w[i] * x[i,j], sum{i in I} w[i] * x[i,j] /
cmax * 100 ;
printf "Item Batch Alloy Mould\n";
for {i in I: x[i,j]==1} {
printf "%3d %s%d %s\n",i ,ba[i] ,al[i],mo[i];
}
printf "mold types: %d\n", card(setof{i in I: x[i,j]==1} mo[i] );
}
data;
When run, I got:
Min number of bins used: 4
Bin 1 # items: 4 - Total weight: 254 - Filling % 85
Item Batch Alloy Mould
1 H27587V2502 P27795
2 H27587V2502 P27795
9 H27587V2502 P27532
10 H27587V2502 P27532
mold types: 2
Bin 2 # items: 5 - Total weight: 288 - Filling % 96
Item Batch Alloy Mould
5 H27587V2502 P12396
6 H27587V2502 P12396
11 H27587V2502 P27532
12 H27587V2502 P27532
15 H27587V2502 P35495
mold types: 3
Bin 3 # items: 4 - Total weight: 290 - Filling % 97
Item Batch Alloy Mould
3 H27587V2502 P27795
4 H27587V2502 P27795
13 H27587V2502 P27532
14 H27587V2502 P35495
mold types: 3
Bin 4 # items: 3 - Total weight: 204 - Filling % 68
Item Batch Alloy Mould
7 H27587V2502 P12396
8 H27587V2502 P12396
16 H27587V2502 P35495
mold types: 2
Model has been successfully processed
As you can see in bin 2 and 3 there are 3 mold types, so sadly s.t. fred is
not limiting to 2
I also tried
s.t. cardset{j in J}: card(setof{i in I: x[i,j] == 1} mo[i] ) <= 2;
which is the same I used in printfs to check how many type of items are in
every bin j, but it seems that this expression can't be used inside an s.t.
Il giorno gio 5 ott 2023 alle ore 21:28 Michael Hennebry <
henne...@web.cs.ndsu.nodak.edu> ha scritto:
> I'm assuming the your e-mail was intended for the list.
> I'm quoting most of it because the list does not have it.
>
> In either case, forget about what I wrote.
> GMPL is more powerful than I remembered.
>
> I think the desired constraint is
> fred{b in 1..n, t in mouldTypes} sum{i in I: mo[i]==t} x[i, b] <= 2 ;
> The above two lines are duplicated at an appropriate point.
> I did not add anything else.
>
> On Thu, 5 Oct 2023, Leonardo Corato wrote:
>
> > 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
> >
> >
Re: bpp plus type constrain
I'm assuming the your e-mail was intended for the list.
I'm quoting most of it because the list does not have it.
In either case, forget about what I wrote.
GMPL is more powerful than I remembered.
I think the desired constraint is
fred{b in 1..n, t in mouldTypes} sum{i in I: mo[i]==t} x[i, b] <= 2 ;
The above two lines are duplicated at an appropriate point.
I did not add anything else.
On Thu, 5 Oct 2023, Leonardo Corato wrote:
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
I think the desired constraint is
fred{b in 1..n, t in mouldTypes} sum{i in I: mo[i]==t} x[i, b] <= 2 ;
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
Re: bpp plus type constrain
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. If you want the types to have names, they will have to be a set. You could just give them indices. You will need a 2D boolean array indexed by item and type. Once you have that, the rest should be obvious. -- Michael henne...@mail.cs.ndsu.nodak.edu "Occasionally irrational explanations are required" -- Luke Roman
