检索结果-内蒙古大学图书馆

On the number of local minima for the multidimensional assignment problem

JOURNAL OF COMBINATORIAL OPTIMIZATION 2007年第1期13卷 1-18页

作者： Grundel, Don A. Krokhmal, Pavlo A. Oliveira, Carlos A. S. Pardalos, Panos M. Univ Iowa Dept Mech & Ind Engn Seamans Ctr Engn Arts & Sci 2403 Iowa City IA 52242 USA Air Armament Ctr Div Anal Eglin AFB FL 32542 USA Oklahoma State Univ Sch Ind Engn & Management Stillwater OK 74078 USA Univ Florida Dept Ind & Syst Engn Ctr Appl Optimizat Gainesville FL 32611 USA

The multidimensional assignment problem (MAP) is an NP-hard combinatorial optimization problem occurring in many applications, such as data association, target tracking, and resource planning. As many solution approaches to this problem rely, at least partly, on local neighborhood search algorithms, the number of local minima affects solution difficulty for these algorithms. This paper investigates the expected number of local minima in randomly generated instances of the MAP. Lower and upper bounds are developed for the expected number of local minima, E[M], in an MAP with iid standard normal coefficients. In a special case of the MAP, a closed-form expression for E[M] is obtained when costs are iid continuous random variables. These results imply that the expected number of local minima is exponential in the number of dimensions of the MAP. Our numerical experiments indicate that larger numbers of local minima have a statistically significant negative effect on the quality of solutions produced by several heuristic algorithms that involve local neighborhood search.

关键词： multidimensional assignment problem random costs combinatorial optimization local minima neighborhood search

来源：评论

学校读者我要写书评

暂无评论

Sequential constraint augmentation with variable neighbourhood search for the multidimensional assignment problem

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL SCIENCE AND ENGINEERING 2007年第3期3卷 184-193页

作者： Pasiliao, Eduardo L. Pardalos, Panos M. Air Force Res Lab 101 West Eglin Blvd Eglin AFB FL 32542 USA Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA

This work proposes the Sequential Constraint Augmentation (SCA) procedure for the multidimensional assignment problem (MAP). Although the two-dimensional assignment problem has been shown to be solvable in polynomial time, the problem becomes NP-hard when it is extended to three dimensions. We investigate the benefits of implementing an intra-permutation 2-exchange and variable neighbourhood search for the SCA. The variable neighbourhood approach utilises the intra-permutation 2 and n-exchanges and the inter-permutation 2-exchange. All three k-exchange neighbourhoods are motivated by the permutation formulation of the MAP. Computational results show that the SCA procedure provides a tight upper bound with little computational effort. Exploring our variable neighbourhood significantly improves the SCA solution within a relatively short amount of computation time.

关键词： multidimensional assignment problem combinatorial optimisation computational results

来源：评论

学校读者我要写书评

暂无评论

Asymptotic behavior of the expected optimal value of the multidimensional assignment problem

引用

MATHEMATICAL PROGRAMMING 2007年第2-3期109卷 525-551页

作者： Krokhmal, Pavlo A. Grundel, Don A. Pardalos, Panos M. Univ Iowa Dept Mech & Ind Engn Iowa City IA 52242 USA USAF Res Lab Munit Directorate Eglin AFB FL 32542 USA Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA

The multidimensional assignment problem (MAP) is a higher-dimensional version of the Linear assignment problem that arises in the areas of data association, target tracking, resource allocation, etc. This paper elucidates the question of asymptotical behavior of the expected optimal value of the large-scale MAP whose assignment costs are independent identically distributed random variables with a prescribed probability distribution. We demonstrate that for a broad class of continuous distributions the limiting value of the expected optimal cost of the MAP is determined by the location of the left endpoint of the support set of the distribution, and construct asymptotical bounds for the expected optimal cost.

关键词： multidimensional assignment problem random assignment problem expected optimal value asymptotical analysis convergence bounds

来源：评论

学校读者我要写书评

暂无评论

Randomized parallel algorithms for the multidimensional assignment problem

引用

APPLIED NUMERICAL MATHEMATICS 2004年第1期49卷 117-133页

作者： Oliveira, CAS Pardalos, PM Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA

The multidimensional assignment problem (MAP) is a combinatorial optimization problem arising in diverse applications such as computer vision and motion tracking. In the MAP, the objective is to match tuples of objects with minimum total cost. Randomized parallel algorithms are proposed to solve MAPs appearing in multi-sensor multi-target applications. A parallel construction heuristic is described, together with some variations, as well as a parallel local search heuristic. Experimental results using the proposed algorithms are discussed. (C) 2003 IMACS. Published by Elsevier B.V. All rights reserved.

关键词： multidimensional assignment problem parallel algorithms randomized algorithms heuristics

来源：评论

学校读者我要写书评

暂无评论

Randomized parallel algorithms for the multidimensional assignment problem

Randomized parallel algorithms for the multidimensional assi...

引用

3rd Workshop of the ERCIM-Working-Group-on-Matrix-Computations-and-Statitsics

作者： Oliveira, CAS Pardalos, PM Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA

关键词： multidimensional assignment problem parallel algorithms randomized algorithms heuristics

来源：评论

学校读者我要写书评

暂无评论

Optimising LTE Uplink Scheduling by Solving the multidimensional assignment problem 6

Optimising LTE Uplink Scheduling by Solving the Multidimensi...

引用

6th International ICST Conference on Mobile Networks and Management (MONAMI)

