Portal de Periódicos da CAPES

An implicit enumeration program for zero-one integer programming

1972; Springer Science+Business Media; Volume: 1; Issue: 1 Linguagem: Inglês

10.1007/bf01108520

0091-7036

Toshihide Ibaraki, T. K. Liu, C.R. Baugh, Saburo Muroga,

Advanced Optimization Algorithms Research

This paper describes some techniques to improve the speed of the implicit enumeration method for solving zero-one integer programming problems. Among these techniques, the most powerful is the one of using a column vector which works as a tag for each inequality, indicating whether or not the inequality should be checked for the current partial solution. A new condition for underlining a variable and the concept of pseudo-underlining are also proposed. These techniques were implemented in the computer programil lip (ILLinois Integer Programming code). The computational results for different types of problems are discussed.