An 0(n(log n + log m)) Algorithm for LP Knapsacks with GUB Constraints.

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. Computational bounds are provided for this method of 0(n(log n + log m)), where n is the total number of problem variables and m is the number of GUB sets. In the commonly encountered situation where the number of variables in each GUB set is the same, our bound becomes 0(n log n). These bounds reduce the previous best estimate of the order of complexity of the LP/GUB knapsack problem and provide connections to computational bounds for the ordinary knapsack problem.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1978
Accession Number
ADA058107

Entities

People

  • Darwin Dee Klingman
  • Fred W. Glover

Organizations

  • University of Texas at Austin

Tags

Communities of Interest

  • Counter IED
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Business Administration
  • Computational Complexity
  • Computations
  • Computer Programming
  • Computer Science
  • Integer Programming
  • Linear Programming
  • Lists (Data Structures)
  • Mathematical Programming
  • Mathematics
  • Operations Research
  • Simplex Method
  • Specialization
  • United States

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Operations Research