本書のSCIP対応について

[jiro-iwanaga]

背景

数理最適化ソルバーSCIPが、2022年11月4日からApache 2.0ライセンスとなり、商用での利用が可能となった。

License Since November 4, SCIP is licensed under the Apache 2.0 License. https://www.scipopt.org/index.php#license

モデリング言語PuLPからソルバーSCIPの呼び出しについて

以下のようにPuLPからSCIPを呼び出して実行可能であることを確認した。

ファイル（test.py）

import pulp

problem = pulp.LpProblem('LP', pulp.LpMaximize)

x = pulp.LpVariable('x', cat='Integer')
y = pulp.LpVariable('y', cat='Integer')

problem += 1 * x + 3 * y <= 30
problem += 2 * x + 1 * y <= 40
problem += x >= 0
problem += y >= 0
problem.objective = x + 2 * y

solver = pulp.SCIP_CMD()
status = problem.solve(solver)

print('Status:', pulp.LpStatus[status])
print('x=', x.value(), 'y=', y.value(), 'obj=', problem.objective.value())

実行

$python test.py

出力

SCIP version 8.0.2 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: Soplex 6.0.2] [GitHash: 5f0473c4fb]
Copyright (C) 2002-2022 Konrad-Zuse-Zentrum fuer Informationstechnik Berlin (ZIB)

External libraries: 
  Readline EditLine w  GNU library for command line editing (gnu.org/s/readline)
  Soplex 6.0.2         Linear Programming Solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: 45f6420d]
  CppAD 20180000.0     Algorithmic Differentiation of C++ algorithms developed by B. Bell (github.com/coin-or/CppAD)
  ZLIB 1.2.11          General purpose compression library by J. Gailly and M. Adler (zlib.net)
  GMP 6.2.1            GNU Multiple Precision Arithmetic Library developed by T. Granlund (gmplib.org)
  AMPL/MP 4e2d45c4     AMPL .nl file reader library (github.com/ampl/mp)

user parameter file <scip.set> not found - using default parameters

read problem </var/folders/5f/6t2pl2pd5l53yt6l2ms05lww0000gn/T/2c5b92d0c2a94cd7970564ff31af6f16-pulp.lp>
============

original problem has 2 variables (0 bin, 2 int, 0 impl, 0 cont) and 4 constraints

feasible solution found by trivial heuristic after 0.0 seconds, objective value 0.000000e+00
presolving:
(round 1, fast)       0 del vars, 2 del conss, 0 add conss, 2 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 2, fast)       0 del vars, 2 del conss, 0 add conss, 5 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 3, exhaustive) 0 del vars, 2 del conss, 0 add conss, 5 chg bounds, 0 chg sides, 0 chg coeffs, 2 upgd conss, 0 impls, 0 clqs
   Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).
presolving (4 rounds: 4 fast, 2 medium, 2 exhaustive):
 0 deleted vars, 2 deleted constraints, 0 added constraints, 5 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
 0 implications, 0 cliques
presolved problem has 2 variables (0 bin, 2 int, 0 impl, 0 cont) and 2 constraints
      2 constraints of type <varbound>
transformed objective value is always integral (scale: 1)
Presolving Time: 0.00
transformed 1/1 original solutions to the transformed problem space

 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl. 
p 0.0s|     1 |     0 |     0 |     - | vbounds|   0 |   2 |   2 |   2 |   0 |  0 |   0 |   0 | 4.000000e+01 | 2.000000e+01 | 100.00%| unknown
p 0.0s|     1 |     0 |     0 |     - | vbounds|   0 |   2 |   2 |   2 |   0 |  0 |   3 |   0 | 4.000000e+01 | 2.100000e+01 |  90.48%| unknown
* 0.0s|     1 |     0 |     2 |     - |    LP  |   0 |   2 |   2 |   2 |   0 |  0 |   4 |   0 | 2.600000e+01 | 2.600000e+01 |   0.00%| unknown
  0.0s|     1 |     0 |     2 |     - |   580k |   0 |   2 |   2 |   2 |   0 |  0 |   4 |   0 | 2.600000e+01 | 2.600000e+01 |   0.00%| unknown

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.00
Solving Nodes      : 1
Primal Bound       : +2.60000000000000e+01 (4 solutions)
Dual Bound         : +2.60000000000000e+01
Gap                : 0.00 %

written solution information to file </var/folders/5f/6t2pl2pd5l53yt6l2ms05lww0000gn/T/2c5b92d0c2a94cd7970564ff31af6f16-pulp.sol>

Status: Optimal
x= 18.0 y= 4.0 obj= 26.0

モデリング言語Python-MIPからソルバーSCIPの呼び出しについて

python-mipはscipに未対応（2022年11月5日）。 しかしながらコードに将来的にSCIP対応する計画があるとの記述がされている。 https://github.com/coin-or/python-mip/blob/master/mip/constants.py#L32

SCIP = "SCIP"  # we plan to support SCIP in the future

なお、Python-MIPの場合、次のコードで実行することになる想定。

import mip

problem = mip.Model(solver_name=mip.SCIP)

x = problem.add_var(var_type='I')
y = problem.add_var(var_type='I')

problem += 1 * x + 3 * y <= 30
problem += 2 * x + 1 * y <= 40
problem.objective = mip.maximize(x + 2 * y)

problem.optimize()

print('Status:', problem.status)
print('x=', x.x, 'y=', y.x, 'obj=', problem.objective.x)

検討事項

本書のコードを将来的にSCIP対応するかどうかだったり、本レポジトリでSCIP対応コードを公開するかどうか検討する。

[jiro-iwanaga]

SCIPのページ

https://scipopt.org/index.php#welcome

SCIPのインストール方法

SCIPは別途インストールする必要がある。以下のページが参考になる。

• SCIPをMacにインストール
• MAC：最適化ソルバーSCIPのインストール

[jiro-iwanaga]

追記

SCIPは、pythonインターフェースとしてPySCIPOptを用意している。 PySCIPOptを利用して実装したコードをGitHubに公開するのはよさそう。