177,369 research outputs found
A subexponential algorithm for the coloured tree partition problem
No full textAbstractGiven a tree of n vertices and a list of feasible colours for each vertex, the coloured tree partition problem (CTPP) consists in partitioning the tree into p vertex-disjoint subtrees of minimum total cost, and assigning to each subtree a different colour, which must be feasible for all of its vertices. The problem is strongly NP-hard on general graphs, as well as on grid and bipartite graphs. This paper deals with the previously open case of tree graphs, showing that it is strongly NP-complete to determine whether a feasible solution exists. It presents reduction, decomposition and bounding procedures to simplify the problem and an exact algorithm of O(nplog2(ap-2)) complexity (with a>32) for the special case in which a vertex of each subtree is given
A Heuristic for the Vehicle Routing Problem with Time Windows
No full textIn this paper we propose a heuristic algorithm to solve the Vehicle Routing Problem with Time Windows. Its framework is a smart combination of three simple procedures: the classical k-opt exchanges improve the solution, an ad hoc procedure reduces the number of vehicles and a second objective function drives the search out of local optima. No parameter tuning is required and no random choice is made: these are the distinguishing features with respect to the recent literature. The algorithm has been tested on benchmark problems which prove it to be more effective than comparable algorithms
A heuristic approach to the overnight security service problem
No full textThis paper introduces the overnight security service problem. The model obtained is a single-objective mixed integer programming problem. It is NP-hard in the strong sense, and exact approaches are not practicable when solving real-life instances. Thus, the model is solved heuristically, through a decomposition in two subproblem. The former is a capacitated clustering problem, the latter is a multiple travelling salesman problem with time windows. Both have a radius constraint which is unusual. The computational results prove the robustness of the approach used. Moreover, a detailed discussion of the results shows that the management objectives are satisfied, providing lower costs, a strong guarantee on the level of service and several different solutions
Better and faster solutions for the maximum diversity problem
No full textThe aim of the Maximum Diversity Problem (MDP) is to extract a subset M of given cardinality from a set of elements N, in such a way that the sum of the pairwise distances between the elements of M is maximum. This problem, introduced by Glover [7], has been deeply studied using GRASP methodologies [6, 1, 17, 2, 16]. Usually, effective algorithms owe their success more to the careful exploitation of problem-specific features than to the application of general-purpose methods. A solution for MDP has a very simple structure which can not be exploited for sophisticated neighborhood search. This paper explores the performance of three alternative solution approaches, that is Tabu Search, Variable Neighborhood Search and Scatter Search, comparing them with those of best GRASP algorithms in literature. We also focus our attention on the comparison of these three methods applied in their pure form
Comparing local search metaheuristics for the maximum diversity problem
No full textThe Maximum Diversity Problem (MDP) requires to extract a subset M of given cardinality from a set N, maximising the sum of the pair-wise diversities between the extracted elements. The MDP has recently been the subject of much research, and several sophisticated heuristics have been proposed to solve it. The present work compares four local search metaheuristics for the MDP, all based on the same Tabu Search procedure, with the aim to identify what additional elements provide the strongest improvement. The four metaheuristics are an Exploring Tabu Search, a Scatter Search, a Variable Neighbourhood Search and a simple Random Restart algorithm. All of them prove competitive with the best algorithms proposed in the literature. Quite surprisingly, the best ones are the simple Random Restart algorithm and a Variable Neighbourhood Search algorithm with an unusual parameter setting, which makes it quite close to random restart. Although this is probably related to the elementary structure of the MDP, it also suggests that, more often than expected, simpler algorithms might be better
Metaheuristics for the Minimum Gap Graph Partitioning Problem
No full textThe Minimum Gap Graph Partitioning Problem (MGGPP) consists in partitioning a vertex-weighted undirected graph into a given number of connected subgraphs with the minimum difference between the largest and the smallest weight in each subgraph. We propose a two-level Tabu Search algorithm and an Adaptive Large Neighborhood Search algorithm to solve the MGGPP in reasonable time on instances with up to about 23 000 vertices. The quality of the heuristic solutions is assessed comparing them with the solutions of a polynomially solvable combinatorial relaxation
The multicommodity multilevel bottleneck assignment problem
No full textThe Multilevel Bottleneck Assignment Problem is defined on a weighted graph of L levels and consists in finding Formula Not Shown complete matchings between contiguous levels, such that the heaviest path formed by the arcs in the matchings has a minimum weight. The problem, introduced by Carraresi and Gallo (1984) to model the rostering of bus drivers in order to achieve an even balance of the workload among the workers, though frequently cited, seems to have never been applied or extended to more general cases. In this paper, we discuss one possible extension, that is the introduction of multicommodity aspects to model different classes of workers
Monitor Optimization in Petri Net Control
No full textDeadlock Prevention and Liveness Enforcement in Petri nets are mostly addressed with monitor-based methods, designed indirectly using the concept of siphon or the theory of regions. The obtained control solutions are sometimes maximally permissive, but generally not optimal in terms of the number of monitors, nor in the cost of the control subnet. This paper proposes an optimization approach aiming at the direct design of the monitors, that allows for an easy formalization of the various control objectives. An efficient solution scheme, based on a branch-and-bound approach is also presented. The proposed monitor design algorithm yields significant improvements over known benchmark problems
On the complexity of graph tree partition problems
No full textAbstractThis paper concerns the optimal partition of a graph into p connected clusters of vertices, with various constraints on their topology and weight. We consider different objectives, depending on the cost of the trees spanning the clusters. This rich family of problems mainly applies to telecommunication network design, but it can be useful in other fields. We achieve a complete characterization of its computational complexity, previously studied only for special cases: a polynomial algorithm based on a new matroid solves the easy cases; the others are strongly NP-hard by direct reduction from SAT. Finally, we give results on special graphs
- …
