Answers to: Bin spreadinghttp://www.or-exchange.com/questions/4283/bin-spreading<p>Hi I am working on a bin packing problem where rather than optimizing for the least number of needed bins we would like to optimize for the most remaining space amongst all bins (including bins containing an item). To achieve the spreading we came up with the idea to minimize the sum of the used space in each bin squared, that way the more full it is the more it is penalized. However this makes the problem an MIQP problem due to the quadratic component in the minimization, assumedly slowing down the optimization. <strong>Does anyone have a suggestion on how to better formulate the optimization parameter to achieve the same or similar effect?</strong></p>
<p>I've created two different models using OPL and CPLEX 12.3 to solve, using 80 bins and 4 items (as a test) the first model solves in ~9minutes on a 8 thread machine, the second model I ran for 30 minutes and still had a GAP of 47.51% and gave up. 9 minutes isn't terrible but I'd like to use about 320 items, and scaling is very poor (8 items was over an hour). I'm listing my two models and data below. <strong>Does anyone have a suggestion how to tweak the model for better runtime/scaling?</strong></p>
<p>Also one thing that confused me was when I ran model 1 CPLEX told me it took 65859055 iterations to finish, however I'd expect 40960000 to be enough to explore all possibilities of decision variable assignment (80^4). Why the disparity?</p>
<p><em>Thanks in advance!</em></p>
<p><strong>Model 1:</strong></p>
<pre><code>{string} bins = ...;
{string} items = ...;
float itemSize[bins] = ...;
float binCapacity[bins] = ...;
range r = 0..1;
dvar int X[items][bins] in r;
minimize sum(u in bins) pow(((sum(a in items) itemSize[a]*X[a][u])), 2);
subject to {
/* Item in only one bin constraint */
forall(i in items)
sum(b in bins)
X[i, b] == 1;
/* Capacity Constraint */
forall(b in bins)
sum(i in items) X[i][b]*itemSize[i] <= binCapacity[b];
};
execute DISPLAY {
writeln("Mapping:");
for (var i in items) {
for (var b in bins) {
if (X[i][b] == 1) {
writeln("Item " + i + " is in bin " + b);
}
}
}
}
</code></pre>
<p><strong>Data 1:</strong></p>
<pre><code>bins = {"01", "02", "03", "04", "05", "06", "07", "08", "09", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20", "21", "22", "23", "24", "25", "26", "27", "28", "29", "30", "31", "32", "33", "34", "35", "36", "37", "38", "39", "40", "41", "42", "43", "44", "45", "46", "47", "48", "49", "50", "51", "52", "53", "54", "55", "56", "57", "58", "59", "60", "61", "62", "63", "64", "65", "66", "67", "68", "69", "70", "71", "72", "73", "74", "75", "76", "77", "78", "79", "80"};
items = {"01", "02", "03", "04"};
itemSize = #[
"01": 0.56583464,
"02": 0.60144615,
"03": 0.4545771,
"04": 0.47858784
]#;
binCapacity = #[
"01": 2,
"02": 2,
"03": 2,
"04": 2,
"05": 2,
"06": 2,
"07": 2,
"08": 2,
"09": 2,
"10": 2,
"11": 2,
"12": 2,
"13": 2,
"14": 2,
"15": 2,
"16": 2,
"17": 2,
"18": 2,
"19": 2,
"20": 2,
"21": 2,
"22": 2,
"23": 2,
"24": 2,
"25": 2,
"26": 2,
"27": 2,
"28": 2,
"29": 2,
"30": 2,
"31": 2,
"32": 2,
"33": 2,
"34": 2,
"35": 2,
"36": 2,
"37": 2,
"38": 2,
"39": 2,
"40": 2,
"41": 2,
"42": 2,
"43": 2,
"44": 2,
"45": 2,
"46": 2,
"47": 2,
"48": 2,
"49": 2,
"50": 2,
"51": 2,
"52": 2,
"53": 2,
"54": 2,
"55": 2,
"56": 2,
"57": 2,
"58": 2,
"59": 2,
"60": 2,
"61": 2,
"62": 2,
"63": 2,
"64": 2,
"65": 2,
"66": 2,
"67": 2,
"68": 2,
"69": 2,
"70": 2,
"71": 2,
"72": 2,
"73": 2,
"74": 2,
"75": 2,
"76": 2,
"77": 2,
"78": 2,
"79": 2,
"80": 2
]#;
</code></pre>
<p><strong>Model 2:</strong></p>
<pre><code>int binCount = 80;
int itemCount = 4;
float itemSize[1..itemCount] = ...;
int binCapacity[1..binCount] = ...;
dvar int X[1..itemCount] in 1..binCount;
minimize sum(i in 1..binCount) pow(sum(j in 1..itemCount) (X[j] == i) * itemSize[j], 2);
subject to {
// bin Capacity constraint
forall(i in 1..binCount)
(sum(j in 1..itemCount) (X[j] == i) * itemSize[j]) <= binCapacity[i];
};
execute DISPLAY {
writeln("Mapping:");
for (var i = 1; i <= itemCount; ++i) {
writeln("Item " + i + " is in bin " + X[i]);
}
}
</code></pre>
<p><strong>Data 2:</strong>
itemSize = #[
1: 0.56583464,
2: 0.60144615,
3: 0.4545771,
4: 0.47858784
]#;
binCapacity = #[
1: 2,
2: 2,
3: 2,
4: 2,
5: 2,
6: 2,
7: 2,
8: 2,
9: 2,
10: 2,
11: 2,
12: 2,
13: 2,
14: 2,
15: 2,
16: 2,
17: 2,
18: 2,
19: 2,
20: 2,
21: 2,
22: 2,
23: 2,
24: 2,
25: 2,
26: 2,
27: 2,
28: 2,
29: 2,
30: 2,
31: 2,
32: 2,
33: 2,
34: 2,
35: 2,
36: 2,
37: 2,
38: 2,
39: 2,
40: 2,
41: 2,
42: 2,
43: 2,
44: 2,
45: 2,
46: 2,
47: 2,
48: 2,
49: 2,
50: 2,
51: 2,
52: 2,
53: 2,
54: 2,
55: 2,
56: 2,
57: 2,
58: 2,
59: 2,
60: 2,
61: 2,
62: 2,
63: 2,
64: 2,
65: 2,
66: 2,
67: 2,
68: 2,
69: 2,
70: 2,
71: 2,
72: 2,
73: 2,
74: 2,
75: 2,
76: 2,
77: 2,
78: 2,
79: 2,
80: 2
]#;</p>enWed, 04 Jan 2012 07:41:55 -0500- Answer by Paul Rubinhttp://www.or-exchange.com/questions/4283/bin-spreading/4344<p>Letting <code>load[i]</code> be the actual load in the i-th bin, something like</p>
<pre><code>maximize d1 + d2
s.t. load[i] <= binCapacity[i] - d1*binCapcity[i] for all i
load[i] >= binCapacity[i] + d2*binCapcity[i] for all i
0 <= d1, d2 <= 1
...
</code></pre>
<p>shrinks the range of bin loadings (in percentage terms).</p>Paul RubinWed, 04 Jan 2012 07:41:55 -0500http://www.or-exchange.com/questions/4283/bin-spreading/4344
- Answer by pierre schaushttp://www.or-exchange.com/questions/4283/bin-spreading/4343<p>Hello,</p>
<p>I did my thesis on using constraint programming to solve this kind of problem (<a href="https://docs.google.com/viewer?url=http%3A%2F%2Fbecool.info.ucl.ac.be%2Fpub%2Ftheses%2Fthesis-pschaus.pdf">here</a>).
You might have a look at this article: Pierre Schaus, Pascal Van Hentenryck, Jean-Charles RĂ©gin: Scalable Load Balancing in Nurse to Patient Assignment Problems. CPAIOR 2009: 248-262.</p>pierre schausWed, 04 Jan 2012 06:44:56 -0500http://www.or-exchange.com/questions/4283/bin-spreading/4343
- Answer by Ehsanhttp://www.or-exchange.com/questions/4283/bin-spreading/4294<p>I'm sorry because I read objective function of your model #1 incorrectly last night and therefore I implemented your first model in GAMS incorrectly. Therefore, I've to correct my previous statements as follows (apparently, I was way too sleepy while answering your question):</p>
<p><strong>a)</strong> If number of items is less than bins as in your examples, the optimal objective function would constant based on your inputs, which is equal to sum(i, (itemSize(i))^2). There are obvious multiple optimal solutions to this problem: Allocate items to distinct bins. However, if number of bins is less than items, then the finding optimal solution and optimal objective function are not trivial.</p>
<p><strong>b)</strong> Since I implemented your model incorrectly, the solution time I reported was wrong and your reported solution time was correct. However, I found an insight on why the CPLEX might be very slow to solve the model as in your data sets, number of bins is larger than number of bins. Apparently, as there are multiple optimal solutions (<em>n</em>!, which <em>n</em> is the number of items), CPLEX has a really hard time closing the gap as it has to explore a large number of nodes with equal objective function values in the branch & bound tree.</p>
<p><strong>c)</strong> I developed a another mathematical model in GAMS for your problem. The model minimizes the squared unused capacity of bins (please note the difference in objective function). For this matter, I had to add a binary variable denoting selection of bins. The model is as follows:</p>
<pre><code>Sets i items / i1 * i4 /
j bins / b1 * b80/;
Parameter Size(i) Size of i_th item/
i1 0.56583464
i2 0.60144615
i3 0.4545771
i4 0.47858784/;
Parameter Cap(j) Capacity of j_th bin;
Cap(j) = 2;
variable Z Objective function value;
integer variable X(i,j) Ammount of item i allocated to bin j;
binary variable Y(j) Selecting bin j;
Equations
objfun
AllocationConstraint
CapacityConstraint
AllocationSelection;
objfun.. Z =e=sum(j, Power((Cap(j) * Y(j) - sum(i, Size(i) * X(i,j))),2));
AllocationConstraint(i).. sum(j, X(i,j)) =e= 1;
CapacityConstraint(j).. sum(i, Size(i) * X(i,j)) =l= Cap(j);
AllocationSelection(i,j).. X(i,j) =l= Y(j);
model binpacking /all/;
solve binpacking using miqcp minimizing Z;
</code></pre>
<p>This model could be solved effectively for your data sets (in about 10 seconds on four x64 threads). Another positive side of this model is that it tends to keep the number of used bins small even if the number of available bins is larger than the number of items. Feel free to ask question if you don't understand the logic behind my model.</p>
<p>ps. GAMS does not reformulate the models and just acts as medium for transforming your model to what could be understood by the solvers. However there are some solvers which could do this.</p>EhsanWed, 28 Dec 2011 11:25:12 -0500http://www.or-exchange.com/questions/4283/bin-spreading/4294
- Answer by Marco Luebbeckehttp://www.or-exchange.com/questions/4283/bin-spreading/4287<p>A. This sounds like "load balancing". I understand that you do not wish to solve a bin packing problem but a closely related machine scheduling problem. Think of your items as jobs and the bins as machines. You would like to "schedule" the jobs on machines (assign the items to bins) such that the latest finishing time (the "makespan") is minimized. This should have the desired effect. You will achieve this goal using a linear objective function as follows: Introduce a (continuous) variable, say z. Then you need to replace the constraints</p>
<p>sum(i in items) .... <= binCapacity[b];</p>
<p>by</p>
<p>sum(i in items) .... <= z;</p>
<p>and have "minimize z" as the objective function. This is a "min max" objective function, and hopefully does the job.</p>
<p>B. use binary variables for modeling by all means (if you have the choice between integer and binary variables); this usually is stronger in terms of the linear relaxation, which in turn helps the branch-and-bound algorithm. This appears to be a reason why the second model is much weaker.</p>
<p>C. The models have a lot of "symmetry", another reason for bad performance. That means: The solver does not know that there is no essential difference between bin 1 and bin 2 ... and bin 80. You can help the solver by introducing "an artificial distinction" between bins, eg., by introducing constraints that enforce that you open bin i+1 only if bin i is already open. This works for "standard" bin packing, but possibly not with your "balancing" objective function. Hm. </p>
<p>D. The number of iterations reported is most probably the number of simplex iterations which is <em>not</em> the number of combinations to pack items. The solver solves the linear relaxation of your model first (and in every node of the branch-and-bound tree), this has nothing to do with the number of solutions to the integer program. Anyway, the number of iterations is extremely large for such a toy model.</p>
<p>E. What comes to my mind as a remedy to several of your problems: An entirely different model formulation as a set covering model may help: Enumerate all possibilities ("patterns") to pack a bin, and choose a subset of patterns, such that every item is contained in one pattern. This will require column generation (and possibly branch-and-price) to solve the model, which is not easy/possibly in OPL.</p>
<p>My answer may leave you with more questions than before, feel free to follow-up on this post. One helpful information would be: do you need <em>optimal</em> solutions or "only" good quality?</p>Marco LuebbeckeTue, 27 Dec 2011 06:47:47 -0500http://www.or-exchange.com/questions/4283/bin-spreading/4287