自然言語のシフト要望をLLMで構造化し、OR-Toolsで最適化してみた。

Posted at 2025-12-29

TL;DR

「LLMは自然言語を構造化、ソルバは最適化を計算」 という役割分担の提案と、それを実装する具体的なやり方
自然言語のシフト要望 → LLM → JSON DSL → 制約変換 → OR-Tools というハイブリッドなシフト自動編成フローの全体像
1ヶ月のシフト最適化問題を題材にした、最適解までのDSL設計・制約モデリング・検証結果

読者層と前提知識

読者層

制約プログラミングや最適化問題に興味があるエンジニア
シフト管理などの最適化問題を扱う人
LLMと従来のソルバを組み合わせた実装に興味がある人

前提知識

制約プログラミング・LLM・Pythonに「ざっくり触れたことがある」程度の経験があると読みやすい想定です。

サンプルコードとGitHubリポジトリ

本記事で紹介する実装は、次のGitHubリポジトリにまとめています。

GitHub: beita-1024/llm-ortools-shift-scheduling

このリポジトリには、本記事で使っているサンプルコード一式を置いています（ざっくり構成は次のとおりです）。

notebooks/shift_optimization.ipynb：この記事と対応した検証用ノートブック
src/shift_solver/：LLMを呼び出すモジュールやJSON形式のDSLをOR-Toolsのモデルに変換して解くためのモジュールなど

本記事では、厳密な分類にはこだわらず、制約を満たしつつスコア（目的関数）を最適化してくれるソルバ全般を「制約ソルバ（あるいは制約・最適化ソルバ）」と呼びます。
この種のソルバは、たとえば次のような「割り当て・スケジューリング」系の問題でよく使われます。

シフト表・勤務表の自動編成
学校や塾の時間割作成
車両や配達ルートの割り当て（経路最適化）
工場の生産計画・ラインスケジューリング

制約ソルバを運用するには入力を構造化する必要がある。でもその入力を書くのがしんどい

多くの入門書や解説では、制約ソルバで解く問題を「変数 → 制約 → 目的関数」という3つの要素で説明しています。
（例：線形最適化のチュートリアル、CP-SAT のサンプル）

一方で実際には、解く対象の問題は、チャットやメールのような自然言語だけでなく、フォーム入力やExcelシート、既存業務システムの設定画面など、さまざまな形をとります。しかも「必須条件」と「希望」が混ざっています。

要件とソルバをいきなり直結するのは不可能で、その間に「制約ソルバへの入力を構造化する」工程が必ず必要になります。

ただ、ここで新たな問題が出てきます。その中間表現を、人間が手で書くのもしんどい。

そこで、LLMなら、自然言語から制約ソルバへの入力への翻訳を簡単にできるのではないか？ というのをシフト最適化を題材にやってみました。制約ソルバにはOR-Toolsを使います。OR-ToolsのCP-SATソルバは、制約プログラミングと最適化の両方に対応しており、Pythonから使いやすく、シフト最適化のような組み合わせ最適化問題に適しているためです。

アプローチ

入力を構造化する方法には、フォーム入力やExcelシートなども選択肢として考えられますが、本記事ではJSON形式のDSLを採用しました。主な理由は以下の通りです。

安全性: execを使わないため、コード実行まわりのセキュリティリスクを抑えられる
扱いやすさ: JSONは構造化されており、デバッグ時も対応関係の整理も容易
拡張性: 将来ソルバを差し替えたり、フォームなどのUIを追加したりするのも容易

DSLの例

DSLの仕様は、こんな感じでやることにしました。

自然言語での要望例

「Tanakaは2/3（月）は必ず休みたい。Suzukiは2/1（土）はできれば入りたい。
個人ごとの勤務日数は、Tanaka：3〜5日、Suzuki：3〜5日。
平日は各日ちょうど2人必要。」

これが以下のDSLに対応する感じです（簡略化した例。完全な例は後述の「DSLの仕様」セクションを参照）。

{
  "members": [
    { "id": "tanaka", "name": "Tanaka", "projects": [] },
    { "id": "suzuki", "name": "Suzuki", "projects": [] }
  ],
  "requests": [
    {
      "member_id": "tanaka",
      "type": "must_off",
      "day_id": "2025-02-03"
    },
    {
      "member_id": "suzuki",
      "type": "prefer_work",
      "day_id": "2025-02-01"
    }
  ],
  "constraints": [
    {
      "type": "member_total_days_range",
      "member_id": "tanaka",
      "min": 3,
      "max": 5
    },
    {
      "type": "member_total_days_range",
      "member_id": "suzuki",
      "min": 3,
      "max": 5
    },
    {
      "type": "day_required_staff_range",
      "day_pattern": "weekday",
      "min": 2,
      "max": 2
    }
  ]
}

このJSON形式のDSLをOR-Toolsの制約に変換して解くことで、最適解を計算します。
詳細な仕様と完全な例は、後述の「DSLの仕様」セクションで説明します。

