max ==5x +8x, 整数规划的分枝定界法 s.x1+x2≤6 BB: Branch and Bound 5x1+9x2≤45 基本思想:隐式地枚举一切可行解(“分而治之”) x1,x20且为整数 所谓分枝,就是逐次对解空间〔可行域)进行划分;而 去掉整数限制后,可行域为点(0,0),(6,0),(0,5), 所谓定界,是指对于每个分枝(或称子域),要计算原 P(225375)国成的4边形 问题的最优解的下界(对极小化问题).这些下界用来 在求解过程中判定是否需要对目前的分枝进一步划分 LP最优解PP的含入解最靠近P的可行解P最优解 也就是尽可能去掉一些明显的非最优点,避免完全枚举 (225,3.75)(2,4) z=4125 对于极小化问题,在子域上解LP,其最优值是IP限定 从LP最优解经过简单的“移动不一定得到P最优解 在该子域时的下界;IP任意可行点的函数值是IP的上界 线性 IP min 2=cx 分枝定界算法-例mn:=x-为 s.Ax=b,x≥0(P0) s1.2x1-x2≥ 2x1+x2≤ 线性规划松弛定界A∈Zmx,m≤n (P0 该问题的P松弛解为x=(,), x2≥ 若在某一时刻,得到一个全整数解的费用为乙m,则乙m 不是整数解最优值为。=4 为原问题的一个上界 QP1):(P0)加上x22 否则得该分枝的一个下界,继续分枝 为:少 dr= b 不是整数解最优值为=3.5 P3):(P1)加上x222 P)x2:1P2)x1 P4):(P1)加上x2≤1 x∈Z (学学奖 P0=(,3),z4 分枝定界算法QMin问题 x=(2引),z=7/2 STEP.令 actives{0(原问题:U-; currentbest=0. P1 STEPI如果 activeset=2,则已经得到原问题的最优解,结束;否 则从活跃分枝点集合 activeset中选择一个分枝点k;将k从 去掉继续STEP2 =-13/4 STEP生成k的各分枝产12…,n4及其对应的下界z 无可行解 STEP3对分枝12…,n4:如果分枝i得到的是全整数解且 x°=(21)y EU则令U=且 currentbest响如果分枝i得到的不是全整数 无可行解 解且x<U则把i加入 actveset中 STEP4.转STEP14 , 0 且为整数 5 9 45 . . 6 max 5 8 1 2 1 2 1 2 1 2 ≥ + ≤ + ≤ = + x x x x st x x z x x ． ． ． ． ． ． ．． ． ． ． ． ． ． ． ． ． ． ． x1 x2 0 oP 6 9 Zmax 5 6 去掉整数限制后，可行域为点（0,0), (6,0), (0,5), P (2.25,3.75) 围成的4边形 LP 最优解P P 的舍入解 最靠近P 的可行解 IP 最优解 （2.25，3.75） （2，4） （2，3） （0，5） z=41.25 不可行 z=34 z=40 从LP最优解经过简单的 “移动”不一定得到IP最优解 基本思想：隐式地枚举一切可行解（“分而治之”） 所谓分枝，就是逐次对解空间（可行域）进行划分；而 所谓定界，是指对于每个分枝（或称子域），要计算原 问题的最优解的下界（对极小化问题）. 这些下界用来 在求解过程中判定是否需要对目前的分枝进一步划分， 也就是尽可能去掉一些明显的非最优点，避免完全枚举. 整数规划的分枝定界法 （BB: Branch and Bound） 对于极小化问题，在子域上解LP，其最优值是IP限定 在该子域时的下界；IP任意可行点的函数值是IP的上界 线性规划松弛定界 若在某一时刻，得到一个全整数解的费用为zm，则zm 为原问题的一个上界; 否则得该分枝的一个下界，继续分枝． （P1） ⎣ ⎦ n i i T x Z x x x st Ax b c x ∈ ≥ + ≥ = 1 0 . . min 0 （P2） ⎣ ⎦ n i i T x Z x x x st Ax b c x ∈ ≤ ≥ = 0 0 . . min A Z m n s t Ax b x P z c x m n T ∈ ≤ = ≥ = × , . . , 0 ( 0) 线性IP min 分枝定界算法 – 例 （P0） + ∈ ≥ + ≤ − ≥ = − − x x Z x x x st x x z x x 1 2 2 1 2 2 11 1 2 2 1 1 2 1 2 , 2 . . 2 min 该问题的LP松弛解为 , 不是整数解,最优值为z0=-4. (P1): (P0)加上 ; (P2): (P0)加上 . T x ( , )2 5 2 0 3 = 2 x1 ≥ 1 x1 ≤ 问题(P1)的LP松弛解为 , 不是整数解,最优值为z1=-3.5 (P3): (P1)加上 ; (P4): (P1)加上 . T x (2, )2 1 3 = x2 ≥ 2 1 x2 ≤ P0 P1 P2 x1 ≥ 2 1 x1 ≤ P3 P4 2 x2 ≥ x2 ≤ 1 P5 P6 3 x1 ≥ x1≤2 T , x x (2,1) * 6 = = 6 3 * z =z =− 无可行解 P0 P1 P2 P3 P4 2 x1≥ x1 ≤1 2 x2 ≥ x2 ≤1 T x ( , )2 5 2 0 3 = , z0=-4 T x (2, )2 1 3 = , z1=-7/2 T x ( ,1) 4 4 9 = z0=-13/4 T x (2,1) 6 = z0=-3 无可行解 T x (1, ) 2 2 3 = z2=-2.5 > z6 分枝定界算法(Min问题) STEP4. 转STEP1. STEP0. 令activeset={0}(原问题);U = ∞；currentbest=0. STEP1. 如果 activeset=∅, 则已经得到原问题的最优解, 结束; 否 则从活跃分枝点集合 activeset 中选择一个分枝点 k ；将 k 从 activeset中去掉, 继续STEP2. STEP2. 生成 k 的各分枝 i=1,2,…,nk 及其对应的下界zi . STEP3.对分枝 i=1,2,…,nk : 如果分枝 i 得到的是全整数解且 zi <U, 则令 U=zi 且 currentbest=i；如果分枝 i 得到的不是全整数 解且zi <U, 则把 i 加入activeset中