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

Computing minimum 2-edge-connected Steiner networks in the Euclidean plane

NETWORKS 2019年第1期73卷 89-103页

作者： Brazil, Marcus Volz, Marcus Zachariasen, Martin Ras, Charl Thomas, Doreen Univ Melbourne Dept Elect & Elect Engn Melbourne Vic 3010 Australia Univ Melbourne Dept Mech Engn Melbourne Vic Australia Univ So Denmark Det Naturvidenskabelige Fak Odense Denmark Univ Melbourne Math & Stat Melbourne Vic Australia

We present a new exact algorithm for computing minimum 2-edge-connected Steiner networks in the Euclidean plane. The algorithm is based on the GeoSteiner framework for computing minimum Steiner trees in the plane. Several new geometric and topological properties of minimum 2-edge-connected Steiner networks are developed and incorporated into the new algorithm. Comprehensive experimental results are presented to document the performance of the algorithm which can reliably compute exact solutions to randomly generated instances with up to 50 terminals-doubling the range of existing exact algorithms. Finally, we discuss the appearance of Hamiltonian cycles as solutions to the minimum 2-edge-connected Steiner network problem.

关键词： 2-connected Steiner networks 2-edge-connected networks computational geometry exact algorithm GeoSteiner Steiner trees

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for the precedence-constrained single-machine scheduling problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2013年第2期229卷 345-352页

作者： Tanaka, Shunji Sato, Shun Kyoto Univ Dept Elect Engn Nishikyo Ku Kyoto 6158510 Japan

This study proposes an efficient exact algorithm for the precedence-constrained single-machine scheduling problem to minimize total job completion cost where machine idle time is forbidden. The proposed algorithm is based on the SSDP (Successive Sublimation Dynamic Programming) method and is an extension of the authors' previous algorithms for the problem without precedence constraints. In this method, a lower bound is computed by solving a Lagrangian relaxation of the original problem via dynamic programming and then it is improved successively by adding constraints to the relaxation until the gap between the lower and upper bounds vanishes. Numerical experiments will show that the algorithm can solve all instances with up to 50 jobs of the precedence-constrained total weighted tardiness and total weighted earliness-tardiness problems, and most instances with 100 jobs of the former problem. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Scheduling Single-machine Precedence constraints exact algorithm Lagrangian relaxation Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Resolution and linear CNF formulas: Improved (n, 3)-MAxSAT algorithms

引用

THEORETICAL COMPUTER SCIENCE 2019年 774卷 113-123页

作者： Xu, Chao Chen, Jianer Wang, Jianxin Cent S Univ Sch Informat Sci & Engn Changsha 410083 Hunan Peoples R China Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA

We study techniques for solving the MAxSAT problem on instances in which the variable degree is bounded by 3. The problem is NP-hard. We show how resolution principle can be applied that converts an instance into an equivalent instance in which the CNF formula becomes a linear CNF formula. We then show how more efficient branching strategies can be applied on linear CNF formulas. As applications, we present two algorithms: one of running time O*(1.194(k)) that solves the parameterized version of the problem, and the other of running time O*(1.237(n)) that solves the optimization version of the problem, both significantly improving previous best upper bounds. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Maximum satisfiability Linear CNF formula Resolution principle Parameterized algorithm exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimum-width annulus with outliers: Circular, square, and rectangular cases

引用

INFORMATION PROCESSING LETTERS 2019年 145卷 16-23页

作者： Ahn, Hee-Kap Ahn, Taehoon Bae, Sang Won Choi, Jongmin Kim, Mincheol Oh, Eunjin Shin, Chan-Su Yoon, Sang Duk POSTECH Dept Comp Sci & Engn Pohang South Korea Kyonggi Univ Div Comp Sci & Engn Suwon South Korea Max Planck Inst Informat Saarbrucken Germany Hankuk Univ Foreign Studies Div Comp & Elect Syst Engn Seoul South Korea Samsung Display Co Ltd Yongin South Korea

We study the problem of computing a minimum-width annulus with outliers. Specifically, given a set of n points in the plane and an integer k with 1 <= k <= n, the problem asks to find a minimum-width annulus that contains at least n - k input points. The k excluded points are considered as outliers of the input points. In this paper, we are interested in particular in annuli of three different shapes: circular, square, and rectangular annuli. For the three cases, we present first and improved algorithms to the problem. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Computational geometry Geometric shape matching exact algorithm Annulus Outlier

来源：评论

学校读者我要写书评

暂无评论

exact solution methods for the multi-period vehicle routing problem with due dates

引用

COMPUTERS & OPERATIONS RESEARCH 2019年第Oct.期110卷 148-158页

作者： Larrain, Homero Coelho, Leandro C. Archetti, Claudia Speranza, M. Grazia Pontificia Univ Catolica Chile Santiago Chile Univ Laval CIRRELT Quebec City PQ Canada Univ Laval Canada Res Chair Integrated Logist Quebec City PQ Canada Univ Brescia Dept Econ & Management Brescia Italy

In this paper we study the multi-period vehicle routing problem with due dates. A supplier has to determine a distribution plan to visit a set of customers over a given planning horizon. Each customer is associated with a release date and a due date, that is, the date at which the goods required by the customer become available at the supplier's depot, and the date by which the customer has to be visited, respectively. A fleet of capacitated vehicles is available at the depot to perform the distribution and the objective is to minimize the distribution costs and the costs related to delayed deliveries. New families of valid inequalities are presented that allow us to improve a branch-and-bound algorithm proposed in the literature. The new branch-and-bound algorithm reduces to 5.1% the optimality gap which is 12.1% for the known branch-and-bound on instances with one vehicle. A variable MIP neighborhood descent (VMND) algorithm is also presented, which speeds up the search for high quality solutions through a local search heuristic embedded in the branch-and-bound algorithm. Computational tests are performed to assess the quality of the VMND algorithm against the new branch-and-bound algorithm. The computational results show that the VMND algorithm improves 35 out of 80 solutions on instances with one vehicle, reducing the average optimality gap from 5.1% to 3.6%. It further matches the performance of the new branch-and-bound algorithm on another 35 instances. On instances with two and three vehicles the average optimality gap obtained by the VMND algorithm is 5.5% and 5.6%, respectively. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Routing Due dates Heuristic Local search exact algorithm Hybrid algorithm VMND

来源：评论

学校读者我要写书评

暂无评论

Computing a minimum-width cubic and hypercubic shell

引用

OPERATIONS RESEARCH LETTERS 2019年第5期47卷 398-405页

作者： Bae, Sang Won Kyonggi Univ Div Comp Sci & Engn Suwon South Korea

This paper addresses the problem of computing a minimum-width axis-aligned cubic shell enclosing a given set of n points in R-3. A cubic shell is a closed volume between two concentric and face-parallel cubes. Prior to this work, there was no known algorithm for this problem in the literature. We present the first nontrivial algorithm whose running time is O(n log(2) n) in the worst case. Our approach extends to higher dimension d > 3, resulting in an algorithm in O(n left perpendicular d/2 right perpendicular log(d-1) n) expected time. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Facility location Geometric optimization exact algorithm Cubic shell Hypercubic shell Minimum width

来源：评论

学校读者我要写书评

暂无评论

Heterogeneous vehicle pickup and delivery problems: Formulation and exact solution

引用

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW 2019年第May期125卷 181-202页

作者： Sun, Wei Yu, Yang Wang, Junwei Liaoning Univ Sch Business Shenyang 110316 Liaoning Peoples R China Northeastern Univ State Key Lab Synthet Automat Proc Ind Dept Intelligent Syst Engn Shenyang 110819 Liaoning Peoples R China Univ Hong Kong Dept Ind & Mfg Syst Engn Pokfulam Rd Hong Kong Peoples R China

The heterogeneous green pickup and delivery problem (GPDP) aims to minimize carbon emissions of pickups and deliveries by a fleet of heterogeneous vehicles. We propose the first exact algorithm for solving the heterogeneous GPDP. This exact algorithm is based on a set partitioning model and the key characteristics of its optimal solution. We prove that the optimal solution is composed of the optimal trips of heterogeneous vehicles;thus, the solution space is significantly reduced by cutting the non-optimal trips. The proposed exact algorithm can rapidly find the optimal solution of the largest-scale instance from Li & Lim benchmarks and three types of vehicles. The exact algorithm is also validated by solving a practical case of heterogeneous GPDP in China. Based on the extensive experiments, we conclude an interesting managerial insight that heterogeneous vehicles can always effectively reduce carbon emissions except for two situations.

关键词： Carbon emissions Green pickup and delivery problem Heterogeneous vehicles exact algorithm

来源：评论

学校读者我要写书评

暂无评论

A branch-and-price-and-cut algorithm for a pickup and delivery problem in retailing

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2019年 89卷 71-91页

作者： Li, Chongshou Gong, Lijun Luo, Zhixing Lim, Andrew Nanjing Univ Sch Management & Engn Nanjing 210093 Jiangsu Peoples R China Natl Univ Singapore Dept Ind Syst Engn & Management 1Engn Dr 2 Singapore 117576 Singapore City Univ Hong Kong Dept Management Sci Kowloon Tong Tat Chee Ave Hong Kong Peoples R China

We investigate a real-world product distribution problem faced by a fast fashion retailer in Singapore. It is a generalization of the multi-commodity pickup and delivery traveling salesman problem (m-PDTSP) proposed by Hernandez-Perez and Salazar-Gonzalez [15]. Each weekend the retailer forecasts the demand of each product for the next week. To ensure the inventory level equal to the forecast, the retailer schedules a fleet of vehicles to pick up or deliver products from/to each store at the beginning of each week. Shipping products from a store in surplus to another store in shortage is encouraged. For products that cannot be balanced among the stores, they are either picked up or delivered from/to the warehouse, which incurs a handling cost for each unit. The objective is to minimize the total travel distance as well as the total handling cost at the warehouse. To solve this problem, we propose a branch-and-price-and-cut algorithm based on a strong set-partitioning model, where an ad-hoc label-setting algorithm is designed to solve the pricing problem. The algorithm is tested on a set of instances generated according to a real-world database from the retailer and the m-PDTSP benchmark instances. Computational results show that our algorithm can optimally solve instances with 20 stores and over 100 products in one hour computational time. Moreover, it successfully solves several open m-PDTSP benchmark instances to optimality. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Vehicle routing Pickup and delivery Branch-price-and-cut exact algorithm

来源：评论

学校读者我要写书评

暂无评论

New exact approaches and approximation results for the Penalized Knapsack Problem

引用

DISCRETE APPLIED MATHEMATICS 2019年 253卷 122-135页

作者： Della Croce, Federico Pferschy, Ulrich Scatamacchia, Rosario Politecn Torino Dipartimento Ingn Gest & Prod Corso Duca Abruzzi 24 I-10129 Turin Italy CNR IEIIT Turin Italy Karl Franzens Univ Graz Dept Stat & Operat Res Univ Str 15 A-8010 Graz Austria

We consider the 0-1 Penalized Knapsack Problem (PKP). Each item has a profit, a weight and a penalty and the goal is to maximize the sum of the profits minus the greatest penalty value of the items included in a solution. We propose an exact approach relying on a procedure which narrows the relevant range of penalties, on the identification of a core problem and on dynamic programming. The proposed approach turns out to be very effective in solving hard instances of PKP and compares favorably both to commercial solver CPLEX 12.5 applied to the ILP formulation of the problem and to the best available exact algorithm in the literature. Then we present a general inapproximability result and investigate several relevant special cases which permit fully polynomial time approximation schemes (FPTASs). (C) 2017 Elsevier B.V. All rights reserved.

关键词： Penalized Knapsack Problem exact algorithm Dynamic programming Approximation schemes

来源：评论

学校读者我要写书评

暂无评论

A maximum edge-weight clique extraction algorithm based on branch-and-bound

引用

DISCRETE OPTIMIZATION 2020年 37卷 100583-100583页

作者： Shimizu, Satoshi Yamaguchi, Kazuaki Masuda, Sumio Kobe Univ Grad Sch Engn Kobe Hyogo Japan

The maximum edge-weight clique problem is to find a clique whose sum of edgeweight is the maximum for a given edge-weighted undirected graph. The problem is NP-hard and some branch-and-bound algorithms have been proposed. In this paper, we propose a new exact algorithm based on the branch-and-bound method. It assigns edge-weights to vertices and calculates upper bounds using vertex coloring. By some computational experiments, we confirmed our algorithm works fine. (C) 2020 Published by Elsevier B.V.

关键词： Maximum edge-weight clique exact algorithm Branch-and-bound Upper bound calculation NP-hard

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：