To present geographical distribution as a constraint in linear problems?

Question

I am studying the Solver Foundation right now. I actually connect lpsolve for my project, but I think that my problem is a common problem of how to best represent my limitations.

I, I think, have a pretty typical problem with a backpack or packing. I have a collection of places and everyone has a "rating". I want to choose the minimum number of places to achieve the target score.

(In practice, this is a little more complicated than this - each location has several different properties, and I will often focus on several properties).

So far so good. However, I have an additional limitation - I want to maximize the geographic dispersion of my chosen locations. How can I imagine this limitation?

Here is a basic example of what I have 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; } } 

It will just pick the first three locations that give me my goal of 60, but these three locations are grouped very close together. I would prefer that he choose one of the first three (ID 0 - 2) and the last two (ID 3 and 4), which are further distributed.

Can anyone suggest some recommendations here? Thank you very much in advance.

Answer 1

The problem is a little more complicated than I thought. As I mentioned above, you need to calculate the variance. However, calculating the standard deviation of geographic points is not easy. Here is a description of MathWorks .

It seems that if your points do not cover a large geographic area, you can approximate the variance by calculating a standard deviation of 2 dimensions. Otherwise, you will have to write a function such as in MatLab, stdm .

Update

It took me a while, but I decided that I had solved the problem. I have to say that the entire Solver suite of programs is complex. I checked the following code with the example you provided, and it correctly selects 0, 3, and 4. The code changes below.

The next section computes the distance from location i to location j, where i and j are elements of the provided target set. Data is tied to Parameter , so it can be requested later in the target.

 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 final goal actually consists of two parts. The first goal is to maximize the score, and the second goal is to maximize the variance of locations. In this case, I scattered the variance as the total distance between the selected locations. I received an exception: “The model has more than one goal” when I added 2 goals, so I had to combine them into one 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() calculates the distance between two coordinates using System.Device.Location.GeoCoordinate ; it turns out there is a C # implementation. I changed the latitude and longitude types to double to avoid type casting. This code will need to be updated before use in 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); }