OR-Tools 從小白到入門

前面介紹了 OptaPy 與 OptaPlanner 求解器，這篇談的則是另一款由 Google 出品的求解器 OR-Tools，為了文章的完整性，在進入 OR-Tools 前，還是快速介紹一下什麼是規劃問題，以及什麼是求解器。

規劃問題與求解器

對一般用戶來說，他們可以在 LibreOffice Calc 等試算表中，建立一些公式及目標，然後使用求解器功能幫他們找出最接近目標的儲存格組合，例如「該怎麼找零才能不會讓顧客拿到一大堆硬幣？」這個問題在求解器的模型中，我們改以這種形式提問：「該怎麼組合各種幣值的鈔票與硬幣，好讓顧客拿到的貨幣數量是最少，並且金額是對的？」我們以下圖表達此問題：

最後求出之解如下：

最終顧客拿到 11 個各式貨幣，並且金額正確（詳見〈認識求解器〉）。

像上面這樣的問題，屬於線性規劃問題，但還有一些更為複雜的問題，例如：

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

這些問題的共同特徵是「運算複雜、驗證簡單」，運算之所以複雜，是因為其中有近似無限種可能，舉例來說，暴走二人組要走遍全台灣所有鄉鎮市區，其中路徑就有幾乎無限種可能，而驗證之所以簡單，有沒有真的走遍全台灣，用座標就可以秒驗證。

對於這類問題，我們不太可能去窮舉所有可能性再找出最佳解，因為如此所耗費的時間可能是天文數字，但可以透過求解器來幫我們找出「近似最佳解」，在理論上之「真．最佳解」無法求得的情況下，近似最佳解已足夠滿足我們的需求。

OR-Tools

OR-Tools 是 Google 開發的求解器，名字中的「OR」表示 operations research（作業研究），這是一門科學化探討各種作業問題的學科。OR-Tools 本身是以 C++ 開發，另提供多種語言的 API，由於 C++ 可直接編譯成各平台的原生二進位檔，因此不像 OptaPy 那樣還要等 JVM 跑起來，OR-Tools 即使在世界知名的慢速語言 Python 下跑起來都可以秒解問題，既提高了效率，也減少了客怨。

OR-Tools 內集合了多個求解器，每個求解器就是一套演算法，它們各有擅長之處，有的適合解線性問題，有的適合解約束問題，因為本人的需求為約束問題，所以下面只會談到 OR-Tools 中的約束問題求解器 CP-SAT。

在 Python 安裝 OR-Tools 就是那永遠的 pip install：

$ pip install ortools

OR-Tools 的 CP-SAT

CP-SAT 是 OR-Tools 內建的求解器之一，「CP」表示 constraint programming（約束編程）、「SAT」表示 Boolean satisfiability problem（布林可滿足性問題），這些專業名詞有點艱澀，簡單說就是上面舉的那些規劃問題，而 CP-SAT 就是針對這類問題的求解器。

使用 OR-Tools 主要有幾個大步驟：

1. 創建變數
2. 制定約束
3. 制定目標
4. 執行求解

不論用的是哪款求解器，大多也都是這些步驟，包括 LibreOffice Calc 內的求解器以及 OptaPy、OptaPlanner，差別在於建立問題模型的思維模式不同，在 OR-Tools 這邊，我們需要把具體的問題以數學方程式的形式表達，雖說是數學方程式，但其實還是程式碼的形式，也就是說我們在建模時腦中的思維模式必須走過「理解問題 → 數學化 → 程式碼化」三個階段，這個過程不要求我們是數學專家，但需要有強健的邏輯思維，這也是邏輯孱弱的本人難以跨越之鴻溝所在。

無論如何，頭已經洗下去了，讓我們繼續吧。

簡單約束問題

一個簡單約束問題如下：

• 有 x、y、z 三個變數，它們的值可以是 0、1、2。
• x 不等於 y。
• x + y + z 最大可能是多少？

建立一個 cp_example.py 腳本，一開始先引入套件，並建立 CpModel 實例，命名為 model：

