×

QUAD01: A data-structured implementation of Hansen’s quadratic zero-one programming algorithm. (English) Zbl 0947.90611

Summary: The QUAD01 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; same results are reported here.

MSC:

90C09 Boolean programming
90C20 Quadratic programming

Software:

QUAD01
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Chakradhar, S. T.; Bushnell, M. L., A solvable class of quadratic 0-1 programming, Discrete Applied Mathematics, 36, 233-251 (1992) · Zbl 0771.90071
[2] Comley, W. J., The location of ambivalent facilities: Use of a quadratic zero-one programming algorithm, Applied Mathematical Modelling, 19, 26-29 (1995) · Zbl 0828.90070
[3] Crowder, H.; Johnson, E. L.; Padberg, M., Solving large-scale zero-one linear programming problems, Operations Research, 31, 803-834 (1983) · Zbl 0576.90065
[4] Fletcher, R., Practical Methods of Optimization (1987), John Wiley and Sons: John Wiley and Sons Chichester · Zbl 0905.65002
[5] Glover, F.; Woolsey, R. E.D., Note on converting the 0-1 polynomial programming problem to a 0-1 linear program, Operations Research, 22, 180-181 (1974) · Zbl 0272.90049
[6] Hansen, P., Quadratic zero-one programming by implicit enumeration, (Lootsma, F. A., Numerical Methods for Non-linear Optimization (1972), Academic Press: Academic Press London), 265-278
[7] Hansen, P., Methods of non-linear 0-1 programming, (Hammer, P. L.; Johnson, E. L.; Korte, B. H., Discrete Optimization, II (1979), North-Holland: North-Holland Amsterdam), 53-70 · Zbl 0426.90063
[8] Pardalos, P. M.; Jha, S., Complexity of uniqueness and local search in quadratic 0-1 programming, Operations Research Letters, 11, 119-123 (1992) · Zbl 0761.90070
[9] Pardalos, P. M.; Rodgers, G. P., Parallel branch and bound algorithms for quadratic zero-one on a hypercube architecture, Annals of Operations Research, 22, 271-292 (1990) · Zbl 0722.90047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.