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

On linear programming relaxations for solving polynomial programming problems

COMPUTERS & OPERATIONS RESEARCH 2018年 99卷 67-77页

作者： Dalkiran, Evrim Ghalami, Laleh Wayne State Univ Ind & Syst Engn 4815 Fourth St Detroit MI 48202 USA

This paper studies linear programming (LP) relaxations for solving polynomial programming problems. A polynomial programming problem can be equivalently formulated as a quadratically constrained quadratic program (QCQP) by introducing new variables that represent nonlinear monomials and substituting them within the original formulation. Whereas Reformulation-linearization Technique (RLT)-based LP relaxations constructed for the original formulation are tight, the relaxations generated using the equivalent lower degree formulations are smaller and require less computational effort to optimize in comparison to the effort the former requires. In this study, we analyze the strength and tractability of the standard RLT, the J-set, and recursive McCormick relaxations for polynomial programming problems, and identify the superior relaxation depending on the problem characteristics. Extensive computational results are provided to demonstrate the relative effectiveness of the standard RLT, J-set, and recursive McCormick algorithms using problems from the literature and randomly generated test instances. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Reformulation-linearization Technique (RLT) J-set relaxation McCormick inequalities Polynomial programming problems linear programming relaxations Branch-and-bound algorithms

来源：评论

学校读者我要写书评

暂无评论

Comparative analysis of linear programming relaxations for the robust knapsack problem

引用

ANNALS OF OPERATIONS RESEARCH 2023年第1-2期323卷 65-78页

作者： Joung, Seulgi Oh, Seyoung Lee, Kyungsik Chonnam Natl Univ Dept Ind Engn 77Yongbong Ro Gwangju 61186 South Korea Seoul Natl Univ Dept Ind Engn 1 Gwanak Ro Seoul 08826 South Korea

In this study, we consider the robust knapsack problem defined by the model of Bertsimas and Sim (Operations Research 52(1):35-53, 2004) where each item weight is uncertain and is defined with an interval. The problem is to choose a subset of items that is feasible for all of the cases in which up to a pre-specified number of items are allowed to take maximum weights simultaneously while maximizing the sum of profits of chosen items. Several integer optimization formulations for the problem have been proposed, however the strength of the upper bounds obtained from their LP-relaxations have not been theoretically analyzed and compared. In this paper, we establish a theoretical relationship among those formulations in terms of their LP-relaxations. Especially, we theoretically prove that previously proposed strong formulations (two extended formulations and a formulation using submodularity) yield the same LP-relaxation bound. In addition, through computational tests with benchmark instances, we analyze the trade-off between the strength of the lower bounds and the required computation time to solve the LP-relaxations. The results show that the formulation using submodularity shows competitive theoretical and computational performance.

关键词： Robust knapsack problem Integer optimization models Strong formulations linear programming relaxations Comparative analysis

来源：评论

学校读者我要写书评

暂无评论

Polynomial programming: LP-relaxations also converge

引用

SIAM JOURNAL ON OPTIMIZATION 2005年第2期15卷 383-393页

作者： Lasserre, JB CNRS LAAS F-31077 Toulouse France

We consider the global minimization of a multivariate polynomial on a compact semialgebraic set. Using a result of Krivine [J. Analyse Math., 12 (1964), pp. 307-326;C. R. Acad. Sci. Paris, 258 (1964), pp. 3417-3418], it is shown that LP-relaxations based on products of the original constraints, in the spirit of the reformulation-linearization technique procedure of Sherali and Adams, converge to the global optimum. This extends to compact semialgebraic sets, previous results known for polytopes, and 0-1 programs. The asymptotic behavior of the LP-relaxations is also analyzed, and it is shown that in important cases, finite convergence cannot occur.

关键词： real algebraic geometry global optimization semidefinite programming relaxations linear programming relaxations

来源：评论

学校读者我要写书评

暂无评论

Reduced first-level representations via the reformulation-linearization technique: results, counterexamples, and computations

引用

DISCRETE APPLIED MATHEMATICS 2000年第1-3期101卷 247-267页

作者： Sherali, HD Smith, JC Adams, WP Virginia Polytech Inst & State Univ Dept Ind & Syst Engn Blacksburg VA 24061 USA Clemson Univ Dept Math Sci Clemson SC 29634 USA

In this paper, we consider the reformulation-linearization: :technique (RLT) of Sherali and Adams (SIAM J. Discrete Math. 3 (3) (1990) 411-430, Discrete Appl. Math. 52 (1994) 83-106) and explore the generation of reduced first-level representations for 0-1 mixed-integer programs that tend ro retain the strength of the full first-level linear programming relaxation. The motivation for this study is provided by the computational success of the first-level RLT representation (in full or partial form) experienced by-several researchers working on various classes of problems. We show that there exists a first-level representation having only about half the:RLT constraints that yields the same lower bound value via its relaxation, Accordingly, we attempt to a priori predict the form of this representation and identify many special cases for which this prediction is accurate. However, using various counter examples, we show that this prediction as well as several variants of it are not accurate in general, even for the case of a single binary variable. In addition, since the full first-level relaxation produces the convex hull representation for the case of a single binary variable, we investigate whether this is the case with respect to the reduced first-level relaxation as well,showing similarly that it holds true only for-some special cases. Some empirical results on the relative merit and prediction capability of the reduced, versus the full, first-level representation are also provided. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： reformulation-linearization technique (RLT) linear programming relaxations convex hull representations

