規劃問題與 OptaPy

之前寫了一篇〈認識求解器〉，裡面介紹了 LibreOffice Calc 內建的求解器，並且以自助結帳機找錢為例，示範如何用求解器得出最少的貨幣數量，避免客人拿到一大堆小硬幣，結果如下圖：

像這樣的問題，如果不用求解器，自己寫的話，邏輯也很簡單，把 12,345 除以 2,000，商即是 6，而餘數 345 再繼續除以 1,000，如此反覆迭代運算即可。

其中迭代除法計算的次數會隨貨幣面額的多寡而定，台灣有十一種貨幣，就要跑十一次迭代除法計算，日本有十種貨幣，就要跑十次迭代除法運算，如果跑一次花一秒，那十種貨幣就要花十秒，十一種貨幣就要花十一秒囉，像這樣計算時間與貨幣面額數量成等比增長的演算法，在充滿神秘符號學的資訊領域將其標示為 O(n)。

「O()」是用於表示時間複雜度的符號，這裡的「O」表示「order of」，是用來表示一個演算法的時間效率的符號，也就是時間複雜度，而 O(n) 表示該演算法的時間複雜度與 n 成正比關係，n 為輸入規模，它是迭代次數、遞迴次數、運算項目長度等的泛稱，在上面的例子中，就是除法運算的迭代次數啦。

除了 O(n)，當然還有別種時間複雜度，上一張維基百科的圖：

圖中橫軸 n 為前面提到的輸入規模，縱軸 N 為所需之時間，更確切的說，應該為運算的次數，因為時間可能會隨硬體算力的不同而異，而以運算次數計的話就可以除去不同機器算力之間的時間變異，總之就是個表達運算有多複雜的一個代數。

可以看到綠色的那條就是 O(n)，隨著橫軸 n 增大，縱軸 N 也等比增大。

綠色下面還有一條紫色線段，它是時間複雜度 O(1) 以圖形表示的線段，這裡的 1 表示常數，也就是不論那 n 有多大，運算複雜度都是始終如一。

對於一個 stack（堆疊）的取出元素的操作，就是 O(1) 型運算，不管這個 stack 的元素（n）有多少，成千上萬個都沒關係，取出它的最後一個元素所花的運算都是不變的，就像這疊盤子：

不論整疊盤子有幾個，要拿取最上面那個盤子所需的精力都相同。

回到複雜度圖表，以綠色的 O(n) 線段為中心，下面的線段，包括紫色的 O(1) 等等，都是有機會算出來的，而另外一半線型一路往上衝的，表示只要 n 的數量多一點點，所需的運算時間或資源就會指數級暴漲，漲到就算你有鈔能力也解不出來。

以具體的例子來說，暴力破解密碼就屬於這種只要 n 多一點，複雜度就成指數增長的形式，這也是為什麼一般都會建議把密碼設得越長越好，除破解複雜度高之外，密碼還有另一項特性：驗證簡單，也就是說，儘管暴力破解需要花無量大數般的時間，但從另一方面來說，要驗證一個密碼是對是錯則非常快速。

回到求解器話題，這類「運算複雜、驗證簡單」的問題，不僅有密碼破解，還有這些：

• 排班、排程、排工問題，怎麼排才能公平又滿足多方需求？
• 路徑規劃問題，怎麼走才能讓運輸效率最大化？
• 裝箱問題，怎麼裝才能讓箱體利用率最大化？
• 裁切問題，怎麼切才能讓物料利用率最大化？
• 賽事問題，怎麼排才能讓賽事公平而不強碰？
• 投資問題，怎麼配置才能讓收益最大化？

求解器本質上也是一種演算法，它試圖在有限的時間內，找出問題的「可接受的近似最佳解」，也就是說它不追求完美的最佳解，因此，雖然密碼問題也是運算複雜、驗證簡單，但它對與錯一翻兩瞪眼，並不存在所謂「近似最佳解」，因此求解器在破解密碼是派不上用場的，還是去研究加密算法的缺陷吧。

對於這類「運算複雜、驗證簡單」的問題，在深奧的資訊科學領域被歸為 NP 問題，或者更通俗的泛稱為「規劃問題」。

對於規劃問題，或者更簡單的自助結帳機找零問題，求解器就是我們的好幫手。

除了像 LibreOffice Calc 這類終端應用中有內建求解器，求解器當然也以程式套件的形式存在，如果是 Python，可以參考有人整理好的求解器清單，下面要來介紹其中的 OptaPy。

認識 OptaPy

