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

A reformulation-linearization technique for optimization over simplices

MATHEMATICAL PROGRAMMING 2023年第1期197卷 427-447页

作者： Selvi, Aras den Hertog, Dick Wiesemann, Wolfram Imperial Coll London Imperial Coll Business Sch South Kensington Campus London SW7 2AZ England Univ Amsterdam Amsterdam Business Sch NL-1018 TV Amsterdam Netherlands

We study non-convex optimization problems over simplices. We show that for a large class of objective functions, the convex approximation obtained from the reformulation-linearization technique (RLT) admits optimal solutions that exhibit a sparsity pattern. This characteristic of the optimal solutions allows us to conclude that (i) a linear matrix inequality constraint, which is often added to tighten the relaxation, is vacuously satisfied and can thus be omitted, and (ii) the number of decision variables in the RLT relaxation can be reduced from O(n(2)) to O(n). Taken together, both observations allow us to reduce computation times by up to several orders of magnitude. Our results can be specialized to indefinite quadratic optimization problems over simplices and extended to non-convex optimization problems over the Cartesian product of two simplices as well as specific classes of polyhedral and non-convex feasible regions. Our numerical experiments illustrate the promising performance of the proposed framework.

关键词： reformulation-linearization technique Global optimization Semidefinite optimization

来源：评论

学校读者我要写书评

暂无评论

Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming

引用

JOURNAL OF GLOBAL OPTIMIZATION 2009年第2-3期43卷 471-484页

作者： Anstreicher, Kurt M. Univ Iowa Dept Management Sci Tippie Coll Business Iowa City IA 52242 USA

We consider relaxations for nonconvex quadratically constrained quadratic programming (QCQP) based on semidefinite programming (SDP) and the reformulation-linearization technique (RLT). From a theoretical standpoint we show that the addition of a semidefiniteness condition removes a substantial portion of the feasible region corresponding to product terms in the RLT relaxation. On test problems we show that the use of SDP and RLT constraints together can produce bounds that are substantially better than either technique used alone. For highly symmetric problems we also consider the effect of symmetry-breaking based on tightened bounds on variables and/or order constraints.

关键词： Semidefinite programming reformulation-linearization technique Quadratically constrained quadratic programming

来源：评论

学校读者我要写书评

暂无评论

A level-2 reformulation-linearization technique bound for the quadratic assignment problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2007年第3期180卷 983-996页

作者： Adams, Warren P. Guignard, Monique Hahn, Peter M. Hightower, William L. Clemson Univ Dept Math Sci Clemson SC 29634 USA Univ Penn OPIM Dept Philadelphia PA 19104 USA Univ Penn Dept Elect & Syst Engn Philadelphia PA 19104 USA High Point Univ High Point NC 27262 USA

This paper studies polyhedral methods for the quadratic assignment problem. Bounds on the objective value are obtained using mixed 0-1 linear representations that result from a reformulation-linearization technique (rlt). The rlt provides different "levels" of representations that give increasing strength. Prior studies have shown that even the weakest level-1 form yields very tight bounds, which in turn lead to improved solution methodologies. This paper focuses on implementing level-2. We compare level-2 with level-1 and other bounding mechanisms, in terms of both overall strength and ease of computation. In so doing, we extend earlier work on level-1 by implementing a Lagrangian relaxation that exploits block-diagonal structure present in the constraints. The bounds are embedded within an enumerative algorithm to devise an exact solution strategy. Our computer results are notable, exhibiting a dramatic reduction in nodes examined in the enumerative phase, and allowing for the exact solution of large instances. (c) 2006 Elsevier B.V. All rights reserved.

关键词： combinatorial optimization assignment branch and bound quadratic assignment problem reformulation-linearization technique

来源：评论

学校读者我要写书评

暂无评论

Enumeration approach for linear complementarity problems based on a reformulation-linearization technique

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1998年第2期99卷 481-507页

作者： Sherali, HD Krishnamurthy, RS Al-Khayyal, FA Virginia Polytech Inst & State Univ Dept Ind & Syst Engn Blacksburg VA 24061 USA Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA SABRE Technol Solut Ft Worth TX USA

In this paper, we consider the linear complementarity problem (LCP) and present a global optimization algorithm based on an application of the reformulation-linearization technique (RLT). The matrix M associated with the LCP is not assumed to possess any special structure. In this approach, the LCP is formulated first as a mixed-integer 0-1 bilinear programming problem. The RLT scheme is then used to derive a new equivalent mixed-integer linear programming formulation of the LCP. An implicit enumeration scheme is developed that uses Lagrangian relaxation, strongest surrogate and strengthened cutting planes, and a heuristic, designed to exploit the strength of the resulting linearization. Computational experience on various test problems is presented.

关键词： linear complementarity problem bilinear programming implicit enumeration Lagrangian relaxation reformulation-linearization technique

来源：评论

学校读者我要写书评

暂无评论

A revised reformulation-linearization technique for the quadratic assignment problem

引用

DISCRETE OPTIMIZATION 2014年 14卷 97-103页

作者： Rostami, Borzou Malucelli, Federico Politecn Milan Dipartimento Elettron Informaz & Bioingn I-20133 Milan Italy

The reformulation linearization technique (RLT) applied to the Quadratic Assignment Problem yields mixed 0-1 programming problems whose linear relaxations provide a strong bound on the objective value. Nevertheless, in the high level RLT representations the computation requires much effort. In this paper we propose a new compact reformulation for each level of the RLT representation exploiting the structure of the problem. Computational results on some benchmark instances indicate the potential of the new RLT representations as the level of the RLT increases. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Quadratic assignment problem reformulation-linearization technique Lower bound Dual ascent

来源：评论

学校读者我要写书评

暂无评论

A reformulation-linearization technique (RLT) for semi-infinite and convex programs under mixed 0-1 and general discrete restrictions

引用

DISCRETE APPLIED MATHEMATICS 2009年第6期157卷 1319-1333页

作者： Sherali, Hanif D. Adams, Warren P. Virginia Polytech Inst & State Univ Grado Dept Ind & Syst Engn 0118 Blacksburg VA 24061 USA Clemson Univ Dept Math Sci Clemson SC 29634 USA

The reformulation-linearization technique (RLT) provides a hierarchy of relaxations spanning the spectrum from the continuous relaxation to the convex hull representation for linear 0-1 mixed-integer and general mixed-discrete programs. We show in this paper that this result holds identically for semi-infinite programs of this type. As a consequence, we extend the RLT methodology to describe a construct for generating a hierarchy of relaxations leading to the convex hull representation for bounded 0-1 mixed-integer and general mixed-discrete convex programs, using an equivalent semi-infinite linearized representation for such problems as an intermediate stepping stone in the analysis. For particular use in practice, we provide specialized forms of the resulting first-level RLT formulation for such mixed 0-1 and discrete convex programs, and illustrate these forms through two examples. (C) 2008 Elsevier B.V. All rights reserved.

关键词： reformulation-linearization technique RLT Semi-infinite programs Convex discrete programs Mixed 0-1 programs Mixed-discrete programs

来源：评论

学校读者我要写书评

暂无评论

Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the reformulation-linearization technique

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2010年第1期206卷 54-63页

作者： Pessoa, Artur Alves Hahn, Peter M. Guignard, Monique Zhu, Yi-Rong Univ Penn Wharton Sch Philadelphia PA 19104 USA Univ Fed Fluminense Dept Prod Engn BR-24220000 Niteroi RJ Brazil Elder Res Inc Charlottesville VA 22903 USA

In this paper, we propose two exact algorithms for the GQAP (generalized quadratic assignment problem). In this problem, given M facilities and N locations, the facility space requirements, the location available space, the facility installation costs, the flows between facilities, and the distance costs between locations, one must assign each facility to exactly one location so that each location has sufficient space for all facilities assigned to it and the sum of the products of the facility flows by the corresponding distance costs plus the sum of the installation costs is minimized. This problem generalizes the well-known quadratic assignment problem (QAP). Both exact algorithms combine a previously proposed branch-and-bound scheme with a new Lagrangean relaxation procedure over a known RLT (reformulation-linearization technique) formulation. We also apply transformational lower bounding techniques to improve the performance of the new procedure. We report detailed experimental results where 19 out of 21 instances with up to 35 facilities are solved in up to a few days of running time. Six of these instances were open. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Quadratic assignment Lagrangean decomposition reformulation-linearization technique Branch-and-bound

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A new reformulation-linearization technique for bilinear programming problems

引用

Journal of Global Optimization 1992年第4期2卷 379-410页

作者： Sherali, Hanif D. Alameddine, Amine Department of Industrial and Systems Engineering Virginia Polytechnic Institute and State University Blacksburg 24061-0118 VA United States

This paper is concerned with the development of an algorithm for general bilinear programming problems. Such problems find numerous applications in economics and game theory, location theory, nonlinear multi-commodity network flows, dynamic assignment and production, and various risk management problems. The proposed approach develops a new reformulation-linearization technique (RLT) for this problem, and imbeds it within a provably convergent branch-and-bound algorithm. The method first reformulates the problem by constructing a set of nonnegative variable factors using the problem constraints, and suitably multiplies combinations of these factors with the original problem constraints to generate additional valid nonlinear constraints. The resulting nonlinear program is subsequently linearized by defining a new set of variables, one for each nonlinear term. This "RLT" process yields a linear programming problem whose optimal value provides a tight lower bound on the optimal value to the bilinear programming problem. Various implementation schemes and constraint generation procedures are investigated for the purpose of further tightening the resulting linearization. The lower bound thus produced theoretically dominates, and practically is far tighter, than that obtained by using convex envelopes over hyper-rectangles. In fact, for some special cases, this process is shown to yield an exact linear programming representation. For the associated branch-and-bound algorithm, various admissible branching schemes are discussed, including one in which branching is performed by partitioning the intervals for only one set of variables x or y, whichever are fewer in number. Computational experience is provided to demonstrate the viability of the algorithm. For a large number of test problems from the literature, the initial bounding linear program itself solves the underlying bilinear programming problem. © 1992 Kluwer Academic Publishers.

关键词： Bilinear programming branch-and-bound global optimization nonconvex programming reformulation-linearization technique

来源：评论

学校读者我要写书评

暂无评论

An reformulation-linearization technique-based Approach to Joint Topology Design and Load Balancing in FSO Networks

An Reformulation-Linearization Technique-based Approach to J...

引用

IEEE Global Telecommunications Conference (GLOBECOM 2010)

作者： Son, In Keun Mao, Shiwen Auburn Univ Dept Elect & Comp Engn Auburn AL 36849 USA

ISBN: (纸本)9781424456383

Free space optical networks have emerged as a viable technology for broadband wireless backbone networks. In this paper, we investigate the challenging problem of joint topology design and load balancing in FSO networks. We consider FSO link characteristics, cost constraints, traffic characteristics, traffic demand, and QoS requirements in the formulation, along with various objective functions including network-wide average load and delay. We apply the reformulation-linearization technique (RLT) to obtain linear programming (LP) relaxations of the original complex problem, and then incorporate the LP relaxations into a branch-and-bound framework. The proposed algorithm can produce highly competitive solutions with performance guarantees in the form of bounded optimality gap. The RLT-based branch-and-bound algorithm is evaluated with extensive simulations and is shown to be highly suitable for jointly optimizing topology and load balancing in FSO networks.

关键词： FSO networks QoS free space optical networks joint topology design linear programming linear programming relaxations load balancing optical communication optical links reformulation-linearization technique

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：