运筹学 - 5 - 整数编程

1、整数线性规划问题定义

整数规划是指在线性规划中对某个变量有整数限制要求的问题。
包括pure integer linear programming、mixed integer linear programming、0-1linear programming等。

2、0-1变量定义限制条件的表达

使用binary variables（0-1变量)来表示逻辑性条件限制。

a. 总的只能有某几个变量被选择 和小于某个数
b. 选择指定某几个变量 这几个变量的和等于某个数
c. 几个之中至少有一个被选择，和等于一
d.有顺序，只有当某个变量x1被选择之后变量x2才有可能被选择。有一定先后顺序 x2<=x1通过大小比较来判断
e.如果选择了x2，那么一定要选择x1。有一定先后顺序 x2<=x1通过大小比较来判断
f.如果选择了x1，就不能再选择x2。x2<=1-x1
g.x1和x2两者选择其一。x1+x2=1
h.如果x1、x2都被选择了，那么必须选择x3。x1+x2<=1+x3

由于是线性规划问题，所以任意一种条件下都不可以写成相乘的形式。

3、有x和y两个变量的整数规划问题

一种问题，需要用x和y来分别表示是否有该种变量，以及该变量的取值。

4、TSP旅行商问题

两种启发式算法：nearest neighbor method & chepest-insertion method
首先从一个点开始，选择离它最近的点，然后再从这个点出发，继续选择离它最近的且不重复的点。最后返回原来的点。
这种方法得到的可能并不是最优解。

5、两种解决整数规划的方法

branch-and-bound 分支定界法
cutting plan algorithm 割平面法