LLMによる変換

自然言語から解までの全体の流れは、こんな感じです。

自然言語の制約（例: Tanakaは月曜日は必ず休みたい）
↓
LLM（GPT-5-mini）
↓
JSON形式のDSL（構造化された制約）
↓
制約変換（DSLをOR-Toolsの制約に変換）
↓
OR-Tools（CP-SATソルバ）
↓
解（シフト表）

プロンプト設計

プロンプトは、こんな感じです。

PROMPT_TEMPLATE = """以下の自然言語で記述されたシフト制約を、JSON形式に変換してください。

制約の内容を正確に理解し、以下のJSONスキーマに従って出力してください。

JSONスキーマ:
{{
  "period": {{ "start": "YYYY-MM-DD", "end": "YYYY-MM-DD" }},
  "days": [...],
  "members": [...],
  "requests": [...],
  "constraints": [...],
  "optimization": {{ "type": "weighted_requests", "weights": {{...}} }}
}}

制約の説明:
- must_off: 絶対に休みたい（ハード制約）
- prefer_off: できれば休みたい（ソフト制約）
- member_total_days_range: 個人の勤務日数レンジ
...

自然言語の制約:
{constraints_text}

JSON形式で出力してください。JSON以外のテキストは含めないでください。
"""

変換プロセス

LLMによる変換は、こんな感じにしました。

自然言語で書かれた制約テキストから、JSONスキーマや制約タイプの説明を含むプロンプト文字列を組み立てる。
組み立てたプロンプトを使って、ChatOpenAI で LLM API を呼び出す。
レスポンスとして返ってきた文字列から、JSON部分（コードブロックを含む場合は除去）を取り出す。
取り出したJSON文字列を json.loads でパースし、Pythonの辞書オブジェクトに変換する。
Pydanticモデル（ShiftProblem）でバリデーションし、内部表現として扱えるDSLオブジェクトにする。

DSLの仕様

詳細な仕様と完全な例は、こんな感じにしました。

要望の種類
- requests[] の type が
  - must_off（絶対休みたい）
  - prefer_off（できれば休みたい）
  - prefer_work（できれば入りたい）
仕事の制約
- 人単位の勤務日数レンジ
  - type: "member_total_days_range"
- 月の稼働勤務レンジ（全体）
  - type: "team_total_days_range"
- 各日・各スロットの必要人数
  - type: "day_required_staff_range"
    - day_pattern に "weekday" / "weekend" を指定
- 各人の連勤の上限
  - type: "member_max_consecutive_days"
プロジェクト・納期の制約
- スタッフごとの所属プロジェクト（タグ）
  - members[].projects
- プロジェクトごとの必要工数（人日）
  - type: "project_required_man_days"
- 特定の人に対する定例・イベント
  - type: "member_must_work_on_day"
日付情報
- days[] の weekday / tags で
  平日・週末・イベントなどを表現
最適化の設定
- optimization ブロック内で
  - prefer_off = 2点
  - prefer_work = 1点
    などを指定

例：以下の３人１週間の制約

対象期間は 2025/02/01（土）〜 2025/02/07（金） の1週間です。
土日（2/1・2/2）は週末扱い、それ以外（2/3〜2/7）は平日として扱います。
スタッフは3名です。
- Tanaka：プロジェクトA所属
- Suzuki：プロジェクトA・B所属
- Yamada：プロジェクトB所属
スタッフからの希望は次の通りです。
- Tanaka
  - 2/3（月）は 必ず休みたい（子どもの行事のため）
  - 2/6（木）は できれば休みたい
- Suzuki
  - 2/1（土）は できれば入りたい
個人ごとの勤務日数は、次の範囲に収めてください。
- Tanaka：3〜5日
- Suzuki：3〜5日
- Yamada：2〜4日
全メンバー全体の 合計勤務日数 は、8〜12日 の範囲にしてください。
各日の必要人数は次の通りです。
- 平日（2/3〜2/7）：各日ちょうど2人 必要
- 週末（2/1・2/2）：各日1〜2人
連勤の上限は次の通りです。
- Tanaka：最大 3連勤 まで
- Suzuki：最大 3連勤 まで
- Yamada：最大 2連勤 まで
プロジェクトごとの今週の必要工数（人日）は次の通りです。
- プロジェクトA：合計5人日以上 アサインしてください。
- プロジェクトB：合計3人日以上 アサインしてください。
Suzuki は 2/4（火）に必ず出勤 としてください。（週次定例MTGのため）
最適化の方針は次の通りです。
- 「できれば休みたい」希望が叶ったら +2点
- 「できれば入りたい」希望が叶ったら +1点
- すべてのハード制約を満たしたうえで、合計点が最大になるシフト案 を採用します。

