將線性概率中的地理分佈表示爲約束條件？

Question

我正在學習Solver基金會。實際上，我爲我的項目插入了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.代碼更改如下。

以下部分計算我到位置Ĵ，其中我和Ĵ是設定所提供的目標的元件從位置的距離。數據綁定到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部分組成。第一個目標是最大化分數，第二個目標是最大化分散的位置。在這種情況下，我已經將散佈抽象爲選定位置之間的總距離。我收到一個例外，「模型有一個以上的目標」，當我添加了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); 
}