OptaPy 的真身是 OptaPlanner，它是 Java 語言開發的求解器，而 OptaPy 則是給 Python 用的一層封裝，透過 OptaPy API，我們得以直接在自己的 Python 程式內調用 OptaPlanner 的功能，也因為如此，我們的電腦或主機中必須裝有 Java。

OptaPlanner 一直以來都是 RedHat 贊助的開源專案，但隨著 IBM 併購 RedHat，創始人決定自行開業以新公司的身份自行發展以 OptaPlanner 為基礎的事業，新的公司與專案叫做 Timefold，希望他們不會遇到創業三寶。

安裝 OptaPy 時，它已經內建了 OptaPlanner，不須另外安裝，只要確保電腦內有 JRE 或 JDK 即可。

安裝 OptaPy 的指令也就是那一行萬年不變的：

$ pip install optapy

下面開始進入真槍實彈，這裡的內容來自 OptaPy 的〈Quickstart〉一文，但並非一比一的翻譯。

OptaPy 解決排課問題

排課是典型的規劃問題之一，如何既讓老師與學生都上到該上的課，而且不能衝堂，想想就會發現這不是件簡單的事，參照以下示意圖：

首先建立問題的領域模型，命名為 domain.py，這裡會放與問題領域相關的 class。

既有事實（fact）

在 domain.py 中制定一些既有事實，例如教室與時段：

from dataclasses import dataclass
from datetime import time

from optapy import problem_fact

@problem_fact
@dataclass(frozen=True)
class Room:
    id: int
    name: str

    @planning_id
    def get_id(self):
        return self.id

@problem_fact
@dataclass(frozen=True)
class Timeslot:
    id: int
    day_of_week: str
    start_time: time
    end_time: time

    @planning_id
    def get_id(self):
        return self.id

這裡的 class 都盡可能用 Data Class，省下自己寫物件初始化函式（__init__()）的功夫，本文不會過度討論 Data Class，有興趣的朋友可以去問 ChatGPT。

上面兩個 class Room 與 Timeslot 都冠上了裝飾器 @problem_fact，這使它們在後面可以作為既有事實（fact）為求解器所用。

而那個被冠上 @planning_id 的函式，則是讓後續 OptaPy 能取得每個教室與時段物件的 ID 所用。

事實（fact）的性質是它在求解過程中是固定不變的，一天五個時段就是五個時段，三間教室就是三間教室，不會因為排不下就冒出第四間教室，也不會突然出現禮拜八或禮拜九，如果是排火車時刻表的話，也沒有九又四分之三月台（誰叫我們是麻瓜呢）。

規劃實體（planning entity）

規劃實體就是我們要求解的標的，在這裡就是「課」，一節課可能是禮拜一上午八點半在 A 教室的英文，也可能是禮拜二下午一點半在 B 教室的數學，站在 class（類別，非指課目）的觀點看，一個 Lesson class 就會具有 room 與 timeslot 的屬性，後面我們會讓 OptaPy 幫我們求出每節課應該在禮拜幾的幾點上什麼。

同樣在 domain.py 制定一個 Lesson class：

from optapy import planning_entity, planning_variable

@planning_entity
@dataclass(frozen=False)
class Lesson:
    id: int
    subject: str
    teacher: str
    student_group: str
    timeslot: Timeslot | None = None
    room: Room | None = None

    @planning_id
    def get_id(self):
        return self.id
    
    @planning_variable(variable_type=Timeslot, value_range_provider_refs=['timeslotRange'])
    def get_timeslot(self):
        return self.timeslot
    
    def set_timeslot(self, new_timeslot: Timeslot):
        self.timeslot = new_timeslot

    @planning_variable(variable_type=Room, value_range_provider_refs=['roomRange'])
    def get_room(self):
        return self.room
    
    def set_room(self, new_room: Room):
        self.room = new_room

對於一個 Lesson 物件，最初它的教室與時段都是未定的，交由 OptaPy 幫我們安排，透過裝飾器 @planning_variable 將其設為規劃變數（planning variable），這讓 OptaPy 知道這些如何取得 room 與 timeslot，以及它們的 setter 函式讓 OptaPy 知道該如何賦值，但除了裝飾器外，這邊的 getter 與 setter 還必須按照 OptaPy 要求來命名，getter 函式必須命名為 get_xxx，setter 函式必須命名為 set_xxx。

對於裝飾器函式 planning_variable() 我們填入了兩個參數：

• variable_type=Timeslot 告訴 OptaPy 這格變數對應的物件是 Timeslot 物件。
• value_range_provider_refs=['timeslotRange'] 告訴 OptaPy 這格可能的值在哪裡取得。