{
  "period": {
    "start": "2025-02-01",
    "end": "2025-02-07"
  },

  "days": [
    { "id": "2025-02-01", "weekday": "Sat", "tags": ["weekend"] },
    { "id": "2025-02-02", "weekday": "Sun", "tags": ["weekend"] },
    { "id": "2025-02-03", "weekday": "Mon", "tags": ["weekday"] },
    { "id": "2025-02-04", "weekday": "Tue", "tags": ["weekday"] },
    { "id": "2025-02-05", "weekday": "Wed", "tags": ["weekday"] },
    { "id": "2025-02-06", "weekday": "Thu", "tags": ["weekday"] },
    { "id": "2025-02-07", "weekday": "Fri", "tags": ["weekday"] }
  ],

  "members": [
    {
      "id": "tanaka",
      "name": "Tanaka",
      "projects": ["A"]
    },
    {
      "id": "suzuki",
      "name": "Suzuki",
      "projects": ["A", "B"]
    },
    {
      "id": "yamada",
      "name": "Yamada",
      "projects": ["B"]
    }
  ],

  "requests": [
    {
      "member_id": "tanaka",
      "type": "must_off",
      "day_id": "2025-02-03",
      "reason": "子どもの行事"
    },
    {
      "member_id": "tanaka",
      "type": "prefer_off",
      "day_id": "2025-02-06"
    },
    {
      "member_id": "suzuki",
      "type": "prefer_work",
      "day_id": "2025-02-01"
    }
  ],

  "constraints": [
    {
      "type": "member_total_days_range",
      "member_id": "tanaka",
      "min": 3,
      "max": 5
    },
    {
      "type": "member_total_days_range",
      "member_id": "suzuki",
      "min": 3,
      "max": 5
    },
    {
      "type": "member_total_days_range",
      "member_id": "yamada",
      "min": 2,
      "max": 4
    },

    {
      "type": "team_total_days_range",
      "min": 8,
      "max": 12
    },

    {
      "type": "day_required_staff_range",
      "day_pattern": "weekday",
      "min": 2,
      "max": 2
    },
    {
      "type": "day_required_staff_range",
      "day_pattern": "weekend",
      "min": 1,
      "max": 2
    },

    {
      "type": "member_max_consecutive_days",
      "member_id": "tanaka",
      "max": 3
    },
    {
      "type": "member_max_consecutive_days",
      "member_id": "suzuki",
      "max": 3
    },
    {
      "type": "member_max_consecutive_days",
      "member_id": "yamada",
      "max": 2
    },

    {
      "type": "project_required_man_days",
      "project": "A",
      "min_man_days": 5
    },
    {
      "type": "project_required_man_days",
      "project": "B",
      "min_man_days": 3
    },

    {
      "type": "member_must_work_on_day",
      "member_id": "suzuki",
      "day_id": "2025-02-04",
      "label": "週次定例MTG"
    }
  ],

  "optimization": {
    "type": "weighted_requests",
    "weights": {
      "prefer_off": 2,
      "prefer_work": 1
    }
  }
}

扱う問題

ある期間の日単位のスタッフのアサインを決める問題を扱うことにしました。

■ 要望の種類（スタッフ側）

絶対に休みたい
- 例：病院、子どもの行事など
できれば休みたい（ソフト制約）
できれば入りたい（ソフト制約）

■ 仕事の制約（働き方ルール）

人単位の勤務日数レンジ
- 例：その月に 10〜20 日の範囲で勤務
月の稼働勤務レンジ（全体）
- 全メンバー全体で何人日くらい稼働させたいか
各日・各スロットの必要人数
- 例：平日は3人、土日は2人必須、など
各人の連勤の上限
- 例：最大3連勤まで

■ プロジェクト・納期の制約

スタッフごとの所属プロジェクト（タグ）
- 例：Aプロジェクト / Bプロジェクトなど
プロジェクトごとの必要工数（人日）
- 例：今月はAプロジェクトに 20人日以上アサイン
特定の人に対する定例・イベント
- 例：毎週火曜はAさんを必ず勤務（定例MTG対応）

■ 日付情報

各日の曜日情報（自動）
- 例：平日・土日・祝日などのラベル付け用

■ 最適化の設定

ソフト要望の種類ごとに点数を設定する。
- 「できれば休みたい」が叶った： +2 点
- 「できれば入りたい」が叶った： +1 点

実装の流れ

実装は、こんな感じで進めました。

問題の範囲と表現力の決定
- シフト最適化問題で扱う制約の種類を決定
DSLの設計
- JSON形式のDSLの入力・出力形式を定義
- シフト最適化に必要な情報（スタッフ、日付、制約、希望など）を構造化
制約ソルバへの変換処理の実装
- DSLを読み込み、OR-Toolsの制約に落とし込む処理を実装
解の出力処理の実装
- 制約ソルバが返した解を、JSON形式で出力する処理を実装
プロンプト設計
- 自然言語からDSLへの変換を正確に行うためのプロンプトを設計
LLM API連携の実装
- 設計したプロンプトを使ってLLM APIを呼び出す処理を実装
結果描画の実装
- JSON形式の解を、表形式などで視覚的に表示する処理を実装

