Reduced RLT representations for nonconvex polynomial programming problems |
| |
Authors: | Hanif D Sherali Evrim Dalkiran Leo Liberti |
| |
Institution: | 1.Grado Department of Industrial and Systems Engineering,Virginia Tech,Blacksburg,USA;2.CNRS LIX, école Polytechnique,Palaiseau,France |
| |
Abstract: | This paper explores equivalent, reduced size Reformulation-Linearization Technique (RLT)-based formulations for polynomial
programming problems. Utilizing a basis partitioning scheme for an embedded linear equality subsystem, we show that a strict
subset of RLT defining equalities imply the remaining ones. Applying this result, we derive significantly reduced RLT representations
and develop certain coherent associated branching rules that assure convergence to a global optimum, along with static as
well as dynamic basis selection strategies to implement the proposed procedure. In addition, we enhance the RLT relaxations
with v-semidefinite cuts, which are empirically shown to further improve the relative performance of the reduced RLT method over
the usual RLT approach. We present computational results for randomly generated instances to test the different proposed reduction
strategies and to demonstrate the improvement in overall computational effort when such reduced RLT mechanisms are employed. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|