整数编程》第 2 章--松弛和成对问题

最编程 2024-04-16 10:14:06

...

上一章我们学习了整数规划的formulations以及常见的几个整数规划问题，对于整数规划问题，由于精确解的难以求出，我们通常会关心它的精确解的上下界（bounds），并从中得到最优解的信息。

以下讨论都在最大化max目标函数的框架下进行。

一、整数规划问题的界（Bounds）

最优解的下界：一般由Primal Bound来作为下界，每一个该问题的可行解都是Primal Bound;
最优解的上界：通常由该问题的松弛问题或对偶问题得到，其中，对偶问题的最优解也被称为Dual Bound。

通常我们的思路是利用primal bound和dual bound来控制并逼近最优解。

二、整数规划的松弛问题（Relaxation）

顾名思义，松弛问题就是相较于原问题，约束的更松（可行域更大）的问题。原问题的松弛问题求出的最优解一定是原问题的上界。

松弛问题的数学定义如下
Definition (Relaxation)：A problem (RP) $ZRP = max\{f (x):x\in T\subset ℝ_n\}$ is a relaxation of (IP) $Z = max\{c(x):x\in X\subset ℝ_n\}$ if
(i) $X \subset T$ , and
(ii) $f (x) \geq c(x) for\ all\ x\in X$ .

从松弛问题的定义可以得到以下结论：

若(RP)松弛问题的最优解 $x^* \in X$ ，则 $x^*$ 也是(IP)原问题的最优解；
若(RP)松弛问题无可行解，则(IP)原问题也无可行解。

常见的松弛问题构造方式有以下几种：

线性松弛（Linear Programming Relaxation）:将限定为整数取值的变量可行域扩展为实数域。

$\begin{aligned} &max\quad cx \qquad \qquad \qquad \qquad \qquad \qquad &max\quad cx \\ &Ax \leq b &Ax \leq b \\ &x\ integer &x\in R_+ \end{aligned}$
拉格朗日松弛（Lagrangian Relaxation）:将约束乘以一个系数（即一个常数u）并加在目标函数后面，起到惩罚项(penalty)的作用。如下，直观上理解拉格朗日松弛的目标既要考虑cx尽可能大，也要考虑Ax尽可能小于等于b。

$\begin{aligned} &max\quad cx \qquad \qquad \qquad \qquad \qquad \qquad &max\quad cx+u(b-Ax) \\ &Ax \leq b &x\ integer \\ &x\ integer & \end{aligned}$
除了以上两种松弛方法以外，还有一些依靠经验的松弛方法，其中一些是基于组合优化的方法（3.1&3.2），另一些则是与割平面法密切相关的松弛方法（3.3）。

3.1. TSP（Traveling Salesman Problem）:
$Z^{TSP} = min_{T\subset A}\{\sum_{(i,j)\in T}c_{ij}:\ T\ forms\ a\ tour \} \geq \\ Z^{ASS} = min_{T\subset A}\{\sum_{(i,j)\in T}c_{ij}:\ T\ forms\ an\ assignment \}$ 其中tour指我们希望的一趟旅行（每个城市到达且只到达一次，最后回到起点，可以理解为囊括所有城市的一个大回路，不存在子回路），assignment指考虑每个城市的一种排列，这样的排列可能是多个囊括不同城市的子回路组成的，可参见chapter 1的figure 1.2。因此，ASS是TSP的一个松弛。

3.2. The Quadratic 0–1 Problem：
$max\{\sum_{i,j:1\leq i<j\leq n}q_{ij}x_iy_j - \sum_{j=1}^np_jx_j,\ x\neq 0,\ x\in \{0,1\}^n \} \leq \\ max\{\sum_{i,j:1\leq i<j\leq n}max\{q_{ij},0 \}x_iy_j - \sum_{j=1}^np_jx_j,\ x\neq 0,\ x\in \{0,1\}^n \}$

