Dmitri,
This is a problem with two objectives which, depending on problem data, may
conflict with each other. So the best we can do is to find tradeoffs
between the conflicting objectives. Here's one solution where alpha is a
parameter expressing the relative significance of the two objectives.
set BINS := 1..3;
set ITEMS := 1..8;
param weight{ITEMS};
var wmax >= 0;
var x{i in ITEMS, b in BINS} binary;
s.t. A{i in ITEMS}: sum{b in BINS} x[i,b] = 1;
s.t. B{b in BINS}: sum{i in ITEMS} weight[i]*x[i,b] <= wmax;
minimize obj: wmax + alpha*sum{b in BINS, i in ITEMS}
(card(BINS)-b)*i*x[i,b];
solve;
for {b in BINS}: {
printf "Bin %d: total weight %d\n", b, sum{i in ITEMS} weight[i]*x[i,b];
printf {i in ITEMS : x[i,b] = 1}: " item %d (%d)\n", i, weight[i];
printf "\n";
}
data;
param weight :=
1 40
2 60
3 30
4 70
5 50
6 40
7 15
8 25 ;
end;
Bin 1: total weight 110
item 1 (40)
item 4 (70)
Bin 2: total weight 110
item 2 (60)
item 5 (50)
Bin 3: total weight 110
item 3 (30)
item 6 (40)
item 7 (15)
item 8 (25)
Another solution would be to solve the problem in two phases. The first
phase determines the minimum weight for each bin (for this data, 110), a
second phase that seeks the tightest packing subject to a bound on bin
weight that's greater than or equal to the minimum possible weight. Here's
a solution to that problem where a bound of 130 is used:
set BINS := 1..3;
set ITEMS := 1..8;
param weight{ITEMS};
param wmax;
var x{i in ITEMS, b in BINS} binary;
s.t. A{i in ITEMS}: sum{b in BINS} x[i,b] = 1;
s.t. B{b in BINS}: sum{i in ITEMS} weight[i]*x[i,b] <= wmax;
minimize obj: sum{b in BINS, i in ITEMS} (card(BINS)-b)*i*x[i,b];
solve;
for {b in BINS}: {
printf "Bin %d: total weight %d\n", b, sum{i in ITEMS} weight[i]*x[i,b];
printf {i in ITEMS : x[i,b] = 1}: " item %d (%d)\n", i, weight[i];
printf "\n";
}
data;
param wmax := 130;
param weight :=
1 40
2 60
3 30
4 70
5 50
6 40
7 15
8 25 ;
end;
Bin 1: total weight 100
item 1 (40)
item 2 (60)
Bin 2: total weight 100
item 3 (30)
item 4 (70)
Bin 3: total weight 130
item 5 (50)
item 6 (40)
item 7 (15)
item 8 (25)
On Sun, Jan 27, 2013 at 1:55 PM, Dmitri Goutnik <[email protected]> wrote:
> Hi Jeff,
>
> Thanks, yes that would be preferable packing. My goal is to pack items as
> "tightly" as possible while preserving even (within some predefined margin)
> weight distribution between bins.
>
> Best regards,
> Dmitri
>
> On 27/01/2013, at 13:40, Jeffrey Kantor <[email protected]> wrote:
>
> Hi Dmitri,
>
> This could be done through the objective function. But before going there,
> I'm wondering a bit
> about the solution you're showing for your example. Wouldn't you want
> move item 7 from Bin 3 to Bin 2 to meet your primary objective?
>
> Jeff
>
>
> On Sun, Jan 27, 2013 at 1:34 PM, Dmitri Goutnik <[email protected]> wrote:
>
>> Hello everyone,
>>
>> I modified bpp.mod to pack items in predefined number of bins of
>> unlimited capacity so that weight is (approximately) evenly distributed
>> between bins. In addition to weight, each item has an "order" or
>> "position". Is there a way to write an additional model constraint so that
>> items are preferably packed in compact order, e.g. items with sequential
>> positions should go to the the same container? For example, for this
>> solution:
>>
>> Bin 1: total weight 110
>> item 1 (40)
>> item 4 (70) <--
>>
>> Bin 2: total weight 90
>> item 5 (50)
>> item 6 (40)
>>
>> Bin 3: total weight 130
>> item 2 (60) -->
>> item 3 (30)
>> item 7 (15)
>> item 8 (25)
>>
>> is there a way to add such constraint so item 2 would preferably be
>> packed to bin 1?
>>
>> Thanks,
>> Dmitri
>> _______________________________________________
>> Help-glpk mailing list
>> [email protected]
>> https://lists.gnu.org/mailman/listinfo/help-glpk
>>
>
>
>
_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk
