Microsoft Solver Foundation位置分散目标

Question

我正在尝试使用Microsoft Solver Foundation，因此我能够从集合中选择最分散的位置。我在模型中添加了两个目标，一个目标确保选择了3个位置，另一个确保它们是最分散的位置。

。

static void Main(string[] args)
    {
        Location candidate1 = new Location(0, 43.432, -79.432);
        Location candidate2 = new Location(1, 43.0, -79.0);
        Location candidate3 = new Location(2, 23.0, 29.0);
        Location candidate4 = new Location(3, 43.0, -79.0);
        Location candidate5 = new Location(4, 43.0, -79.0);
        Location[] candidates = {candidate1, candidate2, candidate3, candidate4, candidate5};
        SolverContext solver = new SolverContext();
        Model model = solver.CreateModel();
        model.Name = "LocationModel";
        Set items = new Set(Domain.Any, "candidates");
        Decision take = new Decision(Domain.Boolean, "candidate", items);
        model.AddDecision(take);
        Parameter locations = new Parameter(Domain.RealNonnegative, "locations", items);
        locations.SetBinding(candidates, "ID", "ID");
        model.AddParameter(locations);

        var dist = from l1 in candidates from l2 in candidates select new { ID1 = l1.ID, ID2 = l2.ID, dist = Geography.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);            
        Term goal = Model.Sum(Model.ForEach(items, i => Model.ForEach(items, j => take[i]*take[j]* distance[i, j])));
        model.AddConstraint("LocationsQuantityMax", Model.Sum(Model.ForEach(items, item => take[item])) == 3);
        model.AddGoal("Dispersion", GoalKind.Maximize, goal); 
        Directive directive = new HybridLocalSearchDirective();            
        Solution solution = solver.Solve(directive);
        List<Location> locations1 = new List<Location>();
        if (solution.Decisions.Any())
        {
            var selections = solution.Decisions.First().GetValues()
                .Where(d => (bool) d[0])
                .Select(d => Convert.ToInt32(d[1]));
            locations1.AddRange(
                from c in candidates
                join s in selections on c.ID equals s
                select c);
        }
        foreach (Location location in locations1)
        {
            Console.WriteLine("ID: {0}, Latitude: {1}, Longitude: {2}", location.ID, location.Latitude, location.Longitude);
        } 

此外，我的位置课程如下：

class Location
{
    public int ID { get; private set; }
    public double Latitude { get; private set; }
    public double Longitude { get; private set; }
    public Location(int LocationID, double latitude, double longitude)
    {
        this.ID = LocationID;
        this.Latitude = latitude;
        this.Longitude = longitude;
    }
} 

我的距离计算是：

    public static double ToRad(this double num)
    {
        return num * Math.PI / 180;
    }
    public static double GetDistance(double lat1, double lon1, double lat2, double lon2)
    {
        const int r = 6371; // Radius of earth in KM
        // Convert to Radians
        lat1 = lat1.ToRad();
        lon1 = lon1.ToRad();
        lat2 = lat2.ToRad();
        lon2 = lon2.ToRad();
        // Spherical Law of Cosines
        var resultCos =
            Math.Acos(
                Math.Sin(lat1) * Math.Sin(lat2) +
                Math.Cos(lat1) * Math.Cos(lat2) * Math.Cos(lon2 - lon1)
                ) * r;
        return resultCos;
    } 

现在我的代码有两个问题，我不知道它们起源于哪里，

首先，

我的代码是为5个位置的大多数排列工作，其中三个是相同的经度纬度（即在此；示例cantidate2，cantidate4 and cantidate5），但对于候选人的某些排列，它不会返回最多的分散3（即，对于同一问题实例，只需更改候选人声明的顺序）即可。我无法理解为什么。

其次，

如果您评论至少3个位置的约束，而不是像预期的那样选择所有位置，则选择无。

我的目标在大多数情况下都起作用的事实似乎表明它是正确的，有人知道为什么有时会摇摆吗？

这不是作业，非常感谢任何答复的人。

Answer 1

我相信您的问题是您要指定HybridLocalSearchDirective。我从您发布的代码中删除了该内容，并获得了最佳答案：

ID: 0, Latitude: 43.432, Longitude: -79.432
ID: 1, Latitude: 43, Longitude: -79
ID: 2, Latitude: 23, Longitude: 29

重新排列术语甚至添加新位置仍然会导致最佳解决方案。

此外，我删除了约束，您的代码选择了所有五个Location对象作为解决方案。

我希望我能阐明为什么这有效，但是当谈到无国界医生时，我只是一个周末的战士。这是我可以找到有关HybridLocalSearchDirective及其如何达到解决方案的最多信息。重要的是，注意到的第一个限制是：

它不能保证最佳结果。

这可能是您第一个问题的答案（为什么它不会返回最大分散的位置）。

关于您的第二个问题（为什么删除约束不会导致更多选择的位置），我不能确定。您的问题规范可能是该指令的退化案例，尽管我不知道为什么。

不是最好的答案，但我希望它有帮助！