以時段（Timeslot）為例，前面已經定義了它的 class，後面會再把具體的時段物件產生出來，例如禮拜一早上八點半、禮拜二下午一點半等等，把這些可用的時段物件存入一個清單，再令其為 timeslotRange，如此 OptaPy 就會根據既有的時段為我們排定課表。

另一個規劃變數教室也是如此這般，後面會建立具體的教室物件，把可用教室存入一個清單，令其為 roomRange，如此 Opta 就會根據既有的時段與教室為我們排定課表。

在建立實際的時段與教室物件前，先來定義一些防止衝堂的約束條件。

約束（Constraint）

在排課表時，有些約束一定要遵守，例如同一時段的同一教室只能容納一堂課，此外，有的老師懂兩門課目，又會教物理又會教化學，但就是不會影分身之術，因此他也必然在同一時段內只能上一門課，像這類無法違背的約束，稱為硬約束。

有硬約束相對就有軟約束囉，軟約束指的是那些「體育最好在下午」、「老師最好不要一直換教室」、「老老師 A 希望下午不要排課」之類的請求，能滿足的盡量滿足，但可能難以全部滿足。

OptyPy 每解算出一回結果就會視滿足約束的多寡來取得分數，對 OptaPy 而言，它的目標就是在有限的時間內找出分數最高的結果，這也就是所謂的「近似最佳解」。

認識了約束的概念後，下面來寫成程式碼吧～。

新開個檔案，就叫 constraints.py，內容如下：

from optapy import constraint_provider
from optapy.constraint import Joiners, Constraint, ConstraintFactory
from optapy.score import HardSoftScore

from domain import Lesson, Room

@constraint_provider
def define_constraints(
    constraint_factory: ConstraintFactory,
) -> list[Constraint]:
    constraint_list: list[Constraint] = [
        # Hard constraints
        room_conflict(constraint_factory=constraint_factory),
        teacher_conflict(constraint_factory=constraint_factory),
        student_group_conflict(constraint_factory=constraint_factory),

        # Soft constraints are only implemented in the optapy-quickstarts code
    ]
    return constraint_list


def room_conflict(
    constraint_factory: ConstraintFactory,
) -> Constraint:
    # A room can accommodate at most one lesson at the same time.
    constraint: Constraint = constraint_factory.for_each(
        source_class=Lesson,
    ).join(
        Lesson,
        # ... in the same timeslot ...
        Joiners.equal(lambda lesson: lesson.timeslot),
        # ... in the same room ...
        Joiners.equal(lambda lesson: lesson.room),
        # ... and the pair is unique (different id, no reverse pairs) ...
        Joiners.less_than(lambda lesson: lesson.id),
    ).penalize(
        'Room conflict', # Contraint name
        HardSoftScore.ONE_HARD, # Constraint weight
    )
    return constraint


def teacher_conflict(
    constraint_factory: ConstraintFactory,
) -> Constraint:
    # A teacher can teach at most one lesson at the same time.
    constraint: Constraint = constraint_factory.for_each(
        source_class=Lesson,
    ).join(
        Lesson,
        Joiners.equal(lambda lesson: lesson.timeslot),
        Joiners.equal(lambda lesson: lesson.teacher),
        Joiners.less_than(lambda lesson: lesson.id)
    ).penalize(
        'Teacher conflict', # Contraint name
        HardSoftScore.ONE_HARD, # Constraint weight
    )
    return constraint


def student_group_conflict(
    constraint_factory: ConstraintFactory,
) -> Constraint:
    # A student group can attend at most one lesson at the same time.
    constraint: Constraint = constraint_factory.for_each(
        source_class=Lesson,
    ).join(
        Lesson,
        Joiners.equal(lambda lesson: lesson.timeslot),
        Joiners.equal(lambda lesson: lesson.student_group),
        Joiners.less_than(lambda lesson: lesson.id)
    ).penalize(
        'Student group conflict', # Contraint name
        HardSoftScore.ONE_HARD, # Constraint weight
    )
    return constraint

內容頗長，先大概看過即可。

最前面用裝飾器函式 constraint_provider() 定義了一個約束供給者（constraint provider），也就是我們的 define_constraints()，根據 constraint_provider() 的要求，約束供給者必須接受一個類型為 ConstraintFactory 的參數，並且返回一份約束清單，這裡的 ConstraintFactory 參數也會傳遞給約束的建立函式，這整段繞口令歸納下來就是要有長這樣的程式碼：

from optapy import constraint_provider
from optapy.constraint import Constraint, ConstraintFactory

