This article presents an exact algorithm for the multi-depot vehicle routing problem (MDVRP) under capacity and route length constraints. The MDVRP is formulated using a vehicle-flow and a set-partitioning formulation...
详细信息
This article presents an exact algorithm for the multi-depot vehicle routing problem (MDVRP) under capacity and route length constraints. The MDVRP is formulated using a vehicle-flow and a set-partitioning formulation, both of which are exploited at different stages of the algorithm. The lower bound computed with the vehicle-flow formulation is used to eliminate non-promising edges, thus reducing the complexity of the pricing sub-problem used to solve the set-partitioning formulation. Several classes of valid inequalities are added to strengthen both formulations, including a new family of valid inequalities used to forbid cycles of an arbitrary length. To validate our approach, we also consider the capacitated vehicle routing problem (CVRP) as a particular case of the MDVRP, and conduct extensive computational experiments on several instances from the literature to show its effectiveness. The computational results show that the proposed algorithm is competitive against state-of-the-art methods for these two classes of vehicle routing problems, and is able to solve to optimality some previously open instances. Moreover, for the instances that cannot be solved by the proposed algorithm, the final lower bounds prove stronger than those obtained by earlier methods. (C) 2014 Elsevier B.V. All rights reserved.
Emerging applications widely use field-programmable gate array(FPGA)prototypes as a tool to verify modern very-large-scale integration(VLSI)circuits,imposing many problems,including routing failure caused by the limit...
详细信息
Emerging applications widely use field-programmable gate array(FPGA)prototypes as a tool to verify modern very-large-scale integration(VLSI)circuits,imposing many problems,including routing failure caused by the limited number of connections among blocks of FPGAs *** a shortage of connections can be alleviated through time-division multiplexing(TDM),by which multiple signals sharing an identical routing channel can be *** this context,the routing quality dominantly decides the performance of such systems,proposing the requirement of minimizing the signal delay between FPGA *** paper proposes algorithms for the routing problem in a multi-FPGA system with TDM support,aiming to minimize the maximum TDM *** algorithm consists of two major stages:(1)A method is proposed to set the weight of an edge according to how many times it is shared by the routing requirements and consequently to compute a set of approximate minimum Steiner trees.(2)A ratio assignment method based on the edge-demand framework is devised for assigning ratios to the edges respecting the TDM ratio *** were conducted against the public benchmarks to evaluate our proposed approach as compared with all published works,and the results manifest that our method achieves a better TDM ratio in comparison.
Heuristics are widely applied to modularity maximization models for the identification of communities in complex networks. We present an approach to be applied as a post-processing to heuristic methods in order to imp...
详细信息
Heuristics are widely applied to modularity maximization models for the identification of communities in complex networks. We present an approach to be applied as a post-processing to heuristic methods in order to improve their performances. Starting from a given partition, we test with an exact algorithm for bipartitioning if it is worthwhile to split some communities or to merge two of them. A combination of merge and split actions is also performed. Computational experiments show that the proposed approach is effective in improving heuristic results. (C) 2012 Elsevier B.V. All rights reserved.
Given a graph G and an integer k, the Graph Burning problem asks whether the graph G can be burned in at most k rounds. Graph burning is a model for information spreading in a network, where we study how fast the info...
详细信息
ISBN:
(数字)9783031343476
ISBN:
(纸本)9783031343469;9783031343476
Given a graph G and an integer k, the Graph Burning problem asks whether the graph G can be burned in at most k rounds. Graph burning is a model for information spreading in a network, where we study how fast the information spreads in the network through its vertices. In each round, the fire is started at an unburned vertex, and fire spreads from every burned vertex to all its neighbors in the subsequent round burning all of them and so on. The minimum number of rounds required to burn the whole graph G is called the burning number of G. Graph Burning is NP-hard even for the union of disjoint paths. Moreover, Graph Burning is known to be W[1]-hard when parameterized by the burning number and para-NP-hard when parameterized by treewidth. In this paper, we prove the following results: - In this paper, we give an explicit algorithm for the problem parameterized by treewidth, tau and k, that runs in time k(2 tau) 4(k) 5(tau) n(O(1)). This also gives an FPT algorithm for Graph Burning parameterized by burning number for apex-minor-free graphs. - Y. Kobayashi and Y. Otachi [algorithmica 2022] proved that the problem is FPT parameterized by distance to cographs and gave a double exponential time FPT algorithm parameterized by distance to split graphs. We improve these results partially and give an FPT algorithm for the problem parameterized by distance to cographs boolean AND split graphs (threshold graphs) that runs in 2(O(t ln t)) time. - We design a kernel of exponential size for Graph Burning in trees. - Furthermore, we give an exact algorithm to find the burning number of a graph that runs in time 2(n)n(O(1)), where n is the number of vertices in the input graph.
We consider two related discrete optimization problems of searching for a subset in a finite set of points in Euclidean space. Both problems are induced by versions of a fundamental problem in data analysis, namely, t...
详细信息
We consider two related discrete optimization problems of searching for a subset in a finite set of points in Euclidean space. Both problems are induced by versions of a fundamental problem in data analysis, namely, that of selecting a subset of similar elements in a set of objects. In each problem, given an input set and a positive real number, it is required to find a cluster (i.e., a subset) of the largest size under constraints on a quadratic clusterization function. The points in the input set, which are outside the sought-for subset, are treated as a second (complementary) cluster. In the first problem, the function under the constraint is the sum over both clusters of the intracluster sums of the squared distances between the elements of the clusters and their centers. The center of the first (i.e., the sought-for) cluster is unknown and determined as a centroid, while the center of the second one is fixed at a given point in Euclidean space (without loss of generality, at the origin of coordinates). In the second problem, the function under the constraint is the sum over both clusters of the weighted intracluster sums of the squared distances between the elements of the clusters and their centers. As in the first problem, the center of the first cluster is unknown and determined as a centroid, while the center of the second one is fixed at the origin of coordinates. In this paper, we show that both problems are strongly NP-hard. Also, we present exact algorithms for the problems in which the input points have integer components. If the space dimension is bounded by some constant, the algorithms are pseudopolynomial.
In this paper we consider two closely related problems of selecting a diverse subset of points with respect to squared Euclidean distance. Given a set of points in Euclidean space, the first problem is to find a subse...
详细信息
In this paper we consider two closely related problems of selecting a diverse subset of points with respect to squared Euclidean distance. Given a set of points in Euclidean space, the first problem is to find a subset of a specified size M maximizing the sum of squared Euclidean distances between the chosen points. The second problem asks for a minimum cardinality subset of points, given a constraint on the sum of squared Euclidean distances between them. We consider the computational complexity of both problems and propose exact dynamic programming algorithms in the case of integer input data. If the dimension of the Euclidean space is bounded by a constant, these algorithms have a pseudo-polynomial time complexity. We also develop an FPTAS for the special case of the first problem, where the dimension of the Euclidean space is bounded by a constant.
In this paper, we present a new exact algorithm for the EDGE DOMINATING SET problem, and analyze its running time by the Measure and Conquer method. Our algorithm runs in 1.3160(n)n(0(1)) time for a graph with n verti...
详细信息
In this paper, we present a new exact algorithm for the EDGE DOMINATING SET problem, and analyze its running time by the Measure and Conquer method. Our algorithm runs in 1.3160(n)n(0(1)) time for a graph with n vertices, which is the currently fastest known time for the EDGE DOMINATING SET problem. By designing new branching rules based upon conceptually simple local structures, which we call clique-producing vertices and cycles, we obtain an algorithm that is simpler than the previously fastest known algorithm and has an improved time bound as well. (C) 2014 Elsevier B.V. All rights reserved.
The generalized list T-coloring is a common generalization of many graph coloring models, including classical coloring, L (p, q) -labeling, channel assignment and T-coloring. Every vertex from the input graph has a li...
详细信息
The generalized list T-coloring is a common generalization of many graph coloring models, including classical coloring, L (p, q) -labeling, channel assignment and T-coloring. Every vertex from the input graph has a list of permitted labels. Moreover, every edge has a set of forbidden differences. We ask for a labeling of vertices of the input graph with natural numbers, in which every vertex gets a label from its list of permitted labels and the difference of labels of the endpoints of each edge does not belong to the set of forbidden differences of this edge. In this paper we present an exact algorithm solving this problem, running in time O* ((tau + 2)(n)), where tau is the maximum forbidden difference over all edges of the input graph and n is the number of its vertices. Moreover, we show how to improve this bound if the input graph has some special structure, e.g. a bounded maximum degree, no big induced stars or a perfect matching.
The 0-1, Multidimensional Knapsack Problem (MKP) is a classical NP-hard combinatorial optimization problem with many engineering applications. In this paper, we propose a novel algorithm combining evolutionary computa...
详细信息
The 0-1, Multidimensional Knapsack Problem (MKP) is a classical NP-hard combinatorial optimization problem with many engineering applications. In this paper, we propose a novel algorithm combining evolutionary computation with the exact algorithm to solve the 0-1 MKP. It maintains a set of solutions and utilizes the information from the population to extract good partial assignments. To find high-quality solutions, an exact algorithm is applied to explore the promising search space specified by the good partial assignments. The new solutions are used to update the population. Thus, the good partial assignments evolve towards a better direction with the improvement of the population. Extensive experimentation with commonly used benchmark sets shows that our algorithm outperforms the state-of-the-art heuristic algorithms, TPTEA and DQPSO , as well as the commercial solver CPlex . It finds better solutions than the existing algorithms and provides new lower bounds for 10 large and hard instances.
This paper presents an approach to optimal routing with resource assignment for traveling among scattered farm fields. To this end, a road network among farm fields is created, which has data on shortest paths of all ...
详细信息
This paper presents an approach to optimal routing with resource assignment for traveling among scattered farm fields. To this end, a road network among farm fields is created, which has data on shortest paths of all pairs of fields and its distances. Two types of multiple traveling salesman problem (mTSP) formulations solved by an exact algorithm are presented to perform optimal routing. The proposed approach is demonstrated through a numerical experiment using data from an agricultural corporation considered in this paper. The results show features of the mTSP formulations and the proposed approach can yield the optimal routes within 2.4 seconds. Hence the proposed approach is feasible for use in actual daily work. Copyright (C) 2022 The Authors.
暂无评论