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

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

来源：评论

学校读者我要写书评

暂无评论

Integer programming approach and application of reformulation-linearization technique to liver exchange problem

引用

EXPERT SYSTEMS WITH APPLICATIONS 2021年 185卷 115599-115599页

作者： Yuh, Junsang Eun, Joonyup Cheong, Taesu Korea Univ Sch Ind & Management Engn Seoul 02841 South Korea Korea Univ Grad Sch Management Technol Seoul 02841 South Korea

Organ transplants are essential for many end-stage organic disease patients. Unfortunately, because of medical or biological incompatibilities, not all donors can donate to their intended recipients. These incompatibilities can be overcome by organ exchange programs, which find new compatible donor-patient pairs by exchanging donors between patients. Organ exchange programs have become prevalent in the last decade for kidneys, and liver exchanges have also been increasing steadily. However, despite the growing number of liver exchanges, since the procedure is relatively new, there is a lack of studies attempting to optimize exchange plans through mathematical programming. This paper develops a new integer programming model for liver exchange programs that takes into account the unique characteristics of liver transplantation. In addition, a new enhanced model is obtained by applying the reformulation-linearization technique (RLT), which provides tight linear programming (LP) relaxation bounds and is computationally efficient.

关键词： OR in health services Integer programming Liver exchange program 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

来源：评论

学校读者我要写书评

暂无评论

On Tractable Convex Relaxations of Standard Quadratic Optimization Problems under Sparsity Constraints

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2025年第3期204卷 1-36页

作者： Bomze, Immanuel Peng, Bo Qiu, Yuzhou Yildirim, E. Alper Univ Vienna Fac Math & Res Network Data Sci Oskar Morgenstern Pl 1 A-1090 Vienna Austria Univ Vienna VGSCO Oskar Morgenstern Pl 1 A-1090 Vienna Austria Univ Vienna ISOR Oskar Morgenstern Pl 1 A-1090 Vienna Austria Univ Edinburgh Sch Math Peter Guthrie Tait Rd Edinburgh EH9 3FD Scotland

Standard quadratic optimization problems (StQPs) provide a versatile modelling tool in various applications. In this paper, we consider StQPs with a hard sparsity constraint, referred to as sparse StQPs. We focus on various tractable convex relaxations of sparse StQPs arising from a mixed-binary quadratic formulation, namely, the linear optimization relaxation given by the reformulation-linearization technique, the Shor relaxation, and the relaxation resulting from their combination. We establish several structural properties of these relaxations in relation to the corresponding relaxations of StQPs without any sparsity constraints, and pay particular attention to the rank-one feasible solutions retained by these relaxations. We then utilize these relations to establish several results about the quality of the lower bounds arising from different relaxations. We also present several conditions that ensure the exactness of each relaxation.

关键词： Standard quadratic optimization problems Sparsity Mixed-integer quadratic optimization reformulation-linearization technique Shor relaxation

来源：评论

学校读者我要写书评

暂无评论

Polynomial Optimization: Tightening RLT-Based Branch-and-Bound Schemes with Conic Constraints

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2025年第1期204卷 1-34页

作者： Gonzalez-Rodriguez, Brais Alvite-Pazo, Raul Alvite-Pazo, Samuel Ghaddar, Bissan Gonzalez-Diaz, Julio Univ Vigo Ourense Dept Stat & Operat Res Orense Galicia Spain CITMAga Galician Ctr Math Res & Technol Santiago De Compostela Galicia Spain Western Univ London Ivey Business Sch London ON Canada Univ Santiago De Compostela Dept Stat Math Anal & Optimizat Santiago De Compostela Galicia Spain Univ Santiago de Compostela MODESTYA Res Grp Santiago De Compostela Galicia Spain

This paper explores the potential of (nonlinear) conic constraints to tighten the relaxations of spatial branch-and-bound algorithms. More precisely, we contribute to the literature on the use of conic optimization for the efficient solution, to global optimality, of nonconvex polynomial optimization problems. Taking as baseline an RLT-based algorithm, we present different families of well-known conic-driven constraints: linear SDP-cuts, second-order cone constraints, and SDP constraints. We integrate these constraints in the baseline algorithm and present a thorough computational study to assess their performance, both with respect to each other and with respect to the standard RLT relaxations for polynomial optimization problems. Our main finding is that the different variants of nonlinear constraints (second-order cone and semidefinite) are the best performing ones in around 50%\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$50\%$$\end{document} of the instances in widely used test sets. Additionally, we discuss how one can benefit from the use of machine learning to decide on the most suitable constraints to add to a given instance. The computational results show that the machine learning approach significantly outperforms each of the individual approaches.

关键词： Global optimization reformulation-linearization technique Polynomial programming Conic optimization Machine learning

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Efficient separation of RLT cuts for implicit and explicit bilinear terms

引用

MATHEMATICAL PROGRAMMING 2024年第1期210卷 47-74页

作者： Bestuzheva, Ksenia Gleixner, Ambros Achterberg, Tobias Zuse Inst Berlin AI Soc Sci & Technol Takustr 7 D-14195 Berlin Germany HTW Berlin D-10313 Berlin Germany Gurobi GmbH Sandstr 104 D-40789 Monheim Germany

The reformulation-linearization technique (RLT) is a prominent approach to constructing tight linear relaxations of non-convex continuous and mixed-integer optimization problems. The goal of this paper is to extend the applicability and improve the performance of RLT for bilinear product relations. First, we present a method for detecting bilinear product relations implicitly contained in mixed-integer linear programs, which is based on analyzing linear constraints with binary variables, thus enabling the application of bilinear RLT to a new class of problems. Strategies for filtering product relations are discussed and tested. Our second contribution addresses the high computational cost of RLT cut separation, which presents one of the major difficulties in applying RLT efficiently in practice. We propose a new RLT cutting plane separation algorithm which identifies combinations of linear constraints and bound factors that are expected to yield an inequality that is violated by the current relaxation solution. This algorithm is applicable to RLT cuts generated for all types of bilinear terms, including but not limited to the detected implicit products. A detailed computational study based on independent implementations in two solvers evaluates the performance impact of the proposed methods.

关键词： reformulation-linearization technique Bilinear terms Cutting planes Mixed-integer programming

来源：评论

学校读者我要写书评

暂无评论

On exact and inexact RLT and SDP-RLT relaxations of quadratic programs with box constraints

引用

JOURNAL OF GLOBAL OPTIMIZATION 2024年第2期90卷 293-322页

作者： Qiu, Yuzhou Yildirim, E. Alper Univ Edinburgh Sch Math Peter Guthrie Tait Rd Edinburgh EH9 3FD Scotland

Quadratic programs with box constraints involve minimizing a possibly nonconvex quadratic function subject to lower and upper bounds on each variable. This is a well-known NP-hard problem that frequently arises in various applications. We focus on two convex relaxations, namely the reformulation-linearization technique (RLT) relaxation and the SDP-RLT relaxation obtained by combining the Shor relaxation with the RLT relaxation. Both relaxations yield lower bounds on the optimal value of a quadratic program with box constraints. We show that each component of each vertex of the RLT relaxation lies in the set { 0 , 1 2 , 1 } \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{0,\frac{1}{2},1\}$$\end{document} . We present complete algebraic descriptions of the set of instances that admit exact RLT relaxations as well as those that admit exact SDP-RLT relaxations. We show that our descriptions can be converted into algorithms for efficiently constructing instances with (1) exact RLT relaxations, (2) inexact RLT relaxations, (3) exact SDP-RLT relaxations, and (4) exact SDP-RLT but inexact RLT relaxations. Our preliminary computational experiments illustrate that our algorithms are capable of generating computationally challenging instances for state-of-the-art solvers.

关键词： Quadratic programming with box constraints reformulation-linearization technique Semidefinite relaxation Convex underestimator

来源：评论

学校读者我要写书评

暂无评论

New bounds for nonconvex quadratically constrained quadratic programming

引用

JOURNAL OF GLOBAL OPTIMIZATION 2023年第3期85卷 595-613页

作者： Zamani, Moslem Tilburg Univ Dept Econometr & Operat Res Tilburg Netherlands

In this paper, we study some bounds for nonconvex quadratically constrained quadratic programs (QCQPs). We propose two types of bounds for QCQPs, quadratic and cubic bounds. We use affine functions as Lagrange multipliers for quadratic bounds. We demonstrate that most semidefinite relaxations can be obtained as the dual of a quadratic bound. In addition, we study bounds obtained by changing the ground set. For cubic bounds, in addition to affine multipliers we employ quadratic functions. We provide a comparison between the proposed cubic bound and typical bounds for standard quadratic programs. Moreover, we report comparison results of some quadratic and cubic bounds.

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

来源：评论

学校读者我要写书评

暂无评论

Disjoint Bilinear Optimization: A Two-Stage Robust Optimization Perspective

引用

INFORMS JOURNAL ON COMPUTING 2022年第5期34卷 2410-2427页

作者： Zhen, Jianzhe Marandi, Ahmadreza de Moor, Danique den Hertog, Dick Vandenberghe, Lieven Swiss Fed Inst Technol Dept Informat Technol & Elect Engn CH-8092 Zurich Switzerland Eindhoven Univ Technol Dept Ind Engn & Innovat Sci NL-5600 MB Eindhoven North Brabant Netherlands Univ Amsterdam Fac Econ & Business Sect Business Analyt NL-1012 WX Amsterdam Netherlands Univ Calif Los Angeles Elect & Comp Engn Dept Los Angeles CA 90095 USA

In this paper, we focus on a subclass of quadratic optimization problems, that is, disjoint bilinear optimization problems. We first show that disjoint bilinear optimization problems can be cast as two-stage robust linear optimization problems with fixed-recourse and right-hand-side uncertainty, which enables us to apply robust optimization techniques to solve the resulting problems. To this end, a solution scheme based on a blending of three popular robust optimization techniques is proposed. For disjoint bilinear optimization problems with a polyhedral feasible region and a general convex feasible region, we show that, under mild regularity conditions, the convex relaxations of the original bilinear formulation and its two-stage robust reformulation obtained from a reformulation-linearization-based technique and linear decision rules, respectively, are equivalent. For generic bilinear optimization problems, the convex relaxations from the reformulation-linearization-based technique are generally tighter than the one from linear decision rules. Numerical experiments on bimatrix games, synthetic disjoint bilinear problem instances, and convex maximization problems demonstrate the efficiency and effectiveness of the proposed solution scheme.

关键词： bilinear optimization linear decision rules reformulation-linearization technique mixed integer convex optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：