数理計画法ライブラリ「Microsoft Solver Foundation」の紹介

2011-12-26

■[C#][MSF]数理計画法ライブラリ「Microsoft Solver Foundation」の紹介

※これはC# Advent Calendar 2011の26日目の記事です。

初めまして。C#よりもF#の方が好きなArigataと申します。

今回、クリスマス終了後のおまけとして記事の題材とさせていただきますのは、
.NET環境向けの数理計画ライブラリ「Microsoft Solver Foundation」です。

以下、数理計画法の何たるかはある程度知っているものとして、簡単に紹介させていただきます。

Microsoft Solver Foundationとは?

Microsoftのdevlabが提供する、数理計画法のモデリングおよびソルバーのライブラリパッケージです。

ライブラリの論理構成は以下に示すように、数理計画問題のモデル定義、
および最適化のための各種ソルバーを呼び出すためのサービスから成ります。

(ライブラリ付属のマニュアルから引用)

線形計画、逐次二次計画、混合整数計画、非線形計画、制約充足問題などのソルバーを搭載しています。
C#などの言語で数理モデルを記述し、適切なソルバーを呼び出して計画問題を解くという形で使用します。

本ライブラリはF#やVB.NETなどの言語で扱えるだけでなく、Excelのアドオンとして各種機能を呼び出すこともできます。
また、独自のモデリング言語OMLで数理モデルを記述、および最適化することもできます。

現在、無償評価版のExpress EditionからMSDNサブスクライバ向けのStandard Edition以降のものが入手できます。
エディションの違いは、モデルサイズの上限と提供されるソルバーの種類などであり、基本的な使い方は変わりません。

詳しくはライブラリ付属のマニュアル・ドキュメントをご覧ください。色々と細かいところまで書いてあります。

例題

実際にC#でSolver Foundationをどのように使うか説明するため、
このパズルを制約充足問題に帰着して解きたいと思います。勝手に問題をお借りしてすみません。

C# Advent Calendar で覆面算
- http://yone64.wordpress.com/2011/12/22/c-advent-calendar-%e3%81%a7-%e8%a6%86%e9%9d%a2%e7%ae%97/

なお、今回は問題を以下のように設定します。

-C# * ADVENT + CALENDAR = 201112xx

ただし、各アルファベットは0から9までのそれぞれ異なる数字
また、xxは01から31までの数字

プロジェクト構成

なお、プロジェクトのプロパティからアプリケーションの対象フレームワークを
「.Net Framework 4」にしてください。Client Profileだとライブラリをロードできません。

ソースプログラム

using System;
using Microsoft.SolverFoundation.Services;

namespace ConsoleApplication5
{
    //覆面算を制約充足問題に帰着して解く
    class Program
    {
        static void Main(string[] args)
        {
            //モデルの生成
            SolverContext solverContext = SolverContext.GetContext();
            Model model = solverContext.CreateModel();

            //変数：各文字は0から9までの数字
            Domain numbers = Domain.IntegerRange(0, 9);
            Decision c = new Decision(numbers, "C");
            Decision s = new Decision(numbers, "S");
            Decision a = new Decision(numbers, "A");
            Decision d = new Decision(numbers, "D");
            Decision v = new Decision(numbers, "V");
            Decision e = new Decision(numbers, "E");
            Decision n = new Decision(numbers, "N");
            Decision t = new Decision(numbers, "T");
            Decision l = new Decision(numbers, "L");
            Decision r = new Decision(numbers, "R");
            model.AddDecisions(c, s, a, d, v, e, n, t, l, r);

            //制約条件：各文字はそれぞれ異なる数字
            model.AddConstraints(null, Model.AllDifferent(c, s, a, d, v, e, n, t, l, r));

            //モデルの項の宣言
            Term tCS = Model.Sum(c * 10, s);
            Term tADVENT = Model.Sum(a * 100000, d * 10000, v * 1000, e * 100, n * 10, t);
            Term tCALENDAR = Model.Sum(c * 10000000, a * 1000000, l * 100000, e * 10000, n * 1000, d * 100, a * 10, r);

            //制約条件：C>0、A>0
            model.AddConstraint(null, c > 0);
            model.AddConstraint(null, a > 0);

            //12月の全ての日について調べる
            for (int tDate = 20111201; tDate < 20111231; tDate++)
            {
                //制約条件：-C#×ADVENT＋CALENDAR＝(日付)
                Constraint constraint = model.AddConstraint(null, Model.Equal(-tCS * tADVENT + tCALENDAR, tDate));

                //制約充足問題を解く
                //解くためのソルバーはモデルから自動で決定される
                Solution solution = solverContext.Solve();

                //解を全て列挙
                while (solution.Quality != SolverQuality.Infeasible)
                {
                    //計算レポートの表示
                    Report report = solution.GetReport();
                    Console.WriteLine(report);

                    //解の表示
                    Console.WriteLine("-{0}{1} * {2}{3}{4}{5}{6}{7} + {0}{2}{8}{5}{6}{3}{2}{9} = {10}\n", c, s, a, d, v, e, n, t, l, r, tDate);

                    //複数解ある場合は次の解を表示
                    solution.GetNext();
                }

                model.RemoveConstraint(constraint);
            }

            Console.WriteLine("-C# * ADVENT + CALENDAR = (Date)\n");
        }
    }
}

実行結果

===Solver Foundation Service Report===
Date: 2011/12/26 22:33:00
Version: Microsoft Solver Foundation 3.0.2.10889 Express Edition
Model Name: DefaultModel
Capabilities Applied: CP
Solve Time (ms): 48
Total Time (ms): 55
Solve Completion Status: Feasible
Solver Selected: Microsoft.SolverFoundation.Solvers.ConstraintSystem
Directives:
Microsoft.SolverFoundation.Services.Directive
Algorithm: TreeSearch
Variable Selection: DomainOverWeightedDegree
Value Selection: ForwardOrder
Move Selection: Any
Backtrack Count: 471
===Solution Details===
Goals:

Decisions:
C: 5
S: 2
A: 6
D: 9
V: 8
E: 1
N: 3
T: 0
L: 4
R: 7

-52 * 698130 + 56413967 = 20111207

===Solver Foundation Service Report===

……(以下、もう一つの解を表示)

以上、簡単ではありますがMicrosoft Solver Foundationのご紹介をさせていただきました。
C#、もとい.NET環境で使える数理計画法ライブラリをお探しの方はお使いになられてはいかがでしょうか。