运筹优化学习08:Repairing MIP infeasibility through local branching

本文涉及的产品
传统型负载均衡 CLB,每月750个小时 15LCU
EMR Serverless StarRocks,5000CU*H 48000GB*H
应用型负载均衡 ALB,每月750个小时 15LCU
简介: 运筹优化学习08:Repairing MIP infeasibility through local branching

寻找一般整数规划问题的可行解是一个比较困难的事情, feasibility pump和local branching方法的提出,为寻找MIP的可行解提供了新的思路,feasibility pump方法可以较低的成本提供局部分支过程的(不一定可行)初始解。在单纯形法中,通过引入人工变量求解增广模型,之后在迭代循环使人工变量的值趋于0,以获取问题的可行解。我们的方法也可以启发式的寻找最小基数约束集,将不可行的MIP转化为可行的MIP。


在实际的应用场景下,找到好的可行方案是商业发展的主要关注,局部搜索通常从一个初始的可行解出发,对其进行迭代改进,从而使算法终止于一个稳定的值。然而,有时找到一个初始解往往是比较困难且不必要的,因为可以通过修复策略使初始解变的可行并最终得到改进。基于上述分析,本文介绍求解MIP的 feasibility pump和local branching方法,这两种方法最初的设计理念就是为了寻找初始和改进初始可行解。


1 引言

1.1 基础模型

为了寻找到要研究问题的可行解决方案,我们首先定义包含0-1变量的MIP模型:

20190922103713175.png

模型变量说明:

image.png


注意:

  • 我们在这里假设存在0-1变量集,因为局部分支启发式算法需要基于这一假设。此外,也可以消除这一约束拓展我们的方法。
  • 对于约束集(3)虽然呈现出不等式形式,但也包含了等式约束;可令201909221039100.png表示所有的整数变量集合


1.2 方法回顾:

Fischetti提出所谓的局部分支启发时方法,来提升给定可行解的质量;【Fischetti M, LodiA. Local branching. Mathematical Programming 2003;98:23–47】

Danna提出RINS启发式方法,需要一个初始可行解,但这对于一些MIP是比较困难的。【 Danna E, Rothberg E, Le Pape C. Exploring relaxation induced neighborhoods to improve MIP solutions. Mathematical Programming. 2005;102:71–90.】

Fischetti提出使用feasibility pump方法通过一系列巧妙的操作来发现MIP的可行或近似可行的解决方案。【Fischetti M, Glover F, LodiA. The feasibility pump. Mathematical Programming 2005;104:91–104.】


1.3 我们的工作

计算和分析了原始LB方法的简单变体,允许接受不可行的参考解,如使用FP返回的解;我们从FP以极小的计算成本提供的几乎可行的参考解出发,对每一个违反约束的MIP模型的约束通过以下三种形式进行放松:引入基于约束本身的人工连续变量、引入二进制人工变量;设置在必须使用人工变量才能满足的情况下将二进制变量设置为1的约束。最后目标函数被替换为类似于单纯形法第一阶段的二进制变量求和的形式。对于放松之后的模型,具有满足约束的可行初始解,其约束数目与违背初始约束的数目是一致的。我们使用标准的LB框架,减少目标函数的值,即不可行解的数目;对于初始问题,不可行解的数目为0时,便得到了它的可行解。尽管对于每一个违反的约束,连续性变量就足够了,但是LB使用二进制变量,则显示了更好的效果。


此外,我们的方法还产生了一个小的基数约束集,将其松弛可将不可行的MIP转化为可行的MIP,这对与分析不可行的MIP非常重要;换言之,可将其视为修复不可行MIP模型的工具,而不仅是修复不可行MIP解决方案的一种启发式方法,其思想与通常研究的寻找LP最大或最小子问题的可行解的理念是一致的。


2 局部分支和可行性泵方法

2.1 局部分支(Local Branching, LB)

基本原理如下:


对于问题给定一个可行的参考解,我们的目标是寻找距离并不太远的改进解。

20190922111309780.png 表示的二进制支持集,对于给定的正整数,定义gif.gif 的邻域gif.png  为问题满足邻域分支约束的可行解:


20190922111652346.png


左侧的两项分别为从1-0或0-1的二进制变量的翻转值;顾名思义,局部分支约束7可以用作问题P方案枚举的分支条件。实质上,若给定,与当前分支节点相关联的解空间做如下分解:


image.png


这里的邻域大小k应足够的小以保证在较短的时间内获得优化解,还应足够的大以保证能顾囊括比更好的解。


Fischetti(2003)的通过控制一个简单的外部分支框架,使用通用的MIP求解器作为一个黑箱工具来在子空间内搜索更合适的解,这个过程包含着著名的局部搜索元启发式算法理念,但是得到了包含邻域约束的MIP的局部分支约束(7),这可以保证算法在一个更完美的框架下被开展实施。在MIP求解器中,通常采用的是精确求解算法策略,尽管LB算法是为了改进MIP求解器而做出的启发式行为。他利用战略级分支定义解的邻域,并在战术级层面上利用MIP求解器进行更优解探索。这一过程可视为一个两级分支策略,既能在早期对现有解进行更新,也能在计算的早期产生改进的解决方案。Fischetti(2003,2006)的研究结论表明,LB方法具有良好的性能,Hansen(2006)也采用变邻域搜索元启发式方法证明了这一点。


