Google OR-Tools : 如何快速尋找最佳解

最近在找尋排班方法，意外找到這個方便的工具Google OR-tools
本著程式界小白的精神，順便整理google內附的範例
以後可以複習用

在閱讀之前要先了解何謂optimization problem

舉個簡單的例子
假設今天我們有n艘船，每艘船的承載量都不同
有x種貨物，每個貨物重量不同
（今天先不考慮貨物大小）
要如何讓每艘船達到最大負載量
以往沒有這公式，大部分的人就只能憑經驗去分配
但自從服用了OR-tools，我每次考試都考１００分呢（誤）
可以幫我們快速尋找到最佳解

廢話不多說，我們先來看第一個例子
先從簡單的線性優化（linear optimization）開始

條件：

0	≤	x	≤	1
0	≤	y	≤	2
		x + y	≤	2

目標：
取 3x+y 的最大值

在開始解之前，大家先記得以下步驟，
這是你在思考每個題目時的思考邏輯

# Step 1: Import the linear solver, or MIP, or cp_model
# Step 2: Add the solution printer
# Step 3: Declare the linear solver, or MIP, or cp_model
# Step 4: Create a database and requests
# Step 5: Create the variables
# Step 6: Define the constraints
# Step 7: Define the objective
# Step 8: Create a solver and invoke solve
# Step 9: Call a printer and display the results

裡面的每個步驟不一定都會用到，但大抵都是照著這個去走

# Step 1: Import the linear solver, or MIP, or cp_model

from __future__ import print_functionfrom ortools.linear_solver import pywraplp

如果還沒安裝OR-tools的人記得去安裝
第一步先匯入線性優化的工具，
不懂沒關係，多看幾次就知道了
之後還有MIP和CP-SAT，都是類似的

# Step 5: Create the variables

這裡直接跳到Step 5，因為沒有太多參數及限制條件

# Create the variables x and y.
x = solver.NumVar(0, 1, 'x')
y = solver.NumVar(0, 2, 'y')
print('Number of variables =', solver.NumVariables())

限定x介於0到1之間的變數(NumVar)，並且將他的名稱叫做'x'
限定y介於0到2之間的變數，並且將他的名稱叫做'y'

# Step 6: Define the constraints

# Create a linear constraint, 0 <= x + y <= 2.
ct = solver.Constraint(0, 2, 'ct')
ct.SetCoefficient(x, 1)
ct.SetCoefficient(y, 1)
print('Number of constraints =', solver.NumConstraints())

定義約束(Constraint)條件:
    1) 先定義這個constraint叫'ct'，並且他會介於0-2之間
    2) 設定x和y之前的係數

# Step 7: Define the objective

# Create the objective function, 3 * x + y.
objective = solver.Objective()
objective.SetCoefficient(x, 3)
objective.SetCoefficient(y, 1)
objective.SetMaximization()

定義我們的目標(objective)
    1) 將objective叫賦值給objective
    2) 設定x和y之前的係數
    3) 目標是取最大值 SetMaximization

# Step 8: Create a solver and invoke solve

# Create the linear solver with the GLOP backend.
solver = pywraplp.Solver('simple_lp_program',
                         pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

指定pywraplp內的參數GLOP_LINEAR_PROGRAMMINGGLOP來解

solver.Solve()
print('Solution:')
print('Objective value =', objective.Value())
print('x =', x.solution_value())
print('y =', y.solution_value())

調用solver.Solve()並且印出解答

之後當我們運用這個程式時，可以得到

Solution:
x =  1.0
y =  1.0

是不是輕鬆又愉快呢，為什麼以前數學要寫這麼久呢ＱＱ
下次開始正式介紹線性優化了
同樣的東西，其實可以寫得更簡單喔