Skip to content

Commit e4b308e

Browse files
merschformannmerschformann
committed
Improving search, fixing clone/reset issue, improving density objective, adding round robin, fixing orientation shuffling
1 parent ab75791 commit e4b308e

8 files changed

Lines changed: 241 additions & 119 deletions

File tree

‎SC.Heuristics/PrimalHeuristic/PointInsertionSkeletonLib.cs‎

Lines changed: 96 additions & 100 deletions
Large diffs are not rendered by default.

‎SC.ObjectModel/Additionals/ContainerInfo.cs‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -105,6 +105,7 @@ public void Clear()
105105
VolumeContained = 0;
106106
WeightContained = 0;
107107
NumberOfPieces = 0;
108+
PackingHeight = 0;
108109
}
109110

110111
/// <summary>
@@ -117,7 +118,8 @@ public ContainerInfo Clone(COSolution solution)
117118
{
118119
VolumeContained = VolumeContained,
119120
WeightContained = WeightContained,
120-
NumberOfPieces = NumberOfPieces
121+
NumberOfPieces = NumberOfPieces,
122+
PackingHeight = PackingHeight,
121123
};
122124
}
123125
}

‎SC.ObjectModel/Additionals/ContainerOrder.cs‎

Lines changed: 36 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -33,6 +33,10 @@ public enum ContainerReorderType
3333
/// Sorts the containers randomly.
3434
/// </summary>
3535
Random,
36+
/// <summary>
37+
/// Uses a round-robin approach to sort the containers.
38+
/// </summary>
39+
RoundRobin,
3640
}
3741

3842
public class ContainerOrderSupply
@@ -60,7 +64,11 @@ public static List<Container> SortInit(List<Container> containers, ContainerInit
6064
/// <summary>
6165
/// The containers to open first.
6266
/// </summary>
63-
public HashSet<Container> OpenContainers { get; private set; }
67+
public List<Container> OpenContainers { get; private set; }
68+
/// <summary>
69+
/// The containers that are not opened immediately.
70+
/// </summary>
71+
public List<Container> ReserveContainers { get; private set; }
6472
/// <summary>
6573
/// BigM value for preferring containers indicated to be opened right away.
6674
/// </summary>
@@ -87,7 +95,7 @@ public ContainerOrderSupply(
8795
Random random)
8896
{
8997
ReorderType = type;
90-
OpenContainers = new HashSet<Container>();
98+
OpenContainers = new List<Container>();
9199
_random = random;
92100
if (openContainerByPieceRatio > 0)
93101
{
@@ -101,23 +109,45 @@ public ContainerOrderSupply(
101109
break;
102110
}
103111
}
112+
ReserveContainers = new List<Container>(containers.Except(OpenContainers));
104113
}
105114

106115
/// <summary>
107116
/// Sorts the containers.
108117
/// </summary>
109118
/// <param name="containers">The containers to sort.</param>
119+
/// <param name="pieceCounter">The counter for piece insertion, i.e., this represents the x-th piece of this insertion round.</param>
110120
/// <returns>The sorted containers.</returns>
111-
public List<Container> SortReorder(List<Container> containers)
121+
public IEnumerable<Container> Reorder(List<Container> containers, int pieceCounter)
112122
{
113123
switch (ReorderType)
114124
{
125+
case ContainerReorderType.None:
126+
foreach (var container in containers)
127+
yield return container;
128+
break;
115129
case ContainerReorderType.Capacity:
116-
return containers.OrderByDescending(c => (OpenContainers.Contains(c) ? OpenContainerBigM : 0) + c.Mesh.Volume).ToList();
130+
foreach (var container in containers.OrderByDescending(c => (OpenContainers.Contains(c) ? OpenContainerBigM : 0) + c.Mesh.Volume))
131+
yield return container;
132+
break;
117133
case ContainerReorderType.Random:
118-
return containers.OrderByDescending(c => (OpenContainers.Contains(c) ? OpenContainerBigM : 0) + _random.Next()).ToList();
134+
foreach (var container in containers.OrderByDescending(c => (OpenContainers.Contains(c) ? OpenContainerBigM + OpenContainerBigM * _random.NextDouble() : 0) + c.ID))
135+
yield return container;
136+
break;
137+
case ContainerReorderType.RoundRobin:
138+
{
139+
var startIndex = pieceCounter / 10 % OpenContainers.Count;
140+
for (int i = 0; i < OpenContainers.Count; i++)
141+
{
142+
var index = (i + startIndex) % OpenContainers.Count;
143+
yield return OpenContainers[index];
144+
}
145+
foreach (var container in ReserveContainers)
146+
yield return container;
147+
}
148+
break;
119149
default:
120-
return containers;
150+
throw new ArgumentException($"Unknown container reorder type: {ReorderType}");
121151
}
122152
}
123153
}

