c# - 将地理分布表示为线性概率中的约束？

Question

我现在正在学习 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) 之一，它们分布得更远。

有人可以在这里提供一些指导吗？非常感谢。

Answer 1

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

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

更新

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

以下部分计算从位置 i 到位置 j 的距离，其中 i 和 j 是元素提供的目标集。数据绑定(bind)到 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 个目标时，我遇到了一个异常(exception)，“模型有多个目标”，因此我不得不将它们组合成一个目标，如下所示。

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 计算两个坐标之间的距离；原来有一个 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);
}