4

私は今ソルバー財団を学んでいます。私は実際に私のプロジェクトに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; }
    }

これにより、最初の3つの場所が選択されるだけで、目標は60になりますが、これら3つの場所は非常に近くにクラスター化されています。私が好むのは、最初の3つ（ID 0〜2）と最後の2つ（ID 3と4）のいずれかを選択することです。

誰かがここでいくつかのガイダンスを提供できますか？よろしくお願いします。

4

1 に答える 1

3

問題は私が最初に思ったよりも少し複雑です。上で述べたように、分散を計算する必要があります。ただし、地理的ポイントの標準偏差の計算は簡単ではありません。これがMathWorksの説明です。

ポイントが広い地理的領域にまたがっていない場合は、2次元の標準偏差を計算することで分散を概算できるようです。それ以外の場合は、MatLabで提供されているような関数stdmを作成する必要があります。

アップデート

しばらく時間がかかりましたが、問題は解決したと思います。ソルバープログラムのセット全体が複雑であると言わなければなりません。提供した例で次のコードをテストしましたが、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つの部分で構成されています。最初の目標はスコアを最大化することであり、2番目の目標は場所の分散を最大化することです。この場合、分散を抽象化して、選択した場所間の合計距離にしました。2つの目標を追加したときに、「モデルには複数の目標があります」という例外が発生したため、以下に示すように、それらを1つの目標に結合する必要がありました。

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;を使用して2つの座標間の距離を計算します。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);
}
于 2012-07-03T16:42:04.523 に答える