Hansen P, Mladenovíc N, Urosevíc D. Variable neighborhood search and local branching. Computers and Operations Research 2006;33:3034–45.


Fischetti M, Polo C, Scantamburlo M. A local branching heuristic for mixed-integer programs with 2-level variables. Networks 2004;44:61–72.


2.2 可行泵


image.png

20190928141951667.png

20190928142007366.png

3 从不可行解开始的局部分支方法


局部分支技术并不严格要求从一个可行解开始,也即一个部分可行的解也可以。通过以合适的方式对模型进行放松,我们有可能将一个不可行解通过局部分支启发式骑术使其逐步变更为可行解。


一种常用的实现方式为,为不可行解中的违反约束添加一个连续的人工变量,使用M对其进行惩罚,这种方法已经被测试是有效的,但是在实际应用中确定M是比较困难的。对于MIPLIB中的许多算例,他们的目标函数值是非常大的,使用M并不能体现出不可行解比可行解差的情形。LB采用了如下组合优化框架:


20190928141829409.png20190928141903181.png

相关实践学习
SLB负载均衡实践
本场景通过使用阿里云负载均衡 SLB 以及对负载均衡 SLB 后端服务器 ECS 的权重进行修改,快速解决服务器响应速度慢的问题
负载均衡入门与产品使用指南
负载均衡(Server Load Balancer)是对多台云服务器进行流量分发的负载均衡服务,可以通过流量分发扩展应用系统对外的服务能力,通过消除单点故障提升应用系统的可用性。 本课程主要介绍负载均衡的相关技术以及阿里云负载均衡产品的使用方法。
相关文章
|
3月前
|
机器学习/深度学习 人工智能 边缘计算
Paper Reading | 一种高效的光流估计方法——NeuFlow v2
本文介绍了一种高效的光流估计方法——NeuFlow v2。
Paper Reading | 一种高效的光流估计方法——NeuFlow v2
|
5天前
|
机器学习/深度学习 数据采集 算法
基于Liquid State Machine的时间序列预测:利用储备池计算实现高效建模
**Liquid State Machine (LSM)** 是一种 **脉冲神经网络 (Spiking Neural Network, SNN)** ,在计算神经科学和机器学习领域中得到广泛应用,特别适用于处理 **时变或动态数据**。它是受大脑自然信息处理过程启发而提出的一种 **脉冲神经网络** 。
27 4
基于Liquid State Machine的时间序列预测:利用储备池计算实现高效建模
|
4月前
|
机器学习/深度学习 数据采集 监控
算法金 | DL 骚操作扫盲,神经网络设计与选择、参数初始化与优化、学习率调整与正则化、Loss Function、Bad Gradient
**神经网络与AI学习概览** - 探讨神经网络设计,包括MLP、RNN、CNN,激活函数如ReLU,以及隐藏层设计,强调网络结构与任务匹配。 - 参数初始化与优化涉及Xavier/He初始化,权重和偏置初始化,优化算法如SGD、Adam,针对不同场景选择。 - 学习率调整与正则化,如动态学习率、L1/L2正则化、早停法和Dropout,以改善训练和泛化。
44 0
算法金 | DL 骚操作扫盲,神经网络设计与选择、参数初始化与优化、学习率调整与正则化、Loss Function、Bad Gradient
|
6月前
|
数据可视化 Python
【视频】风险价值VaR原理与Python蒙特卡罗Monte Carlo模拟计算投资组合实例
【视频】风险价值VaR原理与Python蒙特卡罗Monte Carlo模拟计算投资组合实例
|
6月前
|
存储 调度
R语言解决最优化运营研究问题-线性优化(LP)问题
R语言解决最优化运营研究问题-线性优化(LP)问题
|
6月前
|
算法 决策智能 Python
Python基于粒子群优化的投资组合优化研究
Python基于粒子群优化的投资组合优化研究
|
6月前
|
资源调度 算法 Ubuntu
基于协方差矩阵自适应演化策略(CMA-ES)的高效特征选择
特征选择是指从原始特征集中选择一部分特征,以提高模型性能、减少计算开销或改善模型的解释性。特征选择的目标是找到对目标变量预测最具信息量的特征,同时减少不必要的特征。这有助于防止过拟合、提高模型的泛化能力,并且可以减少训练和推理的计算成本。
110 3
|
机器学习/深度学习 人工智能 算法
强化学习从基础到进阶--案例与实践[8]:近端策略优化(proximal policy optimization,PPO)算法
强化学习从基础到进阶--案例与实践[8]:近端策略优化(proximal policy optimization,PPO)算法
强化学习从基础到进阶--案例与实践[8]:近端策略优化(proximal policy optimization,PPO)算法
|
运维 新能源 C语言
不平衡电网条件下基于变频器DG操作的多目标优化研究(Matlab代码&Simulink实现)
不平衡电网条件下基于变频器DG操作的多目标优化研究(Matlab代码&Simulink实现)
|
机器学习/深度学习 文件存储 计算机视觉
【最强模型之道】AWS Auto-Aug:通过Weight共享改进自动数据增广,打造最高精度单模型
【最强模型之道】AWS Auto-Aug:通过Weight共享改进自动数据增广,打造最高精度单模型
245 0