source: branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/Instances/RandomInstanceProvider.cs @ 14062

Last change on this file since 14062 was 14062, checked in by gkronber, 6 years ago

#1966: reimplemented problem instance generation from paper Silvano Martello, David Pisinger Daniele Vigo, "The Three-Dimensional Bin Packing Problem"

File size: 8.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002 - 2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22
23using System;
24using System.Collections.Generic;
25using System.Diagnostics.Contracts;
26using System.IO;
27using System.Linq;
28using HeuristicLab.Core;
29using HeuristicLab.Problems.Instances;
30using HeuristicLab.Random;
31
32namespace HeuristicLab.Problems.BinPacking3D {
33  // make sure that for each class we have a separate entry in the problem instance providers
34  public class RandomInstanceClass1Provider : RandomInstanceProvider {
35    public RandomInstanceClass1Provider() : base() { @class = 1; binWidth = binHeight = binDepth = 100; }
36  }
37  public class RandomInstanceClass2Provider : RandomInstanceProvider {
38    public RandomInstanceClass2Provider() : base() { @class = 2; binWidth = binHeight = binDepth = 100; }
39  }
40  public class RandomInstanceClass3Provider : RandomInstanceProvider {
41    public RandomInstanceClass3Provider() : base() { @class = 3; binWidth = binHeight = binDepth = 100; }
42  }
43  public class RandomInstanceClass4Provider : RandomInstanceProvider {
44    public RandomInstanceClass4Provider() : base() { @class = 4; binWidth = binHeight = binDepth = 100; }
45  }
46  public class RandomInstanceClass5Provider : RandomInstanceProvider {
47    public RandomInstanceClass5Provider() : base() { @class = 5; binWidth = binHeight = binDepth = 100; }
48  }
49
50  public class RandomInstanceClass6Provider : RandomInstanceProvider {
51    public RandomInstanceClass6Provider() : base() {
52      @class = 6;
53      binWidth = binHeight = binDepth = 10;
54    }
55    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
56      w = rand.Next(1, 11);
57      h = rand.Next(1, 11);
58      d = rand.Next(1, 11);
59    }
60  }
61  public class RandomInstanceClass7Provider : RandomInstanceProvider {
62    public RandomInstanceClass7Provider() : base() {
63      @class = 7;
64      binWidth = binHeight = binDepth = 40;
65    }
66    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
67      w = rand.Next(1, 36);
68      h = rand.Next(1, 36);
69      d = rand.Next(1, 36);
70    }
71  }
72  public class RandomInstanceClass8Provider : RandomInstanceProvider {
73    public RandomInstanceClass8Provider() : base() {
74      @class = 8;
75      binWidth = binHeight = binDepth = 100;
76    }
77    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
78      w = rand.Next(1, 101);
79      h = rand.Next(1, 101);
80      d = rand.Next(1, 101);
81    }
82  }
83
84  // class 9 from the paper (all-fill) is not implemented
85  public abstract class RandomInstanceProvider : ProblemInstanceProvider<BPPData>, IProblemInstanceProvider<BPPData> {
86
87    protected int @class;
88    protected int binWidth, binHeight, binDepth;
89
90    public override string Name {
91      get { return string.Format("Martello, Pisinger, Vigo (class={0})", @class); }
92    }
93
94    public override string Description {
95      get { return "Randomly generated 3d bin packing problems as described in Martello, Pisinger, Vigo: 'The Three-Dimensional Bin Packing Problem', Operations Research Vol 48, Issue 2, 2000, pp. 256-267."; }
96    }
97
98    public override Uri WebLink {
99      get { return null; }
100    }
101
102    public override string ReferencePublication {
103      get { return "Martello, Pisinger, Vigo: 'The Three-Dimensional Bin Packing Problem', Operations Research Vol 48, Issue 2, 2000, pp. 256-267."; }
104    }
105
106    public RandomInstanceProvider() : base() { }
107
108    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
109      // 10 classes
110      var rand = new MersenneTwister(1234); // fixed seed to makes sure that instances are always the same
111      foreach (int numItems in new int[] { 10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90 }) {
112        // get class parameters
113        // generate 30 different instances for each class
114        foreach (int instance in Enumerable.Range(1, 30)) {
115          string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class);
116          var dd = new RandomDataDescriptor(name, name, numItems, @class, seed: rand.Next());
117          yield return dd;
118        }
119      }
120    }
121
122    public override BPPData LoadData(IDataDescriptor dd) {
123      var randDd = dd as RandomDataDescriptor;
124      if (randDd == null) throw new NotSupportedException("Cannot load data descriptor " + dd);
125
126      var data = new BPPData() {
127        BinShape = new PackingShape(binWidth, binHeight, binDepth),
128        Items = new PackingItem[randDd.NumItems]
129      };
130      var instanceRand = new MersenneTwister((uint)randDd.Seed);
131      for (int i = 0; i < randDd.NumItems; i++) {
132        int w, h, d;
133        SampleItemParameters(instanceRand, out w, out h, out d);
134        data.Items[i] = new PackingItem(w, h, d, data.BinShape);
135      }
136      return data;
137    }
138
139    // default implementation for class 1 .. 5
140    protected virtual void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
141      // for classes 1 - 5
142      Contract.Assert(@class >= 1 && @class <= 5);
143      var weights = new double[] { 0.1, 0.1, 0.1, 0.1, 0.1 };
144      weights[@class - 1] = 0.6;
145      var type = Enumerable.Range(1, 5).SampleProportional(rand, 1, weights).First();
146
147      int minW, maxW;
148      int minH, maxH;
149      int minD, maxD;
150      GetItemParameters(type, rand, binWidth, binHeight, binDepth,
151        out minW, out maxW, out minH, out maxH, out minD, out maxD);
152
153      w = rand.Next(minW, maxW + 1);
154      h = rand.Next(minH, maxH + 1);
155      d = rand.Next(minD, maxD + 1);
156    }
157
158    private void GetItemParameters(int type, IRandom rand,
159      int w, int h, int d,
160      out int minW, out int maxW, out int minH, out int maxH, out int minD, out int maxD) {
161      switch (type) {
162        case 1: {
163            minW = 1; maxW = w / 2; // integer division on purpose (see paper)
164            minH = h * 2 / 3; maxH = h;
165            minD = d * 2 / 3; maxD = d;
166            break;
167          }
168        case 2: {
169            minW = w * 2 / 3; maxW = w;
170            minH = 1; maxH = h / 2;
171            minD = d * 2 / 3; maxD = d;
172            break;
173          }
174        case 3: {
175            minW = w * 2 / 3; maxW = w;
176            minH = h * 2 / 3; maxH = h;
177            minD = 1; maxD = d / 2;
178            break;
179          }
180        case 4: {
181            minW = w / 2; maxW = w;
182            minH = h / 2; maxH = h;
183            minD = d / 2; maxD = d;
184            break;
185          }
186        case 5: {
187            minW = 1; maxW = w / 2;
188            minH = 1; maxH = h / 2;
189            minD = 1; maxD = d / 2;
190            break;
191          }
192        default: {
193            throw new InvalidProgramException();
194          }
195      }
196    }
197
198    public override bool CanImportData {
199      get { return false; }
200    }
201    public override BPPData ImportData(string path) {
202      throw new NotSupportedException();
203    }
204
205    public override bool CanExportData {
206      get { return true; }
207    }
208
209    public override void ExportData(BPPData instance, string file) {
210      using (Stream stream = new FileStream(file, FileMode.OpenOrCreate, FileAccess.Write)) {
211        Export(instance, stream);
212      }
213    }
214    public static void Export(BPPData instance, Stream stream) {
215
216      using (var writer = new StreamWriter(stream)) {
217        writer.WriteLine(String.Format("{0,-5} {1,-5} {2,-5}   WBIN,HBIN,DBIN", instance.BinShape.Width, instance.BinShape.Height, instance.BinShape.Depth));
218        for (int i = 0; i < instance.NumItems; i++) {
219          if (i == 0)
220            writer.WriteLine("{0,-5} {1,-5} {2,-5}   W(I),H(I)D(I),I=1,...,N", instance.Items[i].Width, instance.Items[i].Height, instance.Items[i].Depth);
221          else
222            writer.WriteLine("{0,-5} {1,-5} {2,-5}", instance.Items[i].Width, instance.Items[i].Height, instance.Items[i].Depth);
223
224        }
225        writer.Flush();
226      }
227    }
228
229  }
230}
Note: See TracBrowser for help on using the repository browser.