MILP加速运算技巧——模型对称性的预处理

2023-12-18 03:12

本文主要是介绍MILP加速运算技巧——模型对称性的预处理,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 整数规划的对称性
    • 什么是对称性
    • 对称性的影响
  • 对称性的预处理方法


整数规划的对称性

什么是对称性

许多整数规划问题存在对称性,这种对称性是指问题解空间的对称,即在对称的解空间当中解的优化目标值上是相同的。这种对称性并不会改变问题的最优值,如果我们能够限制这种对称性,就能在不改变问题最优值的情况下,缩减问题可行空间的规模,因此很多MIP求解器会对模型的对称性做出检测并进行处理。

以生产排程问题为例,加入存在一批加工工件,每个工件基于它的产品类型有一个加工工艺,若工件1和工件2的加工工艺相同,此时,对于最终的生产方案而言,加工工件1和加工工件2的每个步骤的顺序进行调换,并不会影响问题的目标值,此时工件1和工件2相关的所有决策变量具有对称性。

又例如: 2 x 1 + 2 x 2 + x 3 ≤ 10 , x 1 ≤ 5 , x 2 ≤ 5 2x1+2x2+x3\leq 10, x1\leq 5, x2\leq 5 2x1+2x2+x310,x15,x25,目标函数是 3 x 1 + 3 x 2 + x 3 3x1+3x2+x3 3x1+3x2+x3,此时不论最终的结果如何, x 1 , x 2 x1,x2 x1,x2之间的解进行调换,都不会影响目标值,原因是 x 1 , x 2 x1,x2 x1,x2 不论是约束系数,还是边界,以及目标函数系数都相同,他们的最优解互相对调,也是一个最优解,两个变量具有对称性。

例如以Gurobi预处理为例:

# 添加约束
model.addConstr(2*x1+ 2*x2 + y <= 10)
model.addConstr(x1 <= 5)
model.addConstr(x2 <= 5)
model.addConstr(y >= 5)
# 定义目标函数
model.setObjective(3*x1 +3*x2 + y, sense=grb.GRB.MINIMIZE)

在求解日志当中,上述问题的所有约束和变量都被预处理过程确定下来,当 y y y 确定后, x 1 + x 2 x1+x2 x1+x2 的值能确定,且由于 x 1 , x 2 x1,x2 x1,x2 两个变量对称,所以问题的最优解不唯一。

...
Presolve removed 4 rows and 3 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
...

许多的整数规划问题当中都存在这样的特点,例如在车辆路径问题当中,有两个点到其他所有点的距离都一样,此时这两个点不论先通过哪个点都是一样的,但在求解问题当中,其中一个点在前的方案、以及另一个点在前的方案都包含在问题的可行域内,尽管两者是等价的。

对称性的影响

很显然,过于强烈的对称性有时候就会产生无效的搜索动作。特别是对于经典的精确搜索框架——分支定界,对称的变量会导致大量重复的待搜索节点(子问题),不论是界的收敛还是待剪支数量,对称性都会在这个过程中造成大量的无效动作。而这种具有对称性的等价变量越多,则问题当中等价的可行解就越多,相同节点也就越多,算法的搜索就会变慢。

对于一些问题而言,因为对称性导致原本不复杂的问题,往往难以直接通过求解器在可接受的时间内得到满意的解,因此对于这个混合整数变量的问题,需要采取一定的办法进行处理。

对称性的预处理方法

前面提到,这种等价变量的一个特点就是约束系数以及目标函数系数都一致,因此需要打破这种对称性,而这只需要改变系数的一致性即可,对于一些问题而言,这个动作能直接将求解问题的时间缩短几十上千倍。

一些求解器会建立具有任意目标函数系数的模型,而更一般性的方法是增加对称性割,即添加破坏这种对称性的约束条件:既然这些变量是等价变量,那就增加约束来使得这些变量的值不等价,有一个倾向性,减少算法搜索另一些等价的对称解空间,以此来提升算法效率,这对于大规模的且有大量等价变量的问题尤为重要。

对称性割的基本形式为:

d ⊤ x ≤ d ⊤ π ( x ) d^{\top}x \leq d^{\top}\pi (x) dxdπ(x)

