Research Reports from the Department of Operations
Document Type
Report
Publication Date
1-1-1976
Abstract
This report discusses various aspects of group theoretic algorithms in integer programming. A group theoretic algorithm transforms the original integer program to an optimization problem over an abelian group by relaxing nonnegativity, but not integrality, constraints on the variables corresponding to a linear programming basis. More specifically, columns of constraint coefficients, and the right hand sides in the group problem are elements of an abelian group with D elements, where D is the absolute value of the determinant of the linear programming basis. Several groups may be used to derive the optimization problem and the particular group selected indicates the form of its elements. A group theoretic algorithm solves an integer program by first forming, and then solving, the relaxed group problem. If the optimal solution to the group problem satisfies the relaxed nonnegativity constraints, the integer program is solved. Otherwise, a post optimization procedure, such as a branch and bound enumeration, is used. In any case, the minimal solution to the group problem which satisfies the relaxed nonnegativity constraints solves the integer program. The group minimization problem is introduced in Chapter I, together with the equivalent factor group minimization problem obtained via Smith's normal form. Organization of the report and a brief review of recent developments are also discussed. Chapter II deals with construction and solution of the group problem. The group problem is treated as a network problem in which a shortest path is sought. A modified version of an algorithm to derive Smith's normal form is presented first. This is followed by an extensive discussion of a new, efficient, shortest path algorithm specialized to take into account the structure of the network. The use of any dual feasible linear programming basis to construct the group problem, so that its order may be reduced, is also presented. Chapter III discusses a new branch and bound algorithm applied when the solution of the group problem yields negative values for some of the basic variables. Two relatively straightforward cutting plane criteria, namely, node omission and a branching procedure which avoids the creation of duplicate nodes, are presented. It is then shown that a simple combination of these two procedures results in an incorrect algorithm. The proper integration of these two procedures, which has a marked influence on the efficiency of the algorithm, is discussed. Many illustrative examples are provided to motivate the reader, and some interpretation of why the new algorithm works well is presented. The last section deals with sensitivity analysis in integer programming and its relation to the group minimization problem. Computational experiences are summarized in Chapter IV together with a brief description of the computer code. Computational results are divided according to topics and detailed performance is also shown. Possible future modifications of the computer code are suggested. Conclusions, as well as areas of further study, are discussed in the final chapter.
Keywords
Operations research, Integer programming, Group theory, Algorithms, Linear programming, Mathematical optimization, Network analysis (Planning), Branch and bound algorithms, Cutting stock problem
Publication Title
Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 394
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Morito, Susumu, "Integer Programming by Group Theory" (1976). Research Reports from the Department of Operations. 252.
https://commons.case.edu/wsom-ops-reports/252