Using dual network bounds in algorithms for solving generalized set packing/partitioning problems

Using dual network bounds in algorithms for solving generalized set packing/partitioning problems

0.00 Avg rating0 Votes
Article ID: iaor19981398
Country: Netherlands
Volume: 6
Issue: 3
Start Page Number: 293
End Page Number: 303
Publication Date: Nov 1996
Journal: Computational Optimization and Applications
Authors: , ,
Keywords: packing, partitioning, duality
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.

Reviews

Required fields are marked *. Your email address will not be published.