Google OR-Tools で使用できるソルバーのライセンス

はじめに

ソルバーとは数理計画問題を解くアルゴリズムが搭載されているソフトウェアで、商用およびフリーウェア等様々なものがあります。しかし私のような素人にはどのようなソルバーがあってどれを使えば良いかよく分かりません。そこで、ソルバー調査のとっかかりになるものとして、主なソルバーについて簡単に調べたことをまとめたいと思います。企業情報等は2020年4月27日現在のものです。誤り等あればご指摘ください。

なお、著者の実力不足で、技術的観点の比較はありません。

参考

• 企業情報取得元：opencorporates, Wikipedia

その他参考にしたサイト

• 最適化問題ソルバーのGLPKを使ってみた
• GNUオペレーティング・システム
• Python+PuLPによるタダで仕事に使える数理最適化

ソルバーの種類

この記事では Gurobi, CPLEX, SCIP, GLPK, GLOP, CP-SAT の6種類について調べてみました。

この6種類を選んだ理由は、Google or-Tools で連携できるからです。

OR-Tools は最適化のためのオープンソース・ソフトウェア・スイートであり、車両ルーティング、フロー、整数計画法、線形計画法、制約計画法など、世界で最も困難な問題に取り組むために調整されています。
選択したプログラミング言語で問題をモデリングした後、GurobiやCPLEXなどの商用ソルバー、SCIP、GLPK、GoogleのGLOPや受賞歴のあるCP-SATなどのオープンソースソルバーなど、6種類のソルバーを使用して問題を解くことができます。

引用はGoogle OR-ToolsをDeepLで翻訳しました。

Google OR-Tools には標準で、LPはGLOPソルバー、Constraint OptimizationにはCP-SATソルバーが付随しています。他の最適化問題には専用のライブラリなどが含まれています。

Gurobi

Gurobi Optimization, LLC.が提供する商用ソフトウェア。C++、Java、.NETおよびPython用のオブジェクト指向インターフェースやC、MATLABおよびR用の行列指向インターフェースなどがあるようです。

"The fastest and most powerful mathematical programming solver available for your LP, QP and MIP (MILP, MIQP, and MIQCP) problems. See why so many companies are choosing Gurobi for better performance, faster development and better support."

日本では株式会社オクトーバー・スカイが展開しているようです。下記の最適化問題をサポートしています。

• 線形計画 (LP)
• 混合整数線形計画 (MILP)
• 二次計画 (QP)
• 混合整数二次計画 (MIQP)
• 二次制約 (QCP)
• 混合整数二次制約 (MIQCP)

開発元情報

Item	Description
Developer	Gurobi Optimization, LLC.
Founded	2008/07/17
Country	Texas (US)
CEO	Edward Rothberg

CPLEX

IBMが提供する商用ソフトウェア。C++、C#、Java言語へのインターフェイスを提供するConcertと呼ばれるモデリングレイヤーがあります。C インターフェースをベースにした Python 言語インターフェースもあります。さらに、Microsoft ExcelおよびMATLABへのコネクタも提供されています。

High-performance mathematical programming solver for linear programming, mixed-integer programming and quadratic programming

開発元情報

Item	Description
Developer	IBM
Founded	1911/06/16
Country	New York (US)
CEO	Arvind Krishna

SCIP

ドイツの Zuse Institute Berlin で開発されている非商用ソルバー。

SCIP is currently one of the fastest non-commercial solvers for mixed integer programming (MIP) and mixed integer nonlinear programming (MINLP). It is also a framework for constraint integer programming and branch-cut-and-price. It allows for total control of the solution process and the access of detailed information down to the guts of the solver.

ライセンスはZIB Academic Licenseで、学術的使用に限り、SCIP は無料で利用できます。商用で利用したい場合は都度相談のようです。

公式サイトによると複数の言語で使用可能のようです。

• large C-API, C++ wrapper classes for user plugins
• interfaces to other applications and programming languages (contained in source code packages or available from github.com/SCIP-interfaces):
  - Python
  - Java
  - AMPL
  - GAMS
  - MATLAB

開発元情報

Item	Description
Developer	Zuse Institute Berlin
Founded	1984/07/17
Country	Berlin (Germany)

GLPK

GNU Linear Programming Kit の略。大規模線形計画法(LP)、混合整数計画法(MIP)、およびその他の関連問題を解くためのソフトウェア。

The GLPK (GNU Linear Programming Kit) package is intended for solving large-scale linear programming (LP), mixed integer programming (MIP), and other related problems. It is a set of routines written in ANSI C and organized in the form of a callable library.

下記の問題などが解けるようです。

• primal and dual simplex methods
• primal-dual interior-point method
• branch-and-cut method
• translator for GNU MathProg
• application program interface (API)
• stand-alone LP/MIP solver

配信元の例えばglpk-4.65.tar.gzのREADMEにライセンスの記載がありました。ライセンスはGPL v3のようです。

GLPK is free software: you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation, either version 3 of the License, or (at your
option) any later version.

Wikiによると、複数言語のバインディングがあるようです。

The following language bindings have dedicated pages:

• Ada language bindings

• C# language bindings
• Fortran language bindings
• GAMS language bindings
• Java language bindings
• JavaScript language bindings
• Julia language bindings
• Matlab (and Octave) language bindings
• OCaml language bindings
• Octave language bindings
• OptimJ language bindings
• Python language bindings
• R language bindings
• Ruby language bindings

開発元情報

Item	Description
Developer	GNU Project
Founded	1983/09
Country	親組織である Free Software Foundation は US の非営利組織
Chief GNUisance	Richard Stallman

GLOP

Google が開発している線形計画ソルバー。
オープンソースで、ライセンスはApache License 2.0 です。

Glop is Google's in-house linear solver, available as open source. You can access Glop through the OR-Tools linear solver wrapper, which is a wrapper for Glop, as well as several other third-party linear optimization solvers. To learn how solve a simple linear problem using Glop in all of the supported languages, see Getting Started with OR-Tools.

開発元情報

Item	Description
Developer	Google LLC
Founded	1998/07/04
Country	California (US)
CEO	Sundar Pichai

CP-SAT

まとまって記載してあるページが見つけられなかった。
CP-SAT SolverもGoogleが開発したソルバー？
多分ここにあるソルバーのことだと思われる。ソースコードを見た限り、ライセンスは Apache License 2.0　のようである。

ライセンスまとめ

Name	LISENCE	Company
Gurobi	Proprietary	Gurobi Optimization, LLC.
CPLEX	Proprietary	IBM
SCIP	ZIB Academic License	Zuse Institute Berlin
GLPK	GPL	GNU
GLOP	Apache License 2.0	Google
CP-SAT	Apache License 2.0	Google

Pulpって何？

検索しているとしばしば Pulp という単語が出てきたのでメモ。

Pulp は、Python上で数理最適化問題を簡単にコーディングし、ソルバーに接続するpythonモデリングインターフェースです。Pulp自体はソルバーではないです。

Pulp は COIN-OR プロジェクトの一つで、COIN-OR のその他のプロジェクトであるソルバーの CLP および CBC のほか、GLPK、CPLEX、Gurobi などにも接続できるようです。

おわりに

今度は技術的な観点で比較できるようにしたいです。