An iterative scheme for valid polynomial inequality generation in binary polynomial programming

B. Ghaddar, J.C. Vera, M.F. Anjos

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

4 Citations (Scopus)

Abstract

Semidefinite programming has been used successfully to build hierarchies of convex relaxations to approximate polynomial programs. This approach rapidly becomes computationally expensive and is often tractable only for problems of small sizes. We propose an iterative scheme that improves the semidefinite relaxations without incurring exponential growth in their size. The key ingredient is a dynamic scheme for generating valid polynomial inequalities for general polynomial programs. These valid inequalities are then used to construct better approximations of the original problem. As a result, the proposed scheme is in principle scalable to large general combinatorial optimization problems. For binary polynomial programs, we prove that the proposed scheme converges to the global optimal solution for interesting cases of the initial approximation of the problem. We also present examples illustrating the computational behaviour of the scheme and compare it to other methods in the literature.
Original languageEnglish
Title of host publicationProceedings of the 15th Conference on Integer Programming and Combinatorial Optimization
EditorsO. Günlük, G.J. Woeginger
Place of PublicationHeidelberg
PublisherSpringer Verlag
Pages207-222
Volume6655
Publication statusPublished - 2011

Publication series

NameLecture Notes in Computer Science
Volume6655

Fingerprint Dive into the research topics of 'An iterative scheme for valid polynomial inequality generation in binary polynomial programming'. Together they form a unique fingerprint.

  • Cite this

    Ghaddar, B., Vera, J. C., & Anjos, M. F. (2011). An iterative scheme for valid polynomial inequality generation in binary polynomial programming. In O. Günlük, & G. J. Woeginger (Eds.), Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization (Vol. 6655, pp. 207-222). (Lecture Notes in Computer Science; Vol. 6655). Springer Verlag. http://www.springerlink.com/content/pm8320725x3615j1/