【优化2】整数优化

• 概述
• IP类型
• 建立IP
• 逻辑型
  • 或的逻辑约束
  • 三个选择的或
  • 只有才
  • 更多或
  • 整数可除
  • 多边形组合
  • 固定花费
  • 分段线性
• 组合型
  • set covering
  • set packing
  • 食堂定位
  • 地图填色
• Julia例子
  • 9数独

概述

整数优化就是线性优化，加上了一些决策变量的限制，即部分决策变量必须得是整数。

相比LP，IP优势在于：

• 可以对任何LP不可以建模的变量及约束进行建模
• 更实用
• 更灵活

劣势在于：

• 建模更困难
• 求解更困难

IP类型

IP按照程度依次加深，可以分为三类：

• MIPS：混合整数规划。对于部分或者全部的决策变量，都要求非负整数。
• PIPS：纯整数规划。对于全部的决策变量，都要求非负整数。
• BIPS：01整数规划。对于全部的决策变量，都要求在0或1中取值。

建立IP

很多时候，我们遇到的问题并不是直接以线性约束+整数限制的条件给出的，这种情况下，需要我们自己去建立IP。

逻辑型

下面的例子用xi代表第i个是否选中，1为选中0为不选中。

1. 如果选择x1，那么必须选择x3。
2. 如果选择x1，那么不能选择x5。
3. x1被选中当且仅当x2被选中。
4. x2或x3被选中，可以都被选中。
5. x2或x3被选中，不可以都被选中。

对应的IP约束为：

1. x1-x3<=0
2. x1+x5<=1
3. x1-x2=0
4. x2+x3>=1
5. x2+x3=1

或的逻辑约束

或的逻辑问题，可以用用bigM方法去解决，其思想是通过添加新的变量，将部分约束变成多余的。

例如，对于问题

或

（两者可以都出现），y1、y2的定义域是[0，5]。可行域非线性，不可以用LP解决，IP解决方法如下：

类似地，对于

或

，其IP解决 方法是：

三个选择的或

这里写图片描述

只有才

这里写图片描述

更多或

这里写图片描述

这里写图片描述

这里写图片描述

整数可除

这里写图片描述

多边形组合

这里写图片描述

固定花费

这里写图片描述

分段线性

这里写图片描述

组合型

set covering

这里写图片描述

set packing

这里写图片描述

这里写图片描述

食堂定位

这里写图片描述

这里写图片描述

地图填色

这里写图片描述

Julia例子

9数独

• Rule 1. Each cell contains an integer in [1,9].
• Rule 2. Each row must contain each of the integers in [1,9].
• Rule 3. Each column must contain each of the integers in [1,9].
• Rule 4. Each of the nine 3x3 squares with bold outlines must contain each of the integers in [1,9].

# model
m = Model()

# data
# The given digits
init_sol = [ 5 3 0 0 7 0 0 0 0;
6 0 0 1 9 5 0 0 0;
0 9 8 0 0 0 0 6 0;
8 0 0 0 6 0 0 0 3;
4 0 0 8 0 3 0 0 1;
7 0 0 0 2 0 0 0 6;
0 6 0 0 0 0 2 8 0;
0 0 0 4 1 9 0 0 5;
0 0 0 0 8 0 0 7 9]

# variable
@variable(m, x[1:9,1:9,1:9], Bin)

#costraint
for ind = 1:9 # Each row, OR each column
    for k = 1:9 # Each digit
        @constraint(m,sum{x[ind,j,k],j=1:9}==1)
        @constraint(m,sum{x[i,ind,k],i=1:9}==1)
    end
end

for i = 1:9, j = 1:9
    @constraint(m,sum{x[i,j,k],k=1:9}==1)
end

for i = 1:3:7, j = 1:3:7, k = 1:9
# i is the top left row, j is the top left column
# For each 3x3 square, we sum from from row i to i+2 and column j to j+2
    @constraint(m, sum{x[r,c,k], r=i:i+2, c=j:j+2} == 1)
end

for i = 1:9, j = 1:9
    # If the space isn’t empty
    if init_sol[i,j] != 0
    # Then the corresponding variable for that digit and location must be 1
    @constraint(m, x[i,j,init_sol[i,j]] == 1)
    end
end