A New Approach to Ralaxation in Integer Programming

这个项目的重点是分析整数规划问题的一种新的松弛近似，并利用这种技术设计算法。这种新的松弛被称为复合分解，可以被视为代理松弛和拉格朗日松弛的推广。首席研究者最近证明了它控制拉格朗日松弛、代理松弛和LP松弛，从这个意义上讲，最优解的界至少是一样好的，甚至可能更好。该方案的目的是研究似乎最适合复合分解松弛的双上升启发式方法。重点将放在自然适合这种分解的问题类别上，如网络选址问题、广义分配/分配问题、多项选择问题，以及具有一些一般侧面约束的特殊结构问题。

The focus of this project is on the analysis of a new relaxation approximation for integer programming problems and on the design of algorithms exploiting this technique. This new relaxation, called composite decomposition, can be viewed as a generalization of both surrogate and Lagrangean relaxations. The principal investigator has recently proved that it dominates Lagrangean, surrogate and LP relaxations, in the sense that the bounds on the optimum are at least as good and probably better. The aim of this proposal is to study dual ascent heuristic methods which appear best suited to the composite decomposition relaxation. Emphasis will be placed on classes of problems which lend themselves naturally to this kind of decomposition, such as network location problems, generalized assignment/allocation problems, and multiple choice problems, as well as specially structured problems with a few general side constraints.