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

Inventory and investment in setup and quality operations under return on investment maximization

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2008年第2期185卷 593-605页

作者： Li, Jie Min, K. Jo Otake, Toshitsugu Van Voorhis, Timothy Iowa State Univ Dept Ind & Mfg Syst Engn Ames IA 50011 USA Knowledge Band Co Ltd Ikoma Nara Japan Liberty Univ Dept Math Lynchburg VA USA

In this paper, we construct and analyze a Return On Investment (ROI) maximization model for inventory and capital investment in setup and quality operations under an investment budget constraint. Specifically, we show how such an ROI maximization model can be formulated and derive analytical results such as the conditions under which the inventory is reduced and for the determination of the unique global optimal solution. In addition, by applying the reformulation-linearization technique (RLT), we show via numerical examples how this nonconvex optimization model can be solved effectively and how RLT may produce superior results to those from the conventional Cut Across the Board Rule (CABR). Various managerial insights are provided throughout the paper. For example, as the investment budget increases (or decreases), a fundamental shift of investment strategies (setup cost reduction vs. quality improvement) may be necessary so as to maximize ROI. (C) 2007 Elsevier B.V. All rights reserved.

关键词： inventory capital investment return on investment reformulation-linearization technique

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

ALLOCATING NODES TO HUBS FOR MINIMIZING THE HUBS PROCESSING RESOURCES: A CASE STUDY

引用

RAIRO-OPERATIONS RESEARCH 2019年第3期53卷 807-827页

作者： Balma, Ali Mrad, Mehdi Univ Tunis Ecole Natl Super Ingenieurs Tunis 5 Av Taha Hussein Tunis 1008 Tunisia Univ Tunis Tunis Business Sch BADEM POB 65 Bir El Kassaa 2059 Tunisia King Saud Univ Dept Ind Engn Coll Engn POB 800 Riyadh 11421 Saudi Arabia

This paper addresses the problem of allocating the terminal nodes to the hub nodes in a telecommunication network. Since the flow processing induces some undesirable delay, the objective is to minimize the total flow processed by the hubs. This study focuses on a real life network of the tunisian operator Tunisie Telecom whose operations managers are concerned by the quality of service. We provide three compact formulations that give optimal solutions for networks of large size. In particular, the last two are obtained by applying the reformulation-linearization technique to a nonlinear formulation of the problem. The latter formulation derived within this approach is the most computationally effective, as pointed out by the computational experiments conducted on the real life network of Tunisie Telecom with 110 nodes and 5 hubs. Finally, we discuss and compare between the single allocation and double allocation configurations.

关键词： Hub allocation Non-linear programming Combinatorial optimization Graphs and Networks reformulation-linearization technique Telecommunications

来源：评论

学校读者我要写书评

暂无评论

Lower bounds for the Quadratic Minimum Spanning Tree Problem based on reduced cost computation

引用

COMPUTERS & OPERATIONS RESEARCH 2015年 64卷 178-188页

作者： Rostami, Borzou Malucelli, Federico TU Dortmund Fak Math Dortmund Germany Politecn Milan Dipartimento Elettron Informaz & Bioingn I-20133 Milan Italy

The Minimum Spanning Tree Problem (MSTP) is one of the most known combinatorial optimization problems. It concerns the determination of a minimum edge-cost subgraph spanning all the vertices of a given connected graph. The Quadratic Minimum Spanning Tree Problem (QMSTP) is a variant of the MSTP whose cost considers also the interaction between every pair of edges of the tree. In this paper we review different strategies found in the literature to compute a lower bound for the QMSTP and develop new bounds based on a reformulation scheme and some new mixed 0-1 linear formulations that result from a reformulation-linearization technique (RLT). The new bounds take advantage of an efficient way to retrieve dual information from the MSTP reduced cost computation. We compare the new bounds with the other bounding procedures in terms of both overall strength and computational effort. Computational experiments indicate that the dual-ascent procedure applied to the new RLT formulation provides the best bounds at the price of increased computational effort, while the bound obtained using the reformulation scheme seems to reasonably tradeoff between the bound tightness and computational effort. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Quadratic minimum spanning tree problem Lagrangian relaxation reformulation-linearization technique Lower bound Dual-ascent approach Reduced costs

来源：评论

学校读者我要写书评

暂无评论

Lower bounding procedure for the asymmetric quadratic traveling salesman problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2016年第3期253卷 584-592页

作者： Rostami, Borzou Malucelli, Federico Belotti, Pietro Gualandi, Stefano TU Dortmund Fak Math Dortmund Germany Politecn Milan Dipartimento Elettron Informaz & Bioingn I-20133 Milan Italy FICO Xpress Dev Team Birmingham W Midlands England AntOptima SA Lugano Switzerland

In this paper we consider the Asymmetric Quadratic Traveling Salesman Problem (AQTSP). Given a directed graph and a function that maps every pair of consecutive arcs to a cost, the problem consists in finding a cycle that visits every vertex exactly once and such that the sum of the costs is minimal. We propose an extended Linear Programming formulation that has a variable for each cycle in the graph. Since the number of cycles is exponential in the graph size, we propose a column generation approach. Moreover, we apply a particular reformulation-linearization technique on a compact representation of the problem, and compute lower bounds based on Lagrangian relaxation. We compare our new bounds with those obtained by some linearization models proposed in the literature. Computational results on some set of benchmarks used in the literature show that our lower bounding procedures are very promising. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Traveling salesman reformulation-linearization technique Cycle cover Column generation Lower bound

