source: trunk/sources/HeuristicLab.Problems.BinPacking/3.3/3D/ProblemBase.cs @ 14162

Last change on this file since 14162 was 14162, checked in by gkronber, 4 years ago

#2641: first import of bin packing problem (TODO: persistence and sample)

File size: 12.2 KB
Line 
1#region License Information
2
3/* HeuristicLab
4 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
5 *
6 * This file is part of HeuristicLab.
7 *
8 * HeuristicLab is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * HeuristicLab is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
20 */
21
22#endregion
23
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Optimization;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31using HeuristicLab.Problems.Instances;
32
33namespace HeuristicLab.Problems.BinPacking3D {
34  // in comparison to the 2d problem the 3d problem implementation also supports checking stacking constraints
35  [StorableClass]
36  public abstract class ProblemBase<TEnc, TSol> :
37    SingleObjectiveBasicProblem<TEnc>, IProblemInstanceConsumer<BPPData>, IProblemInstanceExporter<BPPData>
38    where TEnc : class, IEncoding
39    where TSol : class, IItem {
40    protected readonly string SolutionEvaluatorParameterName = "SolutionEvaluator";
41    protected readonly string UseStackingConstraintsParameterName = "UseStackingConstraints";
42
43    public readonly string EncodedSolutionName = "EncodedSolution";
44    #region Default Instance
45    private readonly BPPData defaultInstance = new BPPData() {
46      Name = "3D BPP Default Instance",
47      Description = "The default instance for 3D Bin Packing.",
48      BinShape = new PackingShape(25, 25, 35),
49      Items = new PackingItem[] {
50        new PackingItem(12,5,10, new PackingShape(25,25,35)),
51        new PackingItem(10,18,20, new PackingShape(25,25,35)),
52        new PackingItem(9,7,7, new PackingShape(25,25,35)),
53        new PackingItem(21,12,4, new PackingShape(25,25,35)),
54        new PackingItem(8,8,12, new PackingShape(25,25,35)),
55        new PackingItem(3,6,14, new PackingShape(25,25,35)),
56        new PackingItem(20,4,9, new PackingShape(25,25,35)),
57        new PackingItem(5,9,8, new PackingShape(25,25,35)),
58        new PackingItem(7,17,3, new PackingShape(25,25,35)),
59        new PackingItem(13,20,15, new PackingShape(25,25,35)),
60        new PackingItem(9,11,9, new PackingShape(25,25,35)),
61        new PackingItem(10,18,20, new PackingShape(25,25,35)),
62        new PackingItem(9,7,7, new PackingShape(25,25,35)),
63        new PackingItem(21,12,4, new PackingShape(25,25,35)),
64        new PackingItem(8,8,12, new PackingShape(25,25,35)),
65        new PackingItem(3,6,14, new PackingShape(25,25,35)),
66        new PackingItem(20,4,9, new PackingShape(25,25,35)),
67        new PackingItem(5,9,8, new PackingShape(25,25,35)),
68        new PackingItem(7,17,3, new PackingShape(25,25,35)),
69        new PackingItem(13,20,15, new PackingShape(25,25,35)),
70        new PackingItem(9,11,9, new PackingShape(25,25,35)),
71        new PackingItem(10,18,20, new PackingShape(25,25,35)),
72        new PackingItem(9,7,7, new PackingShape(25,25,35)),
73        new PackingItem(21,12,4, new PackingShape(25,25,35)),
74        new PackingItem(8,8,12, new PackingShape(25,25,35)),
75        new PackingItem(3,6,14, new PackingShape(25,25,35)),
76        new PackingItem(20,4,9, new PackingShape(25,25,35)),
77        new PackingItem(5,9,8, new PackingShape(25,25,35)),
78        new PackingItem(7,17,3, new PackingShape(25,25,35)),
79        new PackingItem(13,20,15, new PackingShape(25,25,35)),
80        new PackingItem(9,11, 9,new PackingShape(25,25,35)),
81        new PackingItem(10,18,20, new PackingShape(25,25,35)),
82        new PackingItem(9,7,7, new PackingShape(25,25,35)),
83        new PackingItem(21,12,4, new PackingShape(25,25,35)),
84        new PackingItem(8,8,12, new PackingShape(25,25,35)),
85        new PackingItem(3,6,14, new PackingShape(25,25,35)),
86        new PackingItem(20,4,9, new PackingShape(25,25,35)),
87        new PackingItem(5,9,8, new PackingShape(25,25,35)),
88        new PackingItem(7,17,3, new PackingShape(25,25,35)),
89        new PackingItem(13,20,15, new PackingShape(25,25,35)),
90        new PackingItem(9,11,9, new PackingShape(25,25,35))
91      },
92    };
93    #endregion
94
95    #region parameter properties
96    public IValueParameter<IDecoder<TSol>> DecoderParameter {
97      get { return (IValueParameter<IDecoder<TSol>>)Parameters["Decoder"]; }
98    }
99    public IValueParameter<IEvaluator> SolutionEvaluatorParameter {
100      get { return (IValueParameter<IEvaluator>)Parameters[SolutionEvaluatorParameterName]; }
101    }
102    public IFixedValueParameter<BoolValue> UseStackingConstraintsParameter {
103      get { return (IFixedValueParameter<BoolValue>)Parameters[UseStackingConstraintsParameterName]; }
104    }
105    public IValueParameter<ReadOnlyItemList<PackingItem>> ItemsParameter {
106      get { return (IValueParameter<ReadOnlyItemList<PackingItem>>)Parameters["Items"]; }
107    }
108    public IValueParameter<PackingShape> BinShapeParameter {
109      get { return (IValueParameter<PackingShape>)Parameters["BinShape"]; }
110    }
111    public IValueParameter<Solution> BestKnownSolutionParameter {
112      get { return (IValueParameter<Solution>)Parameters["BestKnownSolution"]; }
113    }
114    public IFixedValueParameter<IntValue> LowerBoundParameter {
115      get { return (IFixedValueParameter<IntValue>)Parameters["LowerBound"]; }
116    }
117    #endregion
118
119    #region properties
120    public IDecoder<TSol> Decoder {
121      get { return DecoderParameter.Value; }
122      set { DecoderParameter.Value = value; }
123    }
124    public IEvaluator SolutionEvaluator {
125      get { return SolutionEvaluatorParameter.Value; }
126      set { SolutionEvaluatorParameter.Value = value; }
127    }
128    public bool UseStackingConstraints {
129      get { return UseStackingConstraintsParameter.Value.Value; }
130      set { UseStackingConstraintsParameter.Value.Value = value; }
131    }
132    public ReadOnlyItemList<PackingItem> Items {
133      get { return ItemsParameter.Value; }
134      set { ItemsParameter.Value = value; }
135    }
136    public PackingShape BinShape {
137      get { return BinShapeParameter.Value; }
138      set { BinShapeParameter.Value = value; }
139    }
140    public Solution BestKnownSolution {
141      get { return BestKnownSolutionParameter.Value; }
142      set { BestKnownSolutionParameter.Value = value; }
143    }
144    public int LowerBound {
145      get { return LowerBoundParameter.Value.Value; }
146    }
147    public int NumberOfItems {
148      get { return Items == null ? 0 : Items.Count; }
149    }
150    #endregion
151
152    // persistence
153    [StorableConstructor]
154    protected ProblemBase(bool deserializing) : base(deserializing) { }
155
156    // cloning
157    protected ProblemBase(ProblemBase<TEnc, TSol> original, Cloner cloner)
158      : base(original, cloner) {
159    }
160
161    protected ProblemBase()
162      : base() {
163      var defaultEvaluator = new PackingRatioEvaluator();
164      Parameters.Add(new ValueParameter<IDecoder<TSol>>("Decoder", "The decoder translates a permutation to a packing solution candidiates"));
165      Parameters.Add(new ValueParameter<IEvaluator>(SolutionEvaluatorParameterName, "The evaluator calculates qualities of solution candidates", defaultEvaluator));
166      Parameters.Add(new FixedValueParameter<BoolValue>(UseStackingConstraintsParameterName, "A flag that determines if stacking constraints are considered when solving the problem.", new BoolValue(false)));
167      Parameters.Add(new ValueParameter<ReadOnlyItemList<PackingItem>>("Items", "The items which must be packed into bins"));
168      Parameters.Add(new ValueParameter<PackingShape>("BinShape", "The size of bins into which items must be packed"));
169      Parameters.Add(new OptionalValueParameter<Solution>("BestKnownSolution", "The best solution found so far"));
170      Parameters.Add(new FixedValueParameter<IntValue>("LowerBound", "A lower bound for the number of bins that is necessary to pack all items"));
171
172      Load(defaultInstance);
173    }
174
175    public override bool Maximization { get { return true; } }
176
177
178    public override double Evaluate(Individual individual, IRandom random) {
179      var encodedSolutionCand = (TSol)individual[EncodedSolutionName];
180      var decoder = Decoder;
181      var solution = decoder.Decode(encodedSolutionCand, BinShape, Items, UseStackingConstraints);
182      return SolutionEvaluator.Evaluate(solution);
183    }
184
185    public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) {
186      base.Analyze(individuals, qualities, results, random);
187      Analyze(individuals.Select(i => (TSol)i[EncodedSolutionName]).ToArray(), qualities, results, random);
188    }
189
190    // NOTE: same implementation as for 2d problem
191    public virtual void Analyze(TSol[] individuals, double[] qualities, ResultCollection results, IRandom random) {
192      var bestSolutionResultName = "Best Packing Solution";
193      var numContainersResultName = "Nr of Containers";
194      var binUtilResultName = "Overall Bin Utilization";
195
196      if (!results.ContainsKey(bestSolutionResultName)) results.Add(new Result(bestSolutionResultName, typeof(Solution)));
197      if (!results.ContainsKey(numContainersResultName)) results.Add(new Result(numContainersResultName, typeof(IntValue)));
198      if (!results.ContainsKey(binUtilResultName)) results.Add(new Result(binUtilResultName, typeof(DoubleValue)));
199
200
201      // find index of item with max quality
202      int bestIdx = 0;
203      for (int j = 1; j < qualities.Length; j++)
204        if (qualities[j] > qualities[bestIdx]) bestIdx = j;
205
206
207      // update best solution so far
208      var bestSolution = results[bestSolutionResultName].Value as Solution;
209      if (bestSolution == null ||
210        bestSolution.Quality.Value < qualities[bestIdx]) {
211
212        var newBestSolution = Decoder.Decode(individuals[bestIdx], BinShape, Items, UseStackingConstraints);
213        newBestSolution.Quality = new DoubleValue(qualities[bestIdx]);
214        results[bestSolutionResultName].Value = newBestSolution;
215        results[numContainersResultName].Value = new IntValue(newBestSolution.NrOfBins);
216        results[binUtilResultName].Value = new DoubleValue(BinUtilizationEvaluator.CalculateBinUtilization(newBestSolution));
217
218        // update best known solution
219        var bestKnownQuality = BestKnownQualityParameter.Value;
220        if (bestKnownQuality == null ||
221            bestKnownQuality.Value < qualities[bestIdx]) {
222          BestKnownQualityParameter.ActualValue = new DoubleValue(qualities[bestIdx]);
223          BestKnownSolutionParameter.ActualValue = newBestSolution;
224        }
225      }
226    }
227
228
229    #region Problem instance handling
230    public void Load(BPPData data) {
231      BestKnownSolutionParameter.Value = null;
232      BestKnownQualityParameter.Value = null;
233
234      if (data.BestKnownQuality.HasValue)
235        BestKnownQuality = data.BestKnownQuality.Value;
236
237      BinShape = data.BinShape;
238      var items = new ItemList<PackingItem>(data.Items);
239      items.Sort((x, y) => y.CompareTo(x));
240      Items = items.AsReadOnly();
241
242      ApplyHorizontalOrientation();
243      LowerBoundParameter.Value.Value = CalculateLowerBound();
244    }
245
246
247    public BPPData Export() {
248      return new BPPData {
249        Name = Name,
250        Description = Description,
251        BinShape = BinShape,
252        Items = Items.ToArray()
253      };
254    }
255    #endregion
256
257
258    #region helpers
259    private void ApplyHorizontalOrientation() {
260      BinShape.ApplyHorizontalOrientation();
261      foreach (var shape in Items) {
262        shape.ApplyHorizontalOrientation();
263      }
264    }
265
266    private int CalculateLowerBound() {
267      //This is the obvious continuous lower bound calculation; Martello and Vigo proposed a better way but it has not been implemented yet;
268      int itemsVol = Items.Select(x => x.Volume).Sum();
269      int binVol = BinShape.Volume;
270      return (itemsVol + binVol - 1) / (binVol);
271    }
272
273    #endregion
274  }
275}
Note: See TracBrowser for help on using the repository browser.