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

IEEE International Conference on Industrial Engineering and Engineering Management

作者： Wu, W. Iori, M. Martello, S. Yagiura, M. Nagoya Univ Nagoya Aichi Japan Univ Modena & Reggio Emilia Reggio Emilia Italy Univ Bologna Bologna Italy

ISBN: (纸本)9781479964109

Many real life optimization problems do not have accurate estimates of the problem parameters at the optimization phase. For this reason, the min-max regret criteria are widely used to obtain robust solutions. In this paper we consider the generalized assignment problem (GAP) with min-max regret criterion under interval costs. We show that the decision version of this problem is Sigma(p)(2)-complete. We present two heuristic methods: a fixed-scenario approach and a dual substitution algorithm. For the fixed-scenario approach, we show that solving the classical GAP under a median-cost scenario leads to a solution of the min-max regret GAP whose objective function value is within twice the optimal value. We also propose exact algorithms, including a Benders' decomposition approach and branch-and-cut methods which incorporate various methodologies, including Lagrangian relaxation and variable fixing. The resulting Lagrangian-based branch-and-cut algorithm performs satisfactorily on benchmark instances.

关键词： generalized assignment problem min-max regret branch-and-cut Benders' decomposition variable fixing Lagrangian relaxation heuristics

来源：评论

学校读者我要写书评

暂无评论

Active Measurement of the Available Transfer Rate Used in an Algorithm for generalized assignment problem 11

Active Measurement of the Available Transfer Rate Used in an...

引用

11th International Symposium on Electronics and Telecommunications (ISETC)

作者： Ivanciu, Iustin Alexandru Rus, Andrei Bogdan Dobrota, Virgil Domingo-Pascual, Jordi Tech Univ Cluj Napoca Commun Dept Cluj Napoca Romania Univ Politecn Cataluna Comp Architecture Dept Barcelona Spain

ISBN: (纸本)9781479972678

This paper proposes a solution for active measurement of the Available Transfer Rate needed in a multi-tunnel architecture with a smart mobile router offering uninterrupted services for its wireless customers. It simultaneously uses several wireless/mobile access networks to the Internet in order to reach the service continuity gateway located somewhere in a broadband network. This customer-oriented approach uses the measurements to select the tunnels between the router and the gateway. Furthermore an algorithm for solving the generalized assignment problem minimizes the costs. The allocation decision must be taken once every second in order to obtain the minimum possible cost.

关键词： Available Transfer Rate generalized assignment problem

来源：评论

学校读者我要写书评

暂无评论

Recent metaheuristic algorithms for the generalized assignment problem

Recent metaheuristic algorithms for the generalized assignme...

引用

International Conference on Informatics Research for Development of Knowledge Society Infrastructure

作者： Yagiura, M Ibaraki, T Kyoto Univ Grad Sch Informat Kyoto 6068501 Japan

ISBN: (纸本)0769521509

The generalized assignment problem is a classical combinatorial optimization problem known to be NP-hard. It can model a variety of real world applications in location, allocation, machine assignment, and so forth. In this paper we review recent metaheuristic algorithms we developed for this problem. The algorithms use the ejection chain approach, which is embedded in a neighborhood construction to create more complex and powerful moves. We also incorporate an automatic mechanism for adjusting search parameters, to maintain a balance between visits to the feasible and infeasible regions. Computational comparisons on benchmark instances show that the methods are very effective compared to other existing metaheuristic algorithms.

关键词： optimisation real-time systems computational complexity search problems heuristic programming metaheuristic algorithm generalized assignment problem combinatorial optimization problem NP-hard problem real world application ejection chain approach automatic mechanism feasible region infeasible region

来源：评论

学校读者我要写书评

暂无评论

A Constant Factor Approximation for the generalized assignment problem with Minimum Quantities and Unit Size Items

A Constant Factor Approximation for the Generalized Assignme...

引用

38th International Symposium on Mathematical Foundations of Computer Science (MFCS)

作者： Bender, Marco Thielen, Clemens Westphal, Stephan Univ Gottingen Inst Numer & Appl Math Lotzestr 16-18 D-37083 Gottingen Germany Univ Kaiserslautern Dept Matemat D-67663 Kaiserslautern Germany

