Using Surrogate Constraints in a Lagrangian Relaxation Approach to Set-Covering Problems |
| |
Authors: | C. Gregory John Gary A. Kochenberger |
| |
Affiliation: | 1.Department of Decision Sciences,Indiana University,USA;2.Department of Business Administration and Economics,University of Southern Colorado,USA |
| |
Abstract: | Lagrangian relaxations have been used in a variety of IP problem settings. The main thrust of such efforts is to obtain bounding information for use in a branch-and-bound procedure. This paper examines the effect of adding a single surrogate constraint to Lagrangian subproblems in an attempt to improve upon the bounds produced by conventional Lagrangian relaxation. Computational results on some randomly generated set-covering problems are reported. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |