Using dual network bounds in algorithms for solving generalized set packing partitioning problems |
| |
Authors: | N. Z. Shor Yu. V. Voitishin V. M. Glushkov |
| |
Affiliation: | (1) Institute for cybernetics, Ukrainian Academy of Sciences, 252207 Kiev, The Ukraine |
| |
Abstract: | This article deals with a method to compute bounds in algorithms for solving the generalized set packing/partitioning problems. The problems under investigation can be solved by the branch and bound method. Linear bounds computed by the simplex method are usually used. It is well known that this method breaks down on some occasions because the corresponding linear programming problems are degenerate. However, it is possible to use the dual (Lagrange) bounds instead of the linear bounds. A partial realization of this approach is described that uses a network relaxation of the initial problem. The possibilities for using the dual network bounds in the approximation techniques to solve the problems under investigation are described. |
| |
Keywords: | integer programming generalized set packing/partitioning problems dual bounds network relaxation approximate solutions |
本文献已被 SpringerLink 等数据库收录! |