システムの構成

システムはPythonで実装し、以下の流れで構成しました。

自然言語の制約
↓
LLM→DSL変換モジュール（llm_converter.py）
↓
JSON形式のDSL
↓
JSON解釈・制約ソルバ入力モジュール（constraint_builder.py）
↓
OR-Tools（CP-SATソルバ）
↓
解の出力モジュール（solution_output.py）
↓
JSON形式の解
↓
結果描画モジュール（visualizer.py）
↓
シフト表

問題の定式化

ここからは、LLMが生成したJSON形式のDSLが、どのような数理モデルとして解釈されるか（意味論） をこんな感じに整理しました。実装は src/shift_solver/constraint_builder.py にあります。

大まかな流れは次の通りです。

決定変数（誰がどの日に入るか）を定義する。
JSONの days / members / tags から集合 (M, D, D_{\text{tag}}) を作る。
constraints[*].type ごとに「JSON → 数式テンプレ」にマッピングする。
ソフトな希望は、目的関数として重み付き和で表現する。

そのうえで、この数理モデルを OR-Tools のCP-SATソルバに流し込みます。

OR-Toolsの基本的な使い方

OR-Toolsで制約プログラミング問題を解くには、2つの主要なオブジェクトを使います。

CpModel(): 制約モデルを構築するオブジェクト。決定変数の作成、制約の追加、目的関数の設定を行う
CpSolver(): 構築したモデルを解くソルバー。Solve()メソッドで最適解を探索する

実装では、初期化時にこれらを作成します。

self.model = cp_model.CpModel()  # モデル構築用
self.solver = cp_model.CpSolver()  # ソルバー

以降、self.modelに対して決定変数や制約を追加し、最後にself.solver.Solve(self.model)で解を求めます。
（詳細な使い方はOR-Tools公式ドキュメントを参照してください）

決定変数

各メンバー $m \in M$ と各日 $d \in D$ に対して、以下の2値変数を定義します。

$$x_{m,d} \in {0, 1}$$

ここで、$x_{m,d} = 1$ はメンバー $m$ が日 $d$ に勤務することを、$x_{m,d} = 0$ は休みであることを表します。

OR-Toolsでは、各メンバーと各日の組み合わせに対して2値変数（ブール変数）を作成します。以下は実装例です。

# 決定変数: work[day_idx][member_idx]
# メンバーがその日に勤務してたら1、そうでないなら0
num_days = len(problem.days)
num_members = len(problem.members)
self.work = {}
for day_idx in range(num_days):
    for member_idx in range(num_members):
        self.work[day_idx, member_idx] = self.model.NewBoolVar(
            f"work_day{day_idx}_member{member_idx}"
        )

このように、決定変数は $x_{m,d}$ だけという非常にシンプルな構造になっています。すべての制約や目的関数は、この変数の組み合わせで表現されます。

ハード制約

1. 各日の必要人数制約

各日 $d$ に対して、必要人数の範囲（下限$\ell_d$、上限$u_d$）を満たす必要があります。

$$\ell_d \leq \sum_{m \in M} x_{m,d} \leq u_d$$

特に、「平日」タグ付き日集合 $D_{\texttt{weekday}}$ や「週末」タグ付き日集合 $D_{\texttt{weekend}}$ に対しては。

$$\forall d \in D_{\texttt{weekday}}: \ell_{\texttt{weekday}} \leq \sum_{m \in M} x_{m,d} \leq u_{\texttt{weekday}}$$

$$\forall d \in D_{\texttt{weekend}}: \ell_{\texttt{weekend}} \leq \sum_{m \in M} x_{m,d} \leq u_{\texttt{weekend}}$$

ここで、$D_{\texttt{weekday}}$ は平日の集合、$D_{\texttt{weekend}}$ は週末の集合です。$\ell_{\texttt{weekday}}, u_{\texttt{weekday}}$ は平日の必要人数レンジで、これらはJSON DSLの constraints[].min, constraints[].max から取得される定数です。同様に、$\ell_{\texttt{weekend}}, u_{\texttt{weekend}}$ は週末の必要人数レンジで、JSON DSLの constraints[].min, constraints[].max から取得されます。

各日の必要人数制約を実装するには、該当するパターン（平日・週末など）の日をフィルタし、その日の人数合計に対して最小値・最大値を設定します。以下は実装例です。

def _add_day_required_staff_range(self, constraint: DayRequiredStaffRange):
    """各日の必要人数レンジ制約"""
    num_members = len(self.problem.members)

    # 該当するパターンの日を取得
    target_days = []
    for day in self.problem.days:
        if constraint.day_pattern == "weekday" and self._is_weekday(day.id):
            target_days.append(day.id)
        elif constraint.day_pattern == "weekend" and self._is_weekend(day.id):
            target_days.append(day.id)

    # 各日について、必要人数の制約を追加
    for day_id in target_days:
        day_idx = self._get_day_idx(day_id)
        staff_count = sum(
            self.work[day_idx, member_idx] for member_idx in range(num_members)
        )
        self.model.Add(staff_count >= constraint.min)
        self.model.Add(staff_count <= constraint.max)