‎SC.ObjectModel/Additionals/Objective.cs‎

Lines changed: 16 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,8 @@
11
using System;
2+
using System.Collections.Generic;
23
using System.Linq;
34
using SC.ObjectModel.Elements;
5+
using SC.Toolbox;
46

57
namespace SC.ObjectModel.Additionals
68
{
@@ -16,6 +18,7 @@ public class Objective
1618
public Objective(COSolution solution)
1719
{
1820
Solution = solution;
21+
_heightBigM = solution.InstanceLinked.Containers.Max(c => c.Mesh.Height);
1922
}
2023

2124
/// <summary>
@@ -35,17 +38,29 @@ public double Value
3538
case ObjectiveType.MaxVolume:
3639
return _volumeContained;
3740
case ObjectiveType.MaxDensity:
38-
return Solution.ContainerInfos.Sum(c => c.VolumeUtilizedPackingHeight);
41+
{
42+
return
43+
-Solution.OffloadPieces.Count * _heightBigM * 2
44+
- Solution.ContainerInfos.Count(c => c.NumberOfPieces > 0) * _heightBigM
45+
+ Solution.ContainerInfos.Where(c => c.NumberOfPieces > 0).MinOrDefault(c => c.PackingHeight) / _heightBigM;
46+
}
3947
default:
4048
throw new ArgumentException($"Unknown objective type: {Solution.Configuration.Objective}");
4149
}
4250
}
4351
}
4452

53+
54+
55+
4556
/// <summary>
4657
/// The volume packed inside of the containers.
4758
/// </summary>
4859
private double _volumeContained;
60+
/// <summary>
61+
/// The big M value for container height.
62+
/// </summary>
63+
private double _heightBigM;
4964

5065
/// <summary>
5166
/// Adds a piece to the container.

‎SC.ObjectModel/Additionals/PieceReorder.cs‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
using SC.ObjectModel.Elements;
2+
using System;
3+
using System.Collections.Generic;
4+
using System.Linq;
5+
using System.Text;
6+
using System.Threading.Tasks;
7+
8+
namespace SC.ObjectModel.Additionals
9+
{
10+
/// <summary>
11+
/// Defines the different piece-reorder types
12+
/// </summary>
13+
public enum PieceReorderType
14+
{
15+
/// <summary>
16+
/// Pieces are re-ordered based on their scores.
17+
/// </summary>
18+
Score,
19+
/// <summary>
20+
/// Pieces are re-ordered randomly.
21+
/// </summary>
22+
Random,
23+
/// <summary>
24+
/// Pieces are not re-ordered.
25+
/// </summary>
26+
None,
27+
}
28+
}

