整数线性规划中有效不等式与割平面研究

摘要

文章研究了整数和混合整数规划中有效不等式以及割平面法的问题,共分四章,在第一章讨论了一般的有效不等式产生规则,并对此如何运用这些简单有效不等式给予举例说明,在此基础上得出著名的C-G割平面,Gomory小数割平面,混合取整割平面以及Gomory混合整数割平面.在第二章运用一个超加性函数,通过参数的变化,取得一系列有效不等式,进而得到上述割平面的联系,同时对其进行有意义的推广.在第三章里,针对整数规划中的Knapsack问题的覆盖不等式进行讨论,通过O-1Knapsack问题,延伸到混合0-1问题,进而对整数Knapsack问题进行研究,文中还对覆盖不等式的升维问题进行了探讨.第四章简要介绍了分枝定界法和割平面法的基本原理,并对有效不等式和割平面在分枝割平面法中的应用作了一些解释.说明了有效不等式在整数规划中的作用是巨大的.

目录

文摘

英文文摘

引言

第一章整数与混合整数规划的有效不等式和割平面

§1.1一些简单的有效不等式

§1.2一些简单有效不等式的应用

§1.3整数规划的割平面

§1.4混合整数规划的割平面

第二章一个整数和混合整数规划中的超加性函数

§2.1一个超加性函数及其应用

§2.2超加性函数中各种割平面的关系

第三章Knapsack问题的有效不等式的研究

§3.1 0-1Knapsack问题的有效不等式

§3.2混合0-1Knapsack问题的有效不等式

§3.3整数Knapsack问题的有效不等式

§3.4 0-1Knapsack问题中的有效不等式的升维

第四章有效不等式和分枝割平面法

§4.1割平面法和分枝定界法概述

§4.2分枝割平面法

§4.3结论

参考文献

常用符号

公开发表论文

致谢