来源：评论

学校读者我要写书评

暂无评论

The asymmetric traveling salesman path LP has constant integrality ratio

引用

MATHEMATICAL programming 2020年第1-2期183卷 379-395页

作者： Koehne, Anna Traub, Vera Vygen, Jens Univ Bonn Res Inst Discrete Math Bonn Germany Univ Bonn Hausdorff Ctr Math Bonn Germany

We show that the classical LP relaxation of the asymmetric traveling salesman path problem (ATSPP) has constant integrality ratio. *** *** denote the integrality ratios for the asymmetric TSP and its path version, *** = *** - 3. We prove an even better bound for node-weighted instances: if the integrality ratio for ATSP on node-weighted instances ***, then the integrality ratio for ATSPP on node-weighted instances is at most *** ATSP - 1. Moreover, we show that for ATSP node-weighted instances and unweighted digraph instances are almost equivalent. From this we deduce a lower bound of 2 on the integrality ratio of unweighted digraph instances.

关键词： Asymmetric traveling salesman problem Integrality gap linear programming relaxations

来源：评论

学校读者我要写书评

暂无评论

Approximability of Capacitated Network Design

引用

ALGORITHMICA 2015年第2期72卷 493-514页

作者： Chakrabarty, Deeparnab Chekuri, Chandra Khanna, Sanjeev Korula, Nitish Microsoft Res Bangalore 560001 Karnataka India Univ Illinois Dept Comp Sci Urbana IL 61801 USA Univ Penn Dept Comp & Informat Sci Philadelphia PA 19104 USA Google Inc New York NY 10011 USA

In the capacitated survivable network design problem (Cap-SNDP), we are given an undirected multi-graph where each edge has a capacity and a cost. The goal is to find a minimum cost subset of edges that satisfies a given set of pairwise minimum-cut requirements. Unlike its classical special case of SNDP when all capacities are unit, the approximability of Cap-SNDP is not well understood;even in very restricted settings no known algorithm achieves a o(m) approximation, where m is the number of edges in the graph. In this paper, we obtain several new results and insights into the approximability of Cap-SNDP. We give an O(logn) approximation for a special case of Cap-SNDP where the global minimum cut is required to be at least R. (Note that this problem generalizes the min-cost lambda-edge-connected subgraph problem, which is the special case of our problem when all capacities are unit.) Our result is based on a rounding of a natural cut-based LP relaxation strengthened with knapsack-cover (KC) inequalities. Our technique extends to give a similar approximation for a new network design problem that captures global minimum cut as a special case. We then show that as we move away from global connectivity, even for the single pair case (that is, when only one pair (s,t) has positive connectivity requirement), this strengthened LP has Omega(n) integrality gap. We also consider a variant of Cap-SNDP in which multiple copies of an edge can be bought: we give an O(logk) approximation for this case, where k is the number of vertex pairs with non-zero connectivity requirement. This improves upon the previously known O(min{k,logR (max)})-approximation when R (max) is large;here R (max) is the largest requirement. On the other hand, we observe that the multiple copy version of Cap-SNDP is Omega(loglogn)-hard to approximate even for the single-source version of the problem.

关键词： Approximation algorithms Network design linear programming relaxations

来源：评论

学校读者我要写书评

暂无评论

ON THE METRIC S-T PATH TRAVELING SALESMAN PROBLEM

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2015年第3期29卷 1133-1149页

作者： Gao, Zhihan Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada

We study the metric s-t path traveling salesman problem (TSP). An, Kleinberg, and Shmoys [Proceedings of the 44th ACM Symposium on Theory of Computing, 2012, pp. 875-886] improved on the long-standing 5/3-approximation factor and presented an algorithm that achieves an approximation factor of 1+root 5/2 approximate to 1.61803. Later, Sebo [Proceedings of the 16th Conference on Integer programming and Combinatorial Optimization, 2013, pp. 362-374] further improved the approximation factor to 8/5. We present a simple, self-contained analysis that unifies both results;our main contribution is a unified correction vector. Additionally, we compare two different linear programming (LP) relaxations of the s-t path TSP, namely, the path version of the Held-Karp LP relaxation for the TSP and a weaker LP relaxation, and we show that both LPs have the same (fractional) optimal value. Also, we show that the minimum cost of integral solutions of the two LPs are within a factor of 3/2 of each other. Furthermore, we prove that a half-integral solution of the stronger LP relaxation of cost c can be rounded to an integral solution of cost at most 3/2c. Finally, we give an example that presents obstructions to two natural methods that aim for an approximation factor of 3/2.

