The field of computational models of argument aims to provide support for automated reasoning through algorithms that operate on arguments and attack relations between them. In this paper we present a new labelling al...
详细信息
ISBN:
(纸本)9789897583728
The field of computational models of argument aims to provide support for automated reasoning through algorithms that operate on arguments and attack relations between them. In this paper we present a new labelling algorithm that lists all preferred extensions of an abstract argumentation framework. The new algorithm is enhanced by a new pruning strategy. We verified our new labelling algorithm and showed that it enumerates preferred extensions faster than the old labelling algorithm.
This paper constructs an algorithm to solve the fractional assignment problem. algorithms that are currently used are mostly based on parametric approaches and must solve a sequence of optimization procedures. They al...
详细信息
This paper constructs an algorithm to solve the fractional assignment problem. algorithms that are currently used are mostly based on parametric approaches and must solve a sequence of optimization procedures. They also neglect the difficulties caused by degeneracy. The proposed algorithm performs optimization once and overcomes degeneracy. The main features of the algorithm are an effective initial heuristic approach, a simple labelling procedure and an implicit primal-dual schema. A numerical example is presented and demonstrates that the proposed algorithm is easy to apply. Computational results are compared with those from other developed methods. The results show that the proposed algorithm is efficient.
This paper provides a tutorial on Branch-Price-and-Cut (BPC) algorithms for a generic class of problems whose objective is to find a set of feasible paths in a graph while optimising a given objective function. The tu...
详细信息
This paper provides a tutorial on Branch-Price-and-Cut (BPC) algorithms for a generic class of problems whose objective is to find a set of feasible paths in a graph while optimising a given objective function. The tutorial is split into two main parts. First, we describe the building blocks of a BPC algorithm: the Branch-and-Bound algorithm, the column generation procedure and the Branch-and-Cut algorithm. Then, we focus on the description of a BPC algorithm for the class of problems we consider. Precisely, we present the classical and advanced techniques that should be embedded in an efficient algorithm. Particular attention is devoted to the solution of the pricing problem in the case where it is formulated as an Elementary Shortest Path Problem with Resource Constraints. The aim of the tutorial is pedagogical. Hence, its intended reader is someone facing the first implementation of a BPC algorithm. Implementation tips and examples accompany the techniques and concepts to ease their comprehension. Precisely, the examples are based on the Capacitated Vehicle Routing Problem, which is a well-known problem belonging to the class we consider.
Multi-stop truckload shipping offers less-than-truckload shippers a promising way to reduce their freight costs by consolidating freights en route, which is similar to ridesharing in the mobility industry. One signifi...
详细信息
Multi-stop truckload shipping offers less-than-truckload shippers a promising way to reduce their freight costs by consolidating freights en route, which is similar to ridesharing in the mobility industry. One significant challenge in practical implementation is designing attractive multi-stop routes that to shippers while conforming to carriers' requirements. It is crucial to develop an efficient optimisation algorithm to automate bundling decisions. However, this routeing problem is complicated by a nonlinear inseparable cost structure and new routeing decisions in the first pickup and last delivery points. We introduce a new variant of pickup and delivery model and propose a column generation algorithm to efficiently solve real-world multi-stop routeing problems. The algorithm utilises a new specialised labelling procedure that exclusively generates labels for pickup sequences and establishes new dominance rules. Theoretical results on the label dominance, algorithm complexity, and optimality gap are also established. We conduct a real-world case study, comparing our methodology against the enumeration method and a heuristic method documented in the literature. The computational results demonstrate the high efficiency of our method and reveal important insights for practitioners.
Additive manufacturing(AM)has attracted significant attention in recent years based on its wide range of applications and growing *** offers the advantages of production flexibility and design *** this study,we consid...
详细信息
Additive manufacturing(AM)has attracted significant attention in recent years based on its wide range of applications and growing *** offers the advantages of production flexibility and design *** this study,we considered a practical variant of the batch-processing-machine(BPM)scheduling problem that arises in AM industries,where an AM machine can process multiple parts simultaneously,as long as the twodimensional rectangular packing constraint is not *** on the set-partitioning formulation of our mixed-integer programming(MIP)model,a branch-and-price(B&P)algorithm was developed by embedding a column-generation technique into a branchand-bound ***,a novel labelling algorithm was developed to accelerate the column-generation *** is the first study to provide a B&P algorithm to solve the BPM scheduling problem in the AM *** tested the performance of our algorithm using a modern MIP solver(Gurobi)and real data from a 3D printing *** results demonstrate that for most instances tested,our algorithm produces results similar or identical to those of Gurobi with reasonable computation time and outperforms Gurobi in terms of solution quality and running time on some large instances.
Shortest path problem in real life applications has to deal with multiple criteria. This article intends to solve a proposed multi-criteria shortest path problem of a weighted connected directed network whose associat...
详细信息
Shortest path problem in real life applications has to deal with multiple criteria. This article intends to solve a proposed multi-criteria shortest path problem of a weighted connected directed network whose associated edge weights are represented as rough variables in order to tackle the imprecision. We have exhibited two different approaches to determine the optimum path (s) of the proposed problem. The first approach is the proposed modified rough Dijkstra's labelling algorithm. The second approach considers the rough chance constrained programming technique to formulate the proposed multi-criteria shortest path problem which is eventually solved by two different methods: the goal attainment method and the nondominated sorting genetic algorithm II. These methodologies are numerically illustrated for a multi-criteria weighted connected directed network. Moreover, the simulated results on similar networks of large order and size are analyzed to show the efficiency of the algorithms.
In order to develop an algorithm, computer theories are essential and often used in a mathematical sequence. Most of them without sufficient mathematics are difficult to understand. A mathematical algorithm is, theref...
详细信息
ISBN:
(纸本)9781728146836
In order to develop an algorithm, computer theories are essential and often used in a mathematical sequence. Most of them without sufficient mathematics are difficult to understand. A mathematical algorithm is, therefore, a better guide to confirm whether or not a software is correct. This implies that a mathematical knowledge-based algorithm is of great concern. Let S={r1, r2, ...rφ(n)} be a set of all co-prime residues of a positive integer n. An integer is termed as totient if the sum of co-prime residues of n is 2 k n, k ≥ 1. A graph G with V and E be the set of vertices and edges of G respectively, then G is said to be a totient graph if there exists a one-one function h:V→ N, whose induced function h * :E→ N, defined by f * (ab)=f(a)f(b) assigns a totient number for each edge of G. In this piece of work, we propose new labeling algorithms for several classes of graphs.
The exact solution and heuristic solution have their own strengths and weaknesses on solving the Vehicle Routing Problems with Time Windows (VRPTW). This paper proposes a hybrid Column Generation algorithm with Metahe...
详细信息
The exact solution and heuristic solution have their own strengths and weaknesses on solving the Vehicle Routing Problems with Time Windows (VRPTW). This paper proposes a hybrid Column Generation algorithm with Metaheuristic Optimization (CGAMO) to overcome their weaknesses. Firstly, a Modified labelling algorithm (MLA) in the sub-problem of path searching is analysed. And a search strategy in CGAMO based on the demand of sub-problem is proposed to improve the searching efficiency. While putting the paths found in the sub-problem into the main problems of CGAMO, the iterations may fall into endless loops. To avoid this problem and keep the main problems in a reasonable size, two conditions on saving the old paths in the main problem are used. These conditions enlarge the number of constraints considered in the iterations to strengthen the limits of dual variables. Through analysing the sub-problem, we can find many useless paths that have no effect on the objective function. Secondly, in order to reduce the number of useless paths and improve the efficiency, this paper proposes a heuristic optimization strategy of CGAMO for dual variables. It is supposed to accelerate the solving speed from the view of on the dual problem. Finally, extensive experiments show that CGAMO achieves a better performance than other state-of-the-art methods on solving VRPTW. The comparative experiments also present the parameters sensitivity analysis, including the different effects of MLA in the different path selection strategies, the characteristics and the applicable scopes of the two path-keeping conditions in the main problem.
This paper proposes an extended connected-components labeling algorithm for sparse Lidar (Light detection and ranging) sensor data. It is difficult to label sparse Lidar data using the general connected-component labe...
详细信息
ISBN:
(纸本)9781479964666
This paper proposes an extended connected-components labeling algorithm for sparse Lidar (Light detection and ranging) sensor data. It is difficult to label sparse Lidar data using the general connected-component labeling algorithm. The proposed technique first increases the density of the sparse data by performing mathematical morphological operation of dilation. Next, labeling is performed on the dilated data, and the resultant labels are mapped to the input sparse Lidar data. The proposed technique does not distort the input Lidar data. We show the application of the proposed algorithm in map building using clustering. Results show that the proposed method can label sparse Lidar data to build maps.
Many design tasks involve the creation of new objects in the context of an existing scene. Existing work in computer vision only provides partial support for such tasks. On the one hand, multi-view stereo algorithms a...
详细信息
ISBN:
(纸本)9781467369657
Many design tasks involve the creation of new objects in the context of an existing scene. Existing work in computer vision only provides partial support for such tasks. On the one hand, multi-view stereo algorithms allow the reconstruction of real-world scenes, while on the other hand algorithms for line-drawing interpretation do not take context into account. Our work combines the strength of these two domains to interpret line drawings of imaginary objects drawn over photographs of an existing scene. The main challenge we face is to identify the existing 3D structure that correlates with the line drawing while also allowing the creation of new structure that is not present in the real world. We propose a labeling algorithm to tackle this problem, where some of the labels capture dominant orientations of the real scene while a free label allows the discovery of new orientations in the imaginary scene. We illustrate our algorithm by interpreting line drawings for urban planing, home remodeling, furniture design and cultural heritage.
暂无评论