专栏首页数据魔术师干货 | 嘿,快递,这里有份数学规划求解器SCIP超详细的使用教程,请你收下

干货 | 嘿,快递,这里有份数学规划求解器SCIP超详细的使用教程,请你收下

前言

小伙伴们大家好呀!继上次lp_solve规划求解器的推文出来以后,大家都期待着更多求解器的具体介绍和用法。小编哪敢偷懒,这不,赶在考试周之际,又在忙里偷闲中给大家送上一篇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 Suite

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

  • 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 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

4) 输出一大堆信息以后,问题已经求解完毕。我们把solution显示出来:> display solution

OK,至此,问题已经求解完毕。

有关SCIP的更多使用,使用help命令可以查看详细说明:

关于CPLEX lp files,可以访问下面链接查看详细说明:

(http://lpsolve.sourceforge.net/5.5/CPLEX-format.htm)

Part3

实战篇

python下使用SCIP

平台还是Windows10 64位。

先用pip把SCIP的包给装上:

pip install pyscipopt

然后记得把环境变量给配置好了。(不知道的同学会去看【SCIP-下载和安装】PATH路径的配置)。

1、进入Python,导入相应的模块:

>> from pyscipopt import Model

2、创建一个实例模型.

>> model = Model("Example") # model name is optional

3、通过模型求解相关问题,举一个栗子, e.g.:

>> x = model.addVar("x") >> y = model.addVar("y", vtype="INTEGER") >> model.setObjective(x + y) >> model.addCons(2*x - y*y >= 0) >> model.optimize()

更多详细说明可以查看这个:

https://github.com/SCIP-Interfaces/PySCIPOpt

Java下使用SCIP

附:代码文件下载请移步留言区。

java下使用SCIP比较麻烦的是,需要自己编译后才能调用。这里简要说明一下编译过程(不想了解的可以跳到第4)步,编译好的文件小编会分享给大家的。):

环境:Windows 10 64位、jdk 64位

注意路径都不要有中文!!!注意路径都不要有中文!!!

1) 小编在这里使用的是Cmake+VS2017编译(所以在此之前确保你安装了Cmake和相关的C编译器)。首先到

(https://github.com/SCIP-Interfaces/JSCIPOpt)

下载整个项目下来,解压到某个文件夹,在命令行下进入该文件夹:

2) 进来以后,创建一个build目录,以用来生成相关文件,然后进入build目录

进来以后,输入cmake .. -G "Visual Studio 15 2017 Win64" 进行相关配置。注意你的编译器,我这里用的是vs2017所以是"Visual Studio 15 2017 Win64",其他编译器设置成相应的名字,比如vs2015就是"Visual Studio 14 2015 Win64"等等。

3) 最后,输入cmake --build . --config "Release" 进行编译。

4) 在build\Release目录下得到我们的成品然后把jscip.dll文件拷贝到C:\Windows\System32,后续编程过程需要用到这个dll,以便编译器找到它。:

至此,编译已经完成。

如何在项目里调用SCIP的接口呢?小编还是先新建一个工程testscip为大家讲解:

1) 新建好一个java工程以后,右键项目,选择Properties,和上次一样,把我们编译出来的scip.jar给导入到工程里面:

2) 然后就可以开始写代码了,下面提供了一个example:

 1package testscip;
 2import jscip.*;
 3
 4
 5public class testscipMain {
 6
 7    public static void main(String[] args) {
 8        // TODO Auto-generated method stub
 9        Scip scip = new Scip();
10        System.loadLibrary("jscip");
11
12        // set up data structures of SCIP
13        scip.create("LinearExample");
14
15        // create variables (also adds variables to SCIP)
16        Variable x = scip.createVar("x", 2.0, 3.0, 1.0, SCIP_Vartype.SCIP_VARTYPE_CONTINUOUS);
17        Variable y = scip.createVar("y", 0.0, scip.infinity(), -3.0, SCIP_Vartype.SCIP_VARTYPE_INTEGER);
18
19        // create a linear constraint
20        Variable[] vars = {x, y};
21        double[] vals = {1.0, 2.0};
22        Constraint lincons = scip.createConsLinear("lincons", vars, vals, -scip.infinity(), 10.0);
23
24        // add constraint to SCIP
25        scip.addCons(lincons);
26
27        // release constraint (if not needed anymore)
28        scip.releaseCons(lincons);
29
30        // set parameters
31        scip.setRealParam("limits/time", 100.0);
32        scip.setRealParam("limits/memory", 10000.0);
33        scip.setLongintParam("limits/totalnodes", 1000);
34
35        // solve problem
36        scip.solve();
37
38        // print all solutions
39        Solution[] allsols = scip.getSols();
40
41        for( int s = 0; allsols != null && s < allsols.length; ++s )
42           System.out.println("solution (x,y) = (" + scip.getSolVal(allsols[s], x) + ", " + scip.getSolVal(allsols[s], y) + ") with objective value " + scip.getSolOrigObj(allsols[s]));
43
44        // release variables (if not needed anymore)
45        scip.releaseVar(y);
46        scip.releaseVar(x);
47
48        // free SCIP
49        scip.free();
50
51    }
52
53}

输出结果:

更多的example可以在这里找到

(https://github.com/SCIP-Interfaces/JSCIPOpt/tree/master/examples)

小编编译好的成品库文件和dll可以在这里下载

(https://pan.baidu.com/s/1w3Dd4lP8ypslFHC5wtvPGQ)

附:代码文件下载请移步留言区。

C/C++下使用SCIP

这官方的文档给的是Linux环境的配置,小编在Windows下摸索了老半天,总算是把这程序跑起来了。天呐,这过程太艰难了。下面开始说重点啦。

1) 首先在这里(https://github.com/SCIP-Interfaces/CSIP)把整个项目给download下来。解压到某个位置。

2) 打开编译器,小编这里还是用VS2017作为演示,新建一个空项目。然后把include\csip.h、src\csip.c这两个文件复制到我们的项目目录:

把这两个文件添加到项目文件里面:

3) 编译环境选择64位,一定要选择64位,一定要选择64位,不然不会成功:

