This research announcement outlines a finite algorithm for finding integer solutions to linear programs. The algorithm is based on the simplex method and involves generating new constraints to ensure integer solutions. The process starts by maximizing the objective function using the simplex method. If the solution is not integer, a new constraint is added that is satisfied by the unknown integer solution but not by the non-integer solution. This new constraint is then used to find a new maximum, and the process is repeated until an integer maximum is found or it is determined that a nearby integer point is optimal.
The algorithm is implemented on an E101 computer and has been successfully used to find integer solutions to small linear programs with seven or fewer variables. The algorithm closely resembles methods used by Dantzig, Fulkerson, and Johnson, as well as Markowitz and Manne, to solve discrete variable programming problems. The key innovation is a systematic method for generating new constraints that ensure the process terminates in a finite number of steps.
The original linear program is transformed into a set of equations with nonnegative variables. The simplex method is used to find a solution, and if the solution is not integer, a new constraint is added. This new constraint is derived from the non-integer components of the solution. The new constraint is added to the original equations, and the process is repeated until an integer solution is found.
The algorithm ensures that any nonnegative integer solution to the original problem corresponds to a nonnegative integer solution to the new set of equations. The process is repeated if the new maximum is not integer, and the number of additional constraints is limited to ensure the algorithm terminates. The choice of which row to use for generating new constraints is based on the fractional part of the solution, with the row having the largest fractional part being preferred. The algorithm is designed to terminate in a finite number of steps, making it a valid finite algorithm for finding integer solutions to linear programs.This research announcement outlines a finite algorithm for finding integer solutions to linear programs. The algorithm is based on the simplex method and involves generating new constraints to ensure integer solutions. The process starts by maximizing the objective function using the simplex method. If the solution is not integer, a new constraint is added that is satisfied by the unknown integer solution but not by the non-integer solution. This new constraint is then used to find a new maximum, and the process is repeated until an integer maximum is found or it is determined that a nearby integer point is optimal.
The algorithm is implemented on an E101 computer and has been successfully used to find integer solutions to small linear programs with seven or fewer variables. The algorithm closely resembles methods used by Dantzig, Fulkerson, and Johnson, as well as Markowitz and Manne, to solve discrete variable programming problems. The key innovation is a systematic method for generating new constraints that ensure the process terminates in a finite number of steps.
The original linear program is transformed into a set of equations with nonnegative variables. The simplex method is used to find a solution, and if the solution is not integer, a new constraint is added. This new constraint is derived from the non-integer components of the solution. The new constraint is added to the original equations, and the process is repeated until an integer solution is found.
The algorithm ensures that any nonnegative integer solution to the original problem corresponds to a nonnegative integer solution to the new set of equations. The process is repeated if the new maximum is not integer, and the number of additional constraints is limited to ensure the algorithm terminates. The choice of which row to use for generating new constraints is based on the fractional part of the solution, with the row having the largest fractional part being preferred. The algorithm is designed to terminate in a finite number of steps, making it a valid finite algorithm for finding integer solutions to linear programs.