其中, π \pi π是置换算子, d = ( 2 n − 1 , 2 x − 2 , . . . 2 0 ) d=(2^{n-1}, 2^{x-2},...2^0) d=(2n1,2x2,...20) n n n 是具有对称性的等价变量数量。例如当 n = 2 n=2 n=2,只有 x 1 , x 2 x1,x2 x1,x2 两个等价变量时,对称性割就为 x 1 + 2 x 2 ≤ x 2 + 2 x 1 x1+2x2\leq x2+2x1 x1+2x2x2+2x1,移项得 x 2 ≤ x 1 x2\leq x1 x2x1。这种约束就使得原本等价的两个解,只能有一个是满足该约束的,缩减了问题的解空间,加速了B&B算法的收敛。但值得注意的是,有大量等价变量不仅意味着对称性割的加速效果显著,也意味着添加的对称性割的数量庞大,减少了相同的节点,但增加了节点处问题的求解难度,在实际中仍需要进行一定的权衡。

这篇关于MILP加速运算技巧——模型对称性的预处理的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/506849

相关文章

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

基于Flask框架添加多个AI模型的API并进行交互

《基于Flask框架添加多个AI模型的API并进行交互》:本文主要介绍如何基于Flask框架开发AI模型API管理系统,允许用户添加、删除不同AI模型的API密钥,感兴趣的可以了解下... 目录1. 概述2. 后端代码说明2.1 依赖库导入2.2 应用初始化2.3 API 存储字典2.4 路由函数2.5 应

电脑win32spl.dll文件丢失咋办? win32spl.dll丢失无法连接打印机修复技巧

《电脑win32spl.dll文件丢失咋办?win32spl.dll丢失无法连接打印机修复技巧》电脑突然提示win32spl.dll文件丢失,打印机死活连不上,今天就来给大家详细讲解一下这个问题的解... 不知道大家在使用电脑的时候是否遇到过关于win32spl.dll文件丢失的问题,win32spl.dl

电脑报错cxcore100.dll丢失怎么办? 多种免费修复缺失的cxcore100.dll文件的技巧

《电脑报错cxcore100.dll丢失怎么办?多种免费修复缺失的cxcore100.dll文件的技巧》你是否也遇到过“由于找不到cxcore100.dll,无法继续执行代码,重新安装程序可能会解... 当电脑报错“cxcore100.dll未找到”时,这通常意味着系统无法找到或加载这编程个必要的动态链接库

如何关闭 Mac 触发角功能或设置修饰键? mac电脑防止误触设置技巧

《如何关闭Mac触发角功能或设置修饰键?mac电脑防止误触设置技巧》从Windows换到iOS大半年来,触发角是我觉得值得吹爆的MacBook效率神器,成为一大说服理由,下面我们就来看看mac电... MAC 的「触发角」功能虽然提高了效率,但过于灵敏也让不少用户感到头疼。特别是在关键时刻,一不小心就可能触

前端bug调试的方法技巧及常见错误

《前端bug调试的方法技巧及常见错误》:本文主要介绍编程中常见的报错和Bug,以及调试的重要性,调试的基本流程是通过缩小范围来定位问题,并给出了推测法、删除代码法、console调试和debugg... 目录调试基本流程调试方法排查bug的两大技巧如何看控制台报错前端常见错误取值调用报错资源引入错误解析错误

C#集成DeepSeek模型实现AI私有化的流程步骤(本地部署与API调用教程)

《C#集成DeepSeek模型实现AI私有化的流程步骤(本地部署与API调用教程)》本文主要介绍了C#集成DeepSeek模型实现AI私有化的方法,包括搭建基础环境,如安装Ollama和下载DeepS... 目录前言搭建基础环境1、安装 Ollama2、下载 DeepSeek R1 模型客户端 ChatBo

mysql线上查询之前要性能调优的技巧及示例

《mysql线上查询之前要性能调优的技巧及示例》文章介绍了查询优化的几种方法,包括使用索引、避免不必要的列和行、有效的JOIN策略、子查询和派生表的优化、查询提示和优化器提示等,这些方法可以帮助提高数... 目录避免不必要的列和行使用有效的JOIN策略使用子查询和派生表时要小心使用查询提示和优化器提示其他常

Apache伪静态(Rewrite).htaccess文件详解与配置技巧

《Apache伪静态(Rewrite).htaccess文件详解与配置技巧》Apache伪静态(Rewrite).htaccess是一个纯文本文件,它里面存放着Apache服务器配置相关的指令,主要的... 一、.htAccess的基本作用.htaccess是一个纯文本文件,它里面存放着Apache服务器