筆者の環境
MacOS Mojave 10.14.3
Python 3.7.2
PuLP 1.6.9
SCIP 6.0.1
PuLPについて
PuLPは線形計画問題を解くPython パッケージです. 使い方はPuLPによるモデル作成方法に分かりやすくまとめられています.
このPuLPで使用されるデフォルトのソルバーはCBCです.
別途, GLPK（無料）、SCIP(学術利用は無料, 商用有料), Gurobi（有料）、CPLEX（有料）などをインストールすると使用するソルバーを変更することができます.
SCIPについて
SCIPとはドイツのZIBという研究機関が開発しているMIP(mixed integer programming)とMINLP(mixed integer nonlinear programmin)ソルバーです. 非商用利用(Academic License)であれば無料で使用することができます.
PuLPでSCIPを使用できるようにする
SCIPのダウンロード
公式サイトのDownloadからSCIP Optimization SuiteをダウンロードしREADME.mdに従って makeを行います.
CMake
mkdir build
cd build
cmake ..
make
make test # チェック
make install
brew install cmake でcmakeをインストールできます
Make
make
make test # チェック
make install
これでターミナルからscipコマンドを使えるようになっているはずです.
pulpの設定ファイルへSCIPのパスを追記
pulp.cfg.osxに次の行を追記します.
pulp.cfg.osx ファイルは
>> import pulp
>> pulp.__path__
で確認できるフォルダにあります
ScipPath = scip
PuLPはSCIPソルバーに対応していないことになっていますが, ありがたいことにSCIPソルバーを使用できるような用意はなされています. それによりこの処理を行うだけでターミナルでscipを実行したときに起動するソルバーをPuLPで使用することができるのです.
m = LpProblem()
solver = pulp.SCIP()
m.solve(solver)
- デフォルトで使用できるオプション
- msg (Default: False) Trueにすると実行ログが表示されます
- keepFiles (Default: False) Trueにすると
.lpファイルと.solファイルが保存されます.
並列化への対応
UGフレームワークを用いてSCIPを並列実行することができます. そのためには, scipだけでなくugもコンパイルします.
# scipoptsuite ディレクトリ上
make PARASCIP=true
make ug
make install
を実行するとfscipがターミナルから使用できるようになります.
pulpにfscipの実行パラメータファイルを置く
fscipを実行するにはパラメータ設定ファイルを指定する必要があります.
これはPuLPフォルダのsolverdir以下に置くのがいいでしょう.
# pulpフォルダ上
mkdir -p solverdir/scip/fscip
cp scipoptsuite-6.0.1(ダウンロードしたscipパス)/ug/setting/default.set solverdir/scip/fscip/default.set
pulpフォルダは
>> import pulp
>>pulp.__path__
で確認できます
pulpの設定ファイル(pulp.cfg.osx)を更新する
FscipPath = fscip
FscipParamPath = %(here)s/solverdir/scip/fscip/default.set
pulpのsolvers.pyを書き換える
fscipとscipの実行コマンド, ならびに最適化結果ファイルのフォーマットが異なるので
調節する必要があります. solvers.pyのdef initialize周辺とclass SCIP_CMDを以下のように書き換えます.
def initialize
**initialize関数内**
fscip_pathとfscip_param_pathを追加.
try:
scip_path = config.get("locations", "ScipPath")
except configparser.Error:
scip_path = 'scip
↓↓↓↓↓↓↓↓
try:
scip_path = config.get("locations", "ScipPath")
fscip_path = config.get("locations", "FscipPath")
fscip_param_path = config.get("locations", "FscipParamPath")
except configparser.Error:
scip_path = 'scip
initialize返り値
fscip_path, fscip_para_pathを追加
return cplex_dll_path, ilm_cplex_license, ilm_cplex_license_signature,\
coinMP_path, gurobi_path, cbc_path, glpk_path, pulp_cbc_path, scip_path
↓↓↓↓↓↓↓↓
return cplex_dll_path, ilm_cplex_license, ilm_cplex_license_signature,\
coinMP_path, gurobi_path, cbc_path, glpk_path, pulp_cbc_path,\
scip_path, fscip_path, fscip_param_path
if name == 'main'の何行か下
fscip_pathとfscip_param_pathを追加
cplex_dll_path, ilm_cplex_license, ilm_cplex_license_signature, coinMP_path,\
gurobi_path, cbc_path, glpk_path, pulp_cbc_path, scip_path\
initialize(config_filename, operating_system, arch)
↓↓↓↓↓↓↓↓
cplex_dll_path, ilm_cplex_license, ilm_cplex_license_signature, coinMP_path,\
gurobi_path, cbc_path, glpk_path, pulp_cbc_path,\
scip_path, fscip_path, fscip_param_path = \
initialize(config_filename, operating_system, arch)
class SCIP_CMD
class SCIP_CMD(LpSolver_CMD):
"""The SCIP optimization solver"""
SCIP_STATUSES = {
'unknown': LpStatusUndefined,
'user interrupt': LpStatusNotSolved,
'node limit reached': LpStatusNotSolved,
'total node limit reached': LpStatusNotSolved,
'stall node limit reached': LpStatusNotSolved,
'time limit reached': LpStatusNotSolved,
'memory limit reached': LpStatusNotSolved,
'gap limit reached': LpStatusNotSolved,
'solution limit reached': LpStatusNotSolved,
'solution improvement limit reached': LpStatusNotSolved,
'restart limit reached': LpStatusNotSolved,
'optimal solution found': LpStatusOptimal,
'infeasible': LpStatusInfeasible,
'unbounded': LpStatusUnbounded,
'infeasible or unbounded': LpStatusNotSolved,
}
FSCIP_STATUSES = {
'objective value': LpStatusOptimal,
'No Solution': LpStatusInfeasible
}
def defaultPath(self):
return self.executableExtension(scip_path)
def __init__(self, keepFiles = 0, msg = 0,
threads = None):
if threads is None or threads == 1:
path = scip_path
else:
path = fscip_path
self.fscip_param_path = fscip_param_path
LpSolver_CMD.__init__(self, path, keepFiles, msg)
self.threads = threads
def available(self):
"""True if the solver is available"""
return self.executable(self.path)
def actualSolve(self, lp):
"""Solve a well formulated lp problem"""
print(self.path)
if not self.executable(self.path):
raise PulpSolverError("PuLP: cannot execute "+self.path)
# TODO: should we use tempfile instead?
if not self.keepFiles:
uuid = uuid4().hex
tmpLp = os.path.join(self.tmpDir, "%s-pulp.lp" % uuid)
tmpSol = os.path.join(self.tmpDir, "%s-pulp.sol" % uuid)
else:
tmpLp = lp.name + "-pulp.lp"
tmpSol = lp.name + "-pulp.sol"
lp.writeLP(tmpLp)
if self.path == scip_path:
proc = [
self.path, '-c', 'read "%s"' % tmpLp, '-c', 'optimize',
'-c', 'write solution "%s"' % tmpSol, '-c', 'quit'
]
else:
proc = [
self.path, self.fscip_param_path, tmpLp,
'-sth', '%d' % self.threads, '-fsol', tmpSol
]
proc.extend(self.options)
if not self.msg:
proc.append('-q')
print(' '.join(proc))
if os.path.exists(tmpSol):
os.remove(tmpSOl)
self.solution_time = clock()
subprocess.check_call(proc, stdout=sys.stdout, stderr=sys.stderr)
self.solution_time += clock()
if not os.path.exists(tmpSol):
raise PulpSolverError("PuLP: Error while executing "+self.path)
if self.path == scip_path:
lp.status, values = self.scip_readsol(tmpSol)
elif self.path == fscip_path:
lp.status, values = self.fscip_readsol(tmpSol)
# Make sure to add back in any 0-valued variables SCIP leaves out.
finalVals = {}
for v in lp.variables():
finalVals[v.name] = values.get(v.name, 0.0)
lp.assignVarsVals(finalVals)
if not self.keepFiles:
for f in (tmpLp, tmpSol):
try:
os.remove(f)
except:
pass
return lp.status
def scip_readsol(self, filename):
"""Read a SCIP solution file"""
with open(filename) as f:
# First line must containt 'solution status: <something>'
try:
line = f.readline()
comps = line.split(': ')
assert comps[0] == 'solution status'
assert len(comps) == 2
except:
raise
raise PulpSolverError("Can't read SCIP solver output: %r" % line)
status = SCIP_CMD.SCIP_STATUSES.get(comps[1].strip(), LpStatusUndefined)
if not status == LpStatusOptimal:
return status, dict()
# Look for an objective value. If we can't find one, stop.
try:
line = f.readline()
comps = line.split(': ')
assert comps[0] == 'objective value'
assert len(comps) == 2
float(comps[1].strip())
except:
raise PulpSolverError("Can't read SCIP solver output: %r" % line)
# Parse the variable values.
values = {}
for line in f:
try:
comps = line.split()
values[comps[0]] = float(comps[1])
except:
raise PulpSolverError("Can't read SCIP solver output: %r" % line)
return status, values
def fscip_readsol(self, filename):
"""Read a SCIP solution file"""
with open(filename) as f:
try:
line = f.readline()
line = f.readline()
comps = line.split(': ')
except:
raise 'Problem is unknonw states'
status = SCIP_CMD.FSCIP_STATUSES.get(comps[0].strip(), LpStatusUndefined)
# Look for an objective value. If we can't find one, stop.
if comps[0] == 'objective value':
float(comps[1].strip())
# Parse the variable values.
values = {}
for line in f:
try:
comps = line.split()
values[comps[0]] = float(comps[1])
except:
raise PulpSolverError("Can't read SCIP solver output: %r" % line)
return status, values
SCIP = SCIP_CMD
これで並列化バージョンのSCIPソルバをPuLPで使用することができます.