Study of Lagrangean Decompositions

点击翻译按钮获取中文摘要

Lagrangean decomposition (LD) and Lagrangean decomposition/aggregation (LD/A) are powerful tools for computing bounds in integer programming. This is a project to study LD for minmax problems and for separable problems with a nonlinear objective function. The research will develop solutions for LD/A problems which decompose into relatively easy subproblems, some or all of them with the integrality property, so that the LD/A bound is as good as (i.e. equal to) the corresponding Lagrangean Relaxation bound. Moreover the LD/A procedure occasionally yields the optimal solution in the not infrequent instance when the subproblems have identical solutions. There is a need for investigation into the LD and LD/A minimax problems. There is a strong potential for a breakthrough in computational efficiency.