Represent geographical distribution as constraint in linear prob?

Question

I'm learning Solver Foundation right now. I'm actually plugging in lpsolve for my project, but I think my problem is a generic issue of how to best represent my constraints.

I have, what I think is, a fairly typical knapsack or packing problem. I have a collection of locations, and each has a 'score'. I want to select the minimum number of locations to meet a target 'score'.

(In practice, it's a bit more complex than that - each location has a number of different properties and I will often target across multiple properties).

So far so good. However, I have an additional constraint - I want to maximise the geographic dispersion of the locations that I choose. How can I represent that constraint?

Here is a basic example of what I have right now:

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

This will simply select the first three locations, which gives me my goal of 60 but these three locations are clustered very close together. What I would prefer is for it to select one of the first three (ID 0 - 2) and the last two (ID 3 and 4), which are spread further out.

Can someone offer some guidance here? Many thanks in advance.

Answer 1

The problem is a little more complicated than I first thought. Like I mentioned above, you need to calculate dispersion. However, calculation of standard deviation of geographical points is not simple. Here is a MathWorks explanation.

It seems that if your points don't span a large geographic area, you can approximate the dispersion by calculating the standard deviation over 2 dimensions. Otherwise, you'll have to write a function like the one provided in MatLab, stdm.

Update

It took me a while but I think I've solved the problem. I must say the whole set of Solver programs are complicated. I tested the following code on the example you provided and it correctly chooses 0, 3, and 4. The code changes are below.

The following section computes the distance from location i to location j, where i and j are elements of the provided target set. The data is bound to a Parameter so it can be queried later in the goal.

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

The end goal is actually made-up of 2 parts. First goal is to maximize score and the second goal is to maximize the dispersion of the locations. In this case I've abstracted the dispersion to be the total distance between the selected locations. I was getting an exception, "Model has more than one goal", when I added 2 goals so I had to combine them into a single goal as you can see below.

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() computes the distance between 2 coordinates using System.Device.Location.GeoCoordinate; turns out there is a C# implementation. I changed the latitude and longitude types to double to avoid type casting. This code will need an update before use on large cases.

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