GROUP THEORETIC ALGORITHMS FOR THE INTEGER PROGRAMMING PROBLEM II: EXTENSION TO A GENERAL ALGORITHM.
Abstract
The main result of this paper is a group theoretic algorithm (GTIP2) for the integer programming problem. This algorithm is an extension of an algorithm from an earlier paper (part I). The algorithm in part I solves a group optimization problem derived from a given integer programming problem. The optimal solution to the group problem thereby obtained is an optimal solution to the integer programming problem if it is feasible. Unfortunately, an optimal solution to the group problem may yield an infeasible integer solution. The algorithm GTIP2 of this paper is an extension of the method of part I when it fails. In particular, GTIP2 employs a search procedure to find an optimal solution to the integer programming problem. The extent of the search is bounded by procedures derived from a variety of relevant group problems which are solved by the algorithm of part I. There is a discussion of the class of problems for which GTIP2 is primarily intended and the relationship of GTIP2 to other algorithms is indicated. A numerical example and some partial computational results are included. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 11, 1968
- Accession Number
- AD0668923
Entities
People
- Jeremy F. Shapiro
Organizations
- Massachusetts Institute of Technology