混合整数规划中的预处理方法

摘要

混合整数线性规划模型(MILP)在公路交通、航空运输、经济与金融以及通信等众多领域中都有广泛的应用，不断对求解混合整数线性规划问题提出新的要求。但是，对于一般实际问题，由于问题规模较大，往往需要使用建模工具进行建模，因此模型中不可避免的包含许多冗余信息，极大的阻碍问题的求解，这就对预处理提出了要求。预处理(presolving)就是将给定的问题模型转化为等价的更容易求解的模型。本文主要基于几种常用的预处理算法，包括线性约束预处理、等式预处理和对偶聚合等，通过对实际生产过程中的一般混合整数规划模型进行预处理，减少模型中的变量和约束条件，从而能够减小模型的规模，使得模型更容易求解。首先学习研究针对不通类型的约束条件的预处理的算法，并分析算法的有效性;然后根据给出的预处理算法对一些混合整数规划问题实例进行数值试验。通过数值试验证明，对于一般的混合整数规划问题，预处理能够有效地减少模型中变量和约束条件的个数，从而简化了模型，使得模型便于求解。

目录

声明

致谢

摘要

第一章 绪论

1 引言

2 研究背景与意义

第二章 域传播(Domain Propagation)

1 理论基础

2 线性约束域传播算法

第三章 预处理(Presolving)

1 一般线性约束预处理

2 特殊形式约束预处理

2．1 背包约束预处理

2．2 集合划分、集合配置和集合覆盖约束

2．3 变量界约束

2．4 整数变量转换为0-1变量

3探测(Probing)

第四章 数值实验

1 几个重要的算法实现技术

1．1 扩展欧几里德算法

1．2 聚合变量的处理

2 数值实验

2．1 较小模型

2．2 较大模型

第五章 结论

参考文献

附录

学位论文数据集