AN ALGORITHM FOR SOLVING THE LINEAR INTEGER PROGRAMMING PROBLEM OVER A FINITE ADDITIVE GROUP, WITH EXTENSIONS TO SOLVING GENERAL LINEAR AND CERTAIN NONLINEAR INTEGER PROBLEMS
Abstract
Ralph Gomory has recently aroused interest in a special type of knapsack problem in which the constraint coefficients and constant term are elements of a finite additive group. The significance of this problem lies in the fact that it is closely related to the general integer linear programming problem, resulting by removing the nonnegativity restrictions on those variables in the general problem that lie in an optimal basis for the associated linear program. Gomory has shown how to solve the special knapsack problem by adapting a dynamic programming recursion originally designed for the ordinary knapsack problem, and has identified sufficient conditions under which the solution of the special knapsack problem will satisfy the nonnegativity requirements in the general integer program, thereby yielding an optimal solution to that problem as well. In this paper the author presents an algorithm for solving the special knapsack problem that is capable of accommodating a variety of constraints in addition to the special knapsack constraint. The purpose in doing this is to expand the range of problems for which the optimal solution for the special problem will also provide an optimal solution to the general integer program from which it was derived.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1966
- Accession Number
- AD0642276
Entities
People
- Fred Glover
Organizations
- University of California, Berkeley