Accession Number : AD0668923

Title :   GROUP THEORETIC ALGORITHMS FOR THE INTEGER PROGRAMMING PROBLEM II: EXTENSION TO A GENERAL ALGORITHM.

Descriptive Note : Technical rept.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE OPERATIONS RESEARCH CENTER

Personal Author(s) : Shapiro,Jeremy F.

Report Date : 11 MAR 1968

Pagination or Media Count : 39

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)

Descriptors :   (*MATHEMATICAL PROGRAMMING, ALGORITHMS), GROUPS(MATHEMATICS), OPTIMIZATION, MATRICES(MATHEMATICS), NETWORKS, PROBLEM SOLVING, THEOREMS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE