📑

LLMと数理最適化を組み合わせる

ohtaman

2024/12/09に公開

本エントリはUbie 生成AI Advent Calendar 2024 の9日目の記事です。LLMの進化が目覚ましいですが、現状ではLLM単体では対応が難しい課題も多く存在します。そこで重要になるのが、LLMと他のツールとの連携です。

本記事では、LLMで不得意な分野を埋めるツールの一つとして数理最適化との連携方法について、自分の試している内容を簡単に紹介します。

LLMと数理最適化を組み合わせる

数理最適化とは、問題に対して明確に定義された条件（制約条件）や目標（目的関数）をもとに、最適な解を見つけ出す技術です。交通計画や物流の効率化、シフト作成、エネルギー管理など、さまざまな応用があります。

出典:日本オペレーションズ・リサーチ学会ポスター

数理最適化を用いると、LLMの苦手とする厳密な制約の取り扱いが可能となります。たとえば配送計画では複数の条件（時間枠、移動時間、積載量など）を満たしたルートを計算することが求められます。現状のLLMに素直に条件を与えてルートを出力させようとしてもうまくいきません。一方、数理最適化を用いると複雑な条件を厳密に満たす結果が得られます。しかし、実務で数理最適化を利用しようとすると以下のような課題に直面することが多いです。

定式化に専門知識とドメイン知識が必要となる
実務で現れる要件を数理最適化ソルバーが解釈可能な形式に変換する（定式化と呼びます）必要があります。そして、それには一定の専門知識が必要です。一般ユーザーが自分で条件を入力するのは現実的ではありません。また、要件を正しく解釈する必要があり、数理最適化の専門知識に加えて業務に関するドメイン知識も必要となることが多いです。
具体的な条件やデータの登録が煩雑になりやすい
実務で使うには、ユーザーがデータや追加の制約条件を入力可能にしておく必要があります。制約条件は案件ごとに異なることが多いので、工数をかけて個別にUIを開発するか、ある程度汎用的なものを作っておくことになります。しかし、汎用的にすると使い勝手が犠牲になりやすいです。データ量が多かったり、条件が複雑な場合はなおさらです。

前者の定式化についてはいくつか先進的な取り組みがあるようですが、まだまだ課題が多いようです^[1]。一方で、後者の具体的な条件やデータの登録については、まさにLLMが活用できそうです。そこで、数理最適化の典型的な例である配送計画問題を例として、自分の試行錯誤している内容を紹介します。

LLMで制約条件の登録を簡単にする

配送計画とは、拠点を出発して複数の店舗を巡回し、再び拠点に戻るルートを最適化する問題です。この際、店舗ごとのサービス時間や各店舗の時間枠、車両の容量制約、ドライバーの作業時間といった様々な条件を考慮しなければなりません。

がんばってUIを設計したとしても、条件が多いと、どうしても入力操作が煩雑になってしまいますし、操作を覚えるのが大変にもなりがちです。また、やっかいなことに必要な条件は現場ごとに異なったりして、なにをどこまで作り込むのかの判断が難しかったりします。そこで、ユーザーが自然言語で制約条件を入力し、OpenAI API のStructured Outputs を用いて数理最適化モデルに変換することを考えます。

制約クラスの定義

まず、それぞれの制約を定義します。

個別の制約条件の定義

from typingimport List, Optionalfrom pydanticimport BaseModel, FieldclassDeliveryTimeWindowConstraint(BaseModel):"""    配送可能な時間帯を定義するクラス。    Attributes:        customer_id (int): 配送対象の顧客の識別ID。        start_time (float): 配送可能な開始時刻（例: 8.0 は午前8時）。        end_time (float): 配送可能な終了時刻（例: 18.0 は午後6時）。    """    customer_id:int    start_time:float    end_time:floatdef__str__(self):returnf"顧客{self.customer_id} への配送時刻は{self.start_time} から{self.end_time} である"classServiceTimeConstraint(BaseModel):"""    各ノードでのサービス時間を定義するクラス。    Attributes:        node_id (int): サービスを行うノードの識別ID。        service_duration (float): サービスに必要な時間（単位: 分）。    """    node_id:int    service_duration:floatdef__str__(self):returnf"ノード{self.node_id} でのサービス所要時間は{self.service_duration} 分である"...

LLMを使って個別の制約条件を抽出するのではなく、一括で抽出したい場合は、以下のように制約条件をまとめたConstraintsクラスも用意しておきます。

各種制約モデルをまとめたコンテナクラス

