PRINTEMPSをWindowsで動かす

# PRINTEMPS関連の参考資料

- [公式ドキュメント](https://snowberryfield.github.io/printemps/)
- [Github](https://github.com/snowberryfield/printemps/blob/master/LICENSE)
- [原理の説明](https://speakerdeck.com/snowberryfield/metahiyurisuteikusuniji-dukufan-yong-xian-xing-zheng-shu-ji-hua-sorubanokai-fa)(Optimization Night #9 の資料)
- [その他Qiita記事](https://qiita.com/___monta___/items/0c6e01b1dea437dd8a33)

# はじめに

2024年11月22日に、[Optimization Night #9](https://optimization.connpass.com/event/332590/) という数理最適化のイベントが開催されました。現地参加して興味を持ったので、実務への活用も見越して試してみました。

PRINTEMPSはMITライセンスのソルバーで、気軽に活用できますが、WindowsのPCで使うには少し障壁があったので、自分の試したやり方を残しておきます。

# 注意
- Windows Subsystem for Linuxを使えばもっと簡単に導入できますので、とりあえず試すだけならまずWSL環境下で、ドキュメントに記載の手順でインストールしましょう。
- PRINTEMPSは、C++のヘッダーオンリーのライブラリとして使う方法と、スタンドアローンのソルバーとしてMPS形式のファイルを読み込ませて使う方法があります。本記事には後者の利用方法に対応するやり方を記載しております。
- C++のビルド方法について詳しくないので、github copilotの助言に基づいて試行錯誤しました。記載されている方法は最小限の変更になっていないかもしれません。

# 実行環境
- OS: Windows 11 Pro 23H2
- cmake-3.31.3
- MinGW-14.2.0-rt_v12-rev0
- PRINTEMPS 2.5.0

# インストール手順

## 1. cmakeのインストール
https://qiita.com/matskeng/items/c466c4751e1352f97ce6 を参考に、最新版をインストール

## 2. MinGWのインストール

参考: https://www.javadrive.jp/cstart/install/index6.html#section1

https://github.com/niXman/mingw-builds-binaries/releases にアクセスし、x86_64-14.2.0-release-win32-seh-msvcrt-rt_v12-rev0.7zをダウンロード

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/68949/ec402d49-8cb7-969f-6c1b-4f61dcc10dc4.png)

解凍し、中身のmingw64フォルダを任意の場所に移動し、pathを登録。

## 3. PRINTEMPSのインストール

### PRINTEMPSの最新版をgit cloneする
```sh
$ git clone https://github.com/snowberryfield/printemps.git
$ cd printemps
```

### プロジェクトの直下にCMakeLists.txtを作成

```cmake:./CMakeLists.txt
cmake_minimum_required(VERSION 3.10)

project(printemps)

# サブディレクトリのCMakeLists.txtをインクルード
add_subdirectory(cmake/application)
```

### 既存のCMakeLists.txtを修正

```cmake:./cmake/application/CMakeLists.txt
cmake_minimum_required(VERSION 3.10)

project(printemps)

find_package(OpenMP REQUIRED)

if(OpenMP_FOUND)
    set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} ${OpenMP_C_FLAGS}")
    set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${OpenMP_CXX_FLAGS}")
endif()

# ##############################################################################
# switch compiler options according to CMAKE_BUILD_TYPE
# ##############################################################################
if(CMAKE_BUILD_TYPE STREQUAL "Release")
    add_compile_options(
        -std=c++17
        -Wall
        -O3
        -Wextra
        -Wno-error=missing-field-initializers
        -pthread
        -march=native
        -mtune=native
        -Wa,-mbig-obj  # 追加
    )
else() # Debug
    add_compile_options(
        -std=c++17
        -Wall
        -Wextra
        -Wno-error=missing-field-initializers
        -pthread
        -march=native
        -mtune=native
        -Wa,-mbig-obj  # 追加
    )
endif()

# ##############################################################################
# executable
# ##############################################################################

# mps_solver
add_executable(mps_solver ${CMAKE_SOURCE_DIR}/application/mps_solver/main.cpp)

target_include_directories(
    mps_solver
    PRIVATE ${CMAKE_SOURCE_DIR}/printemps/
    PRIVATE ${CMAKE_SOURCE_DIR}/external/include/
)

# ##############################################################################
# END
# ##############################################################################

```

#### ※ 変更点:
- コンパイルオプションに```-Wa,-mbig-obj```を追加 (これがないと、too many sectionsというエラーがでる)
- 相対パスの起点を```${TOP_DIR}```から```${CMAKE_SOURCE_DIR}```に変更 (これはビルドコマンド実行方法が変わる兼ね合いで、本質的には不要かも)
- ```${CMAKE_BUILD_TYPE}```がWindowsでは認識されないらしく、```CMAKE_BUILD_TYPE```に変更

## 4. ビルドコマンド実行

```sh
$ mkdir build
$ cd build
$ cmake .. -G "MinGW Makefiles"
$ mingw32-make
```

./build/cmake/applicationの中に、mps_solver.exeが生成されれば成功です。
exeファイルを任意の場所に移動させて良いはずです(試してない)。

# 実行

公式ドキュメントに記載の通りにコマンドを実行します。

testフォルダ内にmps形式のデータがあるのですが、おそらく現状エラーが出る仕様になっているようなので、別のテストデータを使用しました。

[分割可能なアイテムのビンパッキング問題](https://qiita.com/rtonoue/items/6ae16ef090d8dbbefed2)の[簡単な例題](https://github.com/rtonoue/min_fibp)をmpsファイルにエクスポートし、試してみました。
60変数、41制約条件の問題で、混合整数線形計画ソルバーでも一瞬で解けます。

#### コマンド
```sh
$ cd ..
$ ./build/cmake/application/mps_solver test.mps ./test/dat/option/option_01.json --accept-continuous
```
連続変数がある場合は```--accept-continuous```を入力する必要があります。
```./test/dat/option/```にオプションファイルのサンプルが3つ入っていますが、そのうちoption_00.jsonだと実行可能解が得られませんでした。おそらくiteration_maxパラメータが1に設定されていたからだと思われます。
#### 標準出力
```
WARNING : The continuous variable x_('A',_0) will be regarded as an integer variable.
WARNING : The continuous variable x_('A',_1) will be regarded as an integer variable.
WARNING : The continuous variable x_('A',_2) will be regarded as an integer variable.
WARNING : The continuous variable x_('A',_3) will be regarded as an integer variable.
WARNING : The continuous variable x_('A',_4) will be regarded as an integer variable.
WARNING : The continuous variable x_('B',_0) will be regarded as an integer variable.
...(以下略)
```
連続変数は整数変数として取り扱われるようで、設定によっては警告が標準出力されます。

#### 結果
結果は```incumbent.sol```に出力されます。
```
=obj= 7.0000000000e+00
x_('A',_0) 8
x_('A',_1) 0
x_('A',_2) 4
x_('A',_3) 0
x_('A',_4) 0
x_('B',_0) 0
...(以下略)
```
目的関数値は、分枝限定法ソルバー(CBC)で得たものと同じ(7.0)でした。
計算時間はoption_01.jsonでは指定されていないのですが、0.5秒程度で自動終了しました。時間以外にも何らかの終了条件があるっぽいですが、未確認です。

# 感想

- 何度かエラーをフィードバックしながら、なんとかWindows環境にもPRINTEMPSをインストールできました。できれば公式でWindows対応していただけると嬉しいですが、ほかのパッケージやソフトウェアでもWindowsに対応していないことはよくあるので、Github Copilotのありがたみを改めて強く感じました。
- MILPソルバーで問題が解けない時は、これまでは自分でメタヒューリスティクスを実装したり、問題分割を行うことが多かったのですが、今後はその前にこっちを試してみたいです。ただしおそらく近傍のオプションを使いこなすために、著者論文やマニュアルをもっと読み込んで勉強します。