442 Franc¸ois Vanderbeck and Laurence A. Wolsey
set Z as specified in Theorems 13.1 or 13.2. The LP solution to this reformulation
provides a dual bound that is typically tighter than that of the LP relaxation of the
original formulation of X and is equal to the best bound that can be derived by
Lagrangean relaxation of the constraints Dx > d. This will be demonstrated below.
In many applications of interest Bx > b has block diagonal structure: i.e., Z =
Z
1
×···×Z
K
in which case the integer program takes the form
(IP
BD
) min{
K
∑
k=1
c
k
x
k
: (x
1
,. . .,x
K
) ∈Y, x
k
∈ Z
k
for k = 1,. ..,K}
and can be written explicitly as:
(IP
BD
) min c
1
x
1
+ c
2
x
2
+ ··· + c
K
x
K
D
1
x
1
+ D
2
x
2
+ ··· + D
K
x
K
> d
B
1
x
1
> b
1
B
2
x
2
> b
2
.
.
.
>
.
.
.
B
K
x
K
> b
K
x
1
∈ Z
n
1
+
, x
2
∈ Z
n
2
+
,. . .,x
K
∈ Z
n
K
+
.
Here relaxing the constraints
∑
K
k=1
D
k
x
k
≥ d allow one to decompose the problem
into K smaller size optimization problems: min{c
k
x
k
: x
k
∈ Z
k
}.
Another important special case is the identical sub-problem case in which D
k
=
D, B
k
= B, c
k
= c, Z
k
= Z
∗
for all k. In this case the “complicating” constraints only
depend on the aggregate variables
y =
K
∑
k=1
x
k
, (13.10)
so the complicating constraints correspond to a set of the form Y = {y ∈ Z
n
+
: Dy >
d}. The problem can now be written as:
(IP
IS
) min{cy : Dy > d, y =
K
∑
k=1
x
k
, x
k
∈ Z
∗
for k = 1,. ..,K}. (13.11)
Example 5 (The bin packing problem)
Given an unlimited supply of bins of capacity 1 and a set of items indexed by i =
1,. . .,n of size s
i
∈ (0,1], the problem is to find the minimum number of bins that
are needed in order to pack all the items. Let K be an upper bound on the number
of bins that are needed (K = n, or K is the value of any feasible solution). A direct
IP formulation is
剩余71页未读，继续阅读
weiweiwei666
- 粉丝: 0
- 资源: 18
我的内容管理
展开
最新资源
- 解决本地连接丢失无法上网的问题
- BIOS报警声音解析：故障原因与解决方法
- 广义均值移动跟踪算法在视频目标跟踪中的应用研究
- C++Builder快捷键大全：高效编程的秘密武器
- 网页制作入门：常用代码详解
- TX2440A开发板网络远程监控系统移植教程：易搭建与通用解决方案
- WebLogic10虚拟内存配置详解与优化技巧
- C#网络编程深度解析：Socket基础与应用
- 掌握Struts1：Java MVC轻量级框架详解
- 20个必备CSS代码段提升Web开发效率
- CSS样式大全：字体、文本、列表样式详解
- Proteus元件库大全：从基础到高级组件
- 74HC08芯片：高速CMOS四输入与门详细资料
- C#获取当前路径的多种方法详解
- 修复MySQL乱码问题：设置字符集为GB2312
- C语言的诞生与演进：从汇编到系统编程的革命
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
