47 research outputs found
Combining Linear and Non Linear Objectives in Spanning Tree Problems
No full textA classical approach to multicriteria problems asks for the optimization of a suitable linear combination of the objectives. In this work we address such problems when one of the objectives is the linear function, the other is a non-linear one and we seek for a spanning tree of a given graph which optimizes the combination of the two functions.We consider both maximization and minimization problems and present the complexity status of 56 such problems, giving, whenever possible, polynomial solution algorithms
On some Multicriteria Arborescence Problems: Complexity and Algorithms
No full textThe problems of finding an optimum arborescenceof a given digraph with respect to an objective function obtainedcombining linearly two (or more) objective functions of variouskinds are studied
Exact Solution of the SONET Ring Loading Problem
No full textIn this paper we address the problem of planning the capacity of the local rings in Synchronous Optical NETworks (SONET). We present efficient lower and upper bound procedures and a branch and bound algorithm which is able to find the exact solution of large instances within short computing times
The Base-Matroid and Inverse Combinatorial Optimization
No full textA new kind of matroid is introduced: this matroid is defined starting from any matroid and one of its bases, hence we call it Base-Matroid. Besides some properties of the base-matroid, a non trivial algorithm for the solution of the related matroid optimization problem is devised. The new matroid has application in the field of inverse combinatorial optimization problems
New Bounds for Optimum Traffic Assignment in Satellite Communication
No full textIn this paper we assume that a satellite has l receivingand transmitting antennas, and we are given a traffic matrix D tobe transmittedby interconnecting pairs of receiving-transmitting antennas, through anon board switch. We also assume that l is strictly smaller thanthe number of rowsand columns of D, that no preemption of thecommunications is allowed, and that changing the configuration ofthe switch requires a negligible time. We ask for aset of switch configurations that minimizes the totaltime occurring for transmitting the entire traffic matrix.We present some new lower bounds on the optimum solution value anda new technique to combine bounds which obtains a dominating value.We then presentfive heuristics: the first two are obtained modifying algorithmsfrom the literature; two others are obtained with standard techniques;the last algorithm is an implementation of a newand promising tabu search method which is called Exploring Tabu Search.Extensive computational experimentscompare the performances of the heuristics and that of the lower bound,on randomly generated instance
Solution of the cumulative assignment problem with a well-structured tabu search method
No full textThe Cumulative Assignment Problem is an NP-complete problemobtained by substituting the linear objective function of the classicLinear Assignment Problem, with a non-linear cumulative function.In this paper we present a first attempt to solve the Cumulative Assignment Problem with metaheuristic techniques.In particular we consider two standard techniques, namely the Simulated Annealing and the Multi-Start methods, and we describe the eXploring Tabu Search: a new structured Tabu Search algorithm which uses an iterative multi-level approach to improve the search.The new method is analyzed through extensive computational experiments and proves to be more effective than the standard methods
On Prize-CollectingTours and the Asymmetric Travelling Salesman Problem
No full textWe consider a special version of the Travelling Salesman Problemwhich is to determine a tour visitingeach vertex in the graph at most one time;if a vertex is left unrouted a given penalty has to be paid.The objectivefunction is to find a balance between these penalties and the cost of thetour. We call this problem the Profitable Tour Problem (PTP). If,in addition, to each vertex is associated a price andthere is a knapsack constraint which guarantees that a sufficiently largeprice is collected, we have the well knownPrice-Collecting Travelling Salesman Problem (PCTSP).In this paper we summarize the main results presented in the literature,then we give lower bounds for the asymmetric version of PTP and PCTSP. Moreoverwe show, through computational experiments, that large size instances of theAsymmetric PTP can be solved exactly
A Tree Partitioning Dynamic Policies for OVSF Codes Assignment in Wideband CDMA.
No full textThis paper proposes some novel techniques to accommodate users with different rate requirements in a Wideband CDMA system employing orthogonal variable spreading factor codes. Several static and dynamic code assignment strategies areput forth and their behavior investigated, in terms of call blocking probability and number of required reassignments. The efficiency they exhibit under various traffic profiles is demonstrated, quantitatively comparing their performance to some codeassignment schemes recently presented in literature
