【优化2】整数优化

概述

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

相比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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏趣学算法

算法之美——算法复杂性

《趣学算法》在线章节:http://www.epubit.com.cn/book/details/4825

31710
来自专栏数据结构与算法

Noip 2016 Day1 题解

老师让我们刷历年真题, 然后漫不经心的说了一句:“你们就先做做noip2016 day1 吧” 。。。。。。 我还能说什么,,,,,老师你这是明摆着伤害我们啊2...

615120
来自专栏数据派THU

手把手教你由TensorFlow上手PyTorch(附代码)

来源:机器之心 作者:Illarion Khlestov 本文为你解读PyTorch 的易用性。 当我第一次尝试学习 PyTorch 时,没几天就放弃了。和 ...

1K40
来自专栏HansBug's Lab

1059: [ZJOI2007]矩阵游戏

1059: [ZJOI2007]矩阵游戏 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 2154  Solv...

30360
来自专栏WOLFRAM

Mathematica 11在代数与数论中的新功能

20950
来自专栏用户2442861的专栏

kaggle-2美国人口普查年收入50K分类

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/d...

45330
来自专栏Python攻城狮

Python数据科学(九)- 使用Pandas绘制统计图表1.信息可视化

因为人对图像信息的解析效率比文字更高,所以可视化可以使数据更为直观,便于理解,使决策变得高效,所以信息可视化就显得尤为重要。

13030
来自专栏Crossin的编程教室

一段蛋疼的代码:超不清视频播放器

今天分享的这段代码,看起来没啥实际用处,而且有些反潮流,因为现如今大家看视频都追求更高分辨率的超清画质,而我们这个,是一个“超不清”的视频播放器:

14330
来自专栏一“技”之长

Cocos2d-x-v3坐标体系 原

        cocos2d引擎是一款非常优秀的扩平台的游戏开发引擎,在apple游戏榜上,有很多排名靠前的游戏都是由他创造出来的,他也有一套十分方便的坐标体...

6620
来自专栏开心的学习之路

用责任链模式实现图像处理方法的选择(python)

结合我们822实验室开源的图像处理平台(http://822lab.top)介绍用责任链模式实现图像处理方法的选择(python),供后续学弟学妹参考,整个平台...

15940

扫码关注云+社区

领取腾讯云代金券