LoginSignup
16

More than 3 years have passed since last update.

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

Last updated at Posted at 2020-04-27

はじめに

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

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

参考

その他参考にしたサイト

ソルバーの種類

この記事では 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 などにも接続できるようです。

おわりに

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
16