×

A quadratic simplex algorithm for primal optimization over zero-one polytopes. (English) Zbl 07809941

Summary: A primal quadratic simplex algorithm tailored to the optimization over the vertices of a polytope is presented. Starting from a feasible vertex, it performs either strictly improving or admissible non-deteriorating steps in order to determine a locally optimum basic feasible solution in terms of the quadratic objective function. The algorithm so generalizes over local improvement methods for according applications, including in particular quadratic optimization problems whose feasible solutions correspond to vertices of a 0-1 polytope. Computational experiments for unconstrained binary quadratic programs, maximum cut, and the quadratic assignment problem serve as a proof of concept and underline the importance of a pivoting rule that is able to accept at least a restricted class of degenerate steps.

MSC:

90Cxx Mathematical programming
65Kxx Numerical methods for mathematical programming, optimization and variational techniques
90Bxx Operations research and management science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barankin, E.; Dorfman, R., (On Quadratic Programming. On Quadratic Programming, Publications in Statistics, vol. 2, (1958), University of California Press) · Zbl 0080.36502
[2] Beale, E. M.L., On quadratic proramming, Nav. Res. Logist. Q., 6, 3, 227-243, (1959)
[3] Bland, R. G., New finite pivoting rules for the simplex method, Math. Oper. Res., 2, 2, 103-107, (1977) · Zbl 0408.90050
[4] Burer, S.; Monteiro, R. D.C.; Zhang, Y., Rank-Two relaxation heuristics for MAX-CUT and other binary quadratic programs, SIAM J. Optim., 12, 2, 503-521, (2002) · Zbl 1152.90532
[5] Burkard, R. E.; Çela, E.; Karisch, S. E.; Rendl, F.; Anjos, M.; Hahn, P., QAPLIB - A Quadratic Assignment Problem Library - Problem instances and solutions, (2022), University of Edinburgh
[6] Dantzig, G. B., Quadratic Programming. A Variant of the Wolfe-Markowitz AlgorithmsTech. Rep., (1961), OR Center, University of California-Berkeley
[7] Dantzig, G. B., Linear Programming and Extensions, (1963), Princeton University Press · Zbl 0108.33103
[8] Dunning, I.; Gupta, S.; Silberholz, J., What works best when? A systematic evaluation of heuristics for max-cut and QUBO, INFORMS J. Comput., 30, 3, 608-624, (2018) · Zbl 1528.90288
[9] Eaves, B. C., On quadratic programming, Manage. Sci., 17, 11, 698-711, (1971) · Zbl 0242.90040
[10] Giles, F.; Pulleyblank, W., Total dual integrality and integer polyhedra, Linear Algebra Appl., 25, 191-196, (1979) · Zbl 0413.90054
[11] Gill, P. E.; Wong, E., Methods for convex and general quadratic programming, Math. Program. Comput., 7, 1, 71-112, (2015) · Zbl 1317.90225
[12] Gilmore, P. C., Optimal and suboptimal algorithms for the quadratic assignment problem, J. Soc. Ind. Appl. Math., 10, 2, 305-313, (1962) · Zbl 0118.15101
[13] Glover, F.; Kochenberger, G. A.; Alidaee, B., Adaptive memory tabu search for binary quadratic programs, Manage. Sci., 44, 3, 336-345, (1998) · Zbl 0989.90072
[14] Goemans, M. X.; Williamson, D. P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 6, 1115-1145, (1995) · Zbl 0885.68088
[15] Gould, N. I.M., An algorithm for large-scale quadratic programming, IMA J. Numer. Anal., 11, 3, 299-324, (1991) · Zbl 0727.65055
[16] Haus, U.-U.; Köppe, M.; Weismantel, R., A primal all-integer algorithm based on irreducible solutions, Math. Program., 96, 2, 205-246, (2003) · Zbl 1059.90106
[17] Keller, E. L., The general quadratic optimization problem, Math. Program., 5, 1, 311-337, (1973) · Zbl 0276.90044
[18] Lawler, E. L., The quadratic assignment problem, Manage. Sci., 9, 4, 586-599, (1963) · Zbl 0995.90579
[19] Merz, P.; Freisleben, B., Greedy and local search heuristics for unconstrained binary quadratic programming, J. Heuristics, 8, 2, 197-213, (2002) · Zbl 1013.90100
[20] Murthy, K. A.; Li, Y.; Pardalos, P. M., A local search algorithm for the quadratic assignment problem, Informatica, 3, 524-538, (1992), 4 · Zbl 0937.68511
[21] Nocedal, J.; Wright, S. J., Numerical Optimization, (2006), Springer · Zbl 1104.65059
[22] van de Panne, C.; Whinston, A., The simplex and the dual method for quadratic programming, OR, 15, 4, 355-388, (1964)
[23] Pardalos, P. M.; Jha, S., Complexity of uniqueness and local search in quadratic 0-1 programming, Oper. Res. Lett., 11, 2, 119-123, (1992) · Zbl 0761.90070
[24] Pardalos, P. M.; Rendl, F.; Wolkowicz, H., The quadratic assignment problem: A survey and recent developments, (Pardalos, P. M.; Wolkowicz, H., Quadratic Assignment and Related Problems. Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16, (1994), AMS: AMS Providence, RI), 1-42 · Zbl 0817.90059
[25] Pardalos, P.; Schnitger, G., Checking local optimality in constrained quadratic programming is NP-hard, Oper. Res. Lett., 7, 1, 33-35, (1988) · Zbl 0644.90067
[26] Rendl, F.; Rinaldi, G.; Wiegele, A., Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations, Math. Program., 121, 2, 307-335, (2010) · Zbl 1184.90118
[27] Resende, M. G.C.; Ribeiro, C. C., Greedy randomized adaptive search procedures, (Glover, F.; Kochenberger, G. A., Handbook of Metaheuristics, (2003), Springer US: Springer US Boston, MA), 219-249 · Zbl 1102.90384
[28] Rusin, M. H., A revised simplex method for quadratic programming, SIAM J. Appl. Math., 20, 2, 143-160, (1971) · Zbl 0221.90037
[29] Schäffer, A. A.; Yannakakis, M., Simple local search problems that are hard to solve, SIAM J. Comput., 20, 1, 56-87, (1991) · Zbl 0716.68048
[30] Shetty, C. M., A simplified procedure for quadratic programming, Oper. Res., 11, 2, 248-260, (1963) · Zbl 0112.12303
[31] Taillard, E., Robust taboo search for the quadratic assignment problem, Parallel Comput., 17, 4, 443-455, (1991), C++ program applied from http://mistic.heig-vd.ch/taillard/
[32] Thompson, G. L., An integral simplex algorithm for solving combinatorial optimization problems, Comput. Optim. Appl., 22, 3, 351-367, (2002) · Zbl 1039.90060
[33] Wolfe, P., The simplex method for quadratic programming, Econometrica, 27, 3, 382-398, (1959) · Zbl 0103.37603
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.