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

Я изучаю 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), которые распространяются дальше.

Может кто-нибудь предложить здесь какие-нибудь рекомендации? Спасибо заранее.


c# linear-programming lpsolve ms-solver-foundation
person TheNextman    schedule 03.07.2012    source источник
comment
Я думал, что вы реализуете решение динамического программирования рюкзака с добавленным ограничением максимизации d, разброса единиц для предметов в вашем рюкзаке.   -  person user845279    schedule 03.07.2012
comment
Спасибо, да. Есть какие-нибудь подсказки о том, как лучше всего представить это как ограничение в Solver Foundation?   -  person TheNextman    schedule 03.07.2012
comment
:) Я знаю, о чем вы думаете, спасибо, капитан очевидный. В любом случае, вы пробовали добавить дополнительную цель по увеличению дисперсии? Вероятно, вам придется написать функцию, возможно, дисперсию, для расчета дисперсии по заданным параметрам долготы и широты.   -  person user845279    schedule 03.07.2012

Ответы (1)


arrow_upward
3
arrow_downward

Проблема немного сложнее, чем я думал вначале. Как я уже упоминал выше, вам нужно рассчитать дисперсию. Однако вычислить стандартное отклонение географических точек непросто. Вот объяснение 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);
}
person user845279    schedule 03.07.2012
comment
Спасибо. Как я уже сказал, я все еще изучаю Solver Foundation, поэтому мне нужно будет выяснить, как это сделать в контексте этой структуры. Я проведу расследование и сообщу. - person TheNextman; 03.07.2012