NTRS - NASA Technical Reports Server

Back to Results
An improved exploratory search technique for pure integer linear programming problemsThe development is documented of a heuristic method for the solution of pure integer linear programming problems. The procedure draws its methodology from the ideas of Hooke and Jeeves type 1 and 2 exploratory searches, greedy procedures, and neighborhood searches. It uses an efficient rounding method to obtain its first feasible integer point from the optimal continuous solution obtained via the simplex method. Since this method is based entirely on simple addition or subtraction of one to each variable of a point in n-space and the subsequent comparison of candidate solutions to a given set of constraints, it facilitates significant complexity improvements over existing techniques. It also obtains the same optimal solution found by the branch-and-bound technique in 44 of 45 small to moderate size test problems. Two example problems are worked in detail to show the inner workings of the method. Furthermore, using an established weighted scheme for comparing computational effort involved in an algorithm, a comparison of this algorithm is made to the more established and rigorous branch-and-bound method. A computer implementation of the procedure, in PC compatible Pascal, is also presented and discussed.
Document ID
Document Type
Technical Memorandum (TM)
Fogle, F. R. (NASA Marshall Space Flight Center Huntsville, AL, United States)
Date Acquired
September 6, 2013
Publication Date
October 1, 1990
Subject Category
Report/Patent Number
NAS 1.15:103517
Distribution Limits
Work of the US Gov. Public Use Permitted.

Available Downloads

NameType 19910004597.pdf STI