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

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.

Похоже, что если ваши точки не охватывают большую географическую область, вы можете приблизить дисперсию, рассчитав стандартное отклонение по двум измерениям. В противном случае вам нужно будет написать функцию, подобную той, что предусмотрена в MatLab, stdm.

Обновить

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

В следующем разделе вычисляется расстояние от местоположения i до местоположения j, где i и 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 цели, поэтому мне пришлось объединить их в одну цель, как вы можете видеть ниже.

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);
}