SCIP教程

SCIP是什么

SCIP（Solving Constraint Integer Programs）是一个用于求解约束整数规划（Constraint Integer Programming，CIP）问题的优化软件框架。它结合了混合整数线性规划（MILP）、混合整数非线性规划（MINLP）以及约束规划（CP）技术，广泛应用于学术研究和工业优化中。SCIP不仅能够处理线性和非线性约束，还支持用户自定义约束和启发式算法，从而提供了灵活且强大的优化能力。

SCIP Optimization是一套用于生成和求解混合整数非线性规划（MINLP）、混合整数线性规划（MILP）以及整数约束规划（CIP）模型的优化工具。它由多个强大且灵活的组件组成，支持多种优化需求。以下是各组件的简要介绍及其在优化过程中的应用：

1. SCIP：

   • 简介：SCIP（Solving Constraint Integer Programs）是一个集成了混合整数线性规划、混合整数非线性规划和约束规划的求解器和框架。
   • 功能：支持用户定义的约束和启发式算法，能够处理复杂的优化问题，包括线性和非线性约束。
   • 使用：用户可以通过C、C++、Python等编程语言接口使用SCIP，或通过数学建模语言ZIMPL来定义优化问题。

2. SoPlex：

   • 简介：SoPlex是一个高性能的线性规划（LP）求解器。
   • 功能：解决大型线性规划问题，提供精确的单纯形法和内点法。
   • 使用：与SCIP无缝集成，为MILP和MINLP提供高效的线性松弛解法。

3. ZIMPL：

   • 简介：ZIMPL是一个用于定义数学规划模型的建模语言。
   • 功能：支持简洁地表达线性和非线性优化模型，生成SCIP和其他求解器可以读取的模型文件。
   • 使用：用户通过编写ZIMPL脚本，定义优化变量、约束和目标函数。

4. UG：

   • 简介：UG（Ubiquity Generator）是一个用于并行求解混合整数（线性和非线性）规划问题的框架。
   • 功能：利用多核处理器或计算集群加速求解过程，适用于大规模优化问题。
   • 使用：配置并行求解环境，通过SCIP调用UG实现并行化求解。

5. GCG：

   • 简介：GCG（Generic Branch-Cut-and-Price Solver）是一个通用的分支切割定价求解器。
   • 功能：专注于大规模分配和调度问题，通过分支定界和割平面方法有效求解。
   • 使用：与SCIP集成，为特定类型的优化问题提供专业化的求解方法。

SCIP Optimization使用步骤：

1. 建模：

   • 使用ZIMPL语言编写模型，定义变量、目标函数和约束条件。
   • 或者直接在编程语言（如C、C++、Python）中使用SCIP API构建模型。

2. 配置求解器：

   • 根据问题特点配置SCIP参数，如启发式算法、剪枝策略等。
   • 如果问题较大，考虑使用UG进行并行求解。

3. 求解问题：

   • 调用SCIP求解器进行优化，获取最优解。
   • 使用SoPlex求解线性松弛问题，以提高整体求解效率。

4. 分析结果：

   • 提取和分析SCIP求解结果，检查解的有效性和最优性。
   • 结合业务需求对优化结果进行应用和调整。

SCIP Optimization套件因其灵活性和强大的求解能力，广泛应用于调度、物流、金融、能源等领域的复杂优化问题中。通过各组件的协同工作，用户可以高效地构建、求解和分析优化模型，满足各种实际应用需求。

如何获取SCIP

SCIP可以在其官网下载，支持Windows,Linux和Mac。有源码（Source Code）下载和预编译包（Precompiled Packages）下载方式。

选择SCIP版本和平台。

如果仅为了使用，推荐通过预编译包安装，而如果为了结合其他编程语言，比如C++,Python，则推荐为源码安装。

预编译包安装

预编译包安装。

下载需要填写带星号的信息后，点击Start Download后开始下载。

安装时，推荐添加SCIP路径到环境变量PATH中。

随后打开cmd，输入scip，即可进入SCIP交互界面

源码安装

源码安装，第一个是scip套件。然后遵循这里的指令。

Windows

对于Windows下的源码安装，可以借助于Cmake GUI安装，或者命令行

cmake -Bbuild -H. 
cmake --build build --config Release [Debug]

[x]表示参数x是可选择的。

Linux,MacOS

源码编译需要一些依赖工具，对于使用apt作为包管理工具的系统，可以通过以下指令安装依赖

apt install wget cmake g++ m4 xz-utils libgmp-dev unzip zlib1g-dev libboost-program-options-dev libboost-serialization-dev libboost-regex-dev libboost-iostreams-dev libtbb-dev libreadline-dev pkg-config git liblapack-dev libgsl-dev flex bison libcliquer-dev gfortran file dpkg-dev libopenblas-dev rpm

然后，通过以下命令安装

tar xvzf scip-x.y.z.tgz                                                       # 解压下载的源码包，x,y,z替换为对应的版本
cd scip-x.y.z                                                                 # 进入解压后的文件夹
mkdir build                                                                   # 创建build文件夹
cd build                                                                      # 进入build文件夹
cmake .. -DCMAKE_INSTALL_PREFIX=<install/dir>                                 # 编译配置安装路径
make                                                                          # 开始编译
make check                                                                    # (推荐可选) 测试生成文件
make install                                                                  # (可选) 复制编译出来的SCIP到CMAKE_INSTALL_PREFIX

最后在bash输入SCIP即可启动。

SCIP的简单使用

在SCIP界面，可通过输入help查看帮助。

我们可以通过read指令读取一个问题，我们创建一个exmaple.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