ISBN: (纸本)9783642403132;9783642403125

We consider a variant of the generalized assignment problem (GAP) where the items have unit size and the amount of space used in each bin is restricted to be either zero (if the bin is not opened) or above a given lower bound (a minimum quantity). This problem is known to be strongly NP-complete and does not admit a polynomial time approximation scheme (PTAS). By using randomized rounding, we obtain a randomized 3.93-approximation algorithm, thereby providing the first nontrivial approximation result for this problem.

关键词： generalized assignment problem combinatorial optimization approximation algorithms randomized rounding

来源：评论

学校读者我要写书评

暂无评论

Minimum Risk generalized assignment problem and Its Particle Swarm Optimization Algorithm

Minimum Risk Generalized Assignment Problem and Its Particle...

引用

International Symposium on Information and Automation (ISIA 2010)

作者： Bai, Xuejie Agr Univ Hebei Coll Sci Baoding 071001 Hebei Peoples R China

ISBN: (纸本)9783642198526

This paper addresses a new class of two-stage minimum risk generalized assignment problems, in which the resource amounts consumed are represented in the form of fuzzy variables with known possibility distributions. To calculate the credibility in the objective function, an approximation approach (AA) is employed to turn the fuzzy GAP model into an approximating one. Since traditional optimization methods cannot be used to solve the approximating GAP model, to overcome this difficulty, we design a hybrid algorithm integrating the approximation approach and particle swarm optimization (PSO). Finally, one numerical example with six tasks and three agents is given to illustrate the effectiveness of the designed intelligent algorithm.

关键词： generalized assignment problem Minimum risk criteria Two-stage fuzzy programming Approximation approach Particle swarm optimization

来源：评论

学校读者我要写书评

暂无评论

FUZZY generalized assignment problem WITH CREDIBILITY CONSTRAINTS

FUZZY GENERALIZED ASSIGNMENT PROBLEM WITH CREDIBILITY CONSTR...

引用

International Conference on Machine Learning and Cybernetics

作者： Bai, Xue-Jie Liu, Yan-Kui Shen, Si-Yuan Agr Univ Hebei Coll Sci Baoding 071001 Hebei Peoples R China Hebei Univ Coll Math & Comp Sci Baoding 071002 Hebei Peoples R China

ISBN: (纸本)9781424447053

In this paper, we firstly discuss some properties with respect to the credibility constraints. After that, we construct a new class of fuzzy generalized assignment problem with credibility constraints, in which the cost and time are uncertain and assumed to be characterized by fuzzy variables with known possibility distributions, The problem is a very changeable combinational optimization and it is always different to solve the programming problems using the classical algorithms. In some special cases, we can transform the objective and the credibility constraints into the equivalent linear form by means of the results that we deduce. As a consequence, we can solve it with standard software. Finally, we present one application example encountered by the Canadian Department of Transportation to demonstrate the proposed method.

关键词： generalized assignment problem credibility fuzzy variable independent

来源：评论

学校读者我要写书评

暂无评论

Particle Swarm Optimization for Two-Stage Fuzzy generalized assignment problem

Particle Swarm Optimization for Two-Stage Fuzzy Generalized ...

引用

6th International Conference on Intelligent Computing

作者： Bai, Xuejie Zhang, Yajing Liu, Fengtao Agr Univ Hebei Coll Sci Baoding 071001 Hebei Peoples R China

ISBN: (纸本)9783642149214

This paper constructs a new class of two-stage fuzzy generalized assignment problems in which the resource amounts consumed are uncertain and assumed to be characterized by fuzzy variables with known possibility distributions Motivated by the definitions of the positive part and negative part, we can transform the second-stage programming to its equivalent one To calculate the expected value in the objective function an approximation approach (AA) is employed to turn the fuzzy GAP model into an approximating one Since the approximating GAP model is neither linear nor convex traditional optimization methods cannot be used to solve it To overcome tins difficulty, we design a hybrid algorithm integrating the approximation approach and particle swami optimization (PSO) to solve the approximating two-stage GAP model Finally, one numerical example with six tasks and three agents is presented to illustrate the effectiveness of the designed hybrid algorithm

