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.
