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

Approximation algorithms for the 0-extension problem

SIAM JOURNAL ON COMPUTING 2004年第2期34卷 358-372页

作者： Calinescu, G Karloff, H Rabani, Y IIT Dept Comp Sci Chicago IL 60616 USA AT&T Labs Res Florham Pk NJ 07932 USA Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

In the 0-extension problem, we are given a weighted graph with some nodes marked as terminals and a semimetric on the set of terminals. Our goal is to assign the rest of the nodes to terminals so as to minimize the sum, over all edges, of the product of the edge's weight and the distance between the terminals to which its endpoints are assigned. This problem generalizes the multiway cut problem of Dahlhaus et al. [SIAM J. Comput., 23 (1994), pp. 864-894] and is closely related to the metric labeling problem introduced by Kleinberg and Tardos [Proceedings of the 40th IEEE Annual Symposium on Foundations of Computer Science, New York, 1999, pp. 14-23]. We present approximation algorithms for 0-Extension. In arbitrary graphs, we present a O(log k)-approximation algorithm, k being the number of terminals. We also give O(1)-approximation guarantees for weighted planar graphs. Our results are based on a natural metric relaxation of the problem previously considered by Karzanov [European J. Combin., 19 ( 1998), pp. 71-101]. It is similar in flavor to the linear programming relaxation of Garg, Vazirani, and Yannakakis [ SIAM J. Comput., 25 (1996), pp. 235-251] for the multicut problem, and similar to relaxations for other graph partitioning problems. We prove that the integrality ratio of the metric relaxation is at least c root lg k for a positive c for infinitely many k. Our results improve some of the results of Kleinberg and Tardos, and they further our understanding on how to use metric relaxations.

关键词： metric space approximation algorithm linear programming relaxation graph partitioning

来源：评论

学校读者我要写书评

暂无评论

A matheuristic algorithm for the pollution and energy minimization traveling salesman problems

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2023年第2期30卷 655-687页

作者： Cacchiani, Valentina Contreras-Bolton, Carlos Escobar-Falcon, Luis Miguel Toth, Paolo Univ Bologna DEI Viale Risorgimento 2 I-40136 Bologna Italy Univ Concepcion Dept Ingn Ind Edmundo Larenas 219 Concepcion 4070409 Chile Univ Libre Program Syst Engn Belmonte Ave Amer Pereira 660001 Colombia

The pollution traveling salesman problem (PTSP) and the energy minimization traveling salesman problem (EMTSP) generalize the well-known asymmetric traveling salesman problem by including environmental issues and the goal of reducing carbon emissions. Both problems call for determining a Hamiltonian tour that, in the PTSP, minimizes a function of fuel consumption and driver cost (where the fuel consumption depends on the distance traveled, the vehicle speed, and the vehicle load), while, in the EMTSP, minimizes a function depending on the vehicle load and the traveled distances. For both PTSP and EMTSP, we propose a matheuristic algorithm that uses the solution of the linear programming relaxation of a mixed integer linear programming model for the considered problem to determine good initial feasible solutions, applies a multioperator genetic algorithm to improve these solutions, and refines the best solution found through an iterated local search procedure. In order to evaluate the performance of the proposed matheuristics, we compare them with exact and heuristic algorithms from the literature on benchmark instances of both problems.

关键词： pollution traveling salesman problem energy minimization traveling salesman problem matheuristic algorithm linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

Comparison of formulations for the Inventory Routing Problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2022年第3期303卷 997-1008页

作者： Archetti, Claudia Ljubic, Ivana ESSEC Business Sch Dept Informat Syst Decis Sci & Stat Cergy Pontoise France

In this paper we propose an analysis and comparison of the strength of the lower bound, measured as the value of the linear programming relaxation, of different formulations for the Inventory Routing Problem (IRP). In particular, we first focus on aggregated formulations, i.e., formulations where variables have no index associated with vehicles, and we analyse the link between compact formulations and their counterparts involving exponentially many constraints. We show that they are equivalent in terms of value of the linear relaxation. In addition, we study the link between aggregated and disaggregated formulations, i.e., formulations where variables have an index related to vehicles. Also in this case, we show that aggregated and disaggregated formulations are equivalent in terms of the value of the corresponding linear relaxation. To the best of our knowledge, this analysis has never been done for the IRP, which instead is gaining a lot of popularity in the literature. Finally, we propose different exact solution approaches based on the aggregated formulations and we compare them with state-of-the-art exact methods for the IRP. Results show that the approaches based on aggregated formulations are competitive in terms of quality of both upper and lower bounds. (C) 2022 The Author(s). Published by Elsevier B.V.

