Google OR-Tools

[jasperzhong]

https://developers.google.com/optimization

简直就是宝藏！！！

OR-Tools is open source software for combinatorial optimization, which seeks to find the best solution to a problem out of a very large set of possible solutions.

[jasperzhong]

Job-shop Scheduling

就是有一些jobs, 每个job还有一系列的tasks, 每个task需要到固定的机器上执行, 有一定的执行时间, 一个机器同时只能执行一个task.

举个例子.

• job 0 = [(0, 3), (1, 2), (2, 2)]
• job 1 = [(0, 2), (2, 1), (1, 4)]
• job 2 = [(1, 4), (2, 3)]

job 0有三个tasks. 第一个, (0, 3)表示需要在机器0上执行，执行时间是3. 以此类推.

我们用task(i, j)表示第i个job的第j个任务.

这个问题的variables是 t_{i, j}，表示task(i, j)的开始时间.

这个问题的constrains有两个

• precedence constraints (优先限制): 即每个job的任务有固定的执行顺序，不能改变. 比如task(0, 2)和task(0, 3)是job 0的两个顺序执行的任务, task(0, 2)的执行时间是2, 所以有 t{0, 2} + 2 \leq t{0, 3}.
• no overlap constaints. 这是因为同一个机器不能同时执行两个任务. 比如task(0, 2)和task(2, 1)都要在机器1上执行，执行时间分别为2和4. 所以以下两个条件需要满足其中一个: t{0, 2} + 2 \leq t{2, 1} or t{2, 1} + 4 \leq t{0, 2}.

[jasperzhong]

Overview

优化问题的目标是从一个很大的解空间中找到一个最优解. （有时候也许找到一个可行解也够了）.

优化问题包括：优化目标和约束.

• 优化目标是去量化我们想优化的东西. 我们需要定义一个函数来计算每一个解的目标值. 这叫做目标函数. 最优解是指优化函数的值是最优的（a maximum or a minimum）
• 约束时解的限制条件. 可行解是满足所有约束的解.

解决优化问题的第一步就是明确优化目标和约束.

优化问题分类

• Linear optimization: 优化目标和约束都是变量的线性表达式.
• Constraint optimization: 也叫做constraint programming (CP). 只用来找可行解.
• Mixed-integer optimization: 部分或者所有变量要求是整数.
• Bin packing: 一些不同大小的物体装入不同容量的箱子里. 其中一个特殊的问题是knapsack问题，只有一个箱子.
• Network flows: 网络流.
• Assignment: 分配一组代理（如工人或者机器）给一组任务，其中每个代理分配给特定任务的成本是固定的. 问题是找到总开销最低的分配. 分配问题是特殊的网络流问题.
• Scheduling: 在特定时间分配资源执行一些任务. 一个重要的例子是job shop problem.
• Routing: 为车队寻找穿越网络的最优路线. 典型问题是TSP.

[jasperzhong]

Constraint Optimization

也叫constraint programming (CP)."programming"指的是规划, 而不是编程.

CP是基于可行性(找到一个可行解)而不是优化(找到一个最优解)，关注于约束和变量而不是目标函数. 实际上，CP问题可能都不包含目标函数 - 目的可能仅仅是缩小搜索空间的范围.

比如employee scheduling问题就是一个典型例子.

A hospital supervisor needs to create a schedule for four nurses over a three-day period, subject to the following conditions:

• Each day is divided into three 8-hour shifts.
• Every day, each shift is assigned to a single nurse, and no nurse works more than one shift.
• Each nurse is assigned to at least two shifts during the three-day period.

举了一个Cryptarithmetic Puzzles例子确实不错. https://developers.google.com/optimization/cp/cryptarithmetic

在N皇后问题中提到了约束规划的两个重要elements:

• propagation: 看上去就是用约束来剪枝. 比如N皇后问题中，每次放置一个皇后之后，下次就不能在这个皇后所在行列对角线放置其他皇后了，可以利用这点剪枝. 这大大减少了要搜索的范围.
• backtracking: 回溯. 就是当找到一个解或者无法继续搜索的时候回到上一个状态.

所以其实CP就是dfs+剪枝.