QUAD01: A data-structured implementation of Hansen's quadratic zero–one programming algorithm

The QUD01 program described here implements an implicit-enumeration algorithm for quadratic zero–one programming devised by Pierre Hansen just over twenty years ago. The present author's implementation is written in the C programming language and uses an efficient linked-list structure to store and manipulate constraint and objective data. This use, together with the increased speed of modern microcomputers and improved optimisation of generated code, has led to a marked reduction in running times compared with the original implementation (in FORTRAN) by Hansen. Further reductions of running times have been obtained by incorporating dynamic ordering of constraints into QUAD01. Problems having up to 50–100 variables and 100–200 constraints have been solved; some results are reported here.