关键词： generalized assignment problem Two-stage fuzzy programming Approximation approach Particle swarm algorithm

来源：评论

学校读者我要写书评

暂无评论

Kernel Search for the generalized assignment problem 25

Kernel Search for the Generalized Assignment Problem

引用

25th IEEE International Conference on Intelligent Engineering Systems (INES)

作者： Janosikova, L'udmila Univ Zilina Fac Management Sci & Informat Zilina Slovakia

ISBN: (纸本)9781665444996

The generalized assignment problem is a classical optimization problem. Its modifications and extensions occur frequently in practical problems in the area of industry, telecommunications, computer networks, logistics, and many others. It is a hard problem, thus an optimal solution to practical instances cannot be calculated in an acceptable amount of time. That is why approximate methods must be applied. The kernel search is one of the recently developed heuristics that exploit a mathematical programming formulation of the problem. It is a general and simple heuristic framework based on the idea of decomposition of the original problem into smaller sub-problems and using a mathematical programming solver as a black-box to solve them. In this paper we propose an implementation of the kernel search algorithm for the general assignment problem and evaluate the efficiency of the algorithm on benchmark instances.

关键词： generalized assignment problem mathematical programming heuristics kernel search

来源：评论

学校读者我要写书评

暂无评论

Stability properties of the core in a generalized assignment problem

引用

GAMES AND ECONOMIC BEHAVIOR 2021年 130卷 211-223页

作者： Bando, Keisuke Kawasaki, Ryo Shinshu Univ Matsumoto Nagano Japan Tokyo Inst Technol Tokyo Japan

We show that the core of a generalized assignment problem satisfies two types of stability properties. First, the core is the unique stable set defined using the weak domination relation when outcomes are restricted to individually rational and pairwise feasible ones. Second, the core is the unique stable set with respect to a sequential domination relation that is defined by a sequence of weak domination relations that satisfy outsider independence. An equivalent way of stating this result is that the core satisfies the property commonly stated as the existence of a path to stability. These results add to the importance of the core in an assignment problem where agents' preferences may not be quasilinear. (C) 2021 The Author(s). Published by Elsevier Inc.

关键词： generalized assignment problem Core Stable set Path to stability

来源：评论

学校读者我要写书评

暂无评论

A Hybrid Heuristic in GPU-CPU Based on Scatter Search for the generalized assignment problem

A Hybrid Heuristic in GPU-CPU Based on Scatter Search for th...

引用

International Conference on Computational Science (ICCS)

作者： Souza, Danilo S. Santos, Haroldo G. Coelho, Igor M. Univ Fed Ouro Preto Ouro Preto MG Brazil Univ Estado Rio De Janeiro Rio De Janeiro RJ Brazil

In the generalized assignment problem (GAP), tasks must be allocated to machines with limited resources, in order to minimize processing costs. This problem has several industrial applications and often appears as a substructure in other combinatorial optimization problems. We propose a hybrid method inspired by Scatter Search metaheuristic, that efficiently generates a pool of solutions using a Tabu list criteria and an Ejection Chain mechanism. Common characteristics are extracted from the pool and solutions are combined by exploring a restricted search space, as a Binary Programming (BP) model. This method was implemented as a parallel approach to run in a Graphics Processing Unit (GPU). Experimental results show that the proposed method is very competitive to the algorithms found in the literature. On average, a gap of 0.09% is obtained over a set of 45 instances, when compared to lower bounds. Due to the integration of the method with an exact BP solver, it was capable of proving the optimality of small size instances, also finding new best known solutions for 21 instances. In terms of computational times, the proposed method performs on average 8 times faster than literature, also indicating that the proposed approach is scalable and robust for practical applications. (C) 2017 The Authors. Published by Elsevier B.V. Peer-review under responsibility of the scientific committee of the International Conference on Computational Science

关键词： Scatter Search Tabu Search Ejection Chain Binary Programming generalized assignment problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：