PuLPでSCIPソルバーを使用する (MacOS)

筆者の環境
MacOS Mojave 10.14.3
Python 3.7.2
PuLP 1.6.9
SCIP 6.0.1

## PuLPについて

[PuLP](https://pythonhosted.org/PuLP/index.html)は線形計画問題を解くPython パッケージです.　使い方は[PuLPによるモデル作成方法](https://docs.pyq.jp/python/math_opt/pulp.html)に分かりやすくまとめられています.

このPuLPで使用されるデフォルトのソルバーはCBCです.
別途, **GLPK**（無料）、**SCIP**(学術利用は無料, 商用有料), **Gurobi**（有料）、**CPLEX**（有料）などをインストールすると使用するソルバーを変更することができます.



## SCIPについて

**SCIP**とはドイツのZIBという研究機関が開発しているMIP(mixed integer programming)とMINLP(mixed integer nonlinear programmin)ソルバーです. 非商用利用(Academic License)であれば無料で使用することができます.


<img src="https://qiita-image-store.s3.amazonaws.com/0/154548/c82d0b5c-37fa-e28d-30f3-ae97e8ddda11.png" width=500>



## PuLPでSCIPを使用できるようにする

### SCIPのダウンロード

[公式サイト](https://scip.zib.de)のDownloadから`SCIP Optimization Suite`をダウンロードし`README.md`に従って `make`を行います.

**CMake**

```bash
mkdir build
cd build
cmake ..
make
make test # チェック
make install
```

> brew install cmake でcmakeをインストールできます

**Make**

```bash
make
make test # チェック
make install
```

これでターミナルからscipコマンドを使えるようになっているはずです.


### pulpの設定ファイルへSCIPのパスを追記


`pulp.cfg.osx`に次の行を追記します.

> pulp.cfg.osx ファイルは
> \>\> import pulp
> \>\> pulp.\_\_path\_\_
> で確認できるフォルダにあります

```bash
ScipPath = scip
```

PuLPはSCIPソルバーに対応していないことになっていますが, ありがたいことにSCIPソルバーを使用できるような用意はなされています. それによりこの処理を行うだけでターミナルで`scip`を実行したときに起動するソルバーをPuLPで使用することができるのです.

```python
m = LpProblem()
solver = pulp.SCIP()
m.solve(solver)
```

> - デフォルトで使用できるオプション
>   - msg (Default: False) Trueにすると実行ログが表示されます
>   - keepFiles (Default: False) Trueにすると`.lp`ファイルと`.sol`ファイルが保存されます.



### 並列化への対応

[UG](https://ug.zib.de)フレームワークを用いてSCIPを並列実行することができます. そのためには, scipだけでなくugもコンパイルします.

```bash
# scipoptsuite ディレクトリ上
make PARASCIP=true
make ug
make install
```

を実行すると`fscip`がターミナルから使用できるようになります.


**pulpに`fscip`の実行パラメータファイルを置く**

`fscip`を実行するにはパラメータ設定ファイルを指定する必要があります.
これはPuLPフォルダの`solverdir`以下に置くのがいいでしょう.

```bash
# 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)を更新する**

```bash
FscipPath = fscip
FscipParamPath = %(here)s/solverdir/scip/fscip/default.set
```

**pulpの`solvers.py`を書き換える**

`fscip`と`scip`の実行コマンド, ならびに最適化結果ファイルのフォーマットが異なるので
調節する必要があります. `solvers.py`の`def initialize`周辺と`class SCIP_CMD`を以下のように書き換えます.

<details><summary>def initialize</summary><div>
**initialize関数内**

`fscip_path`と`fscip_param_path`を追加.

```python
try:
    scip_path = config.get("locations", "ScipPath")
except configparser.Error:
    scip_path = 'scip
```

↓↓↓↓↓↓↓↓

```python
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`を追加

```python
return cplex_dll_path, ilm_cplex_license, ilm_cplex_license_signature,\
    coinMP_path, gurobi_path, cbc_path, glpk_path, pulp_cbc_path, scip_path
```

↓↓↓↓↓↓↓↓

```python
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`を追加

```python
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)
```

↓↓↓↓↓↓↓↓

```python
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)
```

</div></details>

<details><summary>class SCIP_CMD</summary><div>

```python
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
```

</div></details>

これで並列化バージョンのSCIPソルバをPuLPで使用することができます.