关键词： Routing Inventory routing Aggregated formulation linear programming relaxation Polyhedral projection

来源：评论

学校读者我要写书评

暂无评论

linearized Robust Counterparts of Two-Stage Robust Optimization Problems with Applications in Operations Management

引用

INFORMS JOURNAL ON COMPUTING 2021年第3期33卷 1138-1161页

作者： Ardestani-Jaafari, Amir Delage, Erick Univ British Columbia Fac Management Kelowna BC V1V 1V7 Canada HEC Montreal Dept Decis Sci Montreal PQ H3T 2A7 Canada Grp Res Decis Anal GERAD Montreal PQ Canada

In this article, we discuss an alternative method for deriving conservative approximation models for two-stage robust optimization problems. The method mainly relies on a linearization scheme employed in bilinear programming;therefore, we will say that it gives rise to the linearized robust counterpart models. We identify a close relation between this linearized robust counterpart model and the popular affinely adjustable robust counterpart model. We also describe methods of modifying both types of models to make these approximations less conservative. These methods are heavily inspired by the use of valid linear and conic inequalities in the linearization process for bilinear models. We finally demonstrate how to employ this new scheme in location-transportation and multi-item newsvendor problems to improve the numerical efficiency and performance guarantees of robust optimization.

关键词： two-stage adjustable robust optimization affinely adjustable robust counterpart linear programming relaxation bilinear programming

来源：评论

学校读者我要写书评

暂无评论

Rounding-based Moves for Semi-Metric Labeling

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2016年第1期17卷 3121-3162页

作者： Kumar, M. Pawan Dokania, Puneet K. Univ Oxford Dept Engn Sci Parks Rd Oxford OX1 3PJ England Cent Supelec Ctr Visual Comp F-92295 Chatenay Malabry France

Semi-metric labeling is a special case of energy minimization for pairwise Markov random fields. The energy function consists of arbitrary unary potentials, and pairwise potentials that are proportional to a given semi-metric distance function over the label set. Popular methods for solving semi-metric labeling include (i) move-making algorithms, which iteratively solve a minimum st-cut problem;and (ii) the linear programming (LP) relaxation based approach. In order to convert the fractional solution of the LP relaxation to an integer solution, several randomized rounding procedures have been developed in the literature. We consider a large class of parallel rounding procedures, and design move-making algorithms that closely mimic them. We prove that the multiplicative bound of a move-making algorithm exactly matches the approximation factor of the corresponding rounding procedure for any arbitrary distance function. Our analysis includes all known results for move-making algorithms as special cases.

关键词： semi-metric labeling move-making algorithms linear programming relaxation multiplicative bounds

来源：评论

学校读者我要写书评

暂无评论

On linearization techniques for budget-constrained binary quadratic programming problems

引用

OPERATIONS RESEARCH LETTERS 2016年第6期44卷 702-705页

作者： Yang, Mei-Jia Xia, Yong Zou, Hui-Min Beihang Univ Sch Math & Syst Sci Minist Educ State Key Lab Software Dev EnvironmLMIB Beijing 100191 Peoples R China Beijing Polytech Beijing 100176 Peoples R China

Glover's linearization technique is revisited for solving the binary quadratic programming problem with a budget constraint (BBQP). When compared with the recent two linearizations for (BBQP), it not only provides a tighter relaxation at the root node, but also has a much better computational performance for globally solving (BBQP). (C) 2016 Elsevier B.V. All rights reserved.

关键词： Binary quadratic programming Budget constraint linearization linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithm for facility location with service installation costs

引用

OPERATIONS RESEARCH LETTERS 2008年第1期36卷 46-50页

