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

A new exact approach for the 0-1 Collapsing Knapsack Problem

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2017年第1期260卷 56-69页

作者： Della Croce, Federico Salassa, Fabio Scatamacchia, Rosario Politecn Torino Dipartimento Automat & Informat Corso Duca Abruzzi 24 I-10129 Turin Italy Politecn Torino Dipartimento Ingn Gestionale & Prod Corso Duca Abruzzi 24 I-10129 Turin Italy

We consider the 0/1 Collapsing Knapsack Problem (CKP) and a generalization involving more than a capacity constraint (M-CKP). We propose a novel ILP formulation and a problem reduction procedure together with an exact approach. The proposed approach compares favorably to the methods available in the literature and manages to solve to optimality very large size instances particularly for CKP and 2-CKP. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Branch and Bound Collapsing Knapsack Problem 0-1 Programming exact algorithm

来源：评论

学校读者我要写书评

暂无评论

On partitioning a graph into two connected subgraphs

引用

THEORETICAL COMPUTER SCIENCE 2011年第48期412卷 6761-6769页

作者： Paulusma, Daniel van Rooij, Johan M. M. Univ Durham Sci Labs Dept Comp Sci Durham DH1 3LE England Univ Utrecht Dept Informat & Comp Sci NL-3508 TB Utrecht Netherlands

Suppose a graph G is given with two vertex-disjoint sets of vertices Z(1) and Z(2). Can we partition the remaining vertices of G such that we obtain two connected vertex-disjoint subgraphs of G that contain Z(1) and Z(2), respectively? This problem is known as the 2-DISJOINT CONNECTED SUBGRAPHS problem. It is already NP-complete for the class of n-vertex graphs G = (V, E) in which Z(1) and Z(2) each contain a connected set that dominates all vertices in V\(Z(1)boolean OR Z(2)). We present an O* (1.2051(n)) time algorithm that solves it for this graph class. As a consequence, we can also solve this problem in O*(1.2051(n)) time for the classes of n-vertex P(6)-free graphs and split graphs. This is an improvement upon a recent O*(1.5790(n)) time algorithm for these two classes. Our approach translates the problem to a generalized version of hypergraph 2-coloring and combines inclusion/exclusion with measure and conquer. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Disjoint connected subgraphs Dominating set exact algorithm

来源：评论

学校读者我要写书评

暂无评论

On the Bandpass problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2011年第1期22卷 71-77页

作者： Lin, Guohui Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

The complexity of the Bandpass problem is re-investigated. Specifically, we show that the problem with any fixed bandpass number Ba parts per thousand yen2 is NP-hard. Next, a row stacking algorithm is proposed for the problem with three columns, which produces a solution that is at most 1 less than the optimum. For the special case B=2, the row stacking algorithm guarantees an optimal solution. On approximation, for the general problem, we present an O(B (2))-algorithm, which reduces to a 2-approximation algorithm for the special case B=2.

关键词： Bandpass problem Hamiltonian path problem NP-hard Approximation algorithm exact algorithm

来源：评论

学校读者我要写书评

暂无评论

exact and approximate algorithms for the longest induced path problem

引用

RAIRO-OPERATIONS RESEARCH 2021年第2期55卷 333-353页

作者： Marzo, Ruslan G. Ribeiro, Celso C. Univ Fed Fluminense Inst Comp BR-24210346 Niteroi RJ Brazil

The longest induced path problem consists in finding a maximum subset of vertices of a graph such that it induces a simple path. We propose a new exact enumerative algorithm that solves problems with up to 138 vertices and 493 edges and a heuristic for larger problems. Detailed computational experiments compare the results obtained by the new algorithms with other approaches in the literature and investigate the characteristics of the optimal solutions.

关键词： Longest induced path problem exact algorithm backtracking heuristics

来源：评论

学校读者我要写书评

暂无评论

The Traveling Salesman Problem with Pickups, Deliveries, and Handling Costs

引用

TRANSPORTATION SCIENCE 2010年第3期44卷 383-399页