在项目属性里面:

包含目录把之前安装的SCIPOptSuite 6.0.0下的include目录包含进去。

库目录把之前安装的SCIPOptSuite 6.0.0下的lib目录包含进去。

4) 然后,在链接器-输入-附加依赖库-把scip.lib添加进去:

最后,在csip.c开头添加这句:

至此,已经配置完成了。另外,把include<csip.h> 改为 include"csip.h"。

下面进行代码测试,下面的代码实例了很多模型的求解过程:

找到之前在GitHub下载的CSIP项目的解压文件,把test目录的代码文件复制到vs的项目目录:

同样,把这两文件添加到源代码里面:

test.c文件里面,拉到最后,把这两行注释掉:

编译时提示除0错误,也改过来就行。然后就可以愉快跑起来啦。

不得不吐槽一下这说明文档,写得太模糊不清了,害的小编苦苦编译调试了老半天,最后走投无路的时候发现是lib库没法生成,是版本问题(所以,敲黑板,一定要选64位的编译模式啊。)。不过,也可能是小编太菜啦。然后嘛,毕竟人家是开源的项目,咱们也不能要求太高啦。

附:相关代码文件下载请移步留言区。

Part4

小结

好啦,上面就是SCIP大体的使用教程了。总结起来无非就下面几点:

  1. 使用SCIP自带的求解器,在命令行模式下求解相应的模型文件。
  2. 写程序进行建模,调用SCIP相关的API,进行求解。

可能还有很多遗漏的点没有说,还请各位读者见谅哈,各个方面的资料说明都在文章中给出了。相应的资源也在文章中给出了。最后,谢谢大家!

【如对代码有疑问,可联系小编,可以提供有偿辅导服务】

【有偿辅导纯属个人行为,与团队无关】

精彩文章推荐

干货 | 变邻域搜索算法(VNS)求解TSP(附C++详细代码及注释)

干货 | 变邻域搜索算法(Variable Neighborhood Search,VNS)超详细一看就懂

干货 | 遗传算法(Genetic Algorithm) Java 详细代码及注释

干货 | 遗传算法(Genetic Algorithm) (附代码及注释)

干货|迭代局部搜索算法(Iterated local search)探幽(附C++代码及注释)

干货 | 用模拟退火(SA, Simulated Annealing)算法解决旅行商问题

---The End---

文案 && 编辑:邓发珩

审稿:江玉萍

测试:成贤樟

指导老师: 秦时明岳(华中科技大学管理学院)

如对文中内容有疑问,欢迎交流。PS:部分资料来自网络。

如有需求,可以联系:

秦虎老师(professor.qin@qq.com)

邓发珩 (华中科技大学管理学院本科二年级:2638512393@qq.com、个人公众号:程序猿声)

江玉萍 (南京大学工程管理学院研究生三年级:jiangyuping@smail.nju.edu.cn)

成贤樟 (华中科技大学管理学院本科三年级:hust_st_cxz@foxmail.com)

本文分享自微信公众号 - 数据魔术师(data-magician)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-11-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • android-ramdisk.img分析、recovery.img&boot.img执行过程【转】

    ramdisk通过直面意思就大概能理解意思,ram disk虚拟内存盘,将ram模拟成硬盘来使用的文件系统。对于传统的磁盘文件系统来说,这样做的好处是可以极大提...

    233333
  • 【Java基本功】一文读懂Java中的泛型

    本文参考https://blog.csdn.net/s10461/article/details/53941091

    Java技术江湖
  • 【Java基本功】离开IDE,使用javac和Java构建项目

    前言:本文教你怎么用javac和java命令,讲解了classpath的原理,以及如何利用脚本(shell或bat)进行项目部署,离开ide,还原最本质的Jav...

    Java技术江湖
  • nginx下使用asan和valgrind两个静态检查工具

    valgrind安装:参考:https://blog.csdn.net/justheretobe/article/details/52986461

    用户1215536
  • 如何使用浏览器访问linux本地文件

    配置nginx.conf ,将/usr/local/nginx/conf/nginx.conf替换为以下内容:

    用户5521279
  • 【Java基本功】很多人经常忽视的Java基础知识点

    主函数可以被重载,但是JVM只识别main(String[] args),其他都是作为一般函数。这里面的args知识数组变量可以更改,其他都不能更改。

    Java技术江湖
  • 【Java基本功】一文了解Java中继承、封装、多态的细节

    封装主要是因为Java有访问权限的控制。public > protected > package = default > private。封装可以保护类中的信息...

    Java技术江湖
  • 关于交易的gas 与gassPrice概念已经交易阻塞

    以太坊的交易是通过旷工从矿池中挖矿完成的,而挖矿是❓通俗讲就是将矿池中提交的交易按照价格高低进行筛选打包成块的过程

    大话swift
  • GDB入门教程之如何使用GDB启动调试

    写在前面:今天开始尝试写写除Vim外的其他内容,仍然是以技术为主,可能涉及的内容包括Linux、正则表达式、gdb、makefile等内容,不知道小伙伴们有没有...

    我被狗咬了
  • Java 调试工具、热部署、JVM 监控工具都用到了它

    我们平时写 Java Agent 的机会确实不多,也可以说几乎用不着。但其实我们一直在用它,而且接触的机会非常多。下面这些技术都使用了 Java Agent 技...

    猿天地

扫码关注云+社区

领取腾讯云代金券