A recipe for semidefinite relaxation for (0,1)-quadratic programming
Tóm tắt
Từ khóa
Tài liệu tham khảo
Adams, W. and Dealing, P.M. (1994), On the equivalence between roof duality and Lagrangian duality for unconstrained 0?1 quadratic programming problems.Discrete Appl. Math. 48:1?20.
Alizadeh, F. (1992), Combinatorial optimization with semidefinite matrices. InProceedings of the Second Annual Integer Programming and Combinatorial Optimization Conference, CarnegieMellon University.
Balas, E., Ceria, S., and Cornuejols, G. (1993), A lift-and-project cutting plane algorithm for mixed 0?1 programs.Mathematical Programming 58:295?324.
Balas, E., Ceria, S., Cornuejols, G., and Pataki, G. (1994), Updated semidefinite constraints. Technical report, GSIA Carnegie Mellon University, Pittsburgh, PA, 1994. Personal communication.
Bersekas, D.P. (1982),Constrained Optimization and Lagrange Multipliers. Academic Press, New York, NY.
Delorme, C. and Poljak, S. (1993), Laplacian eigenvalues and the maximum cut problem.Math. Programming 62(3):557?574.
Falkner, J., Rendl, F., Wolkowicz, H., and Zhao, Q., Semidefinite relaxations for the graph partitioning problem. Research report, University of Waterloo, Waterloo, Ontario, In progress.
Finke, G., Burkard, R.E., and Rendl, F. (1987), Quadratic assignment problems.Annals of Discrete Mathematics 31:61?82.
Forgó, F. (1988),Nonconvex Programming. Akadémiai Kiadó, Budapest.
Goemans, M.X. and Williamson, D.P. (1993), 878-approximation algorithms for max cut and max 2sat. Technical report, Department of Mathematics, MIT.
Haemmers, W. (1979), On some problems of lovasz concerning the shannon capacity of graphs.IEEE Transactions on Information Theory 25:231?232.
Hammer, P.L., Hansen, P., and Simeone, B. (1984), Roof duality, complementation and persistency in quadratic 0?1 optimization.Mathematical Programming 28:121?155.
Helmberg, C., Rendl, F., Vanderbei, R.J., and Wolkowicz, H., A primal-dual interior point method for the max-min eigenvalue problem.SIAM Journal on Optimization, To appear. Accepted Aug/94.
Karisch, S., Rendl, F., Wolkowicz, H., and Zhao, Q. (1995), Quadratic Lagrangian relaxation for the quadratic assignment problem. Research report, University of Waterloo, Waterloo, Ontario, In progress.
Körner, F. (1988), A tight bound for the boolean quadratic optimization problem and its use in a branch and bound algorithm.Optimization 19:711?721.
Körner, F. (1992), Remarks on a difficult test problem for quadratic boolean programming.Optimization 26:355?357.
Lovász, L. (1979), On the Shannon capacity of a graph.IEEE Transactions on Information Theory 25:1?7.
Lovász, L. and Schrijver, A. (1991), Cones of matrices and set-functions and 0?1 optimization.SIAM Journal on Optimization 1(2):166?190.
Luenberger, D.G. (1984),Linear and Nonlinear Programming, Reading. Addison-Wesley, Massachusetts, second edition.
Moreé, J.J. and Sorensen, D.C. (1983), Computing a trust region step.SIAM J. Sci. Statist. Comput 4:553?572.
Pardalos, P., Rendl, F., and Wolkowicz, H. (1994), The quadratic assignment problem: A survey and recent developments. InProceedings of the DIMACS Workshop on Quadratic Assignment Problems, volume 16 ofDIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 1?41. American Mathematical Society.
Poljak, S. and Wolkowicz, H., Convex relaxations of 0?1 quadratic programming.Annals of Operations Research. To appear.
Rendl, F. and Wolkowicz, H., A projection technique for partitioning the nodes of a graph.Annals of Operations Research. To appear in the special issue of APMOD93.
Schrijver, A. (1979), A comparison of the Delsarte and Lovász bounds.IEEE Trans. Infor. Theory, IT-25:425?429.
Stern, R. and Wolkowicz, H., Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations.SIAM J. Optimization, To appear. Accepted June/93.
Wolkowicz, H. (1981), Some applications of optimization in matrix theory.Linear Algebra and its Applications 40:101?118.
Wolkowicz, H., Multiple indefinite trust region problems and semidefinite programming. Research report, University of Waterloo, 1994. In progress.