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

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

Iterative Scheme
Programming
Valid
Binary
Polynomial
Semidefinite Relaxation
Convex Relaxation
Valid Inequalities
Semidefinite Programming
Exponential Growth
Approximation
Combinatorial Optimization Problem
Optimal Solution
Converge

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). Heidelberg: Springer Verlag.
Ghaddar, B. ; Vera, J.C. ; Anjos, M.F. / An iterative scheme for valid polynomial inequality generation in binary polynomial programming. Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization. editor / O. Günlük ; G.J. Woeginger. Vol. 6655 Heidelberg : Springer Verlag, 2011. pp. 207-222 (Lecture Notes in Computer Science).
@inproceedings{9166a40fccf64997831d9e0c2e205526,
title = "An iterative scheme for valid polynomial inequality generation in binary polynomial programming",
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.",
author = "B. Ghaddar and J.C. Vera and M.F. Anjos",
year = "2011",
language = "English",
volume = "6655",
series = "Lecture Notes in Computer Science",
publisher = "Springer Verlag",
pages = "207--222",
editor = "O. G{\"u}nl{\"u}k and G.J. Woeginger",
booktitle = "Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization",
address = "Germany",

}

Ghaddar, B, Vera, JC & Anjos, MF 2011, An iterative scheme for valid polynomial inequality generation in binary polynomial programming. in O Günlük & GJ Woeginger (eds), 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.

Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization. ed. / O. Günlük; G.J. Woeginger. Vol. 6655 Heidelberg : Springer Verlag, 2011. p. 207-222 (Lecture Notes in Computer Science; Vol. 6655).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-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 -

Ghaddar B, Vera JC, Anjos MF. An iterative scheme for valid polynomial inequality generation in binary polynomial programming. In Günlük O, Woeginger GJ, editors, Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization. Vol. 6655. Heidelberg: Springer Verlag. 2011. p. 207-222. (Lecture Notes in Computer Science).