作者： Elsner, Raphael Muehleisen, Maciej Timm-Giel, Andreas Hamburg Univ Technol Inst Commun Networks Hamburg Germany

ISBN: (纸本)9783319162928;9783319162911

Inter-cell interference mitigation in LTE networks is important to improve the system throughput. Upcoming Cloud Radio Access Networks (C-RANs) allow controlling multiple cells at a single location enabling novel inter-cell coordination algorithms. Coordinated recourse allocation can be used to achieve optimal spectral efficiency through reduced inter-cell interference. In this paper the uplink resource allocation is optimised by deciding which user terminals served by different base stations should transmit on the same resources. A central meta-scheduler situated in the cloud is responsible for the optimisation. The optimisation is performed using heuristic algorithms to solve the underlying multidimensional assignment problem. The complexity is further reduced to a feasible size by only coordinating a subset of base stations. This way the problem can be solved for real world cellular deployments. The performance for different groupings of cooperatively managed base stations is investigated. Results show that coordinating resource assignment of multiple base stations improves the cell spectral efficiency in general and coordinating three sectors at the same site outperforms coordinating three base stations of different sites.

关键词： LTE Radio resource management Inter-cell interference coordination Base station grouping Interference mitigation Linear assignment problem multidimensional assignment problem IMT-Advanced C-RAN

来源：评论

学校读者我要写书评

暂无评论

Ant Colony Optimization Heuristic for the multidimensional assignment problem in Target Tracking

Ant Colony Optimization Heuristic for the Multidimensional A...

引用

2008 IEEE Radar Conference

作者： Bozdogan, Ali Onder Efe, Murat Ankara Univ Fac Engn Dept Elect Engn TR-06100 Ankara Turkey

ISBN: (纸本)9781424415380

Associating measurements with targets is an important step in target tracking. With the increasing computational power, it became possible to use more complex association logic in tracking algorithms. Although it's optimal solution can be proved to be an NP hard problem, the multidimensional assignment enjoyed a renewed interest mostly due to Lagrangian relaxation approaches to its solution. Recently, it has been reported that randomized heuristic approaches surpassed the performance of Lagrangian relaxation algorithm especially in dense problems. In this paper, inspired by the success of randomized heuristic method, we investigate a different stochastic approach, the biologically inspired ant colony optimization to solve the NP hard multidimensional assignment problem.

关键词： multidimensional assignment problem SD assignment ant colony optimization target tracking

来源：评论

学校读者我要写书评

暂无评论

A map-reduce lagrangian heuristic for multidimensional assignment problems with decomposable costs

引用

PARALLEL COMPUTING 2013年第11期39卷 653-668页

作者： Tauer, Gregory Nagi, Rakesh SUNY Buffalo Dept Ind & Syst Engn Buffalo NY 14260 USA Univ Illinois Dept Ind & Enterprise Syst Engn Urbana IL 61801 USA

Data association is the problem of identifying when multiple data sources have observed the same entity. Central to this effort is the multidimensional assignment problem, which is often used to formulate data association problems. The nature of data association problems dictate that solution methods for the multidimensional assignment problem must return results promptly, and work on large data sets. The contribution of this work is to describe a Lagrangian relaxation based heuristic for the multi-dimensional assignment problem with decomposable costs that can be largely implemented in a map-reduce framework and thus easily distributed across a cluster of computers. Distribution allows the heuristic to address run time and large data requirements of data association. The developed algorithm is tested on a synthesized dataset, and shown to achieve an optimality gap ranging from 0.00008% to 0.6% for dense (no filtering) problems having 10,000 observation. Distribution of the algorithm was found to offer a significant reduction in run time on 30,000 observation problems for an 8 node computing cluster with 96 processors over a single node with 12 processors. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Data association multidimensional assignment problem Lagrangian heuristic Map-reduce framework

来源：评论

学校读者我要写书评

暂无评论

Asymptotic properties of random multidimensional assignment problems

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2004年第3期122卷 487-500页

作者： Grundel, DA Oliveira, CAS Pardalos, PM Univ Florida Dept Ind & Syst Engn Ctr Appl Optimizat Gainesville FL 32611 USA

The multidimensional assignment problem ( MAP) is an NP-hard combinatorial optimization problem occurring in many applications, such as data association. In this paper, we prove two conjectures made in Ref. 1 and based on data from computational experiments on MAPs. We show that the mean optimal objective function cost of random instances of the MAP goes to zero as the problem size increases, when assignment costs are independent exponentially or uniformly distributed random variables. We prove also that the mean optimal solution goes to negative infinity when assignment costs are independent normally distributed random variables.

关键词： multidimensional assignment problem combinatorial optimization asymptotic results

来源：评论

学校读者我要写书评

暂无评论

The constant objective value property for multidimensional assignment problems

引用

DISCRETE OPTIMIZATION 2016年 19卷 23-35页

作者： Custic, Ante Klinz, Bettina Graz Univ Technol Inst Optimierung & Diskrete Math Steyrergasse 30 A-8010 Graz Austria

An instance of a combinatorial optimization problem is said to have the constant objective value property (COVP) if every feasible solution has the same objective function value. In this paper our goal is to characterize the set of all instances with the COVP for multidimensional assignment problems. Our central result deals with planar d-dimensional assignment problems. We show that such constant objective value instances are characterized by so-called sum-decomposable arrays with appropriate parameters. This adds to the known result for the axial d-dimensional case. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Constant objective value Admissible transformation multidimensional assignment problem Sum-decomposable array

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：