Research Reports from the Department of Operations
Document Type
Dissertation
Publication Date
8-1-1969
Abstract
This thesis presents two flexible zero-one integer programming (single branch enumerative) algorithms. It is shown that the first method, applicable to the general program (i.e., min.(c'y: Ay<=b, y_j=0 or 1) ), has the ability, via a new dynamic origin technique, to adapt to the problem data. Other pioneering features, which assist in curtailing the length of the search, are linear programming, post optimization, and criteria for selecting branches from feasible nodes. Using this approach as a foundation, an extension for the mixed integer program (i.e., min.(c'y+d'x: Ay+Dx<=b, x>=0, y_j=0 or 1) ) is discussed. The second algorithm, applicable to the set covering problem (i.e., min.(c'y: Ry>=e, y>=0, y integer); where R is a matrix of 0's and 1's, and e is a vector of 1's), basically obtains upper and lower bounds on the integer problem from the associated linear program. It is shown, by certain proved facts, that one can always obtain two (and sometimes three) integer feasible points from any primal solution to the continuous problem. The bounds obtained from the integer subproblems solved as linear programs, being remarkably "good", have been quite effective in reducing the length of the search. A related problem (i.e., min.(c'y+d'x: Ry+Px>=e, a<=Bx<=b, x_j,y_j =0 or 1); where (R,P) is a matrix of 0's and 1's, e is a vector of 1's, B is a nonnegative matrix, and a>=0, b>=0, c>=0, d>=0) is also discussed in context of the set covering scheme. Both algorithms have been coded and extensively tested on an IBM 360 Model 50 computer. The code for the integer program solved problems with a maximum of 50 variables and 31 constraints were solved in less than 3.7 minutes, and the other program handled problems with as many as 1,642 columns and 200 rows in less than 25 minutes. The results indicate that the algorithms developed in this dissertation have promising futures in the field.
Keywords
Operations research, Integer programming, Linear programming, Algorithms, Set theory, Mathematical optimization, Combinatorial optimization
Publication Title
Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 162
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Salkin, Harvey M., "Enumerative Algorithms for Integer and Mixed Integer Programs" (1969). Research Reports from the Department of Operations. 185.
https://commons.case.edu/wsom-ops-reports/185