"""Simple solve"""
from ortools.sat.python import cp_model

"""Minimal CP-SAT example to showcase calling the solver"""
# Create solver model
model = cp_model.CpModel()

後面我們會利用一系列 model 的方法來建立問題模型。

接著建立 x、y、z 三個變數，這三者皆為整數，範圍從 0 到 2。

利用 NewIntVar() 方法來建立整數變數，其中 lb、ub 分別表示 lower bound 與 upper bound，至於 x、y、z 具體是多少，目前還未定，要等到最後執行求解時才知道。

# Create the variable.
x = model.NewIntVar(lb=0, ub=2, name='x')
y = model.NewIntVar(lb=0, ub=2, name='y')
z = model.NewIntVar(lb=0, ub=2, name='z')

接著建立約束，在此約束為「x 不等於 y」：

# Create the constraints
model.Add( x != y )

接著制定目標，目標為三者之合應盡量大：

# Objective
model.Maximize( x + y + z )

在以上兩段類似數學公式的參數中，可以像一般寫公式那樣在運算子和運算元間加入空格比較好閱讀，特別是在公式變得複雜的時候。

接著就可以來執行求解了：

# Create a solver and solve the model
solver = cp_model.CpSolver()
status = solver.Solve(model=model)

那個 status 只是個表示解題狀態的字串，如果內容為 OPTIMAL 或 FEASIBLE，表示有找到解，除了有沒有解之外，我們也很關心那 x、y、z 以及三者之合最後是多少。

要取得模型變數的值，利用 solver 的 Value() 方法，要取得目標值，也就是三者之合，利用 solver 的 ObjectiveValue() 方法，範例如下：

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f'Maximum of objective function: {solver.ObjectiveValue()}\n')
    print(f'x = {solver.Value(expression=x)}')
    print(f'y = {solver.Value(expression=y)}')
    print(f'z = {solver.Value(expression=z)}')
else: print('No solution found.')

輸出如下：

Maximum of objective function: 5.0

x = 1
y = 2
z = 2

除此之外還有一些求解時的統計指標：

# Statistics
print(solver.ResponseStats())

輸出如下：

CpSolverResponse summary:
status: OPTIMAL
objective: 5
best_bound: 5
integers: 1
booleans: 0
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 1
restarts: 0
lp_iterations: 0
walltime: 0.00235364
usertime: 0.00235602
deterministic_time: 0
gap_integral: 0
solution_fingerprint: 0xbc76f3d3e780d9b7

最後完整的程式碼如下：

"""Simple solve"""
from ortools.sat.python import cp_model


"""Minimal CP-SAT example to showcase calling the solver"""
# Create solver model
model = cp_model.CpModel()

# Create the variable.
x = model.NewIntVar(lb=0, ub=2, name='x')
y = model.NewIntVar(lb=0, ub=2, name='y')
z = model.NewIntVar(lb=0, ub=2, name='z')

# Create the constraints
model.Add( x != y )

# Objective
model.Maximize( x + y + z )

# Create a solver and solve the model
solver = cp_model.CpSolver()
status = solver.Solve(model=model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f'Maximum of objective function: {solver.ObjectiveValue()}\n')
    print(f'x = {solver.Value(expression=x)}')
    print(f'y = {solver.Value(expression=y)}')
    print(f'z = {solver.Value(expression=z)}')
else: print('No solution found.')

# Statistics
print(solver.ResponseStats())

上面這份範例，相較於 OptaPy，實在簡單得太多，特別適合我這種傻瓜開發者，也不要因為看起來很簡單就懷疑 OR-Tools 的能力，初步用過 OptaPy 與 OR-Tools 之後個人的心得是，在懷疑它們能不能辦到前，應該先問自己有沒有正確理解問題，以及能不能從問題建立出相對的問題模型。

本文簡單介紹了 Google 的 OR-Tools 求解器，以及一些最基本的知識，更深入的部份等我參透再寫吧。:p

Share