Group Theoretic Algorithms for the Integer Programming Problem II: Extension to a General Algorithm

Publisher Website
Google Scholar
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 that 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 relation of GTIP2 to other algorithms is indicated. A numerical example and some partial computational results are included.

This publication has 0 references indexed in Scilit: