检索结果-内蒙古大学图书馆

Theoretical filtering of RLT bound-factor constraints for solving polynomial programming problems to global optimality

引用

JOURNAL OF GLOBAL OPTIMIZATION 2013年第4期57卷 1147-1172页

作者： Dalkiran, Evrim Sherali, Hanif D. Wayne State Univ Dept Ind & Syst Engn Detroit MI 48202 USA Virginia Tech Grado Dept Ind & Syst Engn Blacksburg VA 24061 USA

In this paper, we propose two sets of theoretically filtered bound-factor constraints for constructing reformulation-linearization technique (RLT)-based linear programming (LP) relaxations for solving polynomial programming problems. We establish related theoretical results for convergence to a global optimum for these reduced sized relaxations, and provide insights into their relative sizes and tightness. Extensive computational results are provided to demonstrate the relative effectiveness of the proposed theoretical filtering strategies in comparison to the standard RLT and a prior heuristic filtering technique using problems from the literature as well as randomly generated test cases.

关键词： Reformulation-linearization technique (RLT) Filtering strategies polynomial programming Branch-and-bound

来源：评论

学校读者我要写书评

暂无评论

A dynamic inequality generation scheme for polynomial programming

引用

MATHEMATICAL programming 2016年第1-2期156卷 21-57页

作者： Ghaddar, Bissan Vera, Juan C. Anjos, Miguel F. IBM Res Corp Dublin Technol CampusDamastown Ind PkMulhuddart Dublin Ireland Tilburg Univ Tilburg Sch Econ & Management NL-5000 LE Tilburg Netherlands Gerad Discrete Nonlinear Optimizat Engn Montreal PQ H3C 3A7 Canada Ecole Polytech Montreal PQ H3C 3A7 Canada

Hierarchies of semidefinite programs have been used to approximate or even solve polynomial programs. This approach rapidly becomes computationally expensive and is often tractable only for problems of small size. In this paper, we propose a dynamic inequality generation scheme to generate valid polynomial inequalities for general polynomial programs. When used iteratively, this scheme improves the bounds without incurring an exponential growth in the size of the relaxation. As a result, the proposed scheme is in principle scalable to large general polynomial programming problems. When all the variables of the problem are non-negative or when all the variables are binary, the general algorithm is specialized to a more efficient algorithm. In the case of binary polynomial programs, we show special cases for which the proposed scheme converges to the global optimal solution. We also present several examples illustrating the computational behavior of the scheme and provide comparisons with Lasserre's approach and, for the binary linear case, with the lift-and-project method of Balas, Ceria, and Cornu,jols.

关键词： polynomial programming Binary polynomial programming Semidefinite programming Inequality generation

来源：评论

学校读者我要写书评

暂无评论

New reformulation linearization convexification relaxations for univariate and multivariate polynomial programming problems

引用

OPERATIONS RESEARCH LETTERS 1997年第1期21卷 1-9页

作者： Sherali, HD Tuncbilek, CH Virginia Polytech Inst & State Univ Dept Ind & Syst Engn Blacksburg VA 24061 USA

This paper is concerned with the global optimization of polynomial programming problems of the type that arise in various location allocation, chemical process, and engineering design contexts. For such problems, we have previously presented a generic reformulation-linearization technique (RLT) to obtain global optimal solutions. We now introduce several new classes of constraints for both univariate and multivariate versions of this problem, including certain simple convex variable bounding types of restrictions that can be used to augment the basic (linear) RLT relaxation in order to yield tighter lower bounds. A constraint selection strategy is also developed to predict and generate only a useful subset of these constraints, so that the size of the resulting relaxation remains manageable. These relaxations are embedded within a globally convergent branch-and-bound algorithm that additionally incorporates certain range-reduction strategies and a new branching variable selection procedure. Computational results using various chemical process, pooling, and engineering design problems from the literature are also presented to demonstrate the viability of the proposed approach. (C) 1997 Elsevier Science B.V.

关键词： polynomial programming reformulation-linearization technique (RLT) reformulation-convexification approach nonconvex programming global optimization

来源：评论

学校读者我要写书评

暂无评论

Exploiting equalities in polynomial programming

引用

OPERATIONS RESEARCH LETTERS 2008年第2期36卷 223-228页

作者： Pena, Javier F. Vera, Juan C. Zuluaga, Luis F. Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15232 USA Carnegie Mellon Univ Mellon Coll Sci Pittsburgh PA 15213 USA Univ New Brunswick Fac Business Adm Fredericton NB E3B 5A3 Canada

We propose a novel approach for solving polynomial programs over compact domains with equality constraints. By means of a genetic transformation, we show that existing solution schemes for the, typically simpler, problem without equalities can be used to address the problem with equalities. (C) 2007 Elsevier B.V. All rights reserved.

关键词： polynomial programming 0-1 programming stable set problem LMI approximations

来源：评论

学校读者我要写书评

暂无评论

Mixed integer polynomial programming

引用

COMPUTERS & CHEMICAL ENGINEERING 2015年 72卷 387-394页

作者： Dua, Vivek UCL Ctr Proc Syst Engn Dept Chem Engn London WC1E 7JE England

The mixed integer polynomial programming problem is reformulated as a multi-parametric programming problem by relaxing integer variables as continuous variables and then treating them as parameters. The optimality conditions for the resulting parametric programming problem are given by a set of simultaneous parametric polynomial equations which are solved analytically to give the parametric optimal solution as a function of the relaxed integer variables. Evaluation of the parametric optimal solution for integer variables fixed at their integer values followed by screening of the evaluated solutions gives the optimal solutions. (C) 2014 The Author. Published by Elsevier Ltd. This is an open access article under the CC BY-NC-ND license

关键词： Mixed integer programming polynomial programming Nonlinear inversion Multi parametric programming

来源：评论

学校读者我要写书评

暂无评论

Comparison of two reformulation-linearization technique based linear programming relaxations for polynomial programming problems

引用

JOURNAL OF GLOBAL OPTIMIZATION 1997年第4期10卷 381-390页

作者： Sherali, HD Tuncbilek, CH VIRGINIA POLYTECH INST & STATE UNIV DEPT IND & SYST ENGNBLACKSBURGVA 24061

In this paper, we compare two strategies for constructing linear programming relaxations for polynomial programming problems using a Reformulation-Linearization Technique (RLT). RLT involves an automatic reformulation of the problem via the addition of certain nonlinear implied constraints that are generated by using the products of the simple bounding restrictions (among other products), and a subsequent linearization based on variable redefinitions. We prove that applying RLT directly to the original polynomial program produces a bound that dominates in the sense of being at least as tight as the value obtained when RLT is applied to the joint collection of all equivalent quadratic problems that could be constructed by recursively defining additional variables as suggested by Shor.

关键词： polynomial programming reformulation-linearization technique outer-approximations tight linear programming relaxations

来源：评论

学校读者我要写书评

暂无评论

RLT-POS: Reformulation-Linearization Technique-based optimization software for solving polynomial programming problems

引用

MATHEMATICAL programming COMPUTATION 2016年第3期8卷 337-375页

作者： Dalkiran, Evrim Sherali, Hanif D. Wayne State Univ Dept Ind & Syst Engn Detroit MI 48202 USA Virginia Tech Grado Dept Ind & Syst Engn Blacksburg VA 24061 USA

In this paper, we introduce a Reformulation-Linearization Technique-based open-source optimization software for solving polynomial programming problems (RLT-POS). We present algorithms and mechanisms that form the backbone of RLT-POS, including constraint filtering techniques, reduced RLT representations, and semidefinite cuts. When implemented individually, each model enhancement has been shown in previous papers to significantly improve the performance of the standard RLT procedure. However, the coordination between different model enhancement techniques becomes critical for an improved overall performance since special structures in the original formulation that work in favor of a particular technique might be lost after implementing some other model enhancement. More specifically, we discuss the coordination between (1) constraint elimination via filtering techniques and reduced RLT representations, and (2) semidefinite cuts for sparse problems. We present computational results using instances from the literature as well as randomly generated problems to demonstrate the improvement over a standard RLT implementation and to compare the performances of the software packages BARON, COUENNE, and SparsePOP with RLT-POS.

关键词： Reformulation-Linearization Technique (RLT) Open-source code Constraint filtering strategies Valid inequalities Reduced RLT representations polynomial programming

来源：评论

学校读者我要写书评

暂无评论

Processor Frequency Assignment in Three-Dimensional MPSoCs under Thermal Constraints by polynomial programming

Processor Frequency Assignment in Three-Dimensional MPSoCs u...

引用

IEEE Asia Pacific Conference on Circuits and Systems (APCCAS 2008)

作者： Zhao, Guangyao Kwan, Hing-Kit Lei, Chi-Un Wong, Ngai Univ Hong Kong Dept Elect & Elect Engn Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9781424423415

The operating frequency and the number of cores and active layers in Multi-Processor Systems-on-Chips (MPSoC) continue to increase, resulting in rising power density and operating temperature on the die. The increasing temperature reduces the system reliability and performance and increases the cooling cost. Most traditional MPSoC thermal optimization tools are based on two-dimensional planar IC thermal modeling, which is insufficient to capture the different thermal characteristics of three-dimensional(3D) MPSoCs and the behavior subjected to Dynamic Voltage and Frequency Scaling(DVFS). The recently proposed 3D optimization approach still ignores the mutual thermal impact between cores in the same layer, which reduces the precision of frequency assignment and may cause violation in the maximum temperature constraint. In this paper, we propose an approach based on polynomial programming that addresses the problem of processor frequency assignment in 3D MPSoC system, such that the total system performance can be maximized as well as the temperature and power constraints are met for all time instances. We also compare the performance improvement of DVFS in 3D MPSoC with that in 2D MPSoC, studying the importance of intra-layer temperature correlation in 3D MPSoC.

关键词： Multi-Processor Systems-on-Chips 3D thermal model polynomial programming frequency assignment

来源：评论

学校读者我要写书评

暂无评论

Optimality Conditions for Minimizers at Infinity in polynomial programming

引用

MATHEMATICS OF OPERATIONS RESEARCH 2019年第4期44卷 1381-1395页

作者： Tien-Son Pham Ton Duc Thang Univ Inst Computat Sci Div Computat Math & Engn Ho Chi Minh City 700000 Vietnam Ton Duc Thang Univ Fac Math & Stat Ho Chi Minh City 700000 Vietnam

In this paper we study necessary optimality conditions for the problem of minimizing a polynomial function over a set defined by polynomial inequalities. Assume that the problem is bounded below and has the Mangasarian-Fromovitz property at infinity. We first show that if the problem does not have an optimal solution, then a version at infinity of the Fritz John optimality conditions holds. From this we derive a version at infinity of the Karush-Kuhn-Tucker optimality conditions. As applications, we obtain a Frank-Wolfe type theorem which states that the optimal solution set of the problem is nonempty provided the objective function is "convenient." Finally, in the unconstrained case, we show that the optimal value of the problem is the smallest critical value of some polynomial. All the results are presented in terms of the Newton polyhedra of the polynomials defining the problem.

关键词： existence of minimizers Fermat theorem Frank-Wolfe theorem Fritz John optimality conditions Karush-Kuhn-Tucker optimality conditions Mangasarian-Fromovitz constraint qualification Newton polyhedron polynomial programming

来源：评论

学校读者我要写书评

暂无评论

Degree reduction techniques for polynomial optimization problems

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2025年第2期322卷 401-413页

作者： Gonzalez-Rodriguez, Brais Naoum-Sawaya, Joe Western Univ Ivey Business Sch 1255 Western Rd London ON N6G 4W1 Canada

This paper presents anew approach to quadrify a polynomial programming problem, i.e. reduce the polynomial program to a quadratic program, before solving it. The proposed approach, QUAD-RLT, exploits the Reformulation-Linearization Technique (RLT) structure to obtain smaller relaxations that can be solved faster and still provide high quality bounds. QUAD-RLT is compared to other quadrification techniques that have been previously discussed in the literature. The paper presents theoretical as well as computational results showing the advantage of QUAD-RLT compared to other quadrification techniques. Furthermore, rather than quadrifying a polynomial program, QUAD-RLT is generalized to reduce the degree of the polynomial to any degree. Computational results show that reducing the degree of the polynomial to a degree that is higher than two provides computational advantages in certain cases compared to fully quadrifying the problem. Finally, QUAD-RLT along with other quadrification/degree reduction schemes are implemented and made available in the freely available software RAPOSa.

关键词： Nonlinear programming Quadrification Degree reduction Reformulation-linearization technique polynomial programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：