排序方式: 共有13条查询结果,搜索用时 31 毫秒
1.
Roberto Montemanni 《4OR: A Quarterly Journal of Operations Research》2003,1(3):257-260
A survey of the results described in the authors PhD thesis (Montemanni 2001) is presented. The thesis, which was supervised by Prof. Derek H. Smith and Dr. Stuart M. Allen, has been defended in January 2002 at the University of Glamorgan (U.K.). The thesis proposes new heuristic algorithms, based on well-known meta-heuristic paradigms, and new lower bounding techniques, based on linear programming, for the fixed spectrum frequency assignment problem.Received: May 2003, Revised: May 2003, AMS classification:
90C27, 90C59,05C90, 90C05Roberto Montemanni: Present address: Istituto Dalle Molle di Studi sullIntelligenza Artificiale (IDSIA), Galleria 2, 6928 Manno-Lugano, Switzerland (e-mail: roberto@idsia.ch) 相似文献
2.
Roberto Montemanni Parvaz Mahdabi 《Journal of Mathematical Modelling and Algorithms》2011,10(2):145-162
A matheuristic approach, where concepts from linear programming are integrated into an evolutionary algorithm, is proposed.
It is tested on a problem arising in wireless sensor networks: a topology with minimum total power expenditure, that connects
a source node to all the other nodes of the network, has to be identified. Experimental results are presented. 相似文献
3.
Journal of Optimization Theory and Applications - This paper explores a new approach to reduce the maximum clique problem associated with permutation Hamming graphs to smaller clique problems. The... 相似文献
4.
Lower Bounds for Fixed Spectrum Frequency Assignment 总被引:1,自引:0,他引:1
Determining lower bounds for the sum of weighted constraint violations in fixed spectrum frequency assignment problems is important in order to evaluate the performance of heuristic algorithms. It is well known that, when adopting a binary constraints model, clique and near-clique subproblems have a dominant role in the theory of lower bounds for minimum span problems. In this paper we highlight their importance for fixed spectrum problems. We present a method based on the linear relaxation of an integer programming formulation of the problem, reinforced with constraints derived from clique-like subproblems. The results obtained are encouraging both in terms of quality and in terms of computation time. 相似文献
5.
János Barta Valeria Leggieri Roberto Montemanni Paolo Nobili Chefi Triki 《Computational Optimization and Applications》2011,49(1):193-212
In this paper we deal with a probabilistic extension of the minimum power multicast (MPM) problem for wireless networks. The
deterministic MPM problem consists in assigning transmission powers to the nodes, so that a multihop connection can be established
between a source and a given set of destination nodes and the total power required is minimized. We present an extension to
the basic problem, where node failure probabilities for the transmission are explicitly considered. This model reflects the
necessity of taking uncertainty into account in the availability of the hosts. The novelty of the probabilistic minimum power
multicast (PMPM) problem treated in this paper consists in the minimization of the assigned transmission powers, imposing
at the same time a global reliability level to the solution network. An integer linear programming formulation for the PMPM
problem is presented. Furthermore, an exact algorithm based on an iterative row and column generation procedure, as well as
a heuristic method are proposed. Computational experiments are finally presented. 相似文献
6.
Roberto Montemanni Luca Maria Gambardella 《4OR: A Quarterly Journal of Operations Research》2005,3(4):315-328
Many real problems can be modelled as robust shortest path problems on digraphs with interval costs, where intervals represent
uncertainty about real costs and a robust path is not too far from the shortest path for each possible configuration of the
arc costs.
In this paper we discuss the application of a Benders decomposition approach to this problem.
Computational results confirm the efficiency of the new algorithm. It is able to clearly outperform state-of-the-art algorithms
on many classes of networks. For the remaining classes we identify the most promising algorithm among the others, depending
of the characteristics of the networks.
Received: September 2004 / Accepted: March 2005
AMS classification:
90C47, 52B05, 90C57
The work was partially supported by the European Commission IST projects MOSCA (IST-2000-29557) and BISON (IST-2001-38923).
All correspondence to: Roberto Montemanni 相似文献
7.
Ant colony system is a well known metaheuristic framework, and many efficient algorithms for different combinatorial optimization problems have been derived from this general framework. In this paper some directions for improving the original framework when a strong local search routine is available, are identified. In particular, some modifications able to speed up the method and make it competitive on large problem instances, on which the original framework tends to be weaker, are described. The resulting framework, called Enhanced Ant Colony System is tested on three well-known combinatorial optimization problems arising in the transportation field. Many new best known solutions are retrieved for the benchmarks available for these optimization problems. 相似文献
8.
The Minimum Power Multicast Problem arises in wireless sensor networks and consists in assigning a transmission power to each
node of a network in such a way that the total power consumption over the network is minimized, while a source node is connected
to a set of destination nodes, toward which a message has to be sent periodically. A new mixed integer programming model for
the problem, based on paths, is presented. A practical exact algorithm based on column generation and branch and price is
derived from this model. A comparison with state-of-the-art exact methods is presented, and it is shown that the new approach
compares favorably to other algorithms when the number of destination nodes is moderate. Under this condition, the proposed
method is able to solve previously unmanageable instances. 相似文献
9.
Permutation codes (or permutation arrays) have received considerable interest in recent years, partly motivated by a potential
application to powerline communication. Powerline communication is the transmission of data over the electricity distribution
system. This environment is rather hostile to communication and the requirements are such that permutation codes may be suitable.
The problem addressed in this study is the construction of permutation codes with a specified length and minimum Hamming distance,
and with as many codewords (permutations) as possible. A number of techniques are used including construction by automorphism
group and several variations of clique search based on vertex degrees. Many significant improvements are obtained to the size
of the best known codes. 相似文献
10.
Most papers on permutation codes have concentrated on the minimum Hamming distance of the code. An (n, d) permutation code (or permutation array) is simply a set of permutations on n elements in which the Hamming distance between any pair of distinct permutations (or codewords) is at least d. An (n, 2e + 1) or (n, 2e + 2) permutation code is able to correct up to e errors. These codes have a potential application to powerline communications. It is known that in an (n, 2e) permutation code the balls of radius e surrounding the codewords may all be pairwise disjoint, but usually some overlap. Thus an (n, 2e) permutation code is generally unable to correct e errors using nearest neighbour decoding. On the other hand, if the packing radius of the code is defined as the largest value of e for which the balls of radius e are all pairwise disjoint, a permutation code with packing radius e can be denoted by [n, e]. Such a permutation code can always correct e errors. In this paper it is shown that, in almost all cases considered, the number of codewords in the best [n, e] code found is substantially greater than the largest number of codewords in the best known (n, 2e + 1) code. Thus the packing radius more accurately specifies the requirement for an e-error-correcting permutation code than does the minimum Hamming distance. The techniques used include construction by automorphism group and several variations of clique search They are enhanced by two theoretical results which make the computations feasible. 相似文献