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/506848

相关文章

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

大模型研发全揭秘:客服工单数据标注的完整攻略

在人工智能(AI)领域,数据标注是模型训练过程中至关重要的一步。无论你是新手还是有经验的从业者,掌握数据标注的技术细节和常见问题的解决方案都能为你的AI项目增添不少价值。在电信运营商的客服系统中,工单数据是客户问题和解决方案的重要记录。通过对这些工单数据进行有效标注,不仅能够帮助提升客服自动化系统的智能化水平,还能优化客户服务流程,提高客户满意度。本文将详细介绍如何在电信运营商客服工单的背景下进行

Andrej Karpathy最新采访:认知核心模型10亿参数就够了,AI会打破教育不公的僵局

夕小瑶科技说 原创  作者 | 海野 AI圈子的红人,AI大神Andrej Karpathy,曾是OpenAI联合创始人之一,特斯拉AI总监。上一次的动态是官宣创办一家名为 Eureka Labs 的人工智能+教育公司 ,宣布将长期致力于AI原生教育。 近日,Andrej Karpathy接受了No Priors(投资博客)的采访,与硅谷知名投资人 Sara Guo 和 Elad G

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

Retrieval-based-Voice-Conversion-WebUI模型构建指南

一、模型介绍 Retrieval-based-Voice-Conversion-WebUI(简称 RVC)模型是一个基于 VITS(Variational Inference with adversarial learning for end-to-end Text-to-Speech)的简单易用的语音转换框架。 具有以下特点 简单易用:RVC 模型通过简单易用的网页界面,使得用户无需深入了

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

uva 575 Skew Binary(位运算)

求第一个以(2^(k+1)-1)为进制的数。 数据不大,可以直接搞。 代码: #include <stdio.h>#include <string.h>const int maxn = 100 + 5;int main(){char num[maxn];while (scanf("%s", num) == 1){if (num[0] == '0')break;int len =

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

图神经网络模型介绍(1)

我们将图神经网络分为基于谱域的模型和基于空域的模型,并按照发展顺序详解每个类别中的重要模型。 1.1基于谱域的图神经网络         谱域上的图卷积在图学习迈向深度学习的发展历程中起到了关键的作用。本节主要介绍三个具有代表性的谱域图神经网络:谱图卷积网络、切比雪夫网络和图卷积网络。 (1)谱图卷积网络 卷积定理:函数卷积的傅里叶变换是函数傅里叶变换的乘积,即F{f*g}

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费