@constraint_provider
def define_constraints(
    constraint_factory: ConstraintFactory,
) -> list[Constraint]:
    constraint_list: list[Constraint] = [
        a_constraint(constraint_factory),
        ...
    ]
    return constraint_list


def a_constraint(
    constraint_factory: ConstraintFactory,
) -> Constraint:
    constraint: Constraint = constraint_factory.for_each(
        ...
    ).penalize( # Or reward()
        ...
    )
    return constraint

約束工廠 ConstraintFactory 提供了一系列用來建立約束的方法。

前面提過，所謂的近似解就是分數最高的解，而這裡的分數就來自於約束，有的約束是獎勵型的（reward()），滿足了會加分，有的約束是懲罰型的（penalize()），碰到了會減分，以上面的三個約束來說，它們都是懲罰型的約束，碰到了都是減硬約束一分。

目前我們遇到的分數型態是 HardSoftScore，其中 HardSoftScore.ONE_HARD 表示硬約束一分，HardSoftScore.ONE_SOFT 表示軟約束一分，如果想要加減更多分可以用 HardSoftScore.ofHard(int=2) 或 HardSoftScore.ofSoft(int=3)。

下面是個簡單的約束函式範例：

from optapy.score import HardSoftScore
from optapy.constraint import Constraint, ConstraintFactory

from domain import Lesson, Room

@constraint_provider
def define_constraints(
    constraint_factory: ConstraintFactory,
) -> list[Constraint]:
    constraint_list: list[Constraint] = [
        do_not_assign_room_a(constraint_factory=constraint_factory),
    ]
    return constraint_list

def do_not_assign_room_a(
    constraint_factory : ConstraintFactory,
) -> Constraint:
    constraint: Constraint = constraint_factory.for_each(
        source_class=Lesson,
    ).filter(
        predicate=lambda lesson: lesson.room.name == 'Room A'
    ).penalize("Don't assign room A", HardSoftScore.ONE_SOFT)

如此所有 OptaPy 求出來的解都會經由該約束估算分數，如果有堂課排到教室 A，就扣軟約束一分，因此最後 OptaPy 給出的最終解就會趨向盡量少排課到教室 A。

上面的約束只考慮 Lesson，如果要納入別的事實（fact）或實體（entity）可以用約束工廠 ConstraintFactory 的 join() 方法。

例如 Cruz 禮拜一下午想去跑趴，不想排課，那可以把 Timeslot 也納入約束中：

# import XXX

@constraint_provider
def define_constraints(
    constraint_factory: ConstraintFactory,
) -> list[Constraint]:
    constraint_list: list[Constraint] = [
        avoid_monday_last_timeslot_for_cruz(
            constraint_factory=constraint_factory,
        ),
    ]
    return constraint_list

def avoid_monday_last_timeslot_for_cruz(
    constraint_factory: ConstraintFactory,
) -> Constraint:
    constraint: Constraint = constraint_factory.for_each(
        source_class=Lesson,
    ).join(Timeslot).filter(
        predicate=lambda lesson, timeslot:
            lesson.teacher == 'P. Cruz'
            and lesson.timeslot.id == 5
            and timeslot.id == 5,
    ).penalize(...)
    return constraint

上面這個寫法很多餘，純粹只為了展示 join().filter() 而刻意為之，小朋友不要學。

該怎麼理解 join() 呢？可以透過 OptaPy 的圖片：

簡而言之，就是取 Shift 與 DayOff 兩類物件列表的乘積作為評估該約束的來源，這種模式下，如果 join 越多，那用來評估該約束的陣列就會越大，因此 OptaPy 推薦使用 joiner 來處理多重類別的約束運算，joiner 工作示意圖如下：

相較於不使用 joiner 的模式，走 joiner 的模式也更直觀一點，以圖中的程式碼為例：

constraint: Constraint = constraint_factory.for_each(
    source_class=Shift,
).join(
    Dayoff,
    Joiners.equal(
        lambda shift: shift.date,
        lambda day_off: day_off.date,
    ),
    Joiners.equal(
        lambda shift: shift.employee,
        lambda day_off: day_off.employee,
    ),
).penalize(...)

中間那塊 joiner 意即：

上班日（shift.date）與休假日（day_off.date）同天（equal），並且當班人（shift.employee）又與休假人（day_off.employee）為同一人時，就扣分，如此驅使最後 OptaPy 算出來的解就不會把人排到同一天又上班又休假的薛丁格疊加態。

除了比較是否相等（equal），也可以比大小，Joiner 有下面這些方法：

