Help us understand the problem. What is going on with this article?

Google Optimization Toolsを使ってみる

More than 1 year has passed since last update.

概要

 以前、GNUのMIPソルバー「GLPK」についての解説記事を作成しました。
  GLPK for C#/CLIで遊ぼう!
  GLPKを手頃に扱えるラッパークラスを作成しました
 また、ソルバーライブラリ「Microsoft Solver Foundation」についての解説記事も書きました。
  Microsoft Solver Foundationを使ってみる
 今回の記事では、よりモダン・高速なライブラリである「Google Optimization Tools」についての解説を行います。

導入方法

 まず、公式サイトからzipをダウンロードしてください。
 Visual Studio 2017の場合、2017/09/29時点で「or-tools_VisualStudio2017-64bit_v6.4.4495.zip」を落とせば大丈夫です。
 なお、ソースコードおよびリリースバイナリ全部にアクセスしたい場合は、GitHubの当該ページに当たると良いでしょう。

 次に普通にVS上でプロジェクトを作成し、そこにzip内のbinフォルダにある「Google.OrTools.dll」を参照で追加します。
 名前で察せられると思いますが、このバイナリはx64版しかありませんのでビルド設定に注意しましょう。

image.png

 実行には「Google.Protobuf.dll」も必要ですので、プロジェクト内にコピーしておくと便利でしょう。

image.png

2017/09/29 21:19訂正:Google.Protobuf.dllは無くても実行に問題はないようです。

※以下は「Visual Studio 2017でC#を用いて開発する場合」の記述になります。不思議なことに、v6.3のzip(or-tools_VisualStudio2017-64bit_v6.3.4431.zip)だとビルドできこそすれ実行できなかったので注意が必要です

使用方法

 いつものサンプル問題を定式化してみました。

  • 最大化する目的関数:$Z=5X+4Y$
  • 制約式1:$1.5X+3Y\leq13.5$
  • 制約式2:$3X+Y\leq10$
  • 制約式3:$X+2Y\geq7$
  • 変数の範囲:$X\geq0$, $Y\geq0$
  • その他:$X,Y\in\mathbb{N}$
using System;
using Google.OrTools.LinearSolver;

namespace ConsoleApp3 {
    class Program {
        static void Main(string[] args) {
            // 解く問題を初期化(IDisposable対応)
            // ・線形計画法/整数計画法なので"IntegerProgramming"
            // ・ソルバーとしてCoin-or branch and cut(CBC)を使うので"CBC_MIXED_INTEGER_PROGRAMMING"
            // ※ソルバーにGlop(”GLOP_LINEAR_PROGRAMMING”)を指定すると、整数制約が守られないので注意
            using (var solver = Solver.CreateSolver("IntegerProgramming", "CBC_MIXED_INTEGER_PROGRAMMING")) {
                // 初期化できてない場合はnullが返る
                if (solver == null) {
                    Console.WriteLine("ソルバーを初期化できませんでした。");
                    return;
                }
                // 最適化の方向を設定する
                // 最大化→SetMaximization、最小化→SetMinimization
                var objective = solver.Objective();
                objective.SetMaximization();
                // 制約式の数・範囲
                var e1 = solver.MakeConstraint(double.NegativeInfinity, 13.5);
                var e2 = solver.MakeConstraint(double.NegativeInfinity, 10.0);
                var e3 = solver.MakeConstraint(7.0, double.PositiveInfinity);
                // 変数の数・名前・範囲
                // 実数→MakeNumVar、整数→MakeIntVar、0-1変数→MakeBoolVar
                // (0-1変数以外だと、下限および上限を指定できる)
                // なお、MakeVarだと引数で整数制約があるか否かをbool指定できる
                var x = solver.MakeIntVar(0.0, double.PositiveInfinity, "X");
                var y = solver.MakeIntVar(0.0, double.PositiveInfinity, "Y");
                // 目的関数の係数
                objective.SetCoefficient(x, 5);
                objective.SetCoefficient(y, 4);
                // 制約式の係数
                e1.SetCoefficient(x, 1.5);
                e1.SetCoefficient(y, 3);
                e2.SetCoefficient(x, 3);
                e2.SetCoefficient(y, 1);
                e3.SetCoefficient(x, 1);
                e3.SetCoefficient(y, 2);
                // 最適化
                int resultStatus = solver.Solve();
                // 結果表示
                // 結果の返り値はdoubleなので注意
                if (resultStatus != Solver.OPTIMAL) {
                    Console.WriteLine("ソルバーで解けませんでした。");
                    return;
                }
                Console.WriteLine($"計算時間:{solver.WallTime()}[ms]");
                Console.WriteLine($"Z = {solver.Objective().Value()}");
                Console.WriteLine($"{x.Name()} = {x.SolutionValue()}");
                Console.WriteLine($"{y.Name()} = {y.SolutionValue()}");
            }
            return;
        }
    }
}

 GLPKやMicrosoft Solver Foundationと異なり、「変数」「制約式」をGoogle.OrTools.LinearSolver.Variable型およびGoogle.OrTools.LinearSolver.Constraint型として指定しますので、より直感的に問題を構成することができます。
 また、Make○○VarArrayメソッドやMake○○VarMatrixメソッドを使うことで、問題に使用する変数を1次元配列・2次元配列として確保・初期化することができます。
 更に、計算速度も(無償で使える中では)高速なようです。今後は積極的に利用していきたいですね。
 ……フットプリントがかなり大きいけどな(GLPKで2MB,MSFで2.5MBなのに17MB近くもある)

参考資料

Microsoft Solver Foundationで最適化問題を解く | tocsworld

YSRKEN
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした