source: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Algorithms/ExtremePointAlgorithm.cs @ 15585

Last change on this file since 15585 was 15585, checked in by rhanghof, 20 months ago

#2817:

  • Bugfixes for the line projection based extreme point creation
  • Bugfixes for the tests
File size: 15.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 Joseph Helm and 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
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using System.Threading;
26
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
30using HeuristicLab.Encodings.PermutationEncoding;
31using HeuristicLab.Optimization;
32using HeuristicLab.Parameters;
33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
34using HeuristicLab.Problems.BinPacking3D.Packer;
35using HeuristicLab.Problems.BinPacking3D.Encoding;
36using HeuristicLab.Problems.BinPacking3D.Sorting;
37using HeuristicLab.Problems.BinPacking3D.Evaluators;
38
39namespace HeuristicLab.Problems.BinPacking3D {
40
41  public enum SortingMethod { All, Given, VolumeHeight, HeightVolume, AreaHeight, HeightArea, ClusteredAreaHeight, ClusteredHeightArea }
42  public enum FittingMethod { All, FirstFit, ResidualSpaceBestFit, FreeVolumeBestFit }
43
44  public enum ExtremePointCreationMethod { All, PointProjection, LineProjection }
45
46  [Item("Extreme-point-based Bin Packing (3d)", "An implementation of the extreme-point based packing described in Crainic, T. G., Perboli, G., & Tadei, R. (2008). Extreme point-based heuristics for three-dimensional bin packing. Informs Journal on computing, 20(3), 368-384.")]
47  [StorableClass]
48  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms, Priority = 180)]
49  public sealed class ExtremePointAlgorithm : BasicAlgorithm {
50
51    public override Type ProblemType {
52      get { return typeof(PermutationProblem); }
53    }
54
55    public new PermutationProblem Problem {
56      get { return (PermutationProblem)base.Problem; }
57      set { base.Problem = value; }
58    }
59
60    public override bool SupportsPause {
61      get { return false; }
62    }
63
64    [Storable]
65    private readonly IValueParameter<EnumValue<SortingMethod>> sortingMethodParameter;
66    public IValueParameter<EnumValue<SortingMethod>> SortingMethodParameter {
67      get { return sortingMethodParameter; }
68    }
69
70    [Storable]
71    private readonly IValueParameter<EnumValue<FittingMethod>> fittingMethodParameter;
72    public IValueParameter<EnumValue<FittingMethod>> FittingMethodParameter {
73      get { return fittingMethodParameter; }
74    }
75
76    [Storable]
77    private readonly IValueParameter<PercentValue> deltaParameter;
78    public IValueParameter<PercentValue> DeltaParameter {
79      get { return deltaParameter; }
80    }
81
82    [Storable]
83    private readonly IValueParameter<BoolValue> sortByMaterialParameter;
84
85    public IValueParameter<BoolValue> SortByMaterialParameter {
86      get { return sortByMaterialParameter; }
87    }
88
89    [Storable]
90    private readonly IValueParameter<EnumValue<ExtremePointCreationMethod>> extremePointCreationMethodParameter;
91    public IValueParameter<EnumValue<ExtremePointCreationMethod>> ExtremePointCreationMethodParameter {
92      get { return extremePointCreationMethodParameter; }
93    }
94
95    [StorableConstructor]
96    private ExtremePointAlgorithm(bool deserializing) : base(deserializing) { }
97    private ExtremePointAlgorithm(ExtremePointAlgorithm original, Cloner cloner)
98      : base(original, cloner) {
99      sortingMethodParameter = cloner.Clone(original.sortingMethodParameter);
100      fittingMethodParameter = cloner.Clone(original.fittingMethodParameter);
101      deltaParameter = cloner.Clone(original.deltaParameter);
102    }
103    public ExtremePointAlgorithm() {
104      Parameters.Add(sortingMethodParameter = new ValueParameter<EnumValue<SortingMethod>>(
105        "SortingMethod", "In which order the items should be packed.", new EnumValue<SortingMethod>(SortingMethod.All)));
106
107      Parameters.Add(fittingMethodParameter = new ValueParameter<EnumValue<FittingMethod>>(
108        "FittingMethod", "Which method to fit should be used.", new EnumValue<FittingMethod>(FittingMethod.All)));
109
110      Parameters.Add(extremePointCreationMethodParameter = new ValueParameter<EnumValue<ExtremePointCreationMethod>>(
111        "ExtremePointCreationMethod", "Which method should be used for creatomg extreme points.", new EnumValue<ExtremePointCreationMethod>(ExtremePointCreationMethod.All)));
112
113      Parameters.Add(deltaParameter = new ValueParameter<PercentValue>(
114        "Delta", "[1;100]% Clustered sorting methods use a delta parameter to determine the clusters.", new PercentValue(.1)));
115
116      Parameters.Add(sortByMaterialParameter = new ValueParameter<BoolValue>(
117        "SortByMaterial", "If this parameter is set, the items will be sorted by their material first", new BoolValue(true)));
118
119      Problem = new PermutationProblem();
120    }
121
122    public override IDeepCloneable Clone(Cloner cloner) {
123      return new ExtremePointAlgorithm(this, cloner);
124    }
125
126    [StorableHook(HookType.AfterDeserialization)]
127    private void AfterDeserialization() {
128    }
129
130    /// <summary>
131    /// Runs the extreme point algorithm and adds the results to the property <see cref="Result"/>
132    /// </summary>
133    /// <param name="token"></param>
134    protected override void Run(CancellationToken token) {
135      var items = Problem.Items;
136      var bin = Problem.BinShape;
137
138      var sorting = new[] { SortingMethodParameter.Value.Value };
139      if (sorting[0] == SortingMethod.All) {
140        sorting = Enum.GetValues(typeof(SortingMethod)).Cast<SortingMethod>().Where(x => x != SortingMethod.All).ToArray();
141      }
142
143      var fitting = new[] { fittingMethodParameter.Value.Value };
144      if (fitting[0] == FittingMethod.All) {
145        fitting = Enum.GetValues(typeof(FittingMethod)).Cast<FittingMethod>().Where(x => x != FittingMethod.All).ToArray();
146      }
147
148      var extremePointCreation = new[] { ExtremePointCreationMethodParameter.Value.Value };
149      if (extremePointCreation[0] == ExtremePointCreationMethod.All) {
150        extremePointCreation = Enum.GetValues(typeof(ExtremePointCreationMethod))
151                                     .Cast<ExtremePointCreationMethod>()
152                                     .Where(x => x != ExtremePointCreationMethod.All)
153                                     .ToArray();
154      }
155
156      //
157      var result = GetBest(bin, items, sorting, fitting, extremePointCreation, token);
158      if (result == null) {
159        throw new InvalidOperationException("No result obtained!");
160      }
161
162      Results.Add(new Result("Best Solution", "The best found solution", result.Item1));
163      Results.Add(new Result("Best Solution Quality", "The quality of the best found solution according to the evaluator", new DoubleValue(result.Item2)));
164
165      var binUtil = new BinUtilizationEvaluator();
166      var packRatio = new PackingRatioEvaluator();
167      Results.Add(new Result("Best Solution Bin Count",
168        "The number of bins in the best found solution",
169        new IntValue(result.Item1.NrOfBins)));
170      Results.Add(new Result("Best Solution Bin Utilization",
171        "The utilization given in percentage as calculated by the BinUtilizationEvaluator (total used space / total available space)",
172        new PercentValue(Math.Round(binUtil.Evaluate(result.Item1), 3))));
173
174      if (result.Item3.HasValue && sorting.Length > 1) {
175        Results.Add(new Result("Best Sorting Method",
176          "The sorting method that found the best solution",
177          new EnumValue<SortingMethod>(result.Item3.Value)));
178      }
179
180      if (result.Item4.HasValue && fitting.Length > 1) {
181        Results.Add(new Result("Best Fitting Method",
182          "The fitting method that found the best solution",
183          new EnumValue<FittingMethod>(result.Item4.Value)));
184      }
185
186      if (result.Item5.HasValue && extremePointCreation.Length > 1) {
187        Results.Add(new Result("Best extreme point creation method",
188          "The extreme point creation method that found the best solution",
189          new EnumValue<ExtremePointCreationMethod>(result.Item5.Value)));
190      }
191    }
192
193    /// <summary>
194    /// Retunrs the best solution for the given parameters
195    /// </summary>
196    /// <param name="bin"></param>
197    /// <param name="items"></param>
198    /// <param name="sortings"></param>
199    /// <param name="fittings"></param>
200    /// <param name="token"></param>
201    /// <returns></returns>
202    private Tuple<Solution, double, SortingMethod?, FittingMethod?, ExtremePointCreationMethod?> 
203          GetBest(PackingShape bin, 
204                  IList<PackingItem> items, 
205                  SortingMethod[] sortings, 
206                  FittingMethod[] fittings,
207                  ExtremePointCreationMethod[] epCreationMethods,
208                  CancellationToken token) {
209      SortingMethod? bestSorting = null;
210      FittingMethod? bestFitting = null;
211      ExtremePointCreationMethod? bestEPCreation = null;
212      var best = double.NaN;
213      Solution bestSolution = null;
214      foreach (var fit in fittings) {
215        foreach (var sort in sortings) {
216          foreach (var epCreation in epCreationMethods) {
217            IDecoder<Permutation> decoder = new ExtremePointPermutationDecoder() {
218              FittingMethod = fit,
219              ExtremePointCreationMethod = epCreation
220            };
221            Permutation sortedItems;
222                   
223            if (SortByMaterialParameter.Value.Value) {
224              sortedItems = SortItemsByMaterialAndSortingMethod(bin, items, sort, DeltaParameter.Value.Value);
225            } else {
226              sortedItems = SortItemsBySortingMethod(bin, items, sort, DeltaParameter.Value.Value);
227            }
228
229            var result = Optimize(new OptimaizationParamters() {
230              SortedItems = sortedItems,
231              Bin = bin,
232              Items = items,
233              StackingConstraints = Problem.UseStackingConstraints,
234              Decoder = decoder,
235              Evaluator = Problem.SolutionEvaluator,
236              ExtremePointGeneration = epCreation
237            });
238         
239            if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) {
240              continue;
241            }
242
243            if (double.IsNaN(best) || Problem.Maximization && result.Item2 > best || !Problem.Maximization && result.Item2 < best) {
244              bestSolution = result.Item1;
245              best = result.Item2;
246              bestSorting = sort;
247              bestFitting = fit;
248              bestEPCreation = epCreation;
249            }
250            if (token.IsCancellationRequested) {
251              return Tuple.Create(bestSolution, best, bestSorting, bestFitting, bestEPCreation);
252            }
253          }
254        }
255      }
256      if (double.IsNaN(best)) {
257        return null;
258      }
259      return Tuple.Create(bestSolution, best, bestSorting, bestFitting, bestEPCreation);
260    }
261
262    /// <summary>
263    /// Returns a tuple with the solution and the packing ratio depending on the given parameters
264    /// </summary>
265    /// <param name="parameters"></param>
266    /// <returns></returns>
267    private static Tuple<Solution, double> Optimize(OptimaizationParamters parameters) { 
268     
269      var sol = parameters.Decoder.Decode(parameters.SortedItems, parameters.Bin, parameters.Items, parameters.StackingConstraints);
270      var fit = parameters.Evaluator.Evaluate(sol);
271
272      return Tuple.Create(sol, fit);
273    }
274
275    private class OptimaizationParamters {
276      public Permutation SortedItems { get; set; }
277      public PackingShape Bin { get; set; }
278      public IList<PackingItem> Items { get; set; }
279      public bool StackingConstraints { get; set; }
280      public IDecoder<Permutation> Decoder { get; set; }
281      public IEvaluator Evaluator { get; set; }
282      public ExtremePointCreationMethod ExtremePointGeneration { get; set; }
283    }
284   
285
286    /// <summary>
287    /// Returns a new permutation of the given items depending on the sorting method
288    /// </summary>
289    /// <param name="bin"></param>
290    /// <param name="items"></param>
291    /// <param name="sortingMethod"></param>
292    /// <param name="delta"></param>
293    /// <returns></returns>
294    private Permutation SortItemsBySortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {
295      Permutation sorted = null;
296     
297      switch (sortingMethod) {
298        case SortingMethod.Given:
299          sorted = new Permutation(PermutationTypes.Absolute, Enumerable.Range(0, items.Count).ToArray());
300          break;
301        case SortingMethod.VolumeHeight:
302          sorted = items.SortByVolumeHeight();
303          break;
304        case SortingMethod.HeightVolume:
305          sorted = items.SortByMaterialHeightVolume();
306          break;
307        case SortingMethod.AreaHeight:
308          sorted = items.SortByMaterialAreaHeight();
309          break;
310        case SortingMethod.HeightArea:
311          sorted = items.SortByMaterialHeightArea();
312          break;
313        case SortingMethod.ClusteredAreaHeight:
314          sorted = items.SortByMaterialClusteredAreaHeight(bin, delta);
315          break;
316        case SortingMethod.ClusteredHeightArea:
317          sorted = items.SortByMaterialClusteredHeightArea(bin, delta);
318          break;
319        default:
320          throw new ArgumentException("Unknown sorting method: " + sortingMethod);
321      }
322      return sorted;
323    }
324
325    /// <summary>
326    /// Returns a new permutation of the given items depending on the material and sorting method
327    /// </summary>
328    /// <param name="bin"></param>
329    /// <param name="items"></param>
330    /// <param name="sortingMethod"></param>
331    /// <param name="delta"></param>
332    /// <returns></returns>
333    private Permutation SortItemsByMaterialAndSortingMethod(PackingShape bin, IList<PackingItem> items, SortingMethod sortingMethod, double delta) {
334      Permutation sorted = null;
335
336      switch (sortingMethod) {
337        case SortingMethod.Given:
338          sorted = new Permutation(PermutationTypes.Absolute, Enumerable.Range(0, items.Count).ToArray());
339          break;
340        case SortingMethod.VolumeHeight:
341          sorted = items.SortByVolumeHeight();
342          break;
343        case SortingMethod.HeightVolume:
344          sorted = items.SortByHeightVolume();
345          break;
346        case SortingMethod.AreaHeight:
347          sorted = items.SortByAreaHeight();
348          break;
349        case SortingMethod.HeightArea:
350          sorted = items.SortByHeightArea();
351          break;
352        case SortingMethod.ClusteredAreaHeight:
353          sorted = items.SortByClusteredAreaHeight(bin, delta);
354          break;
355        case SortingMethod.ClusteredHeightArea:
356          sorted = items.SortByClusteredHeightArea(bin, delta);
357          break;
358        default:
359          throw new ArgumentException("Unknown sorting method: " + sortingMethod);
360      }
361      return sorted;
362    }
363  }
364}
Note: See TracBrowser for help on using the repository browser.