• equal()：比較是否相等。
• greater_than()、greater_than_or_equal()、less_than()、less_than_or_equal()：比大小。
• overlapping()：比較是否重疊，透過該物件的 start 與 end 屬性來判斷，因此得在 class 定義中添加此兩屬性。

回到排課表，那裏的 join 區塊長這樣：

constraint: Constraint = constraint_factory.for_each(
    source_class=Lesson,
).join(
    Lesson,
    # ... in the same timeslot ...
    Joiners.equal(lambda lesson: lesson.timeslot),
    # ... in the same room ...
    Joiners.equal(lambda lesson: lesson.room),
    # ... and the pair is unique (different id, no reverse pairs) ...
    Joiners.less_than(lambda lesson: lesson.id),
).penalize(...)

這裡 soucce_class 是 Lesson，而 join() 的也是 Lesson，有點像是 SQL 的 self join 的意思，因為是 self join，後面的 equal() 如果都是要比較相同屬性的話，可以只接一個參數：

Joiners.equal(lambda lesson: lesson.timeslot)

上面一句相等於：

Joiners.equal(
    lambda lesson: lesson.timeslot,
    lambda lesson: lesson.timeslot,
)

以上是關於約束的介紹，更詳細的約束用法可以參見〈Constraint streams score calculation〉。

解（solution）

前面我們在 domain.py 定義了幾個 fact class 與 entity class，包括教室、時段、課堂等等，在此要再定義一個 solution class，一個 solution class 用於收納所有的 fact 物件與 entity 物件，並且還有個 score 屬性，用於存放一個 solution 的分數。

在 domain.py 加入以下內容：

from optapy import planning_solution, planning_entity_collection_property, problem_fact_collection_property, value_range_provider, planning_score
from optapy.score import HardSoftScore

@planning_solution
@dataclass(frozen=False)
class TimeTable:
    timeslot_list: list[Timeslot]
    room_list: list[Room]
    lesson_list: list[Lesson]
    score: HardSoftScore | None = None

    @problem_fact_collection_property(fact_type=Timeslot)
    @value_range_provider(range_id='timeslotRange')
    def get_timeslot_list(self):
        return self.timeslot_list
    
    @problem_fact_collection_property(fact_type=Room)
    @value_range_provider(range_id='roomRange')
    def get_room_list(self):
        return self.room_list
    
    @planning_entity_collection_property(entity_type=Lesson)
    def get_lesson_list(self):
        return self.lesson_list
    
    @planning_score(score_type=HardSoftScore)
    def get_score(self):
        return self.score
    
    def set_score(self, score: HardSoftScore):
        self.score = score

這裡又看到好多裝飾器…：

• 最外層的 @planning_solution 讓 OptyPy 知道此處為一個 solution class。
• Fact list getter 函式上方的 @problem_fact_collection_property 告訴 OptyPy 此處為 fact 集合。
• Fact list getter 函式上方另一個裝飾器 @value_range_provider 告訴 OptaPy 此處為 fact 集合，並且呼應了前面 entity 的屬性裝飾器，讓 OptyPy 知道一個 enitiy 的規劃變數的可能的值該如何取得。
• Entity list getter 函式上方的 @planning_entity_collection_property 告訴 OptaPy 此處為 entity 集合。
• Score getter 上方的 @planning_score 告訴 OptaPy 此處為取得 score 之函式，這裡除了要冠上裝飾器外，getter 與 setter 也必須命名為 get_xxx 與 set_xxx。

搞了這麼多 class，總算可以產生實際的物件了，如果這些勾來勾去的 class 令人感到迷惑，那實際生成物件後會比較清楚一些。

繼續在 domain.py 增加下面內容：

from datetime import time