2. 個人の勤務日数レンジ

各メンバー $m$ に対して、勤務日数が指定範囲内である必要があります。

$$\ell_m \leq \sum_{d \in D} x_{m,d} \leq u_m$$

ここで、$\ell_m, u_m$ はメンバー $m$ の勤務日数の下限と上限で、これらはJSON DSLの constraints[].min, constraints[].max から取得される定数です。

実装では、メンバーごとに勤務日の合計を取り、その合計に対して min / max を当てています。

def _add_member_total_days_range(self, constraint: MemberTotalDaysRange):
    """個人の勤務日数レンジ制約"""
    member_idx = self._get_member_idx(constraint.member_id)
    num_days = len(self.problem.days)

    # そのメンバーの総勤務日数
    total_days = sum(
        self.work[day_idx, member_idx] for day_idx in range(num_days)
    )

    self.model.Add(total_days >= constraint.min)
    self.model.Add(total_days <= constraint.max)

3. 全メンバー全体の勤務日数レンジ

全メンバー全体の合計勤務日数が指定範囲内である必要があります。

$$\ell_{\text{team}} \leq \sum_{m \in M} \sum_{d \in D} x_{m,d} \leq u_{\text{team}}$$

ここで、$\ell_{\text{team}}, u_{\text{team}}$ は全メンバー全体の合計勤務日数の下限と上限で、これらはJSON DSLの constraints[].min, constraints[].max から取得される定数です。

実装では、全メンバー・全日について勤務変数を二重ループで合計し、その合計に対して min / max を当てています。

def _add_team_total_days_range(self, constraint: TeamTotalDaysRange):
    """全メンバー全体の勤務日数レンジ制約"""
    num_days = len(self.problem.days)
    num_members = len(self.problem.members)
    
    # 全メンバー全体の総勤務日数
    total_days = sum(
        self.work[day_idx, member_idx]
        for day_idx in range(num_days)
        for member_idx in range(num_members)
    )

    self.model.Add(total_days >= constraint.min)
    self.model.Add(total_days <= constraint.max)

4. 連勤の上限

各メンバー $m$ に対して、連続勤務日数が上限 $k_m$ を超えないようにします。
これは、任意の連続する $k_m+1$ 日間において、すべて勤務することはできないという制約として表現できます。

$$\forall m \in M, \forall i \in {0, 1, \ldots, |D| - 1}: \text{if } i + k_m < |D| \text{ then } \sum_{j=i}^{i+k_m} x_{m,d_j} \leq k_m$$

ここで、$d_j$ は $j$ 番目の日を表します。$k_m$ はメンバー $m$ の最大連勤日数で、これはJSON DSLの constraints[].max から取得される定数です。この制約により、任意の開始日 $i$ から連続する $k_m+1$ 日間において、すべて勤務することはできません（つまり、$k_m+1$ 日連続する期間には少なくとも1日は休む必要があります）。

実装では、各メンバー・各開始日について長さ max+1 の窓を取り、その窓の合計が max を超えないようにしています。

def _add_member_max_consecutive_days(self, constraint: MemberMaxConsecutiveDays):
    """連勤の上限制約"""
    member_idx = self._get_member_idx(constraint.member_id)
    num_days = len(self.problem.days)

    # 各開始日について、連続して勤務する日数をチェック
    for start_day_idx in range(num_days):
        consecutive_days = []
        for offset in range(constraint.max + 1):
            if start_day_idx + offset < num_days:
                consecutive_days.append(
                    self.work[start_day_idx + offset, member_idx]
                )

        # max+1日連続して勤務しない = 少なくとも1日は休む
        if len(consecutive_days) == constraint.max + 1:
            self.model.Add(sum(consecutive_days) <= constraint.max)

5. 「必ず休みたい」希望（ハード制約）

メンバー $m$ が日 $d$ に必ず休みたい場合。

$$x_{m,d} = 0$$

「必ず休みたい」希望を実装するには、該当するメンバーと日の組み合わせに対して、勤務変数を 0 に固定します。以下は実装例です。

def add_hard_constraints(self):
    """ハード制約を追加"""
    # must_offリクエスト: 絶対に休みたい
    for request in self.problem.requests:
        if request.type == "must_off":
            self._add_member_must_off(request)

def _add_member_must_off(self, request: Request):
    """特定日の必須休暇制約"""
    day_idx = self._get_day_idx(request.day_id)
    member_idx = self._get_member_idx(request.member_id)
    self.model.Add(self.work[day_idx, member_idx] == 0)

6. 特定日の必須勤務制約（業務上の制約）

業務上の理由（定例MTG、定例会議など）により、メンバー $m$ が日 $d$ に必ず勤務する必要がある場合。

