Google OR-Tools(三) 整数优化Integer Optimization
本文参考Google OR-Tools官网文档介绍OR-Tools的使用方法。
1 整数规划很多实际问题的变量不能是小数，比如指派多少人员、调度的航班数、分配的机器数等等，我们称这种问题为整数规划，更特殊的，如果要求变量只能取0或1，则称为0-1规划；还有些情况是部分决策变量是整数，其他可以是小数，则称其为混合整数规划。虽然我们可以用线性函数来表示目标和约束，但是有了变量必须是整数的约束，可行域变得极度非凸(Nonconvex), 求解难度要比连续变量线性规划大很多，连续变量线性规划的常用算法是不能直接用于整数规划的。关于这一点，后面我们可以给出实例。
解算整数规划的算法中分支界定法及其衍生算法是最常用的，它的核心思想便是把整数规划问题分解成求解一个个的线性规划（LP）问题（每个LP问题是多项式时间可解），并且在求解的过程中实时追踪原问题的上界（最优可行解）和下界（最优线性松弛解）。除此之外，启发式算法或元启发算法(例如遗传算法)也是常用的手段，因为当整数规划的规模较大时，问题已经属于NP-Hard问题了，这时候在合理的时间内找到一个相对最优解已经足够了。
在OR-Tools中用于解决整数规划的工具是MP Solver和CP-SAT Solver，我们先认识MP Solver，至于CP-SAT Solver在下一篇文章中介绍，因为两者的适用情况是不一样的。
OR-Tools实际上提供的是统一的求解器接口，内部连接的具体求解器我们可以自己配置，默认连接的是OR-Tools内置的CBC(Coin-or branch and cut)求解器，除此之外也支持下面几种第三方求解器：
不过如果要用第三方求解器的话就必须配置OR-Tools源码并手动安装，具体信息可参考官网的安装教程。
另外一点是，MP Solver的算法属于通用型算法，而像路径优化、背包问题和网络流问题这些特定的问题领域，因为场景在现实领域非常常见，有专门解决这类问题的特定算法，因此如果是对这些问题，就不建议使用MP Solver了，而是使用OR-Tools提供的特定接口。
我们例举下面这个例子：
maximizex+10ysubject tox+7y≤17.5x≤3.5x≥0y≥0x,y∈integers
\begin{aligned}
maximize\quad& x+10y\\
subject\ to\quad& x+7y\leq 17.5 \\
& x\leq 3.5 \\
& x\geq 0 \\
& y\geq 0 \\
& x,y \in integers
\end{aligned}
maximizesubject tox+10yx+7y≤17.5x≤3.5x≥0y≥0x,y∈integers
其模型结构和线性规划基本一致，除了多出两个变量必须为整数的约束。下面这张图则更直观地表现这个问题：
我们创建一个.Net Core控制应用，并下载OR-Tools。
首先创建Solver对象，这里我们指明连接的求解器是CBC
// Create the linear solver with the CBC backend.
Solver solver = Solver.CreateSolver("SimpleMipProgram", "CBC_MIXED_INTEGER_PROGRAMMING");
定义变量xxx和yyy，注意这里我们调的接口是MakeIntVar而不是线性规划时调的MakeNumVar
// x and y are integer non-negative variables.
Variable x = solver.MakeIntVar(0.0, double.PositiveInfinity, "x");
Variable y = solver.MakeIntVar(0.0, double.PositiveInfinity, "y");
定义约束和目标
// x + 7 * y <= 17.5.
solver.Add(x + 7 * y <= 17.5);
// x <= 3.5.
solver.Add(x <= 3.5);
// Maximize x + 10 * y.
solver.Maximize(x + 10 * y);
计算得到解，规划问题有时候未必有解，因此我们需要查看Solver对象的计算结果是否是OPTIMAL
Solver.ResultStatus resultStatus = solver.Solve();
// Check that the problem has an optimal solution.
if (resultStatus != Solver.ResultStatus.OPTIMAL)
{
Console.WriteLine("The problem does not have an optimal solution!");
return;
}
Console.WriteLine("Solution:");
Console.WriteLine("Objective value = " + solver.Objective().Value());
Console.WriteLine("x = " + x.SolutionValue());
Console.WriteLine("y = " + y.SolutionValue());
完整的程序和运行结果：
using System;
using Google.OrTools.LinearSolver;
namespace Demo3
{
class Program
{
static void Main(string[] args)
{
// Create the linear solver with the CBC backend.
Solver solver = Solver.CreateSolver("SimpleMipProgram", "CBC_MIXED_INTEGER_PROGRAMMING");
// x and y are integer non-negative variables.
Variable x = solver.MakeIntVar(0.0, double.PositiveInfinity, "x");
Variable y = solver.MakeIntVar(0.0, double.PositiveInfinity, "y");
Console.WriteLine("Number of variables = " + solver.NumVariables());
// x + 7 * y <= 17.5.
solver.Add(x + 7 * y <= 17.5);
// x <= 3.5.
solver.Add(x <= 3.5);
Console.WriteLine("Number of constraints = " + solver.NumConstraints());
// Maximize x + 10 * y.
solver.Maximize(x + 10 * y);
Solver.ResultStatus resultStatus = solver.Solve();
// Check that the problem has an optimal solution.
if (resultStatus != Solver.ResultStatus.OPTIMAL)
{
Console.WriteLine("The problem does not have an optimal solution!");
return;
}
Console.WriteLine("Solution:");
Console.WriteLine("Objective value = " + solver.Objective().Value());
Console.WriteLine("x = " + x.SolutionValue());
Console.WriteLine("y = " + y.SolutionValue());
Console.WriteLine("\nAdvanced usage:");
Console.WriteLine("Problem solved in " + solver.WallTime() + " milliseconds");
Console.WriteLine("Problem solved in " + solver.Iterations() + " iterations");
Console.WriteLine("Problem solved in " + solver.Nodes() + " branch-and-bound nodes");
}
}
}
我们可以看到解算整数规划的代码和之前介绍的线性规划程序几乎一致，那么我们可以改成线性规划来计算结果看看其结果的差异如何
改成线性规划问题只需要该几行代码，首先把CBC求解器改成GLOP:
// Create the linear solver with the CBC backend.
//Solver solver = Solver.CreateSolver("SimpleMipProgram", "CBC_MIXED_INTEGER_PROGRAMMING");
Solver solver = Solver.CreateSolver("SimpleMipProgram", "GLOP_LINEAR_PROGRAMMING");
再把MakeIntVar改成MakeNumVar
//Variable x = solver.MakeIntVar(0.0, double.PositiveInfinity, "x");
//Variable y = solver.MakeIntVar(0.0, double.PositiveInfinity, "y");
Variable x = solver.MakeNumVar(0.0, double.PositiveInfinity, "x");
Variable y = solver.MakeNumVar(0.0, double.PositiveInfinity, "y");
其运算结果：
可以看到其结果和整数规划下的结果相差是比较大的，因此这两种规划问题所采用的算法也不一致。下面这副图直观地表现出区别
作者：皇家园林巡游者
