見出し画像

CPLEXのPython APIでスケジューリング問題を解く！

moai-lab公式


1. 環境の準備とインストール

  • CPLEXのインストール
    まず、IBM ILOG CPLEX Optimization Studioを正式サイトまたは学術版からダウンロードし、インストールしてください。

  • Python環境の確認
    Python（CPLEXが対応しているバージョン）を用意し、pipまたは仮想環境を利用してください。
    また、docplexパッケージをインストールするには：

    1. pip install docplex
      として、DOcplex（特にCP Optimizer用）はpip経由で入れることができます（参考：[7],[9]）。

CPLEXも

pip install cplex
でインストールできます。

CPLEXのPython APIは、数学的最適化と制約プログラミングの両方のフレームワークを提供しています。具体的には以下のような種類の最適化問題を扱うことが可能です。

  • 線形計画問題 (LP)
    ・線形の目的関数と線形の制約条件からなる問題です。

  • 混合整数計画問題 (MIP/MILP)
    ・変数の一部または全部に整数制約をつけた線形計画問題。整数計画問題 (IP) や混合整数線形計画問題 (MILP) として解かれます。

  • 二次計画問題 (QP)
    ・目的関数が二次形式（ただし制約は線形）で表される問題です。

  • 二次制約付き計画問題 (QCP)
    ・制約条件に二次式が含まれる場合の問題で、特定の非線形性を扱います。

  • 制約プログラミング (CP)
    ・docplex.cpモジュールを用いることで、スケジューリングやルーティング、その他の組合せ最適化問題など、論理的・制約的記述が有効な問題を扱うことができます。