$$x_{m,d} = 1$$

特定日の必須勤務制約を実装するには、該当するメンバーと日の組み合わせに対して、勤務変数を 1 に固定します。これはスタッフ個人の要望（できれば入りたい）ではなく、業務上の必須要件として扱われます。以下は実装例です。

def _add_member_must_work_on_day(self, constraint: MemberMustWorkOnDay):
    """特定日の必須勤務制約"""
    day_idx = self._get_day_idx(constraint.day_id)
    member_idx = self._get_member_idx(constraint.member_id)
    self.model.Add(self.work[day_idx, member_idx] == 1)

7. プロジェクト必要工数

プロジェクト $p$ に所属するメンバーの集合を $M_p$ とすると、プロジェクト $p$ の必要工数は。

$$\sum_{m \in M_p} \sum_{d \in D} x_{m,d} \geq \text{min_man_days}_p$$

ここで、$\text{min_man_days}_p$ はプロジェクト $p$ の必要工数の下限で、これはJSON DSLの constraints[].min_man_days から取得される定数です。

実装では、プロジェクトに所属するメンバーだけをフィルタし、その人たちの勤務日数を合計して下限を課しています。

def _add_project_required_man_days(self, constraint: ProjectRequiredManDays):
    """プロジェクトごとの必要工数制約"""
    num_days = len(self.problem.days)

    # そのプロジェクトに所属するメンバーのインデックス
    project_members = [
        idx for idx, member in enumerate(self.problem.members)
        if constraint.project in member.projects
    ]

    # プロジェクトの総人日数
    total_man_days = sum(
        self.work[day_idx, member_idx]
        for day_idx in range(num_days)
        for member_idx in project_members
    )

    self.model.Add(total_man_days >= constraint.min_man_days)

目的関数（ソフト制約の最大化）

ソフト制約を満たすことで得られるスコアを最大化します。

OR-Toolsでソフト制約を実装するには、以下のアプローチを使います。

中間変数の作成: 各ソフト制約に対して、それが満たされたかどうかを表すブール変数を作成
条件付き制約: OnlyEnforceIf() を使って、「条件が満たされたときだけ中間変数が1になる」という制約を追加
目的関数の設定: 中間変数に重みを掛けた和を model.Maximize() で最大化

これにより、「できれば満たしたい」という希望を、目的関数として表現できます。

「できれば休みたい」希望が叶った場合のスコアを $w_{\text{off}}$、「できれば入りたい」希望が叶った場合のスコアを $w_{\text{work}}$ とすると、目的関数は。

$$\max \sum_{(m,d) \in R_{\text{prefer_off}}} w_{\text{off}} \cdot (1 - x_{m,d}) + \sum_{(m,d) \in R_{\text{prefer_work}}} w_{\text{work}} \cdot x_{m,d}$$

ここで、$R_{\text{prefer_off}}$ は「できれば休みたい」希望の集合、$R_{\text{prefer_work}}$ は「できれば入りたい」希望の集合です。$w_{\text{off}}, w_{\text{work}}$ は重みで、これらはJSON DSLの optimization.weights.prefer_off, optimization.weights.prefer_work から取得される定数です。

本記事では、$w_{\text{off}} = 2$、$w_{\text{work}} = 1$ と設定します（「できれば休みたい」希望を「できれば入りたい」希望より優先する設定）。

実装では、まず prefer_off / prefer_work ごとにソフト制約用のブール変数を立て、
それらに重みを掛けた和を最大化することで、上記の目的関数と同等の挙動を実現しています。

実装では、処理を2つのステップに分離しています。

ソフト制約の追加: 各ソフト制約に対して、満たされたかどうかを表す中間変数（0/1）を作成。重みはここでは設定しない。
目的関数の設定: 中間変数に重みを掛けて、その和を最大化する目的関数を設定。

この分離により、重みを変更してもソフト制約の追加処理を変更する必要がありません。

def add_soft_constraints(self):
    """ソフト制約（最適化目標）を追加
    
    各ソフト制約に対して、満たされたかどうかを表す中間変数（0/1）を作成します。
    重みはここでは設定せず、set_objective()で適用されます。
    この分離により、重みを変更してもこのメソッドを変更する必要がありません。
    """
    # prefer_off, prefer_workリクエストをソフト制約として追加
    for request in self.problem.requests:
        if request.type in ["prefer_off", "prefer_work"]:
            day_idx = self._get_day_idx(request.day_id)
            member_idx = self._get_member_idx(request.member_id)

            # ソフト制約用の変数を作成
            var_name = f"soft_{request.type}_{request.member_id}_{request.day_id}"
            soft_var = self.model.NewBoolVar(var_name)
            self.soft_vars[var_name] = soft_var

            if request.type == "prefer_off":
                # 休みたい = work == 0 の場合にスコア
                self.model.Add(soft_var == 1).OnlyEnforceIf(
                    self.work[day_idx, member_idx].Not()
                )
                self.model.Add(soft_var == 0).OnlyEnforceIf(
                    self.work[day_idx, member_idx]
                )
            elif request.type == "prefer_work":
                # 入りたい = work == 1 の場合にスコア
                self.model.Add(soft_var == 1).OnlyEnforceIf(
                    self.work[day_idx, member_idx]
                )
                self.model.Add(soft_var == 0).OnlyEnforceIf(
                    self.work[day_idx, member_idx].Not()
                )

