1,720,998 research outputs found
The monochromatic set partitioning problem.Presentato al convegno Airo 2010, 07-10 Settembre 2010, Villa San Giovanni (RC).
No full textOn the last few years several problems have been studied on a particular class of graphs, where each edge has a label (color) assigned to it.
Real applications for this class of problems arise in fields such as telecommunication or multimodal transport networks (edges of the same color can model transportation lines of the same type, or connections belonging to the same company). Moreover, the edge-labeled graphs can be of interest whenever we need some measure of homogeneity (or heterogeneity) regarding the edges in the solution we are looking for.
In this context we focalize our attention on the "monochromatic set partitioning problem" (MSP). Let G=(V,E) be an edge-colored graph. A sub-graph H of G is said to be monochromatic if all the edges of H have the same color and multicolored if no two edges of H have the same color.
A feasible solution for the MSP is a partitioning of G in monochromatic sub-graph. We look for a feasible solution containing the minimum number of such monochromatic sub-graph.
In our work we first prove the complexity of this problem. Then we propose a mathematical formulation and a polynomial case. Finally we present a meta-heuristic approach to solve the problem and show some preliminary computational results
A branch‐and‐bound algorithm for the double travelling salesman problem with two stacks
No full textThis article studies the double traveling salesman problem with two stacks. A number of requests have to be
served where each request consists in the pickup and
delivery of an item. All the pickup operations have to be
performed before any delivery can take place. A single
vehicle is available that starts from a depot, performs all
the pickup operations and returns to the depot. Then, it
performs all the delivery operations and returns to the
depot. The items are loaded in two stacks, each served
independently from the other with a last-in-first-out policy. The objective is the minimization of the total cost
of the pickup and delivery tours. We propose a branchand-bound approach to solve the problem. The algorithm
uses properties of the problem both to tighten the lower
bounds and to avoid the exploration of redundant subtrees. Computational results performed on benchmark
instances reveal that the algorithm outperforms the other
exact approaches for this problem
A cluster-lightening route reduction strategy for the vehicle routing problem with time windows
No full textAn Additive Branch-and-Bound Algorithm for the Pickup and Delivery Traveling Salesman Problem with LIFO or FIFO Loading
No full textThis paper introduces an additive branch-and-bound algorithm for two variants of the pickup and delivery traveling salesman problem in which loading and unloading operations have to be performed either in a Last-In-First-Out (LIFO) or in a First-In-First-Out (FIFO) order. Two relaxations are used within the additive approach: the assignment problem and the shortest spanning r-arborescence problem. The quality of the lower bounds is further improved by a set of elimination rules applied at each node of the search tree to remove from the problem arcs that cannot belong to feasible solutions because of precedence relationships. The performance of the algorithm and the effectiveness of the elimination rules are assessed on instances from the literature
The Labeled Maximum Matching Problem
No full textGiven a graph G where a label is associated with each edge, we address the problem of
looking for a maximum matching of G using the minimum number of different labels, namely
the labeled maximum matching problem. It is a relatively new problem whose application
is related to the timetabling problem. We prove it is NP-complete and present four different
mathematical formulations. Moreover, we propose an exact algorithm based on a branch-and-bound
approach to solve it. We evaluate the performance of our algorithm on a wide set of instances
and compare our computational times with the ones required by CPLEX to solve the proposed
mathematical formulations. Test results show the effectiveness of our procedure, that hugely
outperforms the solver
Lower and upper bounds for the spanning tree with minimum branch vertices
No full textWe study a variant of the spanning tree problem where we require that, for a given connected graph, the spanning tree to be found has the minimum number of branch vertices (that is vertices of the tree whose degree is greater than two). We provide four different formulations of the problem and compare different relaxations of them, namely Lagrangian relaxation, continuous relaxation, mixed integer-continuous relaxation. We approach the solution of the Lagrangian dual both by means of a standard subgradient method and an ad-hoc finite ascent algorithm based on updating one multiplier at the time. We provide numerical result comparison of all the considered relaxations on a wide set of benchmark instances. A useful follow-up of tackling the Lagrangian dual is the possibility of getting a feasible solution for the original problem with no extra costs. We evaluate the quality of the resulting upper bound by comparison either with the optimal solution, whenever available, or with the feasible solution provided by some existing heuristic algorithms
A hybrid exact approach for maximizing lifetime in sensor networks with complete and partial coverage constraints
Full text linkIn this paper we face the problem of maximizing the amount of time over which a set of target points, located in a given geographic region, can be monitored by means of a wireless sensor network. The problem is well known in the literature as Maximum Network Lifetime Problem (MLP). In the last few years the problem and a number of variants have been tackled with success by means of different resolution approaches, including exact approaches based on column generation techniques. In this work we propose an exact approach which combines a column generation approach with a genetic algorithm aimed at solving efficiently its separation problem. The genetic algorithm is specifically aimed at the Maximum Network α-Lifetime Problem (α-MLP), a variant of MLP in which a given fraction of targets is allowed to be left uncovered at all times; however, since α-MLP is a generalization of MLP, it can be used to solve the classical problem as well. The computational results, obtained on the benchmark instances, show that our approach overcomes the algorithms, available in the literature, to solve both MLP and α-MLP
- …
