×

zbMATH — the first resource for mathematics

An evolutionary heuristic for quadratic 0-1 programming. (English) Zbl 0938.90051
Summary: The authors present a heuristic algorithm for the well-known Unconstrained Quadratic 0-1 Programming Problem. The approach is based on combining solutions in a genetic paradigm and incorporates intensification algorithms used to improve solutions and speed up the method. Extensive computational experiments on instances with up to 500 variables are presented and the authors compare their approach both with powerful heuristic and exact algorithms from the literature establishing the effectiveness of the method in terms of solutions quality and computing time.

MSC:
90C09 Boolean programming
90C59 Approximation methods and heuristics in mathematical programming
90C20 Quadratic programming
Software:
Scatter Search
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alidaee, B.; Kochenberger, G.; Ahmadian, A., 0-1 quadratic programming approach for the optimal solution of two scheduling problems, International journal of system science, 25, 401-408, (1994) · Zbl 0795.90031
[2] Barahona, F., A solvable case of quadratic 0-1 programming, Discrete applied mathematics, 13, 23-26, (1986) · Zbl 0597.90059
[3] Barahona, F.; Jünger, M.; Reinelt, G., Experiments in quadratic 0-1 programming, Mathematical programming, 44, 127-137, (1989) · Zbl 0677.90046
[4] Barahona, F.; Mahjoub, A.R., On the cut polytope, Mathematical programming, 36, 157-173, (1986) · Zbl 0616.90058
[5] P. Carraresi, F. Farinaccio, F. Malucelli, Testing optimality for quadratic 0-1 problems, Mathematical Programming, forthcoming · Zbl 0952.90025
[6] Chardaire, P.; Sutter, A., A decomposition method for quadratic zero – one programming, Management science, 41, 4, 704-712, (1995) · Zbl 0836.90121
[7] De Simone, C., The cut polytope and the Boolean quadratic polytope, Discrete mathematics, 79, 71-75, (1990) · Zbl 0683.90068
[8] Gallo, G.; Hammer, P.; Simeone, B., Quadratic knapsack problems, Mathematical programming, 12, 132-149, (1980) · Zbl 0462.90068
[9] F. Glover, A template for scatter search and path relinking, in: J.K. Hao, E. Lutton, E. Ronald, M. Schoenauer, D. Snyers (Eds.), Artificial Evolution, Lecture Notes in Computer Science, vol. 1363, 1997, pp. 13-54
[10] Glover, F.; Kochenberger, G.A.; Alidaee, B., Adaptive memory tabu search for binary quadratic programs, Management science, 44, 3, 336-345, (1998) · Zbl 0989.90072
[11] F. Glover, G.A. Kochenberger, B. Alidaee, M. Amini, Tabu search with critical event memory: an enhanced application for Binary Quadratic Programs, in: S. Voss, S. Martello, H. Osman, C. Roucairol (Eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers, Boston, MA, 1998, pp. 93-109 · Zbl 0972.90053
[12] Hammer, P., Some network flow problems solved with pseudo-Boolean programming, Operations research, 13, 388-399, (1965) · Zbl 0132.13804
[13] Hammer, P.; Hansen, P.; Simeone, B., Roof duality, complementation and persistence in quadratic 0-1 programming, Mathematical programming, 28, 121-155, (1984) · Zbl 0574.90066
[14] McBride, R.D.; Yormark, J.S., An implicit enumeration algorithm for quadratic integer programming, Management science, 26/3, 282-296, (1980) · Zbl 0443.90067
[15] H. Mühlenbein, Genetic algorithms, in: E. Aarts, J.K. Lenstra (Eds.), Local Search in Combinatorial Optimization, Wiley, Chichester, UK, 1997, pp. 137-191
[16] Padberg, M., The Boolean quadratic polytope: characteristics, facets and relatives, Mathematical programming, 45, 139-172, (1989) · Zbl 0675.90056
[17] Pardalos, P.M.; Rodgers, G.P., Computational aspects of a branch and bound algorithm for quadratic zero – one programming, Computing, 45, 131-144, (1990) · Zbl 0721.65034
[18] Picard, J.C.; Ratliff, H.D., Minimum cuts and related problems, Networks, 5, 357-370, (1974) · Zbl 0325.90047
[19] E. Taillard, Heuristic methods for large centroid clustering problems, Technical Paper IDSIA-96-96, IDSIA, Lugano, Switzerland, 1996 · Zbl 1035.90038
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.