A o(n logn) algorithm for LP knapsacks with GUB constraints |
| |
Authors: | Fred Glover Darwin Klingman |
| |
Affiliation: | (1) University of Colorado, Boulder, Colorado, USA;(2) University of Texas, BEB 608, Austin, Texas, USA |
| |
Abstract: | A specialization of the dual simplex method is developed for solving the linear programming (LP) knapsack problem subject to generalized upper bound (GUB) constraints. The LP/GUB knapsack problem is of interest both for solving more general LP problems by the dual simplex method, and for applying surrogate constraint strategies to the solution of 0–1 Multiple Choice integer programming problems. We provide computational bounds for our method of o(n logn), wheren is the total number of problem variables. These bounds reduce the previous best estimate of the order of complexity of the LP/GUB knapsack problem (due to Witzgall) and provide connections to computational bounds for the ordinary knapsack problem.We further provide a variant of our method which has only slightly inferior worst case bounds, yet which is ideally suited to solving integer multiple choice problems due to its ability to post-optimize while retaining variables otherwise weeded out by convex dominance criteria. |
| |
Keywords: | Integer Programming Knapsack Problems Multiple Choice Surrogate Constraints |
本文献已被 SpringerLink 等数据库收录! |
|