### 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 language | English |
---|---|

Title of host publication | Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization |

Editors | O. Günlük, G.J. Woeginger |

Place of Publication | Heidelberg |

Publisher | Springer Verlag |

Pages | 207-222 |

Volume | 6655 |

Publication status | Published - 2011 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 6655 |

## 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/