Changeset 17891 for branches/3073_IA_constraint_splitting_reintegration/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/IntervalArithCompiledExpressionBoundsEstimator.cs

Timestamp:

03/12/21 16:41:42 (3 years ago)

Author:

gkronber

Message:

#3073 refactoring to prepare for trunk reintegration

Location:

branches/3073_IA_constraint_splitting_reintegration

Files:

• . (modified) (1 prop)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/IntervalArithCompiledExpressionBoundsEstimator.cs (moved) (moved from branches/3073_IA_constraint_splitting_reintegration/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/IACompiledExpressionBoundsEstimator.cs) (8 diffs)

branches/3073_IA_constraint_splitting_reintegration

@@ -1 +1 @@
 bin
+TestResults

@@ -1 +1 @@
 bin
+TestResults

branches/3073_IA_constraint_splitting_reintegration/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/IntervalArithCompiledExpressionBoundsEstimator.cs

@@ -1 +1 @@
 using HEAL.Attic;
-
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -6 +5 @@
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Parameters;
-
 using System;
 using System.Collections.Generic;
@@ -12 +10 @@
 using System.Linq.Expressions;
 
-namespace HeuristicLab.Problems.DataAnalysis.Symbolic
-{
+namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
   [StorableType("60015D64-5D8B-408A-90A1-E4111BC114D4")]
-  [Item("IA Compiled Expression Bounds Estimator", "Compile a symbolic model into a lambda and use it to evaluate model bounds.")]
-  public class IACompiledExpressionBoundsEstimator : ParameterizedNamedItem, IBoundsEstimator
-  {
+  [Item("Interval Arithmetic Compiled Expression Bounds Estimator", "Compile a symbolic model into a lambda and use it to evaluate model bounds.")]
+  public class IntervalArithCompiledExpressionBoundsEstimator : ParameterizedNamedItem, IBoundsEstimator {
     // interval method names
     private static readonly Dictionary<byte, string> methodName = new Dictionary<byte, string>() {
@@ -39 +35 @@
 
     private const string EvaluatedSolutionsParameterName = "EvaluatedSolutions";
-    private const string UseIntervalSplittingParameterName = "Use Interval splitting";
-    private const string MaxSplitParameterName = "MaxSplit";
-    private const string MinWidthParameterName = "MinWidth";
-
     public IFixedValueParameter<IntValue> EvaluatedSolutionsParameter {
       get => (IFixedValueParameter<IntValue>)Parameters[EvaluatedSolutionsParameterName];
     }
-
-    public IFixedValueParameter<BoolValue> UseIntervalSplittingParameter {
-      get => (IFixedValueParameter<BoolValue>)Parameters[UseIntervalSplittingParameterName];
-    }
-
-    public IFixedValueParameter<IntValue> MaxSplitParameter {
-      get => (IFixedValueParameter<IntValue>)Parameters[MaxSplitParameterName];
-    }
-
-    public IFixedValueParameter<DoubleValue> MinWidthParameter {
-      get => (IFixedValueParameter<DoubleValue>)Parameters[MinWidthParameterName];
-    }
-
-    public int MaxSplit {
-      get => MaxSplitParameter.Value.Value;
-      set => MaxSplitParameter.Value.Value = value;
-    }
-
-    public double MinWidth {
-      get => MinWidthParameter.Value.Value;
-      set => MinWidthParameter.Value.Value = value;
-    }
-
     public int EvaluatedSolutions {
       get => EvaluatedSolutionsParameter.Value.Value;
@@ -74 +43 @@
     }
 
-    public bool UseIntervalSplitting {
-      get => UseIntervalSplittingParameter.Value.Value;
-      set => UseIntervalSplittingParameter.Value.Value = value;
-    }
-
     private readonly object syncRoot = new object();
 
-    public IACompiledExpressionBoundsEstimator() : base("IA Bounds Estimator",
+    public IntervalArithCompiledExpressionBoundsEstimator() : base("Interval Arith Bounds Estimator",
       "Estimates the bounds of the model with interval arithmetic, by first compiling the model into a lambda.") {
       Parameters.Add(new FixedValueParameter<IntValue>(EvaluatedSolutionsParameterName,
         "A counter for the total number of solutions the estimator has evaluated.", new IntValue(0)));
-      Parameters.Add(new FixedValueParameter<BoolValue>(UseIntervalSplittingParameterName,
-        "Defines whether interval splitting is activated or not.", new BoolValue(false)));
-      Parameters.Add(new FixedValueParameter<IntValue>(MaxSplitParameterName,
-        "Defines the number of iterations of splitting.", new IntValue(200)));
-      Parameters.Add(new FixedValueParameter<DoubleValue>(MinWidthParameterName,
-        "Width of interval, after the splitting should stop.", new DoubleValue(0.0)));
     }
 
     [StorableConstructor]
-    private IACompiledExpressionBoundsEstimator(StorableConstructorFlag _) : base(_) { }
-
-    private IACompiledExpressionBoundsEstimator(IACompiledExpressionBoundsEstimator original, Cloner cloner) : base(original, cloner) { }
+    private IntervalArithCompiledExpressionBoundsEstimator(StorableConstructorFlag _) : base(_) { }
+
+    private IntervalArithCompiledExpressionBoundsEstimator(IntervalArithCompiledExpressionBoundsEstimator original, Cloner cloner) : base(original, cloner) { }
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new IACompiledExpressionBoundsEstimator(this, cloner);
-    }
-
-
-
-    public double CheckConstraint(ISymbolicExpressionTree tree, IntervalCollection variableRanges, ShapeConstraint constraint) {
-      if (!UseIntervalSplitting) {
-        var modelBound = GetModelBound(tree, variableRanges);
-        if (constraint.Interval.Contains(modelBound)) return 0.0;
-        return Math.Abs(modelBound.LowerBound - constraint.Interval.LowerBound) +
-               Math.Abs(modelBound.UpperBound - constraint.Interval.UpperBound);
-      }
-
-      if (double.IsNegativeInfinity(constraint.Interval.LowerBound) &&
-          double.IsPositiveInfinity(constraint.Interval.UpperBound)) {
-        return 0.0;
-      }
-
-      //ContainsVariableMultipleTimes(tree, out var variables);
-
-      lock (syncRoot) { EvaluatedSolutions++; }
-
-      double upperBound;
-      if (double.IsNegativeInfinity(constraint.Interval.LowerBound)) {
-        upperBound = EstimateUpperBound(tree, variableRanges.GetReadonlyDictionary(), MaxSplit, MinWidth);
-
-        return upperBound <= constraint.Interval.UpperBound
-          ? 0.0
-          : Math.Abs(upperBound - constraint.Interval.UpperBound);
-      }
-
-      double lowerBound;
-      if (double.IsPositiveInfinity(constraint.Interval.UpperBound)) {
-        lowerBound = EstimateLowerBound(tree, variableRanges.GetReadonlyDictionary(), MaxSplit, MinWidth);
-
-        return lowerBound <= constraint.Interval.LowerBound
-          ? 0.0
-          : Math.Abs(lowerBound - constraint.Interval.LowerBound);
-      }
-
-      var ranges = variableRanges.GetReadonlyDictionary();
-      lowerBound = EstimateLowerBound(tree, ranges, MaxSplit, MinWidth);
-      upperBound = EstimateUpperBound(tree, ranges, MaxSplit, MinWidth);
-
-      var res = 0.0;
-
-      res += upperBound <= constraint.Interval.UpperBound ? 0.0 : Math.Abs(upperBound - constraint.Interval.UpperBound);
-      res += lowerBound <= constraint.Interval.LowerBound ? 0.0 : Math.Abs(lowerBound - constraint.Interval.LowerBound);
-
-      return res;
+      return new IntervalArithCompiledExpressionBoundsEstimator(this, cloner);
+    }
+
+    public double GetConstraintViolation(ISymbolicExpressionTree tree, IntervalCollection variableRanges, ShapeConstraint constraint) {
+      var modelBound = GetModelBound(tree, variableRanges);
+      if (constraint.Interval.Contains(modelBound)) return 0.0;
+      return Math.Abs(modelBound.LowerBound - constraint.Interval.LowerBound) +
+             Math.Abs(modelBound.UpperBound - constraint.Interval.UpperBound);
     }
 
@@ -157 +73 @@
     public Interval GetModelBound(ISymbolicExpressionTree tree, IntervalCollection variableRanges) {
       lock (syncRoot) { EvaluatedSolutions++; }
-      var resultInterval = UseIntervalSplitting
-        ? EstimateBounds(tree, variableRanges.GetReadonlyDictionary(), MaxSplit, MinWidth)
-        : EstimateBounds(tree, variableRanges.GetReadonlyDictionary());
+      var resultInterval = EstimateBounds(tree, variableRanges.GetReadonlyDictionary());
 
       if (resultInterval.IsInfiniteOrUndefined || resultInterval.LowerBound <= resultInterval.UpperBound)
@@ -298 +212 @@
         }
       }
-      Array.Resize<Interval>(ref inputIntervals, count);
+      Array.Resize(ref inputIntervals, count);
       return variableIndices;
     }
@@ -309 +223 @@
     }
 
-    public static Interval EstimateBounds(ISymbolicExpressionTree tree, IReadOnlyDictionary<string, Interval> variableRanges, int n = 0, double w = 1e-5) {
+    public static Interval EstimateBounds(ISymbolicExpressionTree tree, IReadOnlyDictionary<string, Interval> variableRanges) {
       var variableIndices = GetVariableIndices(tree, variableRanges, out Interval[] x);
       var f = Compile(tree, variableRanges, variableIndices);
-      if (n == 0) return f(x);
-      var inf = EstimateBound(x, f, true, n, w);
-      var sup = EstimateBound(x, f, false, n, w);
-      return inf < sup ? new Interval(inf, sup) : new Interval(sup, inf);
-    }
-    public  double EstimateLowerBound(ISymbolicExpressionTree tree, IReadOnlyDictionary<string, Interval> variableRanges, int n = 1000, double w = 1e-5) {
-      var variableIndices = GetVariableIndices(tree, variableRanges, out Interval[] x);
-      var f = Compile(tree, variableRanges, variableIndices);
-      var inf = EstimateBound(x, f, true, n, w);
-      return inf;
-    }
-
-    public double EstimateUpperBound(ISymbolicExpressionTree tree, IReadOnlyDictionary<string, Interval> variableRanges, int n = 1000, double w = 1e-5) {
-      var variableIndices = GetVariableIndices(tree, variableRanges, out Interval[] x);
-      var f = Compile(tree, variableRanges, variableIndices);
-      var sup = EstimateBound(x, f, false, n, w);
-      return sup;
-    }
-
-    static double EstimateBound(Interval[] x, Func<Interval[], Interval> f, bool m = false, int n = 1000, double w = 1e-4) {
-      double getBound(Interval iv) => m ? iv.LowerBound : -iv.UpperBound;
-      double getVolume(Interval[] box) => box.Aggregate(1.0, (acc, iv) => acc * iv.Width);
-
-      var splits = Enumerable.Range(0, x.Length).Select(_ => new List<Interval>()).ToArray();
-      var newbox = new Interval[x.Length];
-
-      int compare(Tuple<double, double, Interval[]> a, Tuple<double, double, Interval[]> b) {
-        var res = a.Item1.CompareTo(b.Item1);
-        if (res == 0) {
-          res = b.Item2.CompareTo(a.Item2);
-        }
-        return res;
-      }
-
-      var q = new SortedSet<Tuple<double, double, Interval[]>>(Comparer<Tuple<double, double, Interval[]>>.Create(compare)) {
-        Tuple.Create(getBound(f(x)), getVolume(x), x)
-      };
-
-
-      var bestBound = double.MaxValue;
-
-      // examine all the ordered pairs in the cartesian product
-      void next_pair(int i) {
-        if (i == splits.Length) {
-          var tmp = newbox.ToArray(); // make a copy to put in the queue
-          q.Add(Tuple.Create(getBound(f(tmp)), getVolume(tmp), tmp));
-          return;
-        }
-
-        foreach (var iv in splits[i]) {
-          newbox[i] = iv;
-          next_pair(i + 1);
-        }
-      }
-
-      while (q.Count > 0 && n-- > 0) {
-        var currentBound = q.Min; q.Remove(currentBound);
-        var bound = currentBound.Item1;
-        var box = currentBound.Item3;
-
-        if (!box.Any(b => b.Width > w)) {
-          bestBound = Math.Min(bestBound, bound);
-          continue;
-        }
-
-        // do the splits
-        for (int i = 0; i < box.Length; ++i) {
-          splits[i].Clear();
-          var iv = box[i];
-          if (iv.Width > w) {
-            var t = iv.Split();
-            splits[i].Add(t.Item1);
-            splits[i].Add(t.Item2);
-          } else {
-            splits[i].Add(iv);
-          }
-        }
-        next_pair(0);
-      }
-      if (q.Count > 0) {
-        bestBound = Math.Min(bestBound, q.First().Item1);
-      }
-      return m ? bestBound : -bestBound;
+      return f(x);
     }
     #endregion

@@ -1 +1 @@
 bin
+TestResults