引言

MIP问题的重要性

  • 在实际问题中的广泛应用
  • 解决大规模MIP问题的挑战

研究目标

  • 提出一种分布式方法以高效解决大规模MIP问题

预备知识

MIP的定义

  • MIP的基本形式如下：

    min⁡x,y∑i=1Nfi(xi,yi)\min_{x, y} \sum_{i=1}^N f_i(x_i, y_i)

    subject to:∑i=1Ngi(xi,yi)≤0,(xi,yi)∈Xi×Yi,i=1,…,N\text{subject to:} \quad \sum_{i=1}^N g_i(x_i, y_i) \leq 0, \quad (x_i, y_i) \in X_i \times Y_i, \quad i = 1, \ldots, N

    其中，Xi⊆RpiX_i \subseteq \mathbb{R}^{p_i}是一个紧的凸集合，Yi⊆ZqiY_i \subseteq \mathbb{Z}^{q_i}是一个有限的整数集合。

现有解决方法

  • 分支定界法
  • 分解方法：通过将原问题分解为更小的子问题来提高求解效率。

问题的提出

目标函数

  • 目标函数形式：

    min⁡{(xi,yi)}i=1N∑i=1Nfi(xi,yi)\min_{\{(x_i, y_i)\}_{i=1}^N} \sum_{i=1}^N f_i(x_i, y_i)

约束条件

  • 约束条件形式：

    ∑i=1Ngi(xi,yi)≤0,(xi,yi)∈Xi×Yi,i=1,…,N\sum_{i=1}^N g_i(x_i, y_i) \leq 0, \quad (x_i, y_i) \in X_i \times Y_i, \quad i = 1, \ldots, N

MIP问题的分解

右端分配方法

  • 将原问题分解为主问题和子问题。

主问题形式

  • 主问题形式：

    min⁡{zi}i=1N∑i=1Npi(zi)\min_{\{z_i\}_{i=1}^N} \sum_{i=1}^N p_i(z_i)

    subject to:∑i=1Nzi=0\text{subject to:} \quad \sum_{i=1}^N z_i = 0

子问题形式

  • 子问题形式：

    pi(zi)=min⁡(xi,yi,vi)fi(xi,yi)+Mvip_i(z_i) = \min_{(x_i, y_i, v_i)} f_i(x_i, y_i) + Mv_i

    subject to:gi(xi,yi)−vi≤zi,(xi,yi)∈Xi×Yi,vi≥0\text{subject to:} \quad g_i(x_i, y_i) - v_i \leq z_i, \quad (x_i, y_i) \in X_i \times Y_i, \quad v_i \geq 0

函数$ p_i(z_i) $的半连续性

定义

  • 上半连续和下半连续

命题

  • 函数$ p_i(z_i) $在每个点是连续的

函数$ p_i(z_i)$的可微性

命题

  • 存在右导数

定理

  • 右导数的计算方法

函数$ p_i(z_i) $的计算

分离假设

  • 函数$ f_i(x_i, y_i) 和和 g_i(x_i, y_i) $是可分离的

定理

  • 在分离假设下对$ p_i(z_i) $的描述

算法及收敛性分析

算法1

  • 基于过估计的迭代求解方法

收敛性定理

  • 序列的每个极限点都是局部最优解

分布式算法（算法2）

  • 使用多代理系统的协同处理

收敛性定理

  • 收敛到分解问题的最优点

模拟实验

数值实验

  • 0-1 MIP问题示例

与Gurobi的比较

  • 最优值和运行时间的比较

结果

  • 所提出的算法在大规模N时优于Gurobi

结论

总结

  • 提出了解决大规模MIP问题的分布式算法

主要贡献

  • 比Gurobi具有更高的精度和效率

实际意义

  • 在电力系统、供应链管理和能源优化中的有效应用