Re: [Help-glpk] Ordered bin packing

Dmitri,

One unanswered question is to equalize the bin weights as much as possible subject to tighest packing. Below is a solution. There's probably a more elegant formulation.

In any event, you now have solutions to special cases of your more general multiobjective problem.

-- minimize maximum weight of any bin

-- tightest packing subject to maximum weight on any bin

-- equalize bin weights subject to tightest packing

Jeff

set BINS := 1..3;

set ITEMS := 1..8;

param weight{ITEMS};

param M := 1000;

var wmax >= 0;

var wmin >= 0;

var x{i in ITEMS, b in BINS} binary;

var Imin{b in BINS};

var Imax{b in BINS};

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;

s.t. C{b in BINS}: sum{i in ITEMS} weight[i]*x[i,b] >= wmin;

s.t. D{b in BINS, i in ITEMS}: Imin[b] <= i*x[i,b] + M*(1-x[i,b]);

s.t. E{b in BINS, i in ITEMS}: Imax[b] >= i*x[i,b];

s.t. F{b in BINS, c in BINS : b < c}: Imax[b] <= Imin[c];

minimize obj: wmax-wmin;

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 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 2:57 PM, Dmitri Goutnik <address@hidden> wrote:

Jeff,

Wow, thanks a lot! That is exactly what I was looking for.

Best regards,
Dmitri
On 27/01/2013, at 14:17, Jeffrey Kantor <address@hidden> wrote:
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 <address@hidden> 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 <address@hidden> 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 <address@hidden> 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
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk

From:	Jeffrey Kantor
Subject:	Re: [Help-glpk] Ordered bin packing
Date:	Sun, 27 Jan 2013 15:37:13 -0500