作者： Battarra, Maria Erdogan, Guenes Laporte, Gilbert Vigo, Daniele Univ Bologna Dipartimento Elettron Informat & Sistem I-47521 Cesena FC Italy Ozyegin Univ Dept Ind Engn TR-34662 Istanbul Turkey HEC Montreal Dept Management Sci Montreal PQ J3T 247 Canada

This paper introduces a new variant of the one-to-many-to-one single vehicle pickup and delivery problems (SVPDP) that incorporates the handling cost incurred when rearranging the load at the customer locations. The simultaneous optimization of routing and handling costs is difficult, and the resulting loading patterns are hard to implement in practice. However, this option makes economical sense in contexts where the routing cost dominates the handling cost. We have proposed some simplified policies applicable to such contexts. The first is a two-phase heuristic in which the tour having minimum routing cost is initially determined by optimally solving an SVPDP, and the optimal handling policy is then determined for that tour. In addition, branch-and-cut algorithms based on integer linear programming formulations are proposed, in which routing and handling decisions are simultaneously optimized, but the handling decisions are restricted to three simplified policies. The formulations are strengthened by means of problem specific valid inequalities. The proposed methods have been extensively tested on instances involving up to 25 customers and hundreds of items. Our results show the impact of the handling aspect on the customer sequencing and indicate that the simplified handling policies favorably compare with the optimal one.

关键词： the traveling salesman problem combinatorial optimization exact algorithm

来源：评论

学校读者我要写书评

暂无评论

An exact decomposition method to save trips in cooperative pickup and delivery based on scheduled trips and profit distribution

引用

COMPUTERS & OPERATIONS RESEARCH 2017年 87卷 245-257页

作者： Yu, Yang Lou, Qi Tang, Jiafu Wang, Junwei Yue, XiaoHang Northeastern Univ Inst Syst Engn Shenyang 110816 Liaoning Peoples R China Dongbei Univ Finance & Econ Coll Management Sci & Engn Dalian 116023 Peoples R China Univ Hong Kong Dept Ind & Mfg Syst Engn Pokfulam Rd Hong Kong Hong Kong Peoples R China Univ Wisconsin Lubar Sch Business Milwaukee WI 53201 USA

Compared to the non-cooperative mode, the cooperative mode is a powerful way to reduce operational cost in pickup and delivery service. In order to protect business sensitive information, sometimes participants are unwilling to open the customer's detailed information. Thus, we utilize the publishable trip scheduled results to compute the saved trips brought by cooperation. A mathematical model minimizing trips of cooperation is proposed. To obtain the exact solution, we define the cooperative trip set. We prove that only when cooperative trip set exists it is possible to save trips by cooperation. For a two-trip cooperative trip set, we exactly obtain the saved trips by enumerating all feasible cooperative cases. For a K-trip cooperative trip set, we propose an exact method to obtain the saved trips by decomposing it to at most K-1 two-trip cooperative trip sets. Computational complexity of the based-on-decomposition exact algorithm is O(N), where N is the total number of trips. Using the based-on-decomposition algorithm, we calculate the exact Shapley value to distribute profit. To empirically verify the exact method, we perform the extensive experiment cases of the real cooperative pickup and delivery service, i.e., "picking up and delivering customers to airport service" (PDCA). (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Cooperation exact algorithm Decomposition Profit distribution exact Shapley value

来源：评论

学校读者我要写书评

暂无评论

Implementation of BFA (Backtrack-Free Path Planning algorithm) for Three-Dimensional Workspaces and Its Application to Path Planning of Multi Manipulators

引用

ELECTRONICS AND COMMUNICATIONS IN JAPAN 2011年第12期94卷 1-11页

作者： Murata, Tomonari Tamura, Shinsuke Kawai, Masayuki Univ Fukui Grad Sch Engn Fukui Japan

Together with a newly developed method for avoiding collisions between links themselves, the BFA (Backtrack-Free path planning algorithm) has been implemented for calculating the paths of manipulators that are operated in three-dimensional workspaces. An approach to extending the BFA to an algorithm for calculating the paths of multiple manipulators cooperating to accomplish complicated tasks, in which multiple manipulators are considered as a single composite one with many links, is also discussed. The algorithm is backtrack-free and resolution-complete. Its computational volume is proportional to the total number of links and does not change drastically with the environments in which the manipulators are operated. Simulation results have demonstrated that the BFA allows efficient generation of paths for both single and multiple manipulators. (C) 2011 Wiley Periodicals, Inc. Electron Comm Jpn, 94(12): 1-11,2011;Published online in Wiley Online Library (***). DOI 10.1002/ecj.10392

关键词： manipulator backtrack free path planning exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Location, pricing and the problem of Apollonius

引用

OPTIMIZATION LETTERS 2017年第8期11卷 1797-1805页

作者： Berger, Andre Grigoriev, Alexander Panin, Artem Winokurow, Andrej Maastricht Univ Dept Quantitat Econ Sch Business & Econ POB 616 NL-6200 MD Maastricht Netherlands Sobolev Inst Math Acad Koptyug Ave 4 Novosibirsk 630090 Russia Novosibirsk State Univ 2 Pirogov Str Novosibirsk 630090 Russia

In Euclidean plane geometry, Apollonius' problem is to construct a circle in a plane that is tangent to three given circles. We will use a solution to this ancient problem to solve several versions of the following geometric optimization problem. Given is a set of customers located in the plane, each having a demand for a product and a budget. A customer is satisfied if her total, travel and purchase, costs do not exceed the budget. The task is to determine location of production facilities in the plane and one price for the product such that the revenue generated from the satisfied customers is maximized.

关键词： Pricing problem Facility location Apollonius' problem Complexity exact algorithm

来源：评论

学校读者我要写书评

暂无评论

An efficient algorithm for spare allocation problems

引用

IEEE TRANSACTIONS ON RELIABILITY 2006年第2期55卷 369-378页

作者： Lin, Hung-Yau Yeh, Fu-Min Kuo, Sy-Yen Natl Taiwan Univ Dept Elect Engn Taipei 106 Taiwan Chung Shan Inst Sci & Technol Taoyuan Taiwan Natl Taiwan Ocean Univ Dept Comp Sci & Engn Chilung Taiwan

The spare allocation problem in redundant RAM is to replace faulty rows/columns of memory cells with spare rows/columns. To solve the problem, comparison-based search tree structures were used in traditional exact algorithms. These algorithms are not efficient for large problems because significant amounts of data have to be retained and copied in order to generate new partial solutions. Many data may need to be compared for the removal of each redundant partial solution. To overcome these drawbacks, an efficient algorithm is proposed in this paper. The algorithm transforms a spare allocation problem into Boolean functions, and the renowned BDD is used to manipulate them. Experimental results indicate that the proposed algorithm is very efficient in terms of speed and memory requirements. It may also be useful for problems which can be modeled as constraint bipartite vertex cover problems.

关键词： BDD bipartite graph Boolean functions exact algorithm memory repair RRAM vertex cover

来源：评论

学校读者我要写书评

暂无评论

algorithms for randomized time-varying knapsack problems

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第1期31卷 95-117页

作者： He, Yichao Zhang, Xinlu Li, Wenbin Li, Xiang Wu, Weili Gao, Suogang Shijiazhuang Univ Econ Coll Informat Engn Shijiazhuang 050031 Peoples R China Hebei Normal Univ Coll Math & Informat Sci Shijiazhuang 050024 Peoples R China Shijiazhuang Univ Econ Lab Network & Informat Secur Shijiazhuang 050031 Peoples R China Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

In this paper, we first give the definition of randomized time-varying knapsack problems () and its mathematic model, and analyze the character about the various forms of . Next, we propose three algorithms for : (1) an exact algorithm with pseudo-polynomial time based on dynamic programming;(2) a 2-approximation algorithm for based on greedy algorithm;(3) a heuristic algorithm by using elitists model based on genetic algorithms. Finally, we advance an evaluation criterion for the algorithm which is used for solving dynamic combinational optimization problems, and analyze the virtue and shortage of three algorithms above by using the criterion. For the given three instances of , the simulation computation results coincide with the theory analysis.

关键词： Knapsack problem exact algorithm Approximations Heuristics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：