def generate_problem():
    timeslot_list = [
        Timeslot(id=1, day_of_week='MONDAY', start_time=time(hour=8, minute=30), end_time=time(hour=9, minute=30)),
        Timeslot(id=2, day_of_week='MONDAY', start_time=time(hour=9, minute=30), end_time=time(hour=10, minute=30)),
        Timeslot(id=3, day_of_week='MONDAY', start_time=time(hour=10, minute=30), end_time=time(hour=11, minute=30)),
        Timeslot(id=4, day_of_week='MONDAY', start_time=time(hour=13, minute=30), end_time=time(hour=14, minute=30)),
        Timeslot(id=5, day_of_week='MONDAY', start_time=time(hour=14, minute=30), end_time=time(hour=15, minute=30)),
        Timeslot(id=6, day_of_week='TUESDAY', start_time=time(hour=8, minute=30), end_time=time(hour=9, minute=30)),
        Timeslot(id=7, day_of_week='TUESDAY', start_time=time(hour=9, minute=30), end_time=time(hour=10, minute=30)),
        Timeslot(id=8, day_of_week='TUESDAY', start_time=time(hour=10, minute=30), end_time=time(hour=11, minute=30)),
        Timeslot(id=9, day_of_week='TUESDAY', start_time=time(hour=13, minute=30), end_time=time(hour=14, minute=30)),
        Timeslot(id=10, day_of_week='TUESDAY', start_time=time(hour=14, minute=30), end_time=time(hour=15, minute=30)),
    ]

    room_list = [
        Room(id=1, name='Room A'),
        Room(id=2, name='Room B'),
        Room(id=3, name='Room C'),
    ]

    lesson_list = [
        Lesson(id=1, subject='Math', teacher='A. Turing', student_group='9th grade'),
        Lesson(id=2, subject='Math', teacher='A. Turing', student_group='9th grade'),
        Lesson(id=3, subject='Physics', teacher='M. Curie', student_group='9th grade'),
        Lesson(id=4, subject='Chemistry', teacher='M. Curie', student_group='9th grade'),
        Lesson(id=5, subject='Biology', teacher='C. Darwin', student_group='9th grade'),
        Lesson(id=6, subject='History', teacher='I. Jones', student_group='9th grade'),
        Lesson(id=7, subject='English', teacher='I. Jones', student_group='9th grade'),
        Lesson(id=8, subject='English', teacher='I. Jones', student_group='9th grade'),
        Lesson(id=9, subject='Spanish', teacher='P. Cruz', student_group='9th grade'),
        Lesson(id=10, subject='Spanish', teacher='P. Cruz', student_group='9th grade'),
        Lesson(id=11, subject='Math', teacher='A. Turing', student_group='10th grade'),
        Lesson(id=12, subject='Math', teacher='A. Turing', student_group='10th grade'),
        Lesson(id=13, subject='Math', teacher='A. Turing', student_group='10th grade'),
        Lesson(id=14, subject='Physics', teacher='M. Curie', student_group='10th grade'),
        Lesson(id=15, subject='Chemistry', teacher='M. Curie', student_group='10th grade'),
        Lesson(id=16, subject='French', teacher='M. Curie', student_group='10th grade'),
        Lesson(id=17, subject='Geography', teacher='C. Darwin', student_group='10th grade'),
        Lesson(id=18, subject='History', teacher='I. Jones', student_group='10th grade'),
        Lesson(id=19, subject='English', teacher='P. Cruz', student_group='10th grade'),
        Lesson(id=20, subject='Spanish', teacher='P. Cruz', student_group='10th grade'),
    ]
    
    # Pre-existed lesson
    lesson = lesson_list[0]
    lesson.set_timeslot(new_timeslot=timeslot_list[0])
    lesson.set_room(new_room=room_list[0])
    
    return TimeTable(
        timeslot_list=timeslot_list,
        room_list=room_list,
        lesson_list=lesson_list,
    )

可以看到，這裡的每堂課，都只設定了課目、老師、學生，而時段與教室都懸而未決（除了九年級數學），有待 OptyPy 幫我們排定。

對於九年級數學，在下面已經手動指定了它的教室與時段，這種手動排定的課 OptaPy 不會再幫我們排了。

至此，我們建構了課表的領域模型（domain.py）與約束（constraints.py），並且也產生了實際的時段、教室、課堂物件，終於可以求解了。

規劃求解

我們把執行求解的主程式放在 main.py，內容如下：

from optapy import solver_factory_create
import optapy.config
from optapy.types import Duration
from org.optaplanner.core.config import solver

from domain import generate_problem, Lesson, TimeTable
from constraints import define_constraints

config_module: solver = optapy.config.solver
solver_config = config_module.SolverConfig().withEntityClasses(
    Lesson,
).withSolutionClass(
    TimeTable,
).withConstraintProviderClass(
    define_constraints,
).withTerminationSpentLimit(
    Duration.ofSeconds(20),
)

solver_factory = solver_factory_create(
    solver_config=solver_config,
)

solution: TimeTable = solver_factory.buildSolver().solve(
    generate_problem(),
)
print(solution)
print(solution.score)

這裡先建了個求解器配置，又又又又又再次設定了「Lesson 是 entity 喔」、「TimeTable 是 solution 喔」等等，最後的 withTerminationSpentLimit() 是設定求解器運算的時間上限，還記得前面提過，規劃問題的特性是求出最佳解的時間極大，而求解器的作用是在「有限的時間內」求出近似最佳解，這裡的時間設定就是那「有限的時間」。