3.3. The Integer Knapsack Problem
$max\{cx : \sum_{j=1}^na_jx_j \leq b,\ x\in Z^n \} \leq \\ max\{cx : \sum_{j=1}^n \lfloor a_j \rfloor x_j \leq \lfloor b \rfloor,\ x\in Z^n \}$ 其中符号 $\lfloor x \rfloor$ 意味向下取整。

三、整数规划问题的对偶问题（Dual Problem）

广义来讲，对偶问题指与原问题成对出现的问题。在运筹优化中，我们一般有：若原问题为max，则称某一类min为原问题的对偶问题，若其与原问题成对出现且最优值大于等于原问题最优值。定义如下：

Definition (Dual Problem): The two problems
$\begin{aligned} &(IP) \qquad \qquad &Z\ =\ max\{c(x):x\in X \}\\ &(D) &W\ =\ min\{w(u):u\in U \} \end{aligned}$
form a weak-dual(弱对偶) pair if $c(x)\leq w(u)$ for all $x\in X$ and $u\in U$ , strong dual(强对偶) pair if $c(x)=w(u)$ .

从定义中看出，弱对偶问题可以为原问题提供一个上界，而强对偶问题可以直接提供其最优值与最优解。

线性规划问题的对偶问题

原问题： $max \quad \{cx\ :\ Ax\leq b\}$

对偶问题： $min \quad \{ub\ :\ uA\geq c\}$
匹配问题的对偶问题（Matching Dual）

figure-2.1.png

考虑一个图 $G=(V,E)$ ，V是顶点的集合(vertices)，E是边的集合(edges)，G的一个匹配(matching)定义为一组不相交的边的集合 $M\subset E$ ，G的一个点覆盖(covering by nodes)定义为包含所有边的至少一个端点的集合 $R\subset V$ 。例如在上图中,（1,2）,（3,4）,（5,6）,（7,8）组成一个Matching，（2,3,6,8）组成一个cover by nodes。

最大匹配问题的对偶问题version1

原问题： $max_{M\subset E}\ \{\lvert M\rvert:M\ is\ a\ matching\}$
对偶问题： $min_{R\subset V}\ \{\lvert R\rvert:R\ is\ a\ covering\ by\ nodes\}$

为了将最大匹配问题以及其对偶问题写的更加直观，我们定义图G的node-edge incident matrix为一个 $n=\lvert V \rvert * m=\lvert E\rvert$ 维的矩阵，若点j是边e的端点，则 $a_{j,e}=1$ ，否则 $a_{j,e}=0$ 。

最大匹配问题的对偶问题version2

原问题： $max\ \{\textbf{1}x\ :\ Ax\leq 1,x\in Z_+^m\}$
对偶问题： $min\ \{\textbf{1}y\ :\ yA\geq 1,y\in Z_+^n\}$

上述两个例子都是弱对偶，而对于我们来讲，更理想的状况自然是强对偶，下面介绍一种利用超可加性（superadditive）构造强对偶问题的方法。

Definition (superadditive)：A function F： $\mathcal{R}^m\rightarrow \mathcal{R}$ is superadditive if $F(0)=0$ and $F(u)+F(v)\leq F(u+v)$ for $u,v\in \mathcal{R}^m$ . It is nondecreasing if $F(u)\leq F(v)$ for $u,v\in \mathcal{R}^m$ with $u\leq v$

Theorem (nondecreasing superadditive and strong dual)：Provided it is feasible, and its linear programming relaxation has finite optimal value，then: $max\{cx\ :\ Ax\leq b, x\in \mathcal{Z}^n_+\} = min\{F(b)\ :\ F(a_j)\geq c_j\ for\ j\in [1, n], F\in \mathcal{F}\}$ where $\mathcal{F}$ is the set of nondecreasing superadditive functions.

上一篇：整数分割（动态编程）

下一篇： 0-1整数规划

整数编程》第 2 章--松弛和成对问题

运筹学] 整数编程（整数编程问题解决方案的特点 | 整数编程问题和松弛问题示例）

运筹学] 整数编程（整数编程问题解决方案的特点 | 整数编程问题和松弛问题示例）

整数编程》第 2 章--松弛和成对问题