OR-Tools下的约束规划（constraint programing）简介

1.OR-Tools简介

OR-Tools是Google开源的运筹优化的工具，旨在从大量可能的解决方案中寻找最佳的解决方案。能够用于解决车辆路径、排程、装箱、网络流以及整数和线性规划等棘手问题。OR-Tools是人工智能领域重要的开源工具。

OR-Tools是用C ++编写的，但是支持C++，Java，C#，Python语言进行编写。以下采用的是Python语言进行编写。

官方文档地址（需要翻墙）：https://developers.google.com/optimization
开源代码地址：https://github.com/google/or-tools

2.OR-Tools约束优化求解使用介绍

OR-Tools在约束优化求解问题下使用的求解器是CP-SAT，以下对CP-SAT的建模语法cp_model进行介绍。

CpModel：用于创建模型，其中Cp的全称是constraint programing（约束规划），可以不设置目标，求出的解是可行解或者无解，也可以设置目标，求出的解是最优的、可行的或者无解。与约束规划相对的是good programing（目标规划）。

在OR-Tools中CpModel用于的是整数规划的问题，所以里面处理数必须是int类型，并且要求是线性的运算。如果处理的数是浮点数，可以将要处理的浮点数都乘上某个值使得它们都转化为整数进行处理，例如要处理的数为0.5，可以将0.5乘上10转化乘5进行处理，最后输出的时候将值除以10即可。

CpSolver：用于整数规划问题的约束满足问题（Constraint Satisfaction Problem）求解。

约束限制（constraint）：一般用Add方法进行添加。
决策变量：一般用new的方法进行创建。
目标制定（objective）：一般用max或者min进行目标的制定。

3.OR-Tools约束优化求解的简单使用

python下载OR-Tools的包

pip install ortools

导入包中的cp_model

from ortools.sat.python import cp_model

创建model

model = cp_model.CpModel()

添加变量、约束和目标（根据自己的需求进行建模）

#创建整数变量
x = model.NewIntVar(10, 100, 'makespan1')
y = model.NewIntVar(30, 70, 'makespan2')
#添加约束
model.Add(x + y < 50)
#制定目标
model.Maximize(x - y)

创建一个solver并进行求解

solver = cp_model.CpSolver()
solver.Solve(model)

print('x:'+str(solver.Value(x)))
print('y:'+str(solver.Value(y)))

最终输出的答案

x:19
y:30

4.OR-Tools约束求解常用方法说明

列出一些具体常用的方法，具体使用的说明可查看官方文档。

1. model.NewIntVar：创建一个整数变量
2. model.NewIntervalVar：创建一个区间变量
3. model.AddNoOverlap：确保区间变量不会有交集
4. model.AddAllDifferent：每个变量的取值都不能相同
5. model.AddAbsEquality：变量的绝对值等于一个数
6. model.AddImplication：添加蕴含逻辑关系约束
7. model.NewBoolVar：创建一个0-1整数变量
8. model.Add：可添加一些指定的约束条件
9. LinearExp.Sum：用于线性求和