話說回來，為什麼在 domain.py 與 constraints.py 內的各種 class 都已經有裝飾器定義好它們是 fact、是 entity、是 solution、是 planning variable 了，後面還要處處再次定義什麼是什麼，到底是什麼的什麼的為什麼到底？

抱怨完切回正題，這個 main.py 是幾個腳本中最簡單的，跑跑看：

$ python main.py

順利跑完的結果整理一下大概像這樣：

proxy.TimeTable(
    timeslot_list=[
        proxy.Timeslot(id=1, day_of_week='MONDAY', start_time=datetime.time(8, 30), end_time=datetime.time(9, 30)),
        ...
    ],
    
    room_list=[proxy.Room(id=1, name='Room A'), proxy.Room(id=2, name='Room B'), proxy.Room(id=3, name='Room C')],
    
    lesson_list=[
        proxy.Lesson(id=1,  subject='Math',      teacher='A. Turing', student_group='9th grade', timeslot=proxy.Timeslot(id=1, day_of_week='MONDAY', start_time=datetime.time(8, 30),  end_time=datetime.time(9, 30)),  room=proxy.Room(id=1, name='Room A')),
        proxy.Lesson(id=10, subject='Spanish',   teacher='P. Cruz',   student_group='9th grade', timeslot=proxy.Timeslot(id=3, day_of_week='MONDAY', start_time=datetime.time(10, 30), end_time=datetime.time(11, 30)), room=proxy.Room(id=1, name='Room A')),
        proxy.Lesson(id=4,  subject='Chemistry', teacher='M. Curie',  student_group='9th grade', timeslot=proxy.Timeslot(id=4, day_of_week='MONDAY', start_time=datetime.time(13, 30), end_time=datetime.time(14, 30)), room=proxy.Room(id=1, name='Room A')), 
        proxy.Lesson(id=5,  subject='Biology',   teacher='C. Darwin', student_group='9th grade', timeslot=proxy.Timeslot(id=5, day_of_week='MONDAY', start_time=datetime.time(14, 30), end_time=datetime.time(15, 30)), room=proxy.Room(id=1, name='Room A')),

        proxy.Lesson(id=16, subject='French',  teacher='M. Curie',  student_group='10th grade', timeslot=proxy.Timeslot(id=1, day_of_week='MONDAY', start_time=datetime.time(8, 30),  end_time=datetime.time(9, 30)),  room=proxy.Room(id=2, name='Room B')),
        proxy.Lesson(id=2,  subject='Math',    teacher='A. Turing', student_group='9th grade',  timeslot=proxy.Timeslot(id=2, day_of_week='MONDAY', start_time=datetime.time(9, 30),  end_time=datetime.time(10, 30)), room=proxy.Room(id=2, name='Room B')),
        proxy.Lesson(id=11, subject='Math',    teacher='A. Turing', student_group='10th grade', timeslot=proxy.Timeslot(id=3, day_of_week='MONDAY', start_time=datetime.time(10, 30), end_time=datetime.time(11, 30)), room=proxy.Room(id=2, name='Room B')),
        proxy.Lesson(id=18, subject='History', teacher='I. Jones',  student_group='10th grade', timeslot=proxy.Timeslot(id=4, day_of_week='MONDAY', start_time=datetime.time(13, 30), end_time=datetime.time(14, 30)), room=proxy.Room(id=2, name='Room B')),

        proxy.Lesson(id=15, subject='Chemistry', teacher='M. Curie', student_group='10th grade', timeslot=proxy.Timeslot(id=2, day_of_week='MONDAY', start_time=datetime.time(9, 30),  end_time=datetime.time(10, 30)), room=proxy.Room(id=3, name='Room C')),
        proxy.Lesson(id=14, subject='Physics',   teacher='M. Curie', student_group='10th grade', timeslot=proxy.Timeslot(id=5, day_of_week='MONDAY', start_time=datetime.time(14, 30), end_time=datetime.time(15, 30)), room=proxy.Room(id=3, name='Room C')),

        proxy.Lesson(id=6, subject='History', teacher='I. Jones', student_group='9th grade', timeslot=proxy.Timeslot(id=6,  day_of_week='TUESDAY', start_time=datetime.time(8, 30),  end_time=datetime.time(9, 30)),  room=proxy.Room(id=1, name='Room A')),
        proxy.Lesson(id=7, subject='English', teacher='I. Jones', student_group='9th grade', timeslot=proxy.Timeslot(id=7,  day_of_week='TUESDAY', start_time=datetime.time(9, 30),  end_time=datetime.time(10, 30)), room=proxy.Room(id=1, name='Room A')),
        proxy.Lesson(id=8, subject='English', teacher='I. Jones', student_group='9th grade', timeslot=proxy.Timeslot(id=8,  day_of_week='TUESDAY', start_time=datetime.time(10, 30), end_time=datetime.time(11, 30)), room=proxy.Room(id=1, name='Room A')),
        proxy.Lesson(id=3, subject='Physics', teacher='M. Curie', student_group='9th grade', timeslot=proxy.Timeslot(id=10, day_of_week='TUESDAY', start_time=datetime.time(14, 30), end_time=datetime.time(15, 30)), room=proxy.Room(id=1, name='Room A')), 

        proxy.Lesson(id=13, subject='Math',      teacher='A. Turing', student_group='10th grade', timeslot=proxy.Timeslot(id=6,  day_of_week='TUESDAY', start_time=datetime.time(8, 30),  end_time=datetime.time(9, 30)),  room=proxy.Room(id=2, name='Room B')),
        proxy.Lesson(id=19, subject='English',   teacher='P. Cruz',   student_group='10th grade', timeslot=proxy.Timeslot(id=7,  day_of_week='TUESDAY', start_time=datetime.time(9, 30),  end_time=datetime.time(10, 30)), room=proxy.Room(id=2, name='Room B')),
        proxy.Lesson(id=17, subject='Geography', teacher='C. Darwin', student_group='10th grade', timeslot=proxy.Timeslot(id=8,  day_of_week='TUESDAY', start_time=datetime.time(10, 30), end_time=datetime.time(11, 30)), room=proxy.Room(id=2, name='Room B')),
        proxy.Lesson(id=9,  subject='Spanish',   teacher='P. Cruz',   student_group='9th grade',  timeslot=proxy.Timeslot(id=9,  day_of_week='TUESDAY', start_time=datetime.time(13, 30), end_time=datetime.time(14, 30)), room=proxy.Room(id=2, name='Room B')),
        proxy.Lesson(id=20, subject='Spanish',   teacher='P. Cruz',   student_group='10th grade', timeslot=proxy.Timeslot(id=10, day_of_week='TUESDAY', start_time=datetime.time(14, 30), end_time=datetime.time(15, 30)), room=proxy.Room(id=2, name='Room B'))

        proxy.Lesson(id=12, subject='Math', teacher='A. Turing', student_group='10th grade', timeslot=proxy.Timeslot(id=9, day_of_week='TUESDAY', start_time=datetime.time(13, 30), end_time=datetime.time(14, 30)), room=proxy.Room(id=3, name='Room C')),
    ],

    score=<java object 'org.optaplanner.core.api.score.buildin.hardsoft.HardSoftScore'>
)

