Changeset 15758


Ignore:
Timestamp:
02/12/18 16:53:23 (18 months ago)
Author:
abeham
Message:

#1614: Added LocalSolver model based on lists

Location:
branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3
Files:
1 edited
1 copied

Legend:

Unmodified
Added
Removed
  • branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms-3.3.csproj

    r15719 r15758  
    130130    <Compile Include="LocalSearch\IteratedLS.cs" />
    131131    <Compile Include="LocalSearch\MultistartLS.cs" />
     132    <Compile Include="LocalSolverNet\GQAPListSolver.cs" />
    132133    <Compile Include="LocalSolverNet\GQAPIntegerSolver.cs" />
    133134    <Compile Include="LocalSolverNet\LocalSolverContext.cs" />
  • branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSolverNet/GQAPListSolver.cs

    r15717 r15758  
    3131
    3232namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LocalSolverNet {
    33   [Item("LocalSolver Binary (GQAP)", "LocalSolver algorithm solving the GQAP using 0-1 decision variables")]
     33  [Item("LocalSolver List (GQAP)", "LocalSolver algorithm solving the GQAP using list decision variables")]
    3434  [StorableClass]
    3535  [Creatable(CreatableAttribute.Categories.Algorithms)]
    36   public sealed class GQAPBinarySolver : ContextAlgorithm<LocalSolverContext, IntegerVectorEncoding> {
     36  public sealed class GQAPListSolver : ContextAlgorithm<LocalSolverContext, IntegerVectorEncoding> {
    3737    public override bool SupportsPause {
    3838      get { return false; }
     
    4949
    5050    // LS Program variables
    51     private LSExpression[][] x;
     51    private LSExpression[] x;
    5252    private LSExpression[] equipmentsOnLocations;
    5353    private LSExpression obj;
     
    5656
    5757    [StorableConstructor]
    58     private GQAPBinarySolver(bool deserializing) : base(deserializing) { }
    59     private GQAPBinarySolver(GQAPBinarySolver original, Cloner cloner)
     58    private GQAPListSolver(bool deserializing) : base(deserializing) { }
     59    private GQAPListSolver(GQAPListSolver original, Cloner cloner)
    6060    : base(original, cloner) {
    6161    }
    62     public GQAPBinarySolver() {
     62    public GQAPListSolver() {
    6363      Problem = new GQAP();
    6464      MaximumEvaluationsParameter.Hidden = true;
     
    6767
    6868    public override IDeepCloneable Clone(Cloner cloner) {
    69       return new GQAPBinarySolver(this, cloner);
     69      return new GQAPListSolver(this, cloner);
    7070    }
    7171
     
    107107      var locations = Problem.ProblemInstance.Capacities.Length;
    108108      var best = new int[Problem.ProblemInstance.Demands.Length];
    109       for (var i = 0; i < best.Length; i++) {
    110         for (var j = 0; j < locations; j++) {
    111           if (x[i][j].GetIntValue() == 1) {
    112             best[i] = j;
    113             break;
    114           }
     109      for (var j = 0; j < locations; j++) {
     110        var xcol = x[j].GetCollectionValue();
     111        for (var i = 0; i < xcol.Count(); i++) {
     112          var equip = xcol.Get(i);
     113          best[equip] = j;
    115114        }
    116115      }
     
    140139
    141140      // Declares the optimization model
    142       LSModel model = localSolver.GetModel();
     141      var model = localSolver.GetModel();
    143142
    144143      var data = Problem.ProblemInstance;
    145144
     145      x = new LSExpression[data.Capacities.Length];
    146146      // x[f,l] = 1 if equipments f is on location l, 0 otherwise
    147       x = new LSExpression[data.Demands.Length][];
    148       for (int f = 0; f < data.Demands.Length; f++) {
    149         x[f] = new LSExpression[data.Capacities.Length];
    150         for (int l = 0; l < data.Capacities.Length; l++) {
    151           x[f][l] = model.Bool();
     147      for (int r = 0; r < data.Capacities.Length; r++) {
     148        x[r] = model.List(data.Demands.Length);
     149      }
     150
     151      // All equipments are installed in exactly 1 location
     152      model.Constraint(model.Partition(x));
     153
     154      var demandsArray = model.Array(data.Demands);
     155
     156      // Create distances as an array to be accessed by an at operator
     157      var weightsJagged = new double[data.Demands.Length][];
     158      for (var i = 0; i < data.Demands.Length; i++) {
     159        weightsJagged[i] = new double[data.Demands.Length];
     160        for (var j = 0; j < data.Demands.Length; j++) {
     161          weightsJagged[i][j] = data.Weights[i, j];
    152162        }
    153163      }
    154 
    155       // All equipments are installed in exactly 1 location
    156       for (int f = 0; f < data.Demands.Length; f++) {
    157         LSExpression nbLocationsAssigned = model.Sum();
    158         for (int l = 0; l < data.Capacities.Length; l++) {
    159           nbLocationsAssigned.AddOperand(x[f][l]);
    160         }
    161         model.Constraint(nbLocationsAssigned == 1);
    162       }
    163 
    164       // All locations contain not more equipments than there is capacity for
    165       for (int l = 0; l < data.Capacities.Length; l++) {
    166         LSExpression assignedDemand = model.Sum();
    167         for (int f = 0; f < data.Demands.Length; f++) {
    168           assignedDemand.AddOperand(x[f][l] * data.Demands[f]);
    169         }
    170         model.Constraint(assignedDemand <= data.Capacities[l]);
    171       }
    172 
    173       // Index of the assigned location of equipment f
    174       equipmentsOnLocations = new LSExpression[data.Demands.Length];
    175       for (int f = 0; f < data.Demands.Length; f++) {
    176         equipmentsOnLocations[f] = model.Sum();
    177         for (int l = 0; l < data.Capacities.Length; l++) {
    178           equipmentsOnLocations[f].AddOperand(l * x[f][l]);
    179         }
    180       }
    181 
    182       // Create distances as an array to be accessed by an at operator
    183164      var distancesJagged = new double[data.Capacities.Length][];
    184165      for (var i = 0; i < data.Capacities.Length; i++) {
     
    193174          installJagged[i][j] = data.InstallationCosts[i, j];
    194175      }
    195       LSExpression distancesArray = model.Array(distancesJagged);
    196       LSExpression installCostsArray = model.Array(installJagged);
    197 
    198       // Minimize the sum of product distance*flow
     176      var weightsArray = model.Array(weightsJagged);
     177      var distancesArray = model.Array(distancesJagged);
     178      var installCostsArray = model.Array(installJagged);
     179
    199180      obj = model.Sum();
    200       for (int f1 = 0; f1 < data.Demands.Length; f1++) {
    201         for (int f2 = 0; f2 < data.Demands.Length; f2++) {
    202           obj.AddOperand(data.TransportationCosts * data.Weights[f1, f2] * distancesArray[equipmentsOnLocations[f1], equipmentsOnLocations[f2]]);
     181      // All locations contain not more equipments than there is capacity for
     182      for (int l = 0; l < data.Capacities.Length; l++) {
     183        var c = model.Count(x[l]);
     184        var demandSelector = model.Function(i => demandsArray[x[l][i]]);
     185        var assignedDemand = model.Sum(model.Range(0, c), demandSelector);
     186        model.Constraint(assignedDemand <= data.Capacities[l]);
     187
     188        var installCostSelector = model.Function(i => installCostsArray[x[l][i], l]);
     189        var installCosts = model.Sum(model.Range(0, c), installCostSelector);
     190        obj.AddOperand(installCosts);
     191       
     192        // Flow to other equipments
     193        for (int k = 0; k < data.Capacities.Length; k++) {
     194          var kc = model.Count(x[k]);
     195          var flowCostSelector = model.Function(j => model.Sum(model.Range(0, c), model.Function(i => weightsArray[x[l][i], x[k][j]] * distancesArray[l, k] * data.TransportationCosts)));
     196          obj.AddOperand(model.Sum(model.Range(0, kc), flowCostSelector));
    203197        }
    204         obj.AddOperand(installCostsArray[f1, equipmentsOnLocations[f1]]);
    205       }
    206 
    207       model.Minimize(obj);
     198      }
     199
     200      model.Minimize(this.obj);
    208201
    209202      try {
     
    218211        localSolver.Solve();
    219212
    220         var curObj = obj.GetDoubleValue();
     213        var curObj = this.obj.GetDoubleValue();
    221214        if (curObj < prevObj)
    222215          UpdateSolution(curObj);
Note: See TracChangeset for help on using the changeset viewer.