source: branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Problem.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: 12.2 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 HeuristicLab.Optimization;
23using HeuristicLab.Core;
24using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
25using HeuristicLab.Common;
26using HeuristicLab.Parameters;
27using HeuristicLab.Data;
28using HeuristicLab.PluginInfrastructure;
29using System.Linq;
30using System;
31using HeuristicLab.Encodings.PackingEncoding;
32
33namespace HeuristicLab.Problems.BinPacking {
34  [StorableClass]
35  public abstract class Problem<D, B, I> : SingleObjectiveHeuristicOptimizationProblem<IDecodingEvaluator, IPackingSolutionCreator>
36    where D : class, IPackingPosition
37    where B : PackingShape<D>, new()
38    where I : PackingShape<D>, IPackingItem, new() {
39
40
41    #region Parameter Properties
42    public OptionalValueParameter<PackingPlan<D, B, I>> BestKnownSolutionParameter {
43      get { return (OptionalValueParameter<PackingPlan<D, B, I>>)Parameters["BestKnownSolution"]; }
44    }
45    public ValueParameter<ItemList<I>> PackingItemMeasuresParameter {
46      get { return (ValueParameter<ItemList<I>>)Parameters["PackingItemMeasures"]; }
47    }
48    public IFixedValueParameter<IntValue> PackingItemsParameter {
49      get { return (IFixedValueParameter<IntValue>)Parameters["PackingItems"]; }
50    }
51    public IFixedValueParameter<IntValue> LowerBoundParameter {
52      get { return (IFixedValueParameter<IntValue>)Parameters["LowerBound"]; }
53    }
54    public ValueParameter<IEvaluator> PackingPlanEvaluatorParameter {
55      get { return (ValueParameter<IEvaluator>)Parameters["PackingPlanEvaluator"]; }
56    }
57    public IValueParameter<B> PackingBinMeasuresParameter {
58      get { return (IValueParameter<B>)Parameters["PackingBinMeasures"]; }
59    }
60    public IConstrainedValueParameter<IPackingSolutionDecoder> PackingSolutionDecoderParameter {
61      get { return (IConstrainedValueParameter<IPackingSolutionDecoder>)Parameters["PackingSolutionDecoder"]; }
62    }
63    #endregion
64
65    #region Properties
66    public PackingPlan<D, B, I> BestKnownSolution {
67      get { return BestKnownSolutionParameter.Value; }
68      set { BestKnownSolutionParameter.Value = value; }
69    }
70    public ItemList<I> PackingItemMeasures {
71      get { return PackingItemMeasuresParameter.Value; }
72      set { PackingItemMeasuresParameter.Value = value; }
73    }
74    public IEvaluator PackingPlanEvaluator {
75      get { return PackingPlanEvaluatorParameter.Value; }
76      set { PackingPlanEvaluatorParameter.Value = value; }
77    }
78    public B PackingBinMeasures {
79      get { return PackingBinMeasuresParameter.Value; }
80      set { PackingBinMeasuresParameter.Value = value; }
81    }
82    public PackingSolutionDecoder<D, B, I> PackingSolutionDecoder {
83      get { return PackingSolutionDecoderParameter.Value as PackingSolutionDecoder<D, B, I>; }
84      set { PackingSolutionDecoderParameter.Value = value; }
85    }
86    #endregion
87
88
89    [StorableConstructor]
90    protected Problem(bool deserializing) : base(deserializing) { }
91    protected Problem(Problem<D, B, I> original, Cloner cloner)
92      : base(original, cloner) {
93      InitializeEventHandlers();
94    }
95
96    protected Problem(IDecodingEvaluator e) : this(e, new PackingSequenceRandomCreator()) { }
97
98    protected Problem(IDecodingEvaluator e, IPackingSolutionCreator c)
99      : base(e, c) {
100      Parameters.Add(new OptionalValueParameter<PackingPlan<D, B, I>>("BestKnownSolution", "The best known solution of this bin-packing instance."));
101      Parameters.Add(new ValueParameter<ItemList<I>>("PackingItemMeasures", "Packing-item data defining the measures of the different items that need to be packed.", new ItemList<I>()));
102
103      Parameters.Add(new FixedValueParameter<IntValue>("PackingItems", "The number of packing-items used in this bin packing instance.", new IntValue()));
104      Parameters.Add(new FixedValueParameter<IntValue>("LowerBound", "The lower possible number of bins needed to solve this problem (taken from Dell'Amico, Martello and Vigo; 2002)", new IntValue()));
105      Parameters.Add(new ValueParameter<B>("PackingBinMeasures", "Packing-bin data defining the measures of the used bins.", new B()));
106      Parameters.Add(new ValueParameter<IEvaluator>("PackingPlanEvaluator", "The evaluator is used to determine the quality of a solution.", CreateDefaultEvaluator()));
107      Parameters.Add(new ConstrainedValueParameter<IPackingSolutionDecoder>("PackingSolutionDecoder", "The operator that decodes the representation and creates a packing plan."));
108      this.Maximization.Value = true;
109      InitializeProblemInstance(); // TODO
110      InitializeOperators();
111      InitializeEventHandlers();
112    }
113
114    protected abstract void InitializeDecoder();
115    protected virtual void InitializeProblemInstance() {
116      InitializeProblemData();
117      ApplyHorizontalOrientation();
118      SortItems();
119      RemoveTooBigItems();
120      PackingItemsParameter.Value.Value = PackingItemMeasures.Count;
121      LowerBoundParameter.Value.Value = CalculateLowerBound();
122    }
123    protected virtual void InitializeOperators() {
124      Operators.Clear();
125      Operators.Add(new BestBinPackingSolutionAnalyzer<D, B, I>());
126
127      ApplyEncoding();
128      ParameterizeOperators();
129    }
130    protected virtual void InitializeEventHandlers() {
131      PackingPlanEvaluatorParameter.ValueChanged += PackingPlanEvaluatorParameter_ValueChanged;
132      PackingPlanEvaluator.QualityParameter.ActualNameChanged += PackingPlanEvaluator_QualityParameter_ActualNameChanged;
133      SolutionCreatorParameter.ValueChanged += SolutionCreatorParameter_ValueChanged;
134      SolutionCreator.EncodedSolutionParameter.ActualNameChanged += SolutionCreator_EncodedSolutionParameter_ActualNameChanged;
135      PackingSolutionDecoderParameter.ValueChanged += PackingSolutionDecoderParameter_ValueChanged;
136      if (PackingSolutionDecoder != null) PackingSolutionDecoder.PackingPlanParameter.ActualNameChanged += PackingSolutionDecoder_PackingPlanParameter_ActualNameChanged;
137    }
138
139
140    protected abstract void RemoveTooBigItems();
141    protected abstract void InitializeProblemData();
142    protected abstract IEvaluator CreateDefaultEvaluator();
143    protected void ApplyHorizontalOrientation() {
144      PackingBinMeasures.ApplyHorizontalOrientation();
145      foreach (IPackingShape shape in PackingItemMeasures) {
146        shape.ApplyHorizontalOrientation();
147      }
148    }
149    protected void SortItems() {
150      PackingItemMeasures.Sort((x, y) => y.CompareTo(x));
151    }
152    protected int CalculateLowerBound() {
153      //This is the obvious continuous lower bound calculation; Martello and Vigo proposed a better way but it has not been implemented yet;
154      int items = PackingItemMeasures.Select(x => x.Volume).Sum();
155      int bin = PackingBinMeasures.Volume;
156      return (items + bin - 1) / (bin);
157    }
158
159    private void ApplyEncoding() {
160      if (SolutionCreator.GetType() == typeof(PackingSequenceRandomCreator)) {
161        Operators.AddRange(ApplicationManager.Manager.GetInstances<IPackingSequenceOperator>());
162        InitializeDecoder();
163      } /* else if (SolutionCreator.GetType() == typeof(GroupingVectorRandomCreator)) {
164        Operators.AddRange(ApplicationManager.Manager.GetInstances<IGroupingVectorOperator>());
165        InitializeDecoder();
166      } else if (SolutionCreator.GetType() == typeof(MultiComponentVectorRandomCreator)) {
167        Operators.AddRange(ApplicationManager.Manager.GetInstances<IMultiComponentVectorOperator>());
168        InitializeDecoder();
169      } */
170    }
171    private void ParameterizeOperators() {
172      foreach (var op in Operators.OfType<BestBinPackingSolutionAnalyzer<D, B, I>>()) {
173        op.QualityParameter.ActualName = PackingPlanEvaluator.QualityParameter.ActualName;
174      }
175
176      Evaluator.PackingSolutionDecoderParameter.ActualName = PackingSolutionDecoderParameter.Name;
177      Evaluator.PackingSolutionDecoderParameter.Hidden = true;
178      Evaluator.PackingPlanEvaluatorParameter.ActualName = PackingPlanEvaluatorParameter.Name;
179      Evaluator.PackingPlanEvaluatorParameter.Hidden = true;
180      Evaluator.QualityParameter.ActualName = PackingPlanEvaluator.QualityParameter.ActualName;
181      Evaluator.QualityParameter.Hidden = true;
182
183      if (PackingSolutionDecoder != null)
184        PackingSolutionDecoder.EncodedSolutionParameter.ActualName = SolutionCreator.EncodedSolutionParameter.ActualName;
185
186      if (PackingSolutionDecoder != null) {
187        PackingPlanEvaluator.PackingPlanParameter.ActualName = PackingSolutionDecoder.PackingPlanParameter.ActualName;
188        PackingPlanEvaluator.PackingPlanParameter.Hidden = true;
189      } else {
190        PackingPlanEvaluator.PackingPlanParameter.ActualName = PackingPlanEvaluator.PackingPlanParameter.Name;
191        PackingPlanEvaluator.PackingPlanParameter.Hidden = false;
192      }
193      /*
194
195      foreach (var op in Operators.OfType<IPackingSolutionManipulator>()) {
196        op.EncodedSolutionParameter.ActualName = SolutionCreator.EncodedSolutionParameter.ActualName;
197        op.EncodedSolutionParameter.Hidden = true;
198      }
199
200      foreach (var op in Operators.OfType<IPackingSolutionCrossover>()) {
201        op.ChildParameter.ActualName = SolutionCreator.EncodedSolutionParameter.ActualName;
202        op.ChildParameter.Hidden = true;
203        op.ParentsParameter.ActualName = SolutionCreator.EncodedSolutionParameter.ActualName;
204        op.ParentsParameter.Hidden = true;
205      }
206      */
207      foreach (var op in Operators.OfType<BestBinPackingSolutionAnalyzer<D, B, I>>()) {
208        op.QualityParameter.ActualName = PackingPlanEvaluator.QualityParameter.ActualName;
209        if (PackingSolutionDecoder != null) {
210          op.PackingPlanParameter.ActualName = PackingSolutionDecoder.PackingPlanParameter.ActualName;
211          op.PackingPlanParameter.Hidden = true;
212        } else {
213          op.PackingPlanParameter.ActualName = op.PackingPlanParameter.Name;
214          op.PackingPlanParameter.Hidden = false;
215        }
216      }
217
218    }
219
220    #region Events
221    protected override void OnSolutionCreatorChanged() {
222      InitializeOperators();
223    }
224    protected override void OnEvaluatorChanged() {
225      base.OnEvaluatorChanged();
226      ParameterizeOperators();
227    }
228    private void PackingPlanEvaluatorParameter_ValueChanged(object sender, EventArgs eventArgs) {
229      PackingPlanEvaluator.QualityParameter.ActualNameChanged += PackingPlanEvaluator_QualityParameter_ActualNameChanged;
230      ParameterizeOperators();
231    }
232    private void PackingPlanEvaluator_QualityParameter_ActualNameChanged(object sender, EventArgs eventArgs) {
233      ParameterizeOperators();
234    }
235    private void SolutionCreatorParameter_ValueChanged(object sender, EventArgs eventArgs) {
236      SolutionCreator.EncodedSolutionParameter.ActualNameChanged += SolutionCreator_EncodedSolutionParameter_ActualNameChanged;
237      ParameterizeOperators();
238    }
239    private void SolutionCreator_EncodedSolutionParameter_ActualNameChanged(object sender, EventArgs eventArgs) {
240      ParameterizeOperators();
241    }
242    private void PackingSolutionDecoderParameter_ValueChanged(object sender, EventArgs eventArgs) {
243      if (PackingSolutionDecoder != null) PackingSolutionDecoder.PackingPlanParameter.ActualNameChanged += PackingSolutionDecoder_PackingPlanParameter_ActualNameChanged;
244      ParameterizeOperators();
245    }
246    private void PackingSolutionDecoder_PackingPlanParameter_ActualNameChanged(object sender, EventArgs eventArgs) {
247      ParameterizeOperators();
248    }
249    #endregion
250  }
251}
Note: See TracBrowser for help on using the repository browser.