在同目录下，我们输入scip启动，然后输出

read example.lp		# 读取问题
optimize			# 问题求解

最后的Gap为零说明求得了最优解，而最优的目标函数值为1.225e2，且搜到了三个可行解，输入display solution可得到最优解的变量取值。

输入display sols后输入0或1或2可以打印出对应可行解的取值。

可以看到这里的可行解的目标函数值与求解过程中表格里的primalbound的的数值是一致的。

SCIP与Python的结合

要在Python中使用SCIP，需要借助PySCIPOpt库，可以通过以下命令安装。

pip3 install pyscipopt

安装前需要设置环境变量SCIPOPTDIR为SCIP的安装路径，以便让库能正确与SCIP相结合。

SCIP的安装路径应形如以下格式

SCIPOPTDIR
  > lib
    > libscip.so (或linscip.dll) ...
  > include
    > scip
    > lpi
    > nlpi
    > ...

设置环境变量的方法为

export SCIPOPTDIR=<path_to_install_dir> (Linux, OS X)
set SCIPOPTDIR=<path_to_install_dir> (cmd, Cmder, WSL)
$Env:SCIPOPTDIR = "<path_to_install_dir>" (powershell)

将<path_to_install_dir>替换为SCIP安装路径即可。

不同大版本适应不同版本的SCIP，需根据SCIP选择对应版本的PySCIPOpt。

SCIP	PySCIPOpt
9.0	5.x
8.0	4.x
7.0	3.x
6.0	2.x
5.0	1.4, 1.3
4.0	1.2, 1.1
3.2	1.0

然后创建一个example.py，输入以下内容

from pyscipopt import Model

# 创建模型
model = Model("example")

# 定义变量及其上下界
x1 = model.addVar("x1", vtype="C", lb=0, ub=40)
x2 = model.addVar("x2", vtype="C")
x3 = model.addVar("x3", vtype="C")
x4 = model.addVar("x4", vtype="I", lb=2, ub=3)  # x4为整数变量

# 设置目标函数
model.setObjective(x1 + 2*x2 + 3*x3 + x4, "maximize")

# 添加约束
model.addCons(-x1 + x2 + x3 + 10*x4 <= 20, "c1")
model.addCons(x1 - 3*x2 + x3 <= 30, "c2")
model.addCons(x2 - 3.5*x4 == 0, "c3")

# 求解模型
model.optimize()

# 检查是否找到最优解
if model.getStatus() == "optimal":
    print("Optimal solution found:")
    print(f"x1 = {model.getVal(x1)}")
    print(f"x2 = {model.getVal(x2)}")
    print(f"x3 = {model.getVal(x3)}")
    print(f"x4 = {model.getVal(x4)}")
else:
    print("Optimal solution not found!")

然后python3 example.py运行

结果和上述SCIP的结果一致。

SCIP与神经网络的结合

Ecole（Efficient Combinatorial Optimization Learning Environment）是一个专为结合SCIP和神经网络的研究和应用而设计的库。它为在组合优化问题中利用机器学习提供了一个灵活且高效的框架。以下是ECole库的主要功能和特点：

ECole的主要特点

1. 整合优化与学习：

   • ECole允许将优化求解与机器学习模型无缝集成，支持在优化过程中引入机器学习方法，以增强求解性能。

2. 环境与任务：

   • ECole定义了一系列优化环境和任务，这些任务可以是传统的组合优化问题，也可以是经过扩展的、更具挑战性的问题。这些任务和环境可以直接与强化学习算法结合使用。

3. 多样化的观察与反馈：

   • ECole提供丰富的观察和反馈机制，使用户可以根据需求定制优化过程中的信息收集方式。这有助于在优化过程中动态调整策略。

4. 高效的实现：

   • ECole采用高效的数据结构和算法，确保在求解大规模优化问题时的性能和可扩展性。

要安装Ecole，首先设置好环境变量SCIP_DIR为SCIP的安装路径，然后输入以下指令安装。

pip3 install ecole

注意，该库暂不支持Windows系统。

该库不依赖PyScipOpt，但如果需要自定义Ecole里的模块，则仍需依赖PyScipOpt开发。

Ecole的简单使用

import ecole

# 初始化Ecole环境
env = ecole.environment.Branching()

# 创建一个优化实例生成器
instance_generator = ecole.instance.SetCoverGenerator()

for _ in range(10):
    # 生成一个问题实例
    instance = next(instance_generator)
    # 初始化环境
    observation, action_set, reward_offset, done, info = env.reset(instance)
    
    while not done:
        # 进行分支定界中的变量选择操作，observation就是当前要分支的子问题
        observation, action_set, reward, done, info = env.step(action_set[0])

Ecole类似于OpenAI里的GYM用法，将用分支定界算法求解混合整数线性规划问题抽象成一个序列决策的马尔科夫过程，期间的Observation是对当前子问题的一个描述，它可以是一个二分图表示法，进而作为一个图卷积神经网络的输入，得到动作，即选择的变量。

总结

综上所述，SCIP（Solving Constraint Integer Programs）及其相关组件（SoPlex、ZIMPL、UG、GCG）提供了一个强大且灵活的优化框架，能够有效解决复杂的混合整数规划问题。通过结合SCIP和Python（如使用PySCIPOpt库），用户可以轻松地在编程环境中构建和求解优化模型。此外，Ecole库进一步拓展了SCIP的应用范围，使其能够与机器学习特别是强化学习方法相结合，提供了在组合优化问题上进行深入研究和创新的工具。这些工具在学术研究和工业应用中都有广泛的用途，帮助解决各种实际优化问题，提升决策和资源分配的效率。