毕业设计我帮你

一种基于分支定界的用于解决0-1渐缩问题的新拉格朗日算法

摘要

本文介绍了一种基于分支定界的用于解决0-1渐缩问题的新拉格朗日算法。该算法是基于使用拉格朗日松弛切割过程，该过程允许指数化许多部分的戈莫里切割和延伸封盖不等式成为拉格朗日二元化的候选项。这样做的话，对于，所获得的上限比标准线性规划松弛的更强。该算法的目的是解决具有系数有10的15次方，且现有的解决算法可能不直接适用的一类实例。

关键词：0-1背包问题的拉格朗日松弛法、分支定界

 

目录

摘要 I

1 绪论 1

2 一个新的用于解决的分支定界算法 2

2.1 拉格朗日松弛边界和可变固定测试 2

2.2 枚举树 3

3 计算实验和未来研究 4

参考文献 5

 

参考文献

[1]M. Guignard. “Efficient cuts in Lagrangean Relax and Cut Schemes”. European Journal on Operational Research, 105(1):216–223, 1998.

[2]A. Lucena. “Lagrangian Relax-and-cut algorithms”. In P. Pardalos and M.G.C.Resende, editors, Handbook on Telecommunications, pages 129–146. KluwerAcademic, Boston, MA, 2005.

[3] A. Lucena. “Non Delayed Relax-and-Cut Algorithms”. Annals of OperationsResearch, 140:375–410, 2005.

[4]S. Martello, D. Pisinger, and P. Toth. Dynamic Programming and Strong Boundsfor the 0-1 Knapsack Problem. Management Science, 45:414–424, 1997.

[5]S. Martello and P. Toth. Knapsack Problems: Algorithms and ComputerImplementations. Wiley Interscience, 1990.

[6]D. Pisinger. “A hybrid method for the 0 − 1 Knapsack Problem”. Methods ofOperations Research, 49:277–329, 1985.

[7]D. Pisinger. Where are the hard knapsack problems ? Computers and OperationsResearch, 32:2271–2284, 2005.