Please use this identifier to cite or link to this item:
https://hdl.handle.net/10356/85662
Title: | Enhancing RLT-based relaxations for polynomial programming problems via a new class of v-semidefinite cuts | Authors: | Sherali, Hanif D. Dalkiran, Evrim. Desai, Jitamitra. |
Issue Date: | 2011 | Source: | Sherali, H. D., Dalkiran, E.,& Desai, J. (2012). Enhancing RLT-based relaxations for polynomial programming problems via a new class of v-semidefinite cuts. Computational Optimization and Applications, 52(2), 483-506. | Series/Report no.: | Computational optimization and applications | Abstract: | In this paper, we propose to enhance Reformulation-Linearization Technique (RLT)-based linear programming (LP) relaxations for polynomial programming problems by developing cutting plane strategies using concepts derived from semidefinite programming. Given an RLT relaxation, we impose positive semidefiniteness on suitable dyadic variable-product matrices, and correspondingly derive implied semidefinite cuts. In the case of polynomial programs, there are several possible variants for selecting such particular variable-product matrices on which positive semidefiniteness restrictions can be imposed in order to derive implied valid inequalities. This leads to a new class of cutting planes that we call v-semidefinite cuts. We explore various strategies for generating such cuts, and exhibit their relative effectiveness towards tightening the RLT relaxations and solving the underlying polynomial programming problems in conjunction with an RLT-based branch-and-cut scheme, using a test-bed of problems from the literature as well as randomly generated instances. Our results demonstrate that these cutting planes achieve a significant tightening of the lower bound in contrast with using RLT as a stand-alone approach, thereby enabling a more robust algorithm with an appreciable reduction in the overall computational effort, even in comparison with the commercial software BARON and the polynomial programming problem solver GloptiPoly. | URI: | https://hdl.handle.net/10356/85662 http://hdl.handle.net/10220/13111 |
DOI: | 10.1007/s10589-011-9425-z | Schools: | School of Mechanical and Aerospace Engineering | Fulltext Permission: | none | Fulltext Availability: | No Fulltext |
Appears in Collections: | MAE Journal Articles |
SCOPUSTM
Citations
20
12
Updated on Mar 21, 2024
Web of ScienceTM
Citations
20
11
Updated on Oct 31, 2023
Page view(s) 50
526
Updated on Mar 29, 2024
Google ScholarTM
Check
Altmetric
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.