Information Technology Reference
In-Depth Information
7
Computational Experiments
The heuristic CG algorithm is coded in C++ and run on a Dell 2.20 GHz. The algo-
rithm is tested on a set of 320 instances generated by Martello et al. [5] for the three-
dimensional packing problem. These instances are classified into eight classes, each
of which contains four different types of items. The number of items, in each instance,
could be equal to either 50, 100, 150, or 200. For each class and instance size, ten
different problem instances based on different random seeds are generated. For
classes 1 to 5, the bin size is
100
and the following five types of items
are considered:
Type 1:
uniformly random in
1,
,
uniformly random in
•
,
, and
uniformly random in
,
.
Type 2:
uniformly random in
,
,
uniformly random in
1,
•
, and
uniformly random in
,
.
Type 3:
uniformly random in
,
,
uniformly random in
•
,
, and
uniformly random in
1,
.
Type 4:
uniformly random in
,,
uniformly random in
•
,
, and
uniformly random in
,
.
Type 5:
uniformly random in
1,
,
uniformly random in
1,
•
, and
uniformly random in
1,
.
•
Class 1: type 1 with probability 60%, type 2, 3, 4, 5 with probability 10% each.
•
Class 2: type 2 with probability 60%, type 1, 3,4, 5 with probability 10% each.
•
Class 3: type 3 with probability 60%, type 1, 2, 4, 5 with probability 10% each.
•
Class 4: type 1 with probability 60%, type 1,2, 3, 5 with probability 10% each.
•
Class 5: type 2 with probability 60%, type 1, 2,3,4,with probability 10% each.
Classes 6 to 7 are produced according to instances presented by Berkey and Wang
[19]:
•
Class 6:
,
and
uniformly random in [1,10] and
10
.
•
Class 7:
,
and
uniformly random in [1,35] and
40
.
•
Class 8:
,
and
uniformly random in [1,100] and
100
.
This set of instances can be reproduced by the instance generator available at
www.diku.dk/~pisinger/codes.html.
Since the solution to RMP for all of instances are non-integer, we apply branching
to attain integer solution. D_FH with limit value 0.6 leads to good integer solutions
for most of the instances, but infeasible solutions for maximum of four out of ten
problem instances, in each class and instance size. For the instances with an infeasible
solution, all fixed variables in the branching are released and the current master prob-
lem is solved to integrality by the CPLEX solver. The total execution time for each
