Представить географическое распределение в качестве ограничения в линейной задаче?

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.

Update

Это мне потребовалось некоторое время, но я думаю, что я решил эту проблему. Я должен сказать, что весь набор программ Solver сложный. Я проверил следующий код на примере, который вы указали, и он правильно выбирает 0, 3 и 4. Ниже приведены изменения кода.

В следующем разделе вычисляет расстояние от местоположения я к местоположению J, где я и J являются элементами предоставленного целевого набора. Данные привязаны к 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() вычисляет расстояние между 2 координат с использованием 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); 
}