source: branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Encodings/PackingPlans/PackingPlan.cs @ 14128

Last change on this file since 14128 was 14128, checked in by gkronber, 5 years ago

#1966: refactoring of bin packing implementation

File size: 9.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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 HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
26using HeuristicLab.Core;
27using HeuristicLab.Common;
28using HeuristicLab.Data;
29using HeuristicLab.Collections;
30using HeuristicLab.Encodings.IntegerVectorEncoding;
31using HeuristicLab.Problems.BinPacking;
32using HeuristicLab.Encodings.PermutationEncoding;
33
34namespace HeuristicLab.Encodings.PackingEncoding {
35  [Item("PackingPlan", "Represents a concrete solution for a bin-packing problem.")]
36  [StorableClass]
37  public abstract class PackingPlan<D, B, I> : Item, IPackingPlan
38    where D : class, IPackingPosition
39    where B : PackingShape<D>
40    where I : PackingShape<D>, IPackingItem {
41
42    #region Properties
43    public int NrOfBins {
44      get {
45        if (BinPackings != null)
46          return BinPackings.Count;
47        else return 0;
48      }
49    }
50    [Storable]
51    protected bool StackingConstraints { get; set; }
52    [Storable]
53    protected bool UseExtremePoints { get; set; }
54
55    [Storable]
56    public B BinMeasures { get; private set; }
57
58    [Storable]
59    public ObservableList<BinPacking<D, B, I>> BinPackings { get; set; }
60
61    [Storable]
62    private DoubleValue quality;
63    public DoubleValue Quality {
64      get { return quality; }
65      set {
66        if (quality != value) {
67          if (quality != null) DeregisterQualityEvents();
68          quality = value;
69          if (quality != null) RegisterQualityEvents();
70          OnQualityChanged();
71        }
72      }
73    }
74    #endregion
75
76    protected PackingPlan(B binMeasures, bool useExtremePoints, bool stackingConstraints)
77      : base() {
78      BinMeasures = (B)binMeasures.Clone();
79      StackingConstraints = stackingConstraints;
80      UseExtremePoints = useExtremePoints;
81      BinPackings = new ObservableList<BinPacking<D, B, I>>();
82    }
83
84    [StorableConstructor]
85    protected PackingPlan(bool deserializing) : base(deserializing) { }
86    protected PackingPlan(PackingPlan<D, B, I> original, Cloner cloner)
87      : base(original, cloner) {
88      this.BinPackings = new ObservableList<BinPacking<D, B, I>>(original.BinPackings);
89    }
90
91
92    public abstract BinPacking<D, B, I> NewBinPacking();
93    public void UpdateBinPackings() {
94      BinPackings.RemoveAll(x => x.ItemPositions.Count == 0);
95      BinPackings = new ObservableList<BinPacking<D, B, I>>(BinPackings.OrderByDescending(bp => bp.PackingDensity));
96    }
97
98    /*
99    public void Pack(MultiComponentVectorEncoding solution, ItemList<I> itemMeasures) {
100      var sequenceMatrix = solution.GenerateSequenceMatrix();
101      Dictionary<int, bool> rotated = solution.GenerateRotationArray();
102
103      //Fill bins according to grouping vector
104      List<int> remainingIDs = new List<int>();
105      foreach (var sequence in sequenceMatrix) {
106        remainingIDs = remainingIDs.Concat(sequence).ToList();
107        var bp = NewBinPacking();
108        if (!UseExtremePoints)
109          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures, rotated);
110        else
111          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints, rotated);
112        BinPackings.Add(bp);
113      }
114      UpdateBinPackings();
115
116      //Try to put remaining items in existing bins
117      var temp = new List<int>(remainingIDs);
118      foreach (int id in temp) {
119        foreach (var bp in BinPackings) {
120          var position = UseExtremePoints ? bp.FindExtremePointForItem(itemMeasures[id], rotated[id], StackingConstraints) : bp.FindPositionBySliding(itemMeasures[id], rotated[id]);
121          if (position != null) {
122            bp.PackItem(id, itemMeasures[id], position);
123            remainingIDs.Remove(id);
124            break;
125          }
126        }
127      }
128
129      //Put still remaining items in new bins
130      while (remainingIDs.Count > 0) {
131        var bp = NewBinPacking();
132        if (!UseExtremePoints)
133          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures, rotated);
134        else
135          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints, rotated);
136        BinPackings.Add(bp);
137      }
138      UpdateBinPackings();
139
140      var newSolution = new ObservableDictionary<int, ItemList<PackingInformation>>();
141      foreach (var bp in BinPackings) {
142        int binIndex = newSolution.Count;
143        newSolution[binIndex] = new ItemList<PackingInformation>();
144        foreach (var entry in bp.ItemPositions)
145          newSolution[binIndex].Add(new PackingInformation(entry.Key, entry.Value.Rotated));
146      }
147      solution.PackingInformations = newSolution;
148    }
149    public void Pack(GroupingVectorEncoding solution, ItemList<I> itemMeasures) {
150      var sequenceMatrix = solution.GenerateSequenceMatrix();
151
152      //Fill bins according to grouping vector
153      List<int> remainingIDs = new List<int>();
154      foreach (var sequence in sequenceMatrix) {
155        remainingIDs = remainingIDs.Concat(sequence).ToList();
156        var bp = NewBinPacking();
157        if (!UseExtremePoints)
158          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures);
159        else
160          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints);
161        BinPackings.Add(bp);
162      }
163      UpdateBinPackings();
164
165      //Try to put remaining items in existing bins
166      var temp = new List<int>(remainingIDs);
167      foreach (int id in temp) {
168        foreach (var bp in BinPackings) {
169          var position = UseExtremePoints ? bp.FindExtremePointForItem(itemMeasures[id], false, StackingConstraints) : bp.FindPositionBySliding(itemMeasures[id], false);
170          if (position != null) {
171            bp.PackItem(id, itemMeasures[id], position);
172            remainingIDs.Remove(id);
173            break;
174          }
175        }
176      }
177
178      //Put still remaining items in new bins
179      while (remainingIDs.Count > 0) {
180        var bp = NewBinPacking();
181        if (!UseExtremePoints)
182          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures);
183        else
184          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints);
185        BinPackings.Add(bp);
186      }
187      UpdateBinPackings();
188
189      var newSolution = new int[solution.GroupingVector.Length];
190      int binIndex = 0;
191      foreach (var bp in BinPackings) {
192        foreach (var entry in bp.ItemPositions)
193          newSolution[entry.Key] = binIndex;
194        binIndex++;
195      }
196      solution.GroupingVector = new IntegerVector(newSolution);
197    }
198     *
199     
200    public void Pack(Permutation solution, ItemList<I> itemMeasures) {
201      List<int> remainingIDs = new List<int>(solution);
202      while (remainingIDs.Count > 0) {
203        var bp = NewBinPacking();
204        if (!UseExtremePoints)
205          bp.SlidingBasedPacking(ref remainingIDs, itemMeasures);
206        else
207          bp.ExtremePointBasedPacking(ref remainingIDs, itemMeasures, StackingConstraints);
208        BinPackings.Add(bp);
209      }
210      UpdateBinPackings();
211    }
212
213    */
214    #region Events
215    public event EventHandler QualityChanged;
216    private void OnQualityChanged() {
217      var changed = QualityChanged;
218      if (changed != null)
219        changed(this, EventArgs.Empty);
220    }
221    private void RegisterQualityEvents() {
222      Quality.ValueChanged += new EventHandler(Quality_ValueChanged);
223    }
224    private void DeregisterQualityEvents() {
225      Quality.ValueChanged -= new EventHandler(Quality_ValueChanged);
226    }
227    private void Quality_ValueChanged(object sender, EventArgs e) {
228      OnQualityChanged();
229    }
230
231    public event EventHandler BinPackingsChanged;
232    private void OnBinPackingsChanged() {
233      var changed = BinPackingsChanged;
234      if (changed != null)
235        changed(this, EventArgs.Empty);
236    }
237    private void RegisterBinPackingsEvents() {
238      BinPackings.PropertyChanged += new System.ComponentModel.PropertyChangedEventHandler(BinPackings_PropertyChanged);
239    }
240    private void DeregisterBinPackingsEvents() {
241      BinPackings.PropertyChanged -= new System.ComponentModel.PropertyChangedEventHandler(BinPackings_PropertyChanged);
242    }
243    private void BinPackings_PropertyChanged(object sender, EventArgs e) {
244      OnBinPackingsChanged();
245    }
246    #endregion
247  }
248}
Note: See TracBrowser for help on using the repository browser.