‎SC.ObjectModel/COSolution.cs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -269,7 +269,6 @@ public COSolution Clone(bool unofficial = true)
269269
{
270270
clone.ContainerInfos[container.VolatileID] = ContainerInfos[container.VolatileID].Clone(clone);
271271
}
272-
clone.Objective = Objective.Clone(clone);
273272
clone.ExtremePoints = ExtremePoints.Select(c => c.ToList()).ToArray();
274273
// Add info about the virtual pieces
275274
clone.GenerateVirtualPieceInfo();
@@ -299,6 +298,7 @@ public COSolution Clone(bool unofficial = true)
299298
clone.ConstructionContainerOrder = ConstructionContainerOrder.ToList();
300299
if (ConstructionOrientationOrder != null)
301300
clone.ConstructionOrientationOrder = ConstructionOrientationOrder.Select(p => p.ToArray()).ToArray();
301+
clone.Objective = Objective.Clone(clone);
302302
// Return it
303303
return clone;
304304
}

‎SC.ObjectModel/Configuration/Configuration.cs‎

Lines changed: 10 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -51,7 +51,7 @@ public Configuration(MethodType method, bool handleTetris)
5151
BestFit = true;
5252
MeritType = MeritFunctionType.MEDXYZ;
5353
Improvement = true;
54-
ScoreBasedOrder = true;
54+
PieceReorder = PieceReorderType.Score;
5555
RandomSalt = 0.1;
5656
InflateAndReplaceInsertion = true;
5757
NormalizationOrder = new DimensionMarker[3] { DimensionMarker.X, DimensionMarker.Y, DimensionMarker.Z };
@@ -75,7 +75,7 @@ public Configuration(MethodType method, bool handleTetris)
7575
BestFit = false;
7676
MeritType = MeritFunctionType.MEDXYZ;
7777
Improvement = true;
78-
ScoreBasedOrder = true;
78+
PieceReorder = PieceReorderType.Score;
7979
RandomSalt = 0.08368586690516754;
8080
InflateAndReplaceInsertion = false;
8181
NormalizationOrder = new DimensionMarker[3] { DimensionMarker.X, DimensionMarker.Y, DimensionMarker.Z };
@@ -95,7 +95,7 @@ public Configuration(MethodType method, bool handleTetris)
9595
BestFit = true;
9696
MeritType = MeritFunctionType.MFV;
9797
Improvement = true;
98-
ScoreBasedOrder = false;
98+
PieceReorder = PieceReorderType.Score;
9999
RandomSalt = 0.030644342734285967;
100100
InflateAndReplaceInsertion = false;
101101
NormalizationOrder = new DimensionMarker[3] { DimensionMarker.X, DimensionMarker.Y, DimensionMarker.Z };
@@ -117,7 +117,7 @@ public Configuration(MethodType method, bool handleTetris)
117117
BestFit = false;
118118
MeritType = MeritFunctionType.MEDXY;
119119
Improvement = true;
120-
ScoreBasedOrder = false;
120+
PieceReorder = PieceReorderType.Score;
121121
RandomSalt = 0.8866072829180582;
122122
InflateAndReplaceInsertion = true;
123123
NormalizationOrder = new DimensionMarker[3] { DimensionMarker.X, DimensionMarker.Y, DimensionMarker.Z };
@@ -140,7 +140,7 @@ public Configuration(MethodType method, bool handleTetris)
140140
BestFit = false;
141141
MeritType = MeritFunctionType.MEDXY;
142142
Improvement = true;
143-
ScoreBasedOrder = true;
143+
PieceReorder = PieceReorderType.Score;
144144
RandomSalt = 0.008158387839849155;
145145
InflateAndReplaceInsertion = false;
146146
NormalizationOrder = new DimensionMarker[3] { DimensionMarker.Z, DimensionMarker.X, DimensionMarker.Y };
@@ -160,7 +160,7 @@ public Configuration(MethodType method, bool handleTetris)
160160
BestFit = false;
161161
MeritType = MeritFunctionType.MEDXY;
162162
Improvement = true;
163-
ScoreBasedOrder = true;
163+
PieceReorder = PieceReorderType.Score;
164164
RandomSalt = 0.12794130221974132;
165165
InflateAndReplaceInsertion = false;
166166
NormalizationOrder = new DimensionMarker[3] { DimensionMarker.Z, DimensionMarker.Y, DimensionMarker.X };
@@ -184,7 +184,7 @@ public Configuration(MethodType method, bool handleTetris)
184184
BestFit = false;
185185
MeritType = MeritFunctionType.MEDXYZ;
186186
Improvement = true;
187-
ScoreBasedOrder = true;
187+
PieceReorder = PieceReorderType.Score;
188188
RandomSalt = 0.08368586690516754;
189189
InflateAndReplaceInsertion = false;
190190
NormalizationOrder = new DimensionMarker[3] { DimensionMarker.X, DimensionMarker.Y, DimensionMarker.Z };
@@ -204,7 +204,7 @@ public Configuration(MethodType method, bool handleTetris)
204204
BestFit = true;
205205
MeritType = MeritFunctionType.MFV;
206206
Improvement = true;
207-
ScoreBasedOrder = false;
207+
PieceReorder = PieceReorderType.Score;
208208
RandomSalt = 0.030644342734285967;
209209
InflateAndReplaceInsertion = false;
210210
NormalizationOrder = new DimensionMarker[3] { DimensionMarker.X, DimensionMarker.Y, DimensionMarker.Z };
@@ -389,9 +389,9 @@ public Configuration(MethodType method, bool handleTetris)
389389
public bool ExhaustiveEPProne { get; set; } = false;
390390