def set_objective(self):
    """目的関数を設定
    
    add_soft_constraints()で作成した中間変数（0/1）に重みを掛けて、
    その和を最大化する目的関数を設定します。
    """
    # 重み付きスコアを最大化
    weights = self.problem.optimization.weights

    objective_terms = []
    for var_name, soft_var in self.soft_vars.items():
        if "prefer_off" in var_name:
            weight = weights.get("prefer_off", 0)
        elif "prefer_work" in var_name:
            weight = weights.get("prefer_work", 0)
        else:
            weight = 0

        if weight > 0:
            objective_terms.append(soft_var * weight)

    if objective_terms:
        self.model.Maximize(sum(objective_terms))

制約プログラミングとしての表現

上記の制約と目的関数を、OR-ToolsのCP-SATソルバなどの制約プログラミングソルバに入力することで、最適解を求めることができます。

JSON / 数式 / OR-Toolsコードの対応（代表例）

ここまでの「JSON → 集合／変数 → 数式」は、最終的に OR-Tools のコードに落ちます。
代表的な3種類について、対応関係を表形式で示します（詳細な実装は「問題の定式化」セクションを参照）。

制約タイプ	JSON	数式	OR-Toolsコード（要点）
`day_required_staff_range` （平日・週末ごとの人数レンジ）	`json<br>{ "type": "day_required_staff_range",<br> "day_pattern": "weekday",<br> "min": 2, "max": 2 }<br>`	$\forall d \in D_{\texttt{weekday}}:$ $2 \le \sum_{m \in M} x_{m,d} \le 2$	該当日をフィルタし、 `model.Add(staff_count >= min)` `model.Add(staff_count <= max)`
`member_total_days_range` （メンバーごとの勤務日数レンジ）	`json<br>{ "type": "member_total_days_range",<br> "member_id": "tanaka",<br> "min": 3, "max": 5 }<br>`	$3 \le \sum_{d \in D} x_{\text{tanaka}, d} \le 5$	メンバーごとに勤務日数を合計し、 `model.Add(total_days >= min)` `model.Add(total_days <= max)`
`member_max_consecutive_days` （最大連勤制約）	`json<br>{ "type": "member_max_consecutive_days",<br> "member_id": "suzuki",<br> "max": 3 }<br>`	$\forall d \in D:$ $\sum_{k=0}^{3} x_{\text{suzuki}, d+k} \le 3$	各開始日について長さ`max+1`の窓を取り、 `model.Add(sum(window) <= max)`

他の制約タイプ（プロジェクト工数、must_off など）も、同じように「JSON → 数式テンプレ → OR-Tools の Add(...)」という三段階で落とし込んでいます。

出力形式

まずは、LLMに渡しやすくて、記事にも載せやすい最小構成です。

{
  "status": "optimal", 
  "objective_score": 9,

  "assignments": [
    { "day_id": "2025-02-01", "member_id": "suzuki",   "work": true  },
    { "day_id": "2025-02-01", "member_id": "tanaka", "work": false },
    { "day_id": "2025-02-01", "member_id": "yamada", "work": false },

    { "day_id": "2025-02-02", "member_id": "tanaka", "work": true  },
    { "day_id": "2025-02-02", "member_id": "suzuki",   "work": false },
    { "day_id": "2025-02-02", "member_id": "yamada", "work": true  },

    { "day_id": "2025-02-03", "member_id": "tanaka", "work": false }, 
    ...
  ],

  "request_results": [
    {
      "member_id": "tanaka",
      "type": "must_off",
      "day_id": "2025-02-03",
      "satisfied": true,
      "reason": "子どもの行事"
    },
    {
      "member_id": "tanaka",
      "type": "prefer_off",
      "day_id": "2025-02-06",
      "satisfied": false
    },
    {
      "member_id": "suzuki",
      "type": "prefer_work",
      "day_id": "2025-02-01",
      "satisfied": true
    }
  ]
}

フィールドの意味

status
- "optimal" / "feasible" / "infeasible" など
objective_score
- 「できれば休みたい」＋「できれば入りたい」の重み付き合計点
assignments
- 日×人ごとに、その人がその日入っているかどうか
  （この形だと後から表形式にも変換しやすい）
request_results
- 入力の requests[] に対して、
  - satisfied: true/false を付けたもの
  - reason: string | null で要望の理由を保持（入力のrequests[].reasonから継承）

表示形式