classConstraints(BaseModel):"""    各種制約モデルをまとめたコンテナ。    Attributes:        time_constraints (Optional[List[DeliveryTimeWindowConstraint]]): 顧客ごとのデリバリーウィンドウ制約リスト。        service_time_constraints (Optional[List[ServiceTimeConstraint]]): サービス時間制約リスト。        driver_working_hours_constraints (Optional[List[DriverWorkingHoursConstraint]]): ドライバー運転可能時間制約リスト。        ...    """    time_constraints: Optional[List[DeliveryTimeWindowConstraint]]= Field(None, description="顧客ごとのデリバリーウィンドウ制約リスト")    service_time_constraints: Optional[List[ServiceTimeConstraint]]= Field(None, description="サービス時間制約リスト")...def__str__(self):        output=[]for field_name, field_valuein self:if field_value:                output.append(f"{field_name}:")for constraintin field_value:                    output.append(f"  -{constraint}")return"\n".join(output)if outputelse"制約なし"

ここで重要なのは、制約条件の1つ1つ（正確には、ユーザーの解釈しやすい単位でまとめたもの）を Pydantic のモデルとして定義しておくことです。これにより、 Structured Oputputs の恩恵に預かり、LLMの出力を手動でパースする手間を省けます。

1点注意しないといけないのは、フィールドはStructured Output の対応している型とする必要がある点です。例えばstart_time やend_time をdatetime.time 型で定義してしまうと、OpenAI API が出力スキーマを適切に解釈できず、エラーとなってしまいます^[2]。

また、上述のように__str__ を定義しておくと、実際にどの制約条件が適用されているのかを簡単に確認できるので便利です。

次に、 System Prompt にそれぞれのモデルの定義を与えます^[3]。

システムプロンプトの例(system_prompt)

あなたは、ユーザーから与えられるMarkdown形式の自然言語ルールを解析し、以下で定義される「Constraints」スキーマに適合するJSONを生成するシステムです。## Constraints モデルおよび関連モデル定義### 1. DeliveryTimeWindowConstraint配送可能な時間帯を定義するクラス。-**customer_id (int)**: 配送対象の顧客の識別ID。-**start_time (float)**: 配送可能な開始時刻（例: 8.0 は午前8時）。-**end_time (float)**: 配送可能な終了時刻（例: 18.0 は午後6時）。### 2. ServiceTimeConstraint各ノードでのサービス時間を定義するクラス。-**node_id (int)**: サービスを行うノードの識別ID。-**service_duration (float)**: サービスに必要な時間（単位: 分）。

最後に、プロンプトを用意して、APIを呼びます

プロンプトの例(user_prompt)

### **条件**1.**拠点と店舗**- 配送計画では1台の車を使用し、拠点を出発して複数の店舗を訪問し、拠点に戻る。- 拠点と店舗はそれぞれ**タイムウィンドウ** が設定されている。2.**タイムウィンドウの詳細**-**拠点のタイムウィンドウ**:- 1つのみ指定され、出発時刻および帰還時刻がこの範囲内に収まる必要がある。-**店舗のタイムウィンドウ**:- 各店舗には最大3つのタイムウィンドウが設定される。- 作業開始時刻がいずれかのタイムウィンドウ内に入ればよい。...

制約条件への変換

...completion= client.beta.chat.completions.parse(    model="gpt-4o-2024-08-06",    messages=[{"role":"system","content": system_prompt},{"role":"user","content": user_prompt,}],    max_tokens=16384,    response_format=Constraints,)# 結果を表示print(completion.choices[0].message.parsed)

response_format にConstraints を渡すことで、出力データの構造が保証され、Constraints クラスとして受け取ることができるようになります。このコードの出力は以下のようになります。__str__ のおかげで、理解しやすくなっています。

出力

time_constraints:  - 顧客1 への配送時刻は8.0 から12.0 である  - 顧客2 への配送時刻は10.0 から16.0 であるservice_time_constraints:  - ノード1 でのサービス所要時間は30 分である  - ノード2 でのサービス所要時間は20 分である

これで、自然言語で与えられる曖昧な条件を、数理最適化で必要な形式に変換することができました。あとは、この制約条件を数理最適化ソルバーに渡せば、最適化された結果が得られます。

現時点での課題点

上記の方法で、自然言語で制約条件を指定できるようになりましたが、まだまだ完璧ではないようです。例えば、条件が非常に多くて複雑な場合は、LLMが制約条件を間違えてしまったり、スキップしてしまったりすることがあります。時刻の単位を間違えてしまうこともあります。意図通りに変換されているかを確認する意味でも__str__ を定義しておくと便利です。
また、そもそも論として、人間でも解釈に困るような入力文であるケースもよくあります。テンプレートを用意して、記入してもらうなどの工夫が必要です。