Enhancing RLT-based relaxations for polynomial programming problems via a new class of v-semidefinite cuts

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

Full description

Saved in:
Bibliographic Details
Main Authors: Sherali, Hanif D., Dalkiran, Evrim., Desai, Jitamitra.
Other Authors: School of Mechanical and Aerospace Engineering
Format: Article
Language:English
Published: 2013
Online Access:https://hdl.handle.net/10356/85662
http://hdl.handle.net/10220/13111
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-85662
record_format dspace
spelling sg-ntu-dr.10356-856622020-03-07T13:19:25Z Enhancing RLT-based relaxations for polynomial programming problems via a new class of v-semidefinite cuts Sherali, Hanif D. Dalkiran, Evrim. Desai, Jitamitra. School of Mechanical and Aerospace Engineering 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. 2013-08-15T06:51:12Z 2019-12-06T16:08:02Z 2013-08-15T06:51:12Z 2019-12-06T16:08:02Z 2011 2011 Journal Article 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. https://hdl.handle.net/10356/85662 http://hdl.handle.net/10220/13111 10.1007/s10589-011-9425-z en Computational optimization and applications
institution Nanyang Technological University
building NTU Library
country Singapore
collection DR-NTU
language English
description 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.
author2 School of Mechanical and Aerospace Engineering
author_facet School of Mechanical and Aerospace Engineering
Sherali, Hanif D.
Dalkiran, Evrim.
Desai, Jitamitra.
format Article
author Sherali, Hanif D.
Dalkiran, Evrim.
Desai, Jitamitra.
spellingShingle Sherali, Hanif D.
Dalkiran, Evrim.
Desai, Jitamitra.
Enhancing RLT-based relaxations for polynomial programming problems via a new class of v-semidefinite cuts
author_sort Sherali, Hanif D.
title Enhancing RLT-based relaxations for polynomial programming problems via a new class of v-semidefinite cuts
title_short Enhancing RLT-based relaxations for polynomial programming problems via a new class of v-semidefinite cuts
title_full Enhancing RLT-based relaxations for polynomial programming problems via a new class of v-semidefinite cuts
title_fullStr Enhancing RLT-based relaxations for polynomial programming problems via a new class of v-semidefinite cuts
title_full_unstemmed Enhancing RLT-based relaxations for polynomial programming problems via a new class of v-semidefinite cuts
title_sort enhancing rlt-based relaxations for polynomial programming problems via a new class of v-semidefinite cuts
publishDate 2013
url https://hdl.handle.net/10356/85662
http://hdl.handle.net/10220/13111
_version_ 1681035311426043904