SCIP | 数学规划求解器SCIP超详细的使用教程_混合整数规划求解器——scip

前言

小伙伴们大家好呀！继上次lp_solve规划求解器的推文出来以后，大家都期待着更多求解器的具体介绍和用法。小编哪敢偷懒，这不，赶在考试周之际，又在忙里偷闲中给大家送上一篇SCIP规划求解的推文教程。快一起来看看吧。

 

欲获取代码，请关注我们的微信公众号【程序猿声】，在后台回复：SCIP。即可获取。

 

Part1 惯例科普篇

What is SCIP?

官方的介绍：

SCIP is currently one of the fastest non-commercial solvers for mixed integer programming (MIP) and mixed integer nonlinear programming (MINLP). It is also a framework for constraint integer programming and branch-cut-and-price. It allows for total control of the solution process and the access of detailed information down to the guts of the solver.

SCIP is a framework for Constraint Integer Programming oriented towards the needs of mathematical programming experts who want to have total control of the solution process and access detailed information down to the guts of the solver. SCIP can also be used as a pure MIP and MINLP solver or as a framework for branch-cut-and-price.

SCIP is implemented as C callable library and provides C++ wrapper classes for user plugins. It can also be used as a standalone program to solve mixed integer programs given in various formats such as MPS, LP, flatzinc, CNF, OPB, WBO, PIP, etc. Furthermore, SCIP can directly read ZIMPL models.
有关SCIP概述及其算法的实现原理方法更多详情，可以点击下面链接下载相关文档：

• Constraint Integer Programming: a New Approach to Integrate CP and MIP
  （http://opus.kobv.de/zib/volltexte/2008/1081/pdf/ZR_08_01.pdf）
• SCIP: Solving Constraint Integer Programs
  （http://mpc.zib.de/index.php/MPC/article/view/4）

SCIP的更详细描述：

• Constraint Integer Programming

  （http://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1112）

有关凸与非凸MILPS的全局优化的非线性求解特征：

• SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework

  （http://dx.doi.org/10.1080/10556788.2017.1335312）

SCIP Optimization

SuiteSCIP优化套件是用于生成和求解混合整数非线性规划模型、混合整数线性规划模型和整数约束规划模型的工具集。 它由以下部分组成：

• SCIP mixed integer (linear and nonlinear) programming solver and constraint programming framework
• SoPlex linear programming solver
• ZIMPL mathematical programming language
• UG parallel framework for mixed integer (linear and nonlinear) programs
• GCG generic branch-cut-and-price solver

用户可以使用建模语言ZIMPL轻松生成线性，混合整数和混合整数二次约束的规划模型。 得到的模型可以直接加载到SCIP中并求解。 在解决方案过程中，SCIP可以使用SoPlex作为底层LP求解器。

上面五个组件都可以获得它们的源代码，并且都是免费的。因此它们是用于学术研究和混合整数编程的理想工具。

可以点击下面链接下载SCIP Optimization Suite：
（https://scip.zib.de/index.php#download）

目前最新版本是SCIP version 6.0.0。

支持以下平台：

• Linux
• Mac
• Windows
• SunOS
• Android

SCIP的特点

对于SCIP，它主要有以下几个优点：

• very fast standalone solver for linear programming (LP), mixed integer programming (MIP), and mixed integer nonlinear programming (MINLP)
• framework for branching, cutting plane separation, propagation, pricing, and Benders’ decomposition,
• large C-API, C++ wrapper classes for user plugins
• interfaces to other applications and programming languages (contained in source code packages or available from http://github.com/SCIP-interfaces):

Python
Java
AMPL
GAMS
MATLAB

• open LP solver support:

CPLEX
Gurobi
XPress
Mosek
SoPlex
QSopt
CLP.

• highly flexible through many possible user plugins

Part2 基础入门篇

SCIP-下载和安装前面介绍了这么多，终于要动手撸一撸代码了。想必各位小伙伴也迫不及待了吧。不过这里再强调两句，SCIP和SCIP Optimization Suite的区别就是前者是一个工具，后者是一个工具集。后者包含了前者之外，还包含了其他的求解器。

下载：
前面已经给出了下载地址，大家根据自己的平台下载相应的文件即可。小编系统平台是Windows 10 64bit的。所以就下载了：

安装的话，照旧一路向西。需要注意的是，这里把这些勾选以下，免得后续出现麻烦：

关于SCIP的说明文档，访问（https://scip.zib.de/）定位到右上角Documentation，版本选6.0即可。

0) 好了现在兴高采烈打开命令行，输入SCIP：

纳尼？剧本好像不是这么写的啊。

是什么问题呢？（敲黑板），刚刚即使勾选了把SCIP Optimization Suite添加到系统路径里面，可能对某些情况并不会成功（可能是被杀毒软件拦截了）。所以咱们还是要手动添加一下。

如下图：右键此电脑-属性。然后按下图操作：

找到我们SCIPOptSuite 6.0.0的安装路径，把它复制下来：

然后添加到PATH变量里面：

然后再回到命令行。（注意要重启一下命令行）输入SCIP：

大功告成。

SCIP-简单上手那么，怎么用SCIP求解一个规划问题呢？例如下面一个简单的例子：
Max z = x1 + 2 x2 + 3 x3 + x4
Subject To
- x1 + x2 + x3 + 10 x4 <= 20
x1 - 3 x2 + x3 <= 30
x2 - 3.5 x4 = 0
0 <= x1 <= 40
2 <= x4 <= 3

SCIP支持以下格式的文件：

部分格式文件说明可以点击下面的链接（个别需要科学上网）：

• CNF - file format：
  http://people.sc.fsu.edu/~jburkardt/data/cnf/cnf.html
• FZN - file format：
  http://www.g12.cs.mu.oz.au/minizinc/downloads/doc-1.5/flatzinc-spec.pdf
• (R)LP - file formats：http://publib.boulder.ibm.com/infocenter/cosinfoc/v12r3/topic/ilog.odms.cplex.help/Content/Optimization/Documentation/Optimization_Studio/_pubskel/ps_reffileformatscplex2159.html
• MPS - file format：
  http://en.wikipedia.org/wiki/MPS_%28format%29
• OPB/WBO - file formats：
  http://www.cril.univ-artois.fr/PB12/format.pdf
• OSiL format for MINLP：
  http://www.coin-or.org/OS/OSiL.html
• PIP - file format：
  http://polip.zib.de/pipformat.php
• ZPL - file format：
  http://zimpl.zib.de/download/zimpl.pdf

在这里我们选择CPLEX lp files格式的文件作为演示。将上述模型改写为CPLEX lp files格式便可以用SCIP读取并且求解。例如我们在D:\scip目录下建立一个simple.lp文件，输入以下代码：
Maximize
obj: x1 + 2 x2 + 3 x3 + x4
Subject To
c1: - x1 + x2 + x3 + 10 x4 <= 20
c2: x1 - 3 x2 + x3 <= 30
c3: x2 - 3.5 x4 = 0
Bounds
0 <= x1 <= 40
2 <= x4 <= 3
General
x4
End

保存。

在我们的命令行模式下，进入到D:\scip这个目录。

然后输入以下命令：
1) 首先进入scip：> scip

2) 然后读取我们的模型文件：> read simple.lp

3) 求解我们的问题：> optimize