关键词： approximation algorithms path traveling salesman problem linear programming relaxations

来源：评论

学校读者我要写书评

暂无评论

Facility Location with Client Latencies: LP-Based Techniques for Minimum-Latency Problems

引用

MATHEMATICS OF OPERATIONS RESEARCH 2016年第3期41卷 865-883页

作者： Chakrabarty, Deeparnab Swamy, Chaitanya Microsoft Res Bangalore 560001 Karnataka India Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada

We introduce a problem that is a common generalization of the uncapacitated facility location (UFL) and minimum latency (ML) problems, where facilities not only need to be opened to serve clients, but also need to be sequentially activated before they can provide service. This abstracts a setting where inventory demanded by customers needs to be stocked or replenished at facilities from a depot or warehouse. Formally, we are given a set F of n facilities with facility-opening costs, a set D of m clients, and connection costs c (i, j) specifying the cost of assigning a client j to a facility i, a root node r denoting the depot, and a time metric d() on F boolean OR {r}. Our goal is to open a subset of facilities, find a path P starting at r and spanning the open facilities to activate them, and connecting each client j to an open facility so as to minimize the total facility opening cost, the total client connection cost, and the total time of arrivals at each facility along P. We call this the minimum latency uncapacitated facility location (MLUFL) problem. Our main result is an O (log n max (log n , log m))-approximation for MLUFL. Via a reduction to the group Steiner tree (GST) problem, we show this result is tight in the sense that any improvement in the approximation guarantee for MLUFL, implies an improvement in the (currently known) approximation factor for GST. We obtain significantly improved constant approximation guarantees for two natural special cases of the problem: (a) Related MLUFL, where the connection costs form a metric that is a scalar multiple of the time metric;(b) Metric uniform MLUFL, where we have metric connection costs and the time-metric is uniform. Our LP-based methods are fairly versatile and are easily adapted with minor changes to yield approximation guarantees for MLUFL (and ML) in various more general settings, such as (i) the setting where the latency-cost of a client is a function (of bounded growth) of the delay faced by the facil

关键词： facilty location latency problems approximation algorithms linear programming relaxations

来源：评论

学校读者我要写书评

暂无评论

Multicommodity flow models for spanning trees with hop constraints

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1996年第1期95卷 178-190页

作者： Gouveia, L UNIV LISBON FAC CIENCIASCIODEIOBLOCO C-2 CAMPO GRANDE CIDADE UNIVP-1700 LISBONPORTUGAL

In this paper we compare the linear programming relaxations of undirected and directed multicommodity flow formulations for the terminal layout problem with hop constraints. Hop constraints limit the number of hops (links) between the computer center and any terminal in the network. These constraints model delay constraints since a smaller number of hops decreases the maximum delay transmission time in the network. They also model reliability constraints because with a smaller number of hops there is a lower route loss probability. Hop constraints are easily modelled with the variables involved in multicommodity flow formulations. We give some empirical evidence showing that the linear programming relaxation of such formulations give sharp lower bounds for this hop constrained network design problem. On the other hand, these formulations lead to very large linear programming models. Therefore, for bounding purposes we also derive several lagrangean based procedures from a directed multicommodity flow formulation and present some computational results taken from a set of instances with up to 40 nodes.

关键词： integer programming linear programming relaxations multicommodity flows trees hop constraints reliability

来源：评论

学校读者我要写书评

暂无评论

Minimal spanning trees with a constraint on the number of leaves

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1998年第1期104卷 250-261页

作者： Fernandes, LM Gouveia, L Univ Lisbon Fac Ciencias CIO DEIO P-1700 Lisbon Portugal Univ Nova Lisboa Fac Ciencias & Tecnol Dept Matemat P-2825 Monte De Caparica Portugal

In this paper we discuss minimal spanning trees with a constraint on the number of leaves. Tree topologies appear when designing centralized terminal networks. The constraint on the number of leaves arises because the software and hardware associated to each terminal differs accordingly with its position in the tree. Usually, the software and hardware associated to a "degree-1" terminal is cheaper than the software and hardware used in the remaining terminals because for any intermediate terminal j one needs to check if the arrival message is destined to that node or to any other node located after node j. As a consequence, that particular terminal needs software and hardware for message routing. On the other hand, such equipment is not needed in "degree-1" terminals. Assuming that the hardware and software for message routing in the nodes is already available, the above discussion motivates a constraint stating that a tree solution has to contain exactly a certain number of "degree-1" terminals. We present two different formulations for this problem and some lower bounding schemes derived From them. We discuss a simple local-exchange heuristic and present computational results taken from a set of complete graphs with up to 40 nodes. Integer linear programming formulations for related problems are also discussed st the end. (C) 1998 Elsevier Science B.V.

关键词： integer linear programming linear programming relaxations spanning trees

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：