4

我现在正在学习 Solver Foundation。我实际上正在为我的项目插入 lpsolve，但我认为我的问题是如何最好地表示我的约束的一般问题。

我认为，我有一个相当典型的背包或包装问题。我有一组位置，每个位置都有一个“分数”。我想选择满足目标“分数”的最少位置数。

（实际上，它比这要复杂一些——每个位置都有许多不同的属性，我经常会针对多个属性进行定位）。

到目前为止，一切都很好。但是，我有一个额外的限制 - 我想最大化我选择的位置的地理分布。我如何表示该约束？

这是我现在拥有的基本示例：

    static void Main(string[] args)
    {
        var locations = new List<LocationWithScore>()
        {
            new LocationWithScore() { LocationID = 0, Latitude = 43.644274M, Longitude = -79.478703M, Score = 20 },
            new LocationWithScore() { LocationID = 1, Latitude = 43.644709M, Longitude = -79.476814M, Score = 20 },
            new LocationWithScore() { LocationID = 2, Latitude = 43.643063M, Longitude = -79.477458M, Score = 20 },
            new LocationWithScore() { LocationID = 3, Latitude = 43.650516M, Longitude = -79.469562M, Score = 20 },
            new LocationWithScore() { LocationID = 4, Latitude = 43.642659M, Longitude = -79.463124M, Score = 20 }
        };

        SolverContext sContext = SolverContext.GetContext();
        sContext.ClearModel();

        Model model = sContext.CreateModel();
        model.Name = "LocationWithScore";
        Set items = new Set(Domain.Any, "candidates");
        Decision take = new Decision(Domain.Boolean, "candidate", items);
        model.AddDecision(take);

        Parameter scoreParam = new Parameter(Domain.RealNonnegative, "score", items);
        scoreParam.SetBinding(locations, "Score", "LocationID");
        model.AddParameters(scoreParam);

        model.AddConstraint("scoreConstraint", Model.Sum(Model.ForEach(items, item => scoreParam[item] * take[item])) >= 60);

        model.AddGoal("locationGoal", GoalKind.Minimize, Model.Sum(Model.ForEach(items, item => take[item])));

        var solution = sContext.Solve(new LpSolveDirective());
        var report = solution.GetReport();
        Console.WriteLine(report.ToString());

        Console.WriteLine("Done");
        Console.ReadKey();
    }

    internal class LocationWithScore
    {
        public int LocationID { get; set; }
        public decimal Latitude { get; set; }
        public decimal Longitude { get; set; }
        public double Score { get; set; }
    }

这将只选择前三个位置，这给了我 60 的目标，但是这三个位置非常接近地聚集在一起。我更希望它选择前三个（ID 0 - 2）和后两个（ID 3 和 4）中的一个，它们分布得更远。

有人可以在这里提供一些指导吗？提前谢谢了。

4

1 回答 1

3

这个问题比我最初想象的要复杂一些。就像我上面提到的，你需要计算离散度。然而，地理点的标准差的计算并不简单。这是MathWorks的解释。

似乎如果您的点不跨越大的地理区域，您可以通过计算二维上的标准偏差来近似分散。否则，您将不得不编写一个类似于 MatLab 中提供的函数stdm。

更新

我花了一段时间，但我想我已经解决了这个问题。我必须说整套 Solver 程序很复杂。我在您提供的示例上测试了以下代码，它正确选择了 0、3 和 4。代码更改如下。

以下部分计算从位置i到位置j的距离，其中i和j是提供的目标集的元素。数据绑定到 a Parameter，因此可以稍后在目标中查询。

var dist = from l1 in locations 
          from l2 in locations 
          select new {ID1 = l1.LocationID, ID2 = l2.LocationID, dist = GetDistance(l1.Latitude, l1.Longitude, l2.Latitude, l2.Longitude)};

Parameter distance = new Parameter(Domain.RealNonnegative, "Location", items, items);
distance.SetBinding(dist, "dist", "ID1", "ID2");
model.AddParameter(distance);

最终目标实际上由两部分组成。第一个目标是最大化得分，第二个目标是最大化位置的分散。在这种情况下，我将分散抽象为所选位置之间的总距离。当我添加 2 个目标时，我遇到了一个例外，“模型有多个目标”，因此我必须将它们组合成一个目标，如下所示。

double maxDist = (from distances in dist select distances.dist).Max();
Term goal1 = Model.Sum(Model.ForEach(items, item => take[item] * scoreParam[item]));
Term goal2 = Model.Sum(Model.ForEach(items, i => Model.ForEach(items, j => take[i] * take[j] * distance[i, j])));
model.AddGoal("Dispersion", GoalKind.Maximize, Model.Sum(Model.Sum(goal1, maxDist), goal2));

GetDistance()System.Device.Location.GeoCoordinate使用;计算 2 个坐标之间的距离 原来有一个 C# 实现。我更改了纬度和经度类型double以避免类型转换。此代码在用于大型案例之前需要更新。

public static double GetDistance(double lat1, double long1, double lat2, double long2)
{
    GeoCoordinate geo1 = new GeoCoordinate(lat1, long1);
    GeoCoordinate geo2 = new GeoCoordinate(lat2, long2);
    return geo1.GetDistanceTo(geo2);
}
于 2012-07-03T16:42:04.523 回答