0hard/0soft

最後的分數為 0hard/0sof，意即都沒扣到分，GJ。

以上是規劃問題與拿 OptaPy 排課表的案例，但往往真實的案例會更為複雜，而且我們也往往對於問題的理解過於簡單，把一個實際上為 NP 問題的課題誤以為是簡單的邏輯問題，導致給出的解決方案過於陽春，有著很大的侷限性，但另一方面，掌握求解器需要經歷一定的學習曲線，從這個角度看，直接把問題的複雜度降低，並提出一個手刻陽春解決方案也未嘗不可，總之，只要能滿足可預見的 use case 都是好的，只要能捉老鼠就是好貓。

後記

在陸陸續續摸索了幾個禮拜之後，最終決定放棄 OptyPy，有以下原因：

• 雖然 OptaPy 負責把 Python class 轉換成 Java，但這也因此導致在那些被賦予 OptaPy 裝飾器的 class 或方法使用受限，如果我們嘗試在其中梯加一些額外的邏輯、呼叫其他第三方 Python 套件，可能會導致運作出錯，因此理想的使用模式必須把問題模型獨立於整體系統的業務邏輯之外，然而對於實際上遇到的複雜問題，在業務邏輯上本來就已經有許多 class，如果為了求解還要另外建立更多的 class，將使得整體邏輯變得混亂。

• 因為每次調用 OptaPlanner 都是一次 JVM 的冷啟動，導致速度非常慢，沒辦法在用戶容忍上限的黃金三秒內跑完，或許直接採用 OptaPlanner + Spring，架設成 API，從 Python 發出請求還比較快，但複雜度、維護成本都必然上升。

• 那一堆裝飾器令人感到頭昏眼花。

因此，下一波新玩具，將是開源求解器的另一大作，Google OR-Tools。

Share