作者： Xu, Dachuan Zhang, Shuzhong Beijing Univ Technol Dept Appl Math Beijing 100022 Peoples R China Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China

In this paper, we study the uncapacitated facility location problem with service installation costs depending on the type of service required. We propose a polynomial-time approximation algorithm with approximation ratio 1.808 which improves the previous approximation ratio of 2.391 of Shmoys, Swamy, and Levi. (c) 2007 Elsevier B.V. All rights reserved.

关键词： facility location approximation algorithm linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

Customer order scheduling to minimize total weighted completion time

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2007年第5期35卷 623-626页

作者： Wang, Guoqing Cheng, T. C. Edwin Jinan Univ Dept Business Adm Guangzhou Peoples R China Hong Kong Polytech Univ Dept Logist Kowloon Hong Kong Peoples R China

In this paper we study the scheduling problem in which each customer order consists of several jobs of different types, which are to be processed on m facilities. Each facility is dedicated to the processing of only one type of jobs. All jobs of an order have to be delivered to the customer at the same time. The objective is to schedule all the orders to minimize the total weighted order completion time. While the problem has been shown to be unary NP-hard, we develop a heuristics to tackle the problem and analyze its worst-case performance. (c) 2005 Published by Elsevier Ltd.

关键词： customer order scheduling linear programming relaxation approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Solving MIN ONES 2-SAT as fast as VERTEX COVER

引用

THEORETICAL COMPUTER SCIENCE 2013年 506卷 115-121页

作者： Misra, Neeldhara Narayanaswamy, N. S. Raman, Venkatesh Shankar, Bal Sri Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India Inst Math Sci Madras 600113 Tamil Nadu India Indian Inst Technol Madras 600036 Tamil Nadu India

The problem of finding a satisfying assignment that minimizes the number of variables that are set to 1 is NP-complete even for a satisfiable 2-SAT formula. We call this problem MIN ONES 2-SAT. It generalizes the well-studied problem of finding the smallest vertex cover of a graph, which can be modeled using a 2-SAT formula with no negative literals. The natural parameterized version of the problem asks for a satisfying assignment of weight at most k. In this paper, we present a polynomial-time reduction from MIN ONES 2-SAT to VERTEX COVER without increasing the parameter and ensuring that the number of vertices in the reduced instance is equal to the number of variables of the input formula. Consequently, we conclude that this problem also has a simple 2-approximation algorithm and a 2k - c logk-variable kernel subsuming (or, in the case of kernels, improving) the results known earlier. Further, the problem admits algorithms for the parameterized and optimization versions whose runtimes will always match the runtimes of the best-known algorithms for the corresponding versions of vertex cover. Finally we show that the optimum value of the LP relaxation of the MIN ONES 2-SAT and that of the corresponding VERTEX COVER are the same. This implies that the (recent) results of VERTEX COVER version parameterized above the optimum value of the LP relaxation of VERTEX COVER carry over to the MIN ONES 2-SAT version parameterized above the optimum of the LP relaxation of MIN ONES 2-SAT. (C) 2013 Elsevier B.V. All rights reserved.

关键词： MIN ONES 2-SAT VERTEX COVER linear programming relaxation Parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Effective formulation reductions for the quadratic assignment problem

引用

COMPUTERS & OPERATIONS RESEARCH 2010年第11期37卷 2007-2016页

作者： Zhang, Huizhen Beltran-Royo, Cesar Constantino, Miguel Rey Juan Carlos Univ Madrid Spain Univ Lisbon Fac Ciencias DEIO Ctr Invest Operac Lisbon Portugal

In this paper we study two formulation reductions for the quadratic assignment problem (QAP). In particular we apply these reductions to the well known Adams and Johnson 121 integer linear programming formulation of the QAP. We analyze two cases: In the first case, we study the effect of constraint reduction. In the second case, we study the effect of variable reduction in the case of a sparse cost matrix. Computational experiments with a set of 30 QAPLIB instances, which range from 12 to 32 locations, are presented. The proposed reductions turned out to be very effective. (C) 2010 Elsevier Ltd. All rights reserved.

关键词： Quadratic assignment problem linear integer programming linear programming relaxation Sparse matrix

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：