GB1362910A - Data processing system for finding optimum integer-valued solutions of linear programmes - Google Patents

Abstract

1362910 Linear programming INTERNATIONAL BUSINESS MACHINES CORP 21 Feb 1972 [30 June 1971] 7853/72 Heading G4A In a system for the solution of a set of algebraic equations forming a linear program which includes an objective function Z for the linear program and the requirement that certain x i of the variables x of the solution must be integral valued, an initial linear program is solved, without the integer constraint to derive the optimum value Z LP of the objective function and if this first linear program does not have the required integral solution a branching operation is formed starting from the initial solved program to form new linear programs, a bound being computed for each linear program on which a branch is to be made to predict the best possible solution Z B which could be reached by following the branch path and the branching operation is terminated when it is found that the branch will not provide a better value for the objective function Z than a previously found integral solution. In a first method, the initial linear program is solved using the Simplex method and a variable x i that has a non-integral value is constrained to have the integral values adjacent its value in the optimum solution. If either of these values is feasible, a branch is started with the consequently formed new linear program and bounds are computed to indicate the value which the objective function Z B is expected to take. Bounds are similarly derived for horizontal branches commencing from other integer values. Vertical branching is obtained by subsequently restricting other non-integral variables to their adjacent integral values to derive further linear programs to be solved. At each stage all the unsolved linear programs are examined and the one given the best value Z B is solved until an integral solution is found. When an integral solution is found only branches having bounds giving a better value of the objective function are subsequently processed. In a second method, after the solution of the first linear program, the first variable to be restrained to an integral value is chosen to be the variable producing the largest bound. This results in a considerable reduction in the number of linear programs that have to be solved before the optimum integral solution is found. The Specification includes the mathematical theory for computing the bounds.