391391
/// <summary>
392-
/// Defines whether to use score-based ordering of pieces or just random-order
392+
/// Defines how pieces are being reordered between iterations.
393393
/// </summary>
394-
public bool ScoreBasedOrder { get; set; } = true;
394+
public PieceReorderType PieceReorder { get; set; } = PieceReorderType.Score;
395395

396396
/// <summary>
397397
/// Defines the merit function when best-fit is active

‎SC.Toolbox/EnumerableExtensions.cs‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Linq;
4+
5+
namespace SC.Toolbox
6+
{
7+
public static class EnumerableExtensions
8+
{
9+
/// <summary>
10+
/// Returns the minimum value of a sequence or the default value if the sequence is empty.
11+
/// </summary>
12+
/// <typeparam name="T">The type of the elements in the sequence.</typeparam>
13+
/// <param name="sequence">The sequence to find the minimum value of.</param>
14+
/// <param name="selector">The function to select the value to compare.</param>
15+
/// <returns>The minimum value of the sequence or the default value if the sequence is empty.</returns>
16+
public static double MinOrDefault<T>(this IEnumerable<T> sequence, Func<T, double> selector)
17+
{
18+
var value = default(double);
19+
if (sequence == null || !sequence.Any())
20+
return value;
21+
return sequence.Min(selector);
22+
}
23+
24+
/// <summary>
25+
/// Returns the element in a sequence that has the maximum value of a specified property.
26+
/// </summary>
27+
/// <typeparam name="T">The type of the elements in the sequence.</typeparam>
28+
/// <typeparam name="TKey">The type of the property to compare.</typeparam>
29+
/// <param name="source">The sequence to find the maximum value of.</param>
30+
/// <param name="selector">The function to select the value to compare.</param>
31+
/// <returns>The element in the sequence that has the maximum value of the specified property.</returns>
32+
public static T ArgMax<T, TKey>(this IEnumerable<T> source, Func<T, TKey> selector)
33+
where TKey : IComparable
34+
{
35+
if (source == null || !source.Any())
36+
throw new ArgumentException("Source is empty or null");
37+
var max = source.First();
38+
var maxValue = selector(max);
39+
foreach (var item in source)
40+
{
41+
var value = selector(item);
42+
if (value.CompareTo(maxValue) > 0)
43+
{
44+
max = item;
45+
maxValue = value;
46+
}
47+
}
48+
return max;
49+
}
50+
}
51+
}

0 commit comments

Comments
 (0)