このように、CPLEXのPython APIは多様な問題形式に対応しており、用途に合わせて最適なソルバーエンジン（数学的プログラミング用のDOcplex.MPや制約プログラミング用のDOcplex.CP）を選ぶことで、幅広い最適化問題に柔軟に対応できます[

2. モデルの基本概念とCPLEXのスケジューリングAPI

  • スケジューリング問題の特徴
    スケジューリング問題では、各タスクやアクティビティの開始／終了時刻、持続時間、前後関係、資源の割当てなどを決定する必要があります。
    CPLEX CP Optimizerでは、間隔変数 (interval variables) を使い、各タスクのタイムウィンドウ（開始・終了・継続時間）をモデル化します。
    また、noOverlap や alternative といった組み込み関数を用いることで、作業者や機械での同時実行を防いだり、割当先を定めたりすることができます（参考：[6],[34]）。

  • DOcplex.cpの基本API
    DOcplex.cpでは、基本的なモデリングの流れは以下の通りです。

    • モデルのインスタンス生成
      from docplex.cp.model import CpoModel
      mdl = CpoModel()

    • 間隔変数の作成
      例：
      task = mdl.interval_var(size=duration, name="Task1")
      ※ここでdurationはタスクの所要時間

    • 前後関係（precedence）の制約
      例：
      mdl.add(mdl.end_before_start(task1, task2))

    • リソース割当てや同時実行禁止制約（noOverlap）
      例：
      mdl.add(mdl.no_overlap([task1, task2, task3]))

    • 目的関数の設定
      たとえば、全タスクの完了時刻の最小化など。

3. サンプルモデル：住宅建設のスケジューリング例

以下は、住宅建設のタスク（例：masonry, carpentry, roofing など）をスケジュールする基本的な例です。

from docplex.cp.model import CpoModel

# モデルの作成
mdl = CpoModel(name="House_Building_Scheduling")

# タスクごとの所要日数（例）
durations = {"masonry": 35, "carpentry": 15, "roofing": 5}

# 各タスクの間隔変数の作成
tasks = {}
for t, duration in durations.items():
    tasks[t] = mdl.interval_var(size=duration, name=t)

# 例：前後関係の制約
# masonryが完了してからcarpentryとroofingが開始される制約
mdl.add(mdl.end_before_start(tasks["masonry"], tasks["carpentry"]))
mdl.add(mdl.end_before_start(tasks["masonry"], tasks["roofing"]))

# 同一作業者の場合、複数タスクの同時実行を防ぐためのnoOverlap制約
# （ここでは例としてcarpentryとroofingに対して設定）
mdl.add(mdl.no_overlap([tasks["carpentry"], tasks["roofing"]]))

# 目的関数：全タスクの終了時刻の最小化（住宅完成日を最小化したい場合）
completion_time = mdl.max([mdl.end_of(tasks[t]) for t in tasks])
mdl.minimize(completion_time)

# 解く
solution = mdl.solve(TimeLimit=10)

# 結果の表示
for t in tasks:
    start_time = solution.get_var_solution(tasks[t]).get_start()
    end_time = solution.get_var_solution(tasks[t]).get_end()
    print(f"{t}: 開始 {start_time}, 終了 {end_time}")

print("全体の完了時刻:", solution.get_objective_value())

※このサンプルでは、タスク「masonry」が先に実行され、その後「carpentry」と「roofing」が実行される前提です。環境に応じて追加の制約（リソースの割当、期間制約、平行実行可能性など）を適宜追加してください（参考：[3],[4],[34]）。

4. モデルの実行と結果の確認

  • モデルの実行
    上記のPythonスクリプトを実行すると、DOcplex.cpが内部的に探索を行い、最適（または近似）のスケジュールを求めます。
    また solve() 関数の引数でタイムリミットや探索の詳細パラメータを設定可能です。

  • 結果の読み出し
    各タスクの開始／終了時刻は、solution.get_var_solution(タスク変数) を用いて取得可能です。
    また、全体の目的関数値（例では最終完了時刻）は solution.get_objective_value() で確認できます。

以下の結果が得られます。

! --------------------------------------------------- CP Optimizer 22.1.1.0 --
 ! Satisfiability problem - 4 variables, 3 constraints
 ! TimeLimit            = 10
 ! Initial process time : 0.00s (0.00s extraction + 0.00s propagation)
 !  . Log search space  : 4.8 (before), 4.8 (after)
 !  . Memory usage      : 407.9 kB (before), 407.9 kB (after)
 ! Using parallel search with 16 workers.
 ! ----------------------------------------------------------------------------
 !               Branches  Non-fixed    W       Branch decision
 *                      3  0.01s        1            -
 ! ----------------------------------------------------------------------------
 ! Search completed, 1 solution found.
 ! ----------------------------------------------------------------------------
 ! Number of branches     : 36
 ! Number of fails        : 0
 ! Total memory usage     : 5.6 MB (5.6 MB CP Optimizer + 0.0 MB Concert)
 ! Time spent in solve    : 0.01s (0.01s engine + 0.00s extraction)
 ! Search speed (br. / s) : 3600.0
 ! ----------------------------------------------------------------------------
masonry: 開始 0, 終了 35
carpentry: 開始 35, 終了 50
roofing: 開始 50, 終了 55
全体の完了時刻: 55

  • モデルの保存・可視化
    DOcplexにはソリューションをファイルに書き出す機能もあるため、後で可視化ツール（ガントチャートなど）に取り込むことも可能です（参考：[6],[34]）。

5. 参考情報

  • CPLEX公式ドキュメントやIBMのチュートリアル（例：[6]「Getting Started with Scheduling in CPLEX Studio」や[34]「Scheduling_Tutorial」）では、より複雑なスケジューリング問題（住宅建設、作業者割当、工場のジョブショップなど）の例が紹介されています。

  • また、Qiita等の技術ブログ（例：[1]、[2]）にはPythonからCPLEXを呼び出す方法や具体例が多数掲載されていますので、各種制約の記述方法やパラメータの設定方法など、実際の実装例として参考にしてください。

以上が、PythonからCPLEX（DOcplex.cp）を使用してスケジューリング問題を解くための基本的なマニュアルです。環境構築、モデル定式化、実行、結果確認の各フェーズを順次実施することで、各種スケジューリング問題に応用可能なモデルを作成・解くことができます。

Citations:
[1] https://yambi.hatenablog.com/entry/20160716/1468673454
[2] https://qiita.com/takamya/items/7087f58d769e1472ebf2
[3] https://qiita.com/spssfun2017/items/cd17002cfb5e919d179b
[4] https://qiita.com/Shaw0202/items/8e2c01a42075c4a61c6d
[5] https://github.com/ErayCakici/Machine-Scheduling-OPL-Examples_CP
[6] https://public.dhe.ibm.com/software/products/Decision_Optimization/docs/pdf/sched_gs.pdf
[7] https://www.ibm.com/docs/ja/watsonx/w-and-w/1.1.x?topic=optimization-ways-use-decision
[8] https://pypi.org/project/cplex/
[9] https://www.ibm.com/docs/ja/watsonx/saas?topic=optimization-ways-use-decision
[10] https://qiskit-community.github.io/qiskit-optimization/locale/ja_JP/getting_started.html
[11] https://qiita.com/Hiroskey/items/038704c5a80f4252e741
[12] https://b.hatena.ne.jp/entry/s/qiita.com/takamya/items/7087f58d769e1472ebf2
[13] https://dataplatform.cloud.ibm.com/docs/content/DO/WML_Deployment/DeployPythonClient.html?context=wx&locale=ja
[14] https://orsj.org/wp-content/corsj/or64-4/or64_4_238.pdf
[15] https://zenn.dev/hietan/books/c253d654c6cf66/viewer/8bce2b
[16] https://www.issoh.co.jp/tech/details/2756/
[17] https://zenn.dev/hietan/books/c253d654c6cf66
[18] https://web.tuat.ac.jp/~miya/ipmemo.html
[19] http://www.bunkyo.ac.jp/~hotta/lab/courses/2024/2024semi/24semi2_2.opt6-2ss.pdf
[20] https://dataplatform.cloud.ibm.com/docs/content/DO/DODS_Mdl_Assist/exhousebuild.html?locale=ja&context=cpdaas
[21] https://www.ibm.com/jp-ja/products/ilog-cplex-optimization-studio/cplex-optimizer
[22] https://www.edu.kobe-u.ac.jp/istc-tamlab/cspsat/pdf-open/cspsat2_seminar06_koshimura.pptx
[23] https://appmath.tus.ac.jp/cms/wp-content/uploads/2020/04/胡研究室.pdf
[24] https://www.cit.nihon-u.ac.jp/laboratorydata/kenkyu/kouennkai/reference/No.47/pdf/2-81.pdf
[25] https://www.nii.ac.jp/graduate/wp-content/themes/nii_original/assets/pdf/students_thesis/24/inui_Dr_thesis.pdf
[26] http://www.st.nanzan-u.ac.jp/info/gr-thesis/ms/2011/08mi056.pdf
[27] https://www.ibm.com/jp-ja/products/ilog-cplex-optimization-studio/cplex-cp-optimizer
[28] https://www.jstage.jst.go.jp/article/iscie/34/2/34_58/_pdf
[29] https://www.ibm.com/jp-ja/products/ilog-cplex-optimization-studio
[30] https://dl.ndl.go.jp/view/prepareDownload?itemId=info%3Andljp%2Fpid%2F8707267&contentNo=1
[31] https://msi-jp.com/hexaly/techinfo/2020.pdf
[32] https://community.ibm.com/community/user/ai-datascience/discussion/how-to-model-scheduling-problem-to-pick-stories-or-tasks-from-a-large-list-whose-story-points-sum-up-to-given-team-capacity-using-cplex-python-1
[33] https://qiita.com/makaishi2/items/f24daa097026a970ac9e
[34] https://ibmdecisionoptimization.github.io/tutorials/html/Scheduling_Tutorial.html
[35] https://www.ibm.com/docs/en/icos/22.1.1?topic=tutorials-python-tutorial
[36] https://dataplatform.cloud.ibm.com/docs/content/DO/DODS_Mdl_Assist/exhousebuild.html?context=wx&locale=ja
[37] https://www.ibm.com/docs/en/icos/22.1.1?topic=programming-scheduling-examples
[38] https://www.youtube.com/watch?v=uzTlbdbuXZU
[39] https://www.ibm.com/docs/ja/watsonx/saas?topic=optimization-decision-notebooks
[40] https://github.com/ErayCakici/Machine-Scheduling-DOCPLEX-Examples_CP/blob/main/ParallelMch_UnrelatedSeqDep.ipynb
[41] https://python-mip.readthedocs.io/en/latest/examples.html
[42] https://co-enzyme.fr/blog/multi-objective-employee-shift-scheduling-problem-ssp-in-opl-cplex/
[43] https://stackoverflow.com/questions/64723760/how-can-i-install-cplex-for-python-so-i-can-access-it-via-jupyter
[44] https://qiita.com/ssumika/items/b810b1102b8aae930da9
[45] https://qiskit-community.github.io/qiskit-optimization/locale/ja_JP/tutorials/11_using_classical_optimization_solvers_and_models.html
[46] https://qiita.com/ueduck8x/items/ab9492193bf48e29b5ea
[47] https://www.bunkyo.ac.jp/~hotta/lab/courses/2023/2023knw/23knw_4.pdf
[48] https://dataplatform.cloud.ibm.com/docs/content/DO/DODS_Introduction/configureEnvironments.html?locale=ja&context=cpdaas
[49] https://www.nurse-scheduling-software.com/japanese/nurse_scheduling_problem/chapter24/
[50] https://qiita.com/spssfun2017/items/b84c8ae30f010da8d73f
[51] https://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=17098&item_no=1&attribute_id=1&file_no=1
[52] https://www.jstage.jst.go.jp/article/isciesci/64/6/64_200/_pdf/-char/ja
[53] https://ibmdecisionoptimization.github.io/tutorials/html/Linear_Programming.html
[54] https://www.youtube.com/watch?v=mAZ0nVR372I
[55] https://deus-ex-machina-ism.com/?p=50658
[56] https://stackoverflow.com/questions/68202387/how-to-model-a-scheduling-problem-with-interruptible-tasks-using-docplex-cp-con

いいなと思ったら応援しよう！