日付	曜日	配置メンバー
2025-02-01	土	Suzuki
2025-02-02	日	Tanaka, Yamada
2025-02-03	月	Suzuki, Yamada
…	…	…

検証結果

検証問題の設定

実際の検証として、以下のような1ヶ月間のシフト最適化問題を解きました。

対象期間: 2026/02/01（日）〜 2026/02/28（土）の1ヶ月間

スタッフ構成（5名）:

Tanaka：プロジェクトA所属
Suzuki：プロジェクトA・B所属
Yamada：プロジェクトB所属
Sato：プロジェクトB・C所属
Watanabe：プロジェクトC所属

スタッフからの希望:

Tanaka：「毎週月曜日はできれば休みたい。2/3（火）は必ず休みたい。2/13（金）はできれば休みたい」
Suzuki：「毎週火曜日は必ず出勤したい。毎週金曜日はできれば入りたい。2/11（水）はできれば休みたい。2/22（日）は必ず休みたい」
Yamada：「毎週水曜日は必ず出勤したい。毎週日曜日はできれば休みたい。2/9（月）は必ず休みたい。2/15（日）はできれば入りたい」
Sato：「毎週木曜日はできれば入りたい。毎週土曜日はできれば休みたい。2/5（木）は必ず休みたい。2/20（金）はできれば入りたい」
Watanabe：「毎週金曜日はできれば入りたい。毎週月曜日はできれば休みたい。2/12（木）はできれば休みたい。2/25（水）はできれば入りたい」

制約条件:

個人ごとの勤務日数：Tanaka 10〜15日、Suzuki 12〜18日、Yamada 10〜15日、Sato 11〜16日、Watanabe 10〜15日
全メンバー全体の合計勤務日数：55〜70日
各日の必要人数：平日は各日ちょうど3人、週末は各日0〜1人
連勤の上限：Tanaka 最大5連勤、Suzuki 最大4連勤、Yamada 最大5連勤、Sato 最大5連勤、Watanabe 最大5連勤
プロジェクト必要工数：プロジェクトA 20人日以上、プロジェクトB 18人日以上、プロジェクトC 15人日以上

最適化方針:

「できれば休みたい」希望が叶ったら +2点
「できれば入りたい」希望が叶ったら +1点
すべてのハード制約を満たしたうえで、合計点が最大になるシフト案を採用

検証結果

このツール（LLM（GPT-5-mini） + OR-Tools）で解いた結果、解の状態は optimal、目的関数の値は 48 となりました。

最終的に得られたシフト表は、次のとおりです。

日付	曜日	配置メンバー
2026-02-01	Sun	Watanabe
2026-02-02	Mon	Suzuki, Yamada, Sato
2026-02-03	Tue	Suzuki, Sato, Watanabe
2026-02-04	Wed	Yamada, Sato, Watanabe
2026-02-05	Thu	Tanaka, Suzuki, Watanabe
2026-02-06	Fri	Suzuki, Yamada, Watanabe
2026-02-07	Sat	Watanabe
2026-02-08	Sun	Sato
2026-02-09	Mon	Suzuki, Sato, Watanabe
2026-02-10	Tue	Suzuki, Sato, Watanabe
2026-02-11	Wed	Yamada, Sato, Watanabe
2026-02-12	Thu	Tanaka, Suzuki, Sato
2026-02-13	Fri	Suzuki, Yamada, Watanabe
2026-02-14	Sat	なし
2026-02-15	Sun	Yamada
2026-02-16	Mon	Suzuki, Yamada, Sato
2026-02-17	Tue	Tanaka, Suzuki, Yamada
2026-02-18	Wed	Tanaka, Suzuki, Yamada
2026-02-19	Thu	Tanaka, Yamada, Sato
2026-02-20	Fri	Suzuki, Sato, Watanabe
2026-02-21	Sat	Tanaka
2026-02-22	Sun	なし
2026-02-23	Mon	Suzuki, Yamada, Sato
2026-02-24	Tue	Tanaka, Suzuki, Yamada
2026-02-25	Wed	Tanaka, Yamada, Watanabe
2026-02-26	Thu	Tanaka, Suzuki, Sato
2026-02-27	Fri	Suzuki, Yamada, Watanabe
2026-02-28	Sat	Tanaka

考察：DSL変換の面倒さをLLMに任せると、制約ソルバが使いやすくなる

検証結果から、次のような示唆が得られました。

LLMによるDSL変換は機能する

このツールでは、自然言語の要望をLLM（GPT-5-mini）がJSON形式のDSLに変換し、それをOR-Toolsの制約に変換して解くことで、最適解を導出できました。処理時間は全体で約1分40秒で、そのほぼ全てがLLM呼び出し時間（OR-Tools側は計測上ほぼ0秒＝誤差レベル）でした。

「自然言語の要望を制約ソルバへの入力（今回はJSON形式のDSL）に落とし込む」という面倒な作業をLLMに任せることで、制約ソルバがより簡単に使えるようになるということが分かりました。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up