#region License Information /* HeuristicLab * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. * * HeuristicLab is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * HeuristicLab is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with HeuristicLab. If not, see . */ #endregion using System.Linq; using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Optimization; using HeuristicLab.Parameters; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; using HeuristicLab.Problems.Instances; namespace HeuristicLab.Problems.BinPacking3D { // in comparison to the 2d problem the 3d problem implementation also supports checking stacking constraints [StorableClass] public abstract class ProblemBase : SingleObjectiveBasicProblem, IProblemInstanceConsumer, IProblemInstanceExporter where TEnc : class, IEncoding where TSol : class, IItem { protected readonly string SolutionEvaluatorParameterName = "SolutionEvaluator"; protected readonly string UseStackingConstraintsParameterName = "UseStackingConstraints"; public readonly string EncodedSolutionName = "EncodedSolution"; #region Default Instance private readonly BPPData defaultInstance = new BPPData() { Name = "3D BPP Default Instance", Description = "The default instance for 3D Bin Packing.", BinShape = new PackingShape(25, 25, 35), Items = new PackingItem[] { new PackingItem(12,5,10, new PackingShape(25,25,35)), new PackingItem(10,18,20, new PackingShape(25,25,35)), new PackingItem(9,7,7, new PackingShape(25,25,35)), new PackingItem(21,12,4, new PackingShape(25,25,35)), new PackingItem(8,8,12, new PackingShape(25,25,35)), new PackingItem(3,6,14, new PackingShape(25,25,35)), new PackingItem(20,4,9, new PackingShape(25,25,35)), new PackingItem(5,9,8, new PackingShape(25,25,35)), new PackingItem(7,17,3, new PackingShape(25,25,35)), new PackingItem(13,20,15, new PackingShape(25,25,35)), new PackingItem(9,11,9, new PackingShape(25,25,35)), new PackingItem(10,18,20, new PackingShape(25,25,35)), new PackingItem(9,7,7, new PackingShape(25,25,35)), new PackingItem(21,12,4, new PackingShape(25,25,35)), new PackingItem(8,8,12, new PackingShape(25,25,35)), new PackingItem(3,6,14, new PackingShape(25,25,35)), new PackingItem(20,4,9, new PackingShape(25,25,35)), new PackingItem(5,9,8, new PackingShape(25,25,35)), new PackingItem(7,17,3, new PackingShape(25,25,35)), new PackingItem(13,20,15, new PackingShape(25,25,35)), new PackingItem(9,11,9, new PackingShape(25,25,35)), new PackingItem(10,18,20, new PackingShape(25,25,35)), new PackingItem(9,7,7, new PackingShape(25,25,35)), new PackingItem(21,12,4, new PackingShape(25,25,35)), new PackingItem(8,8,12, new PackingShape(25,25,35)), new PackingItem(3,6,14, new PackingShape(25,25,35)), new PackingItem(20,4,9, new PackingShape(25,25,35)), new PackingItem(5,9,8, new PackingShape(25,25,35)), new PackingItem(7,17,3, new PackingShape(25,25,35)), new PackingItem(13,20,15, new PackingShape(25,25,35)), new PackingItem(9,11, 9,new PackingShape(25,25,35)), new PackingItem(10,18,20, new PackingShape(25,25,35)), new PackingItem(9,7,7, new PackingShape(25,25,35)), new PackingItem(21,12,4, new PackingShape(25,25,35)), new PackingItem(8,8,12, new PackingShape(25,25,35)), new PackingItem(3,6,14, new PackingShape(25,25,35)), new PackingItem(20,4,9, new PackingShape(25,25,35)), new PackingItem(5,9,8, new PackingShape(25,25,35)), new PackingItem(7,17,3, new PackingShape(25,25,35)), new PackingItem(13,20,15, new PackingShape(25,25,35)), new PackingItem(9,11,9, new PackingShape(25,25,35)) }, }; #endregion #region parameter properties public IValueParameter> DecoderParameter { get { return (IValueParameter>)Parameters["Decoder"]; } } public IValueParameter SolutionEvaluatorParameter { get { return (IValueParameter)Parameters[SolutionEvaluatorParameterName]; } } public IFixedValueParameter UseStackingConstraintsParameter { get { return (IFixedValueParameter)Parameters[UseStackingConstraintsParameterName]; } } public IValueParameter> ItemsParameter { get { return (IValueParameter>)Parameters["Items"]; } } public IValueParameter BinShapeParameter { get { return (IValueParameter)Parameters["BinShape"]; } } public IValueParameter BestKnownSolutionParameter { get { return (IValueParameter)Parameters["BestKnownSolution"]; } } public IFixedValueParameter LowerBoundParameter { get { return (IFixedValueParameter)Parameters["LowerBound"]; } } #endregion #region properties public IDecoder Decoder { get { return DecoderParameter.Value; } set { DecoderParameter.Value = value; } } public IEvaluator SolutionEvaluator { get { return SolutionEvaluatorParameter.Value; } set { SolutionEvaluatorParameter.Value = value; } } public bool UseStackingConstraints { get { return UseStackingConstraintsParameter.Value.Value; } set { UseStackingConstraintsParameter.Value.Value = value; } } public ReadOnlyItemList Items { get { return ItemsParameter.Value; } set { ItemsParameter.Value = value; } } public PackingShape BinShape { get { return BinShapeParameter.Value; } set { BinShapeParameter.Value = value; } } public Solution BestKnownSolution { get { return BestKnownSolutionParameter.Value; } set { BestKnownSolutionParameter.Value = value; } } public int LowerBound { get { return LowerBoundParameter.Value.Value; } } public int NumberOfItems { get { return Items == null ? 0 : Items.Count; } } #endregion // persistence [StorableConstructor] protected ProblemBase(bool deserializing) : base(deserializing) { } // cloning protected ProblemBase(ProblemBase original, Cloner cloner) : base(original, cloner) { } protected ProblemBase() : base() { var defaultEvaluator = new PackingRatioEvaluator(); Parameters.Add(new ValueParameter>("Decoder", "The decoder translates a permutation to a packing solution candidiates")); Parameters.Add(new ValueParameter(SolutionEvaluatorParameterName, "The evaluator calculates qualities of solution candidates", defaultEvaluator)); Parameters.Add(new FixedValueParameter(UseStackingConstraintsParameterName, "A flag that determines if stacking constraints are considered when solving the problem.", new BoolValue(false))); Parameters.Add(new ValueParameter>("Items", "The items which must be packed into bins")); Parameters.Add(new ValueParameter("BinShape", "The size of bins into which items must be packed")); Parameters.Add(new OptionalValueParameter("BestKnownSolution", "The best solution found so far")); Parameters.Add(new FixedValueParameter("LowerBound", "A lower bound for the number of bins that is necessary to pack all items")); Load(defaultInstance); } public override bool Maximization { get { return true; } } public override double Evaluate(Individual individual, IRandom random) { var encodedSolutionCand = (TSol)individual[EncodedSolutionName]; var decoder = Decoder; var solution = decoder.Decode(encodedSolutionCand, BinShape, Items, UseStackingConstraints); return SolutionEvaluator.Evaluate(solution); } public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) { base.Analyze(individuals, qualities, results, random); Analyze(individuals.Select(i => (TSol)i[EncodedSolutionName]).ToArray(), qualities, results, random); } // NOTE: same implementation as for 2d problem public virtual void Analyze(TSol[] individuals, double[] qualities, ResultCollection results, IRandom random) { var bestSolutionResultName = "Best Packing Solution"; var numContainersResultName = "Nr of Containers"; var binUtilResultName = "Overall Bin Utilization"; if (!results.ContainsKey(bestSolutionResultName)) results.Add(new Result(bestSolutionResultName, typeof(Solution))); if (!results.ContainsKey(numContainersResultName)) results.Add(new Result(numContainersResultName, typeof(IntValue))); if (!results.ContainsKey(binUtilResultName)) results.Add(new Result(binUtilResultName, typeof(DoubleValue))); // find index of item with max quality int bestIdx = 0; for (int j = 1; j < qualities.Length; j++) if (qualities[j] > qualities[bestIdx]) bestIdx = j; // update best solution so far var bestSolution = results[bestSolutionResultName].Value as Solution; if (bestSolution == null || bestSolution.Quality.Value < qualities[bestIdx]) { var newBestSolution = Decoder.Decode(individuals[bestIdx], BinShape, Items, UseStackingConstraints); newBestSolution.Quality = new DoubleValue(qualities[bestIdx]); results[bestSolutionResultName].Value = newBestSolution; results[numContainersResultName].Value = new IntValue(newBestSolution.NrOfBins); results[binUtilResultName].Value = new DoubleValue(BinUtilizationEvaluator.CalculateBinUtilization(newBestSolution)); // update best known solution var bestKnownQuality = BestKnownQualityParameter.Value; if (bestKnownQuality == null || bestKnownQuality.Value < qualities[bestIdx]) { BestKnownQualityParameter.ActualValue = new DoubleValue(qualities[bestIdx]); BestKnownSolutionParameter.ActualValue = newBestSolution; } } } #region Problem instance handling public void Load(BPPData data) { BestKnownSolutionParameter.Value = null; BestKnownQualityParameter.Value = null; if (data.BestKnownQuality.HasValue) BestKnownQuality = data.BestKnownQuality.Value; BinShape = data.BinShape; var items = new ItemList(data.Items); items.Sort((x, y) => y.CompareTo(x)); Items = items.AsReadOnly(); ApplyHorizontalOrientation(); LowerBoundParameter.Value.Value = CalculateLowerBound(); } public BPPData Export() { return new BPPData { Name = Name, Description = Description, BinShape = BinShape, Items = Items.ToArray() }; } #endregion #region helpers private void ApplyHorizontalOrientation() { BinShape.ApplyHorizontalOrientation(); foreach (var shape in Items) { shape.ApplyHorizontalOrientation(); } } private int CalculateLowerBound() { //This is the obvious continuous lower bound calculation; Martello and Vigo proposed a better way but it has not been implemented yet; int itemsVol = Items.Select(x => x.Volume).Sum(); int binVol = BinShape.Volume; return (itemsVol + binVol - 1) / (binVol); } #endregion } }