Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/Instances/RandomInstanceProvider.cs @ 14063

Last change on this file since 14063 was 14063, checked in by gkronber, 8 years ago

#1966: implemented random instance generation for 2d BPP instances

File size: 8.7 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.BinPacking2D {
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() {
36      @class = 1;
37      binWidth = binHeight = 10;
38    }
39    protected override void SampleItemParameters(IRandom rand, out int w, out int h) {
40      w = rand.Next(1, 11);
41      h = rand.Next(1, 11);
42    }
43  }
44  public class RandomInstanceClass2Provider : RandomInstanceProvider {
45    public RandomInstanceClass2Provider() : base() {
46      @class = 2;
47      binWidth = binHeight = 30;
48    }
49    protected override void SampleItemParameters(IRandom rand, out int w, out int h) {
50      w = rand.Next(1, 11);
51      h = rand.Next(1, 11);
52    }
53  }
54  public class RandomInstanceClass3Provider : RandomInstanceProvider {
55    public RandomInstanceClass3Provider() : base() {
56      @class = 3;
57      binWidth = binHeight = 40;
58    }
59    protected override void SampleItemParameters(IRandom rand, out int w, out int h) {
60      w = rand.Next(1, 36);
61      h = rand.Next(1, 36);
62    }
63  }
64
65  public class RandomInstanceClass4Provider : RandomInstanceProvider {
66    public RandomInstanceClass4Provider() : base() {
67      @class = 4;
68      binWidth = binHeight = 100;
69    }
70    protected override void SampleItemParameters(IRandom rand, out int w, out int h) {
71      w = rand.Next(1, 36);
72      h = rand.Next(1, 36);
73    }
74  }
75  public class RandomInstanceClass5Provider : RandomInstanceProvider {
76    public RandomInstanceClass5Provider() : base() {
77      @class = 5;
78      binWidth = binHeight = 100;
79    }
80    protected override void SampleItemParameters(IRandom rand, out int w, out int h) {
81      w = rand.Next(1, 101);
82      h = rand.Next(1, 101);
83    }
84  }
85  public class RandomInstanceClass6Provider : RandomInstanceProvider {
86    public RandomInstanceClass6Provider() : base() {
87      @class = 6;
88      binWidth = binHeight = 300;
89    }
90    protected override void SampleItemParameters(IRandom rand, out int w, out int h) {
91      w = rand.Next(1, 101);
92      h = rand.Next(1, 101);
93    }
94  }
95  public class RandomInstanceClass7Provider : RandomInstanceProvider {
96    public RandomInstanceClass7Provider() : base() { @class = 7; binWidth = binHeight = 100; }
97  }
98  public class RandomInstanceClass8Provider : RandomInstanceProvider {
99    public RandomInstanceClass8Provider() : base() { @class = 8; binWidth = binHeight = 100; }
100  }
101  public class RandomInstanceClass9Provider : RandomInstanceProvider {
102    public RandomInstanceClass9Provider() : base() { @class = 9; binWidth = binHeight = 100; }
103  }
104  public class RandomInstanceClass10Provider : RandomInstanceProvider {
105    public RandomInstanceClass10Provider() : base() { @class = 10; binWidth = binHeight = 100; }
106  }
107  public abstract class RandomInstanceProvider : ProblemInstanceProvider<BPPData>, IProblemInstanceProvider<BPPData> {
108
109    protected int @class;
110    protected int binWidth, binHeight;
111
112    public override string Name {
113      get { return string.Format("Lodi, Martelli, Vigo (class={0})", @class); }
114    }
115
116    public override string Description {
117      get { return "Randomly generated 2d bin packing problems as described in Lodi, Martello, and Vigo. 'Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems.' INFORMS Journal on Computing 11.4 (1999): 345-357."; }
118    }
119
120    public override Uri WebLink {
121      get { return null; }
122    }
123
124    public override string ReferencePublication {
125      get { return "Lodi, Martello, and Vigo. 'Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems.' INFORMS Journal on Computing 11.4 (1999): 345-357."; }
126    }
127
128    public RandomInstanceProvider() : base() { }
129
130    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
131      // 10 classes
132      var rand = new MersenneTwister(1234); // fixed seed to makes sure that instances are always the same
133      foreach (int numItems in new int[] { 20, 40, 60, 80, 100 }) {
134        // get class parameters
135        // generate 30 different instances for each class
136        foreach (int instance in Enumerable.Range(1, 30)) {
137          string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class);
138          var dd = new RandomDataDescriptor(name, name, numItems, seed: rand.Next());
139          yield return dd;
140        }
141      }
142    }
143
144    public override BPPData LoadData(IDataDescriptor dd) {
145      var randDd = dd as RandomDataDescriptor;
146      if (randDd == null) throw new NotSupportedException("Cannot load data descriptor " + dd);
147
148      var data = new BPPData() {
149        BinShape = new PackingShape(binWidth, binHeight),
150        Items = new PackingItem[randDd.NumItems]
151      };
152      var instanceRand = new MersenneTwister((uint)randDd.Seed);
153      for (int i = 0; i < randDd.NumItems; i++) {
154        int w, h;
155        SampleItemParameters(instanceRand, out w, out h);
156        data.Items[i] = new PackingItem(w, h, data.BinShape);
157      }
158      return data;
159    }
160
161    // default implementation for class 7 .. 10
162    protected virtual void SampleItemParameters(IRandom rand, out int w, out int h) {
163      // for classes 1 - 5
164      Contract.Assert(@class >= 7 && @class <= 10);
165      var weights = new double[] { 0.1, 0.1, 0.1, 0.1 };
166      weights[@class - 7] = 0.7;
167      var type = Enumerable.Range(1, 4).SampleProportional(rand, 1, weights).First();
168
169      int minW, maxW;
170      int minH, maxH;
171      GetItemParameters(type, rand, binWidth, binHeight,
172        out minW, out maxW, out minH, out maxH);
173
174      w = rand.Next(minW, maxW + 1);
175      h = rand.Next(minH, maxH + 1);
176    }
177
178    private void GetItemParameters(int type, IRandom rand,
179      int w, int h,
180      out int minW, out int maxW, out int minH, out int maxH) {
181      switch (type) {
182        case 1: {
183            minW = w * 2 / 3; maxW = w; // integer division on purpose (see paper)
184            minH = 1; maxH = h / 2;
185            break;
186          }
187        case 2: {
188            minW = 1; maxW = w / 2;
189            minH = h * 2 / 3; maxH = h;
190            break;
191          }
192        case 3: {
193            minW = w / 2; maxW = w;
194            minH = h / 2; maxH = h;
195            break;
196          }
197        case 4: {
198            minW = 1; maxW = w / 2;
199            minH = 1; maxH = h / 2;
200            break;
201          }
202        default: {
203            throw new InvalidProgramException();
204          }
205      }
206    }
207
208    public override bool CanImportData {
209      get { return false; }
210    }
211    public override BPPData ImportData(string path) {
212      throw new NotSupportedException();
213    }
214
215    public override bool CanExportData {
216      get { return true; }
217    }
218
219    public override void ExportData(BPPData instance, string file) {
220      using (Stream stream = new FileStream(file, FileMode.OpenOrCreate, FileAccess.Write)) {
221        Export(instance, stream);
222      }
223    }
224    public static void Export(BPPData instance, Stream stream) {
225
226      using (var writer = new StreamWriter(stream)) {
227        writer.WriteLine(String.Format("{0,-5} {1,-5}   WBIN,HBIN", instance.BinShape.Width, instance.BinShape.Height));
228        for (int i = 0; i < instance.NumItems; i++) {
229          if (i == 0)
230            writer.WriteLine("{0,-5} {1,-5}   W(I),H(I),I=1,...,N", instance.Items[i].Width, instance.Items[i].Height);
231          else
232            writer.WriteLine("{0,-5} {1,-5}", instance.Items[i].Width, instance.Items[i].Height);
233
234        }
235        writer.Flush();
236      }
237    }
238
239  }
240}
Note: See TracBrowser for help on using the repository browser.