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

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

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

## 参考
- 企業情報取得元：[opencorporates](https://opencorporates.com), Wikipedia

その他参考にしたサイト

- [最適化問題ソルバーのGLPKを使ってみた](https://qiita.com/anqooqie/items/dc6498909efd7b2d9ee4)
- [GNUオペレーティング・システム](https://www.gnu.org/gnu/gnu.html)
- [Python+PuLPによるタダで仕事に使える数理最適化](https://qiita.com/samuelladoco/items/703bf78ea66e8369c455)



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

この6種類を選んだ理由は、[Google or-Tools](https://developers.google.com/optimization) で連携できるからです。

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

引用は[Google OR-Tools](https://developers.google.com/optimization)をDeepLで翻訳しました。

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


### Gurobi

[Gurobi Optimization, LLC.](https://www.gurobi.com/products/gurobi-optimizer)が提供する商用ソフトウェア。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."

日本では[株式会社オクトーバー・スカイ](https://www.octobersky.jp)が展開しているようです。下記の最適化問題をサポートしています。

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


**開発元情報**

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

### CPLEX

[IBM](https://www.ibm.com/analytics/cplex-optimizer)が提供する商用ソフトウェア。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](https://scip.zib.de/index.php) で開発されている非商用ソルバー。

>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](https://scip.zib.de/academic.txt)で、学術的使用に限り、SCIP は無料で利用できます。商用で利用したい場合は都度相談のようです。

[公式サイト](https://scip.zib.de/index.php#features)によると複数の言語で使用可能のようです。

>- 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](https://www.gnu.org/software/glpk/) の略。大規模線形計画法(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

[配信元](http://ftp.gnu.org/gnu/glpk/)の例えば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](https://en.wikibooks.org/wiki/GLPK)によると、複数言語のバインディングがあるようです。

>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 が開発している線形計画ソルバー。](https://developers.google.com/optimization/lp/lp)
[オープンソース](https://github.com/google/or-tools)で、[ライセンスはApache License 2.0](https://github.com/google/or-tools/blob/stable/LICENSE-2.0.txt) です。

>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](https://developers.google.com/optimization/cp/cp_solver)もGoogleが開発したソルバー？
多分[ここ](https://github.com/google/or-tools/tree/stable/ortools/sat)にあるソルバーのことだと思われる。ソースコードを見た限り、ライセンスは 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 などにも接続できるようです。

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