来源：评论

学校读者我要写书评

暂无评论

Surrogate-RLT cuts for zero-one integer programs

引用

JOURNAL OF GLOBAL OPTIMIZATION 2016年第2期66卷 173-193页

作者： Yuh, Junsang Lee, Youngho Korea Univ Div Ind Management Engn Seoul South Korea

In this paper, we consider the class of 0-1 integer problems and develop an effective cutting plane algorithm that gives valid inequalities called surrogate-RLT cuts (SR cuts). Here we implement the surrogate constraint analysis along with the reformulation-linearization technique (RLT) to generate strong valid inequalities. In this approach, we construct a tighter linear relaxation by augmenting SR cuts to the problem. The level- SR closure of a 0-1 integer program is the polyhedron obtained by intersecting all the SR cuts obtained from RLT polyhedron formed over each set of variables with its initial formulation. We present an algorithm for approximately optimizing over the SR closure. Finally, we present the computational result of SR cuts for solving 0-1 integer programming problems of well-known benchmark instances from MIPLIB 3.0.

关键词： Integer programming Cutting plane reformulation-linearization technique Surrogate constraint analysis Partial convexification cuts Surrogate-RLT cuts

来源：评论

学校读者我要写书评

暂无评论

Lifted polynomial size formulations for the homogeneous and heterogeneous vehicle routing problems

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2017年第3期263卷 755-767页

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

We propose compact formulations for the symmetric and asymmetric capacitated vehicle routing problems. These formulations are obtained by lifting, using the reformulation-linearization technique, a novel polynomial size ordered path-based formulation. We show that the strongest proposed formulation is equivalent to the strongest multi-commodity flow formulation presented so far. In addition, we propose polynomial size valid inequalities that aim at further tightening the proposed formulations. Also, the tightest formulation is extended to model the fleet size and mix vehicle routing problem with fixed costs. We show that the new derived model is not comparable with a state-of-the-art polynomial length formulation. We present the results of computational experiments that demonstrate the tightness of the proposed formulations and the impact of the valid inequalities. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Transportation Capacitated vehicle routing problem reformulation-linearization technique Heterogeneous VRP Compact formulations

来源：评论

学校读者我要写书评

暂无评论

SOLVING QUADRATIC PROGRAMMING BY CUTTING PLANES

引用

SIAM JOURNAL ON OPTIMIZATION 2019年第2期29卷 1076-1105页

作者： Bonami, Pierre Lodi, Andrea Schweiger, Jonas Tramontani, Andrea IBM Spain CPLEX Optimizat Madrid Spain Polytech Montreal Canada Excellence Res Chair CP 6079Succ Ctr Ville Montreal PQ H3C 3A7 Canada Zuse Inst Berlin Berlin Germany

We propose new cutting planes for strengthening the linear relaxations that appear in the solution of nonconvex quadratic problems with linear constraints. By a famous result of Motzkin and Straus, these problems are connected to the clique number of a graph. Our cuts are derived in the context of a spatial branch-and-bound algorithm where linearization variables are introduced to represent products. Their validity is based on the result of Motzkin and Straus, in that it depends on the clique number of certain graphs. For convenience, we derive our cuts for the special case of the so-called standard quadratic programs, where the only (linear) constraint imposes that variables must belong to a simplex. We specifically consider cuts that correspond to carefully constructed complete bipartite graphs. We study the relation between these cuts and the classical ones obtained at the first level of the reformulation-linearization technique. By studying this relation, we derive a new type of valid inequalities that generalizes both types of cuts, and thus leading to a large family of cutting planes to strengthen the linear relaxation. We present extensive computational results using the different cutting planes we propose within the spatial branch and bound implemented by the commercial solver CPLEX. We show that our cuts allow us to obtain a significantly better bound than reformulation-linearization cuts and reduce computing times for global optimality. Finally, we formally establish the scaling necessary for using the proposed cuts to solve nonconvex quadratic problems with linear constraints, e.g., quadratic knapsack problems.

关键词： nonconvex programming standard quadratic programming global optimization cutting planes reformulation-linearization technique

来源：评论

学校读者我要写书评

暂无评论

Branch and cut algorithms for detecting critical nodes in undirected graphs

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2012年第3期53卷 649-680页

作者： Di Summa, Marco Grosso, Andrea Locatelli, Marco Univ Turin Dipartimento Informat I-10149 Turin Italy Univ Padua Dipartimento Matemat I-35121 Padua Italy Univ Parma Dipartimento Ingn Informat I-43124 Parma Italy

In this paper we deal with the critical node problem, where a given number of nodes has to be removed from an undirected graph in order to maximize the disconnections between the node pairs of the graph. We propose an integer linear programming model with a non-polynomial number of constraints but whose linear relaxation can be solved in polynomial time. We derive different valid inequalities and some theoretical results about them. We also propose an alternative model based on a quadratic reformulation of the problem. Finally, we perform many computational experiments and analyze the corresponding results.

关键词： Critical node problem Branch and cut Valid inequalities reformulation-linearization technique

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：