### Abstract

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

### Cite this

*Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization*(Vol. 6655, pp. 207-222). (Lecture Notes in Computer Science; Vol. 6655). Heidelberg: Springer Verlag.

}

*Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization.*vol. 6655, Lecture Notes in Computer Science, vol. 6655, Springer Verlag, Heidelberg, pp. 207-222.

**An iterative scheme for valid polynomial inequality generation in binary polynomial programming.** / Ghaddar, B.; Vera, J.C.; Anjos, M.F.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

TY - GEN

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

AU - Ghaddar, B.

AU - Vera, J.C.

AU - Anjos, M.F.

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

M3 - Conference contribution

VL - 6655

T3 - Lecture Notes in Computer Science

SP - 207

EP - 222

BT - Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization

A2 - Günlük, O.

A2 - Woeginger, G.J.

PB - Springer Verlag

CY - Heidelberg

ER -