关于人工智能:运筹优化工具ortools解读与实践ortools求解LPIPMIP问题

1. 前言

在之前的文章中，运筹优化工具 ortools 解读与实际 - 概览 曾经介绍过线性规划、整数布局、束缚布局的概念。

针对以上问题，ortools 提供了多种解决方案：

• MPSolver 接口：ortools 提供一个名为 MPSolver 的接口，实现了对泛滥 LP、MIP 第三方求解器的封装，其中也蕴含了 google 自研的线性规划求解器 Glop。
• CP-SAT 求解器：google 自研解决 CP 问题的求解器。为了进步求解器计算速度，CP-SAT 被设计成只反对整数问题。因而，当束缚中含有非整数变量时，须要通过乘以一个较大的数转变为整数问题。
• Original CP Solver：解决 CP 问题的晚期求解器，官网倡议应用 CP-SAT。

有意思的是，同样是自研求解器，Glop与第三方求解器并无差别，都须要 MPSolver 初始化之后应用；CP-SAT却是非凡的存在，不与 MPSolver 一起应用，编码格调也有较大变动。

这里以一个线性规划问题引出 MPSolver 及 Glop 求解器的应用办法（整数布局和混合整数布局同样实用）。

2. 套路

针对线性规划问题，求解过程分为 7 步：

• 1. 加载一个线性求解器的 wrapper
• 2. 实例化求解器
• 3. 创立变量，为变量设置上上限
• 4. 定义束缚
• 5. 定义指标函数
• 6. 调用求解办法
• 7. 输入求解后果

在 ortools 官网文档中，主推 google 自研的 GLOP 求解器，从应用体验来讲，GLOP 开发接口十分敌对，代码开发与数学建模完全一致，执行效率也十分高。

3. 案例

依照运筹优化工具 ortools 解读与实际 - 概览中的“三段式”形容解决线性规划问题的过程。

定义问题

e.g. 某企业有两种不同的投资渠道，A 渠道有 3 倍潜在收益，B 渠道有 4 倍的潜在收益。但思考到企业倒退和危险管制，制订了肯定的投资标准：
1）企业账户总金额为 14W
2）每向 B 渠道减少一笔投资，须要留出雷同数额的准备金应答危险
3）投资 B 渠道的金额不应超过 A 渠道投资额的 3 倍
4）A 渠道投资额与 B 渠道投资额之差，应该 2W 以内

定义问题须要将后续建模中优化指标、决策变量、约束条件以自然语言的模式明确分明。其次，作为算法人员，须要依据集体常识储备及过往教训大体明确问题类型和可能的解决方案。

在工作当中，定义问题是最重要的环节。

建模问题

优化指标：Maximize 3x + 4y
决策变量：x、y
约束条件：

• x + 2y ≤ 14
• 3x – y ≥ 0
• x – y ≤ 2
• x ≥ 0
• y ≥ 0

求解问题

#1. 加载一个线性求解器的 wrapper
from ortools.linear_solver import pywraplp


#2. 实例化求解器，这里应用的是 Google 自研的 GLOP 线性规划求解器
solver = pywraplp.Solver.CreateSolver('GLOP')

# 3. 创立变量，为变量设置上上限
x = solver.NumVar(0, solver.infinity(), 'x')
y = solver.NumVar(0, solver.infinity(), 'y')

print('Number of variables =', solver.NumVariables())

#4. 定义束缚
# Constraint 0: x + 2y <= 14.
solver.Add(x + 2 * y <= 14.0)

# Constraint 1: 3x - y >= 0.
solver.Add(3 * x - y >= 0.0)

# Constraint 2: x - y <= 2.
solver.Add(x - y <= 2.0)

print('Number of constraints =', solver.NumConstraints())

#5. 定义指标函数
solver.Maximize(3 * x + 4 * y)

#6. 调用求解办法
status = solver.Solve()

#7. 输入求解后果
if status == pywraplp.Solver.OPTIMAL:
    print('Solution:')
    print('Objective value =', solver.Objective().Value())
    print('x =', x.solution_value())
    print('y =', y.solution_value())
else:
    print('The problem does not have an optimal solution.')

print('\nAdvanced usage:')
print('Problem solved in %f milliseconds' % solver.wall_time())
print('Problem solved in %d iterations' % solver.iterations())

4.MPSolver 构造

除了 GLOP，ortools 同样反对其余求解器。

• CLP_LINEAR_PROGRAMMING or CLP
• CBC_MIXED_INTEGER_PROGRAMMING or CBC
• GLOP_LINEAR_PROGRAMMING or GLOP
• BOP_INTEGER_PROGRAMMING or BOP
• SAT_INTEGER_PROGRAMMING or SAT or CP_SAT
• SCIP_MIXED_INTEGER_PROGRAMMING or SCIP
• GUROBI_LINEAR_PROGRAMMING or GUROBI_LP
• GUROBI_MIXED_INTEGER_PROGRAMMING or GUROBI or GUROBI_MIP
• CPLEX_LINEAR_PROGRAMMING or CPLEX_LP
• CPLEX_MIXED_INTEGER_PROGRAMMING or CPLEX or CPLEX_MIP
• XPRESS_LINEAR_PROGRAMMING or XPRESS_LP
• XPRESS_MIXED_INTEGER_PROGRAMMING or XPRESS or XPRESS_MIP
• GLPK_LINEAR_PROGRAMMING or GLPK_LP
• GLPK_MIXED_INTEGER_PROGRAMMING or GLPK or GLPK_MIP

例如，将 GLOP 变更为 SCIP 或 CP-SAT，同样能够失去最优解。

# solver = pywraplp.Solver.CreateSolver('GLOP')
solver = pywraplp.Solver.CreateSolver('SCIP')

有几个重要的函数，别离是：

NumVar()：创立数值型变量，当然也能够创立其余变量，例如整型变量 IntVar、布尔型变量 BoolVar
solver.Add()：设置束缚
solver.Objective().Value()：获取指标函数后果
solution_value：获取求解后果中变量的值
SetMaximization：指定求最大值还是求最小值

理解了以上次要内容，就能够照葫芦画瓢解决一些简略的线性规划问题了！遇到其余细节能够查阅 ortools 源代码，理解更多办法。

5. 硬编码 VS 数组存储

能够看到，咱们将模型因素硬编码到代码中，这种形式可读性十分强。同样也有毛病，如果咱们的因素参数并不是固定的，会随着工夫的推移发生变化，此时，硬编码的模式将不利于工程化实现。

为此，ortools 提供了一种数组存储模型因素的形式。

咱们将第 3 节案例，依照数组存储模型的形式进行编码，运行后果雷同。

#1. 加载一个线性求解器的 wrapper
from ortools.linear_solver import pywraplp

def create_data_model():
    """Stores the data for the problem."""
    data = {}
    #束缚不等式左侧局部参数
    data['constraint_coeffs'] = [[1, 2],
        [-3, 1],
        [1, -1],
    ]
    #束缚不等式右侧局部参数
    data['bounds'] = [14.0, 0.0, 2.0]
    #指标函数局部参数
    data['obj_coeffs'] = [3,4]
    data['num_vars'] = 2
    data['num_constraints'] = 3
    return data

data = create_data_model()

#2. 实例化求解器，这里应用的是 Google 自研的 GLOP 线性规划求解器
solver = pywraplp.Solver.CreateSolver('GLOP')

infinity = solver.infinity()

# 3. 创立变量，为变量设置上上限
x = {}
for j in range(data['num_vars']):
    x[j] = solver.NumVar(0, infinity, 'x[%i]' % j)

print('Number of variables =', solver.NumVariables())

#4. 定义束缚
for i in range(data['num_constraints']):
        constraint = solver.RowConstraint(-infinity, data['bounds'][i], '')
        for j in range(data['num_vars']):
            constraint.SetCoefficient(x[j], data['constraint_coeffs'][i][j])
print('Number of constraints =', solver.NumConstraints())


#5. 定义指标函数
objective = solver.Objective()
for j in range(data['num_vars']):
    objective.SetCoefficient(x[j], data['obj_coeffs'][j])
objective.SetMaximization()

#6. 调用求解办法
status = solver.Solve()

#7. 输入求解后果
if status == pywraplp.Solver.OPTIMAL:
    print('Solution:')
    print('Objective value =', solver.Objective().Value())
    for j in range(data['num_vars']):
        print(x[j].name(), '=', x[j].solution_value())
else:
    print('The problem does not have an optimal solution.')

print('\nAdvanced usage:')
print('Problem solved in %f milliseconds' % solver.wall_time())
print('Problem solved in %d iterations' % solver.iterations())

特地留神，为了束缚局部代码块编码不便，须要将束缚对立，我这里对立改成了≤的模式。对应的，create_data_model()办法中的编码与建模时存在差别。

原束缚表达形式:

• x + 2y ≤ 14
• -3x + y ≤ 0
• x – y ≤ 2
• x ≥ 0
• y ≥ 0
  援用
  调整后的表达形式:
• x + 2y ≤ 14
• 3x – y ≥ 0
• x – y ≤ 2
• x ≥ 0
• y ≥ 0

6. 结语

本篇文章次要解说了 ortools 利用 MPSolver 及其他求解器解决 LP、IP、MIP 问题的两种办法。这里引出两个问题：

• 不同求解器有哪些异同，理论我的项目中应该如何抉择？
• CP 问题如何求解，google 自研的 CP-SAT 有何特别之处？

以上两个问题将在后续文章中探讨。