GROUP THEORETIC ALGORITHMS FOR THE INTEGER PROGRAMMING PROBLEM II: EXTENSION TO A GENERAL ALGORITHM.
MASSACHUSETTS INST OF TECH CAMBRIDGE OPERATIONS RESEARCH CENTER
Pagination or Media Count:
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
- Operations Research