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

作者： Ganesan, Vikram Virginia Tech | University

The containership design problem involves optimizing a nonconvex objective function over a design space that is restricted by a set of constraints defined in terms of nonconvex functions. An application of standard nonlinear optimization methods to such a problem can at best attain a local optimum that need not be a global optimum. This thesis investigates the application of alternative modeling, approximation, and global optimization techniques for developing a multidisciplinary approach to the containership design problem. The problem involves five design variables, which prioritized according to their relative importance in the model are: design draft, depth at side, speed, overall length, and maximum beam. Five constraints are imposed on the design, viz., an equality constraint to enforce the balance between the weight and the displacement, a linear inequality constraint on the length to depth ratio that is implied by the lightship weight formulation for the design to be acceptable, an inequality constraint on the metacentric height to ensure that the design satisfies the Coast Guard wind heel criterion, an inequality on the freeboard to ensure the minimum required freeboard governed by the code of federal regulations for freeboard (46 CFR 42), and an inequality constraint on the rolling period to ensure that the design satisfies the minimum required rolling period criterion. The objective function employed is the required freight rate, expressed in dollars per metric ton per nautical mile in order to recover annualized construction and operational costs. The model also accommodates various practical issues in a manner suitable to improve its representability. For example, it takes into account the discrete container stowage issue. The carrying capacity (number of containers) is expressed as a continuous function of the principal dimensions by using a linear response surface fit that in turn makes the objective function continuous. The weight-displacement bala

关键词： reformulation-linearization technique Containership Design Problem. Global Optimization Thesis

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A polyhedral study of the generalized vertex packing problem

引用

MATHEMATICAL PROGRAMMING 2006年第3期107卷 367-390页

作者： Sherali, HD Smith, JC Virginia Polytech Inst & State Univ Dept Ind & Syst Engn 0118 Blacksburg VA 24061 USA Univ Arizona Dept Syst & Ind Engn Tucson AZ 85721 USA

The traditional vertex packing problem defined on an undirected graph identifies the largest weighted independent set of nodes, that is, a set of nodes whose induced subgraph contains no edges. In this paper, we examine a generalized vertex packing problem (GVP-k) in which k "violations" to the independent set restriction are permitted, whereby k edges may exist within the subgraph induced by the chosen set of nodes. A particular context in which such problems arise is in the national airspace planning model of Sherali, Smith, and Trani (2000), where a set of flight-plans need to be composed for various flights subject to conflict, workload, and equity considerations. The GVP-k structure arises in modeling the air-traffic control sector workload restrictions, which stipulate that for each sector and during each discretized time-slot, the number of aircraft conflicts that would need to be resolved should not exceed k, for some k >= N1. We derive several classes of facetial valid inequalities for GVP-k for certain specially structured subgraphs, identifying polynomial-sized convex hull representations for some of these cases. Related constraint generation routines are also developed, and some computational results are provided to demonstrate the efficacy of utilizing the proposed valid inequalities in solving GVP-k for different values of k.

关键词： integer programming vertex packing valid inequalities/cutting planes air-space management reformulation-linearization technique

来源：评论

学校读者我要写书评

暂无评论

Expectation and Chance-Constrained Models and Algorithms for Insuring Critical Paths

引用

MANAGEMENT SCIENCE 2010年第10期56卷 1794-1814页

作者： Shen, Siqian Smith, J. Cole Ahmed, Shabbir Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA

In this paper, we consider a class of two-stage stochastic optimization problems arising in the protection of vital arcs in a critical path network. A project is completed after a series of dependent tasks are all finished. We analyze a problem in which task finishing times are uncertain but can be insured a priori to mitigate potential delays. A decision maker must trade off costs incurred in insuring arcs with expected penalties associated with late project completion times, where lateness penalties are assumed to be lower semicontinuous nondecreasing functions of completion time. We provide decomposition strategies to solve this problem with respect to either convex or nonconvex penalty functions. In particular, for the nonconvex penalty case, we employ the reformulation-linearization technique to make the problem amenable to solution via Benders decomposition. We also consider a chance-constrained version of this problem, in which the probability of completing a project on time is sufficiently large. We demonstrate the computational efficacy of our approach by testing a set of size- and-complexity diversified problems, using the sample average approximation method to guide our scenario generation.

关键词： project management integer programming reformulation-linearization technique chance-constrained programming sample average approximation

来源：评论

学校读者我要写书评

暂无评论

A practical solution approach for the green vehicle routing problem

引用

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 2017年 104卷 97-112页

作者： Leggieri, Valeria Haouari, Mohamed Free Univ Bozen Bolzano Fac Sci & Technol Bolzano Italy Qatar Univ Mech & Ind Engn Dept Doha Qatar

Green vehicle routing (GVRP) is an active research area that is concerned with the development and analysis of distribution activities with eco-friendly vehicles. We propose a practical solution approach for the GVRP that uses a mixed-integer linear formulation and a reduction procedure. The newly formulation offers two significant advantages: compactness and flexibility. We provide empirical evidence that the formulation and the reduction procedure enable to derive optimal solutions for medium-sized instances using a general-purpose solver. We show that the proposed exact approach consistently outperforms a state-of-the-art branch-and-cut algorithm and constitutes an appealing and practical alternative for optimally solving GVRPs. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Green vehicle routing problem Compact mixed integer linear programming formulation reformulation-linearization technique Preprocessing procedures

来源：评论

学校读者我要写书评

暂无评论

Second order cone constrained convex relaxations for nonconvex quadratically constrained quadratic programming

引用

JOURNAL OF GLOBAL OPTIMIZATION 2019年第2期75卷 461-494页

作者： Jiang, Rujun Li, Duan Fudan Univ Sch Data Sci Shanghai Peoples R China City Univ Hong Kong Sch Data Sci Hong Kong Peoples R China

In this paper, we present new convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP) problems. While recent research has focused on strengthening convex relaxations of QCQP using the reformulation-linearization technique (RLT), the state-of-the-art methods lose their effectiveness when dealing with (multiple) nonconvex quadratic constraints in QCQP, except for direct lifting and linearization. In this research, we decompose and relax each nonconvex constraint to two second order cone (SOC) constraints and then linearize the products of the SOC constraints and linear constraints to construct some new effective valid constraints. Moreover, we extend the reach of the RLT-like techniques for almost all different types of constraint-pairs (including valid inequalities by linearizing the product of a pair of SOC constraints, and the Hadamard product or the Kronecker product of two respective valid linear matrix inequalities), examine dominance relationships among different valid inequalities, and explore almost all possibilities of gaining benefits from generating valid constraints. We also successfully demonstrate that applying RLT-like techniques to additional redundant linear constraints could reduce the relaxation gap significantly. We demonstrate the efficiency of our results with numerical experiments.

关键词： Nonconvex quadratically constrained quadratic programming Convex relaxations reformulation-linearization technique SOC-RLT

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：