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

generalized cover facet inequalities for the generalized assignment problem

OPTIMIZATION 2010年第2期59卷 223-233页

作者： Gottlieb, Elsie Sterbin CUNY Baruch Coll Dept Stat & Comp Informat Syst Zicklin Sch Business New York NY 10021 USA

The generalized assignment problem is that of finding an optimal assignment of agents to tasks, where each agent may be assigned multiple tasks and each task is performed exactly once. This is an NP-complete problem. Algorithms that employ information about the polyhedral structure of the associated polytope are typically more effective for large instances than those that ignore the structure. A class of generalized cover facet-defining inequalities for the generalized assignment problem is derived. These inequalities are based upon multiple knapsack constraints and are derived from generalized cover inequalities.

关键词： generalized assignment problem knapsack problem special ordered set facet inequalities generalized cover

来源：评论

学校读者我要写书评

暂无评论

THE generalized assignment problem - VALID INEQUALITIES AND FACETS

引用

MATHEMATICAL PROGRAMMING 1990年第1期46卷 31-52页

作者： GOTTLIEB, ES RAO, MR NYU STERN SCH BUSINESSNEW YORKNY 10003

Three classes of valid inequalities based upon multiple knapsack constraints are derived for the generalized assignment problem. General properties of the facet defining inequalities are discussed and, for a special case, the convex hull is completely characterized. In addition, we prove that a basic fractional solution to the linear programming relaxation can be eliminated by a facet defining inequality associated with an individual knapsack constraint.

关键词： facets generalized assignment problem integer polytope knapsack problem special ordered sets

来源：评论

学校读者我要写书评

暂无评论

Novel parallel hybrid genetic algorithms on the GPU for the generalized assignment problem

引用

JOURNAL OF SUPERCOMPUTING 2022年第1期78卷 144-167页

作者： Huang Zhi-Bin Fu Guang-Tao Dong Dan-Yang Xiao Chen Ding Zhe-Lun Dai Zhi-Tao Beijing Univ Posts & Telecommun BUPT Sch Comp Sci Beijing Key Lab Intelligent Telecommun Software & Beijing 100876 CO Peoples R China

The emergence of GPU-CPU heterogeneous architecture has led to a significant paradigm shift in parallel programming. How to effectively implement Parallel Genetic Algorithm (GA) in these environments has become one of the current hot issues. GA's calculation and operators are closely related to specific problems, thereby significantly affecting the acceleration method of GA algorithms. The generalized assignment problem (GAP) is a classic NP-hard combinatorial optimization problem. The more widely used genetic algorithms to solve the GAP in the CPU are difficult to be parallelized in a GPU environment due to severe data dependencies. To address this problem, two algorithms suitable for the implementation on the GPU are proposed, namely RPE algorithm and NNE algorithm, which obtain significant performance speedup by alleviating data dependencies and mutually exclusive synchronization overheads. At the same time, considering the new GPU architecture features and programming models, three different granular implementations of parallel genetic algorithms to solve the GAP are proposed, namely GPGA(thread), GPGA(warpsp) and GPGA(cgroup), by utilizing the warp-specialization technology and the cooperative group mechanism. GPGA series algorithms obtain better solution quality and very significant performance improvements compared with Serial GA, GTS (the GPU-CPU hybrid implementation of Scatter Search with Tabu lists) and Lagrange Relaxation algorithm on a CPU by solving 16 typical large-scale GAP instances.

关键词： Parallel genetic algorithms GPU Warp specialization Cooperative group generalized assignment problem

来源：评论

学校读者我要写书评

暂无评论

TABU SEARCH FOR THE MULTILEVEL generalized assignment problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1995年第1期82卷 176-189页

作者： LAGUNA, M KELLY, JP GONZALEZVELARDE, JL GLOVER, F UNIV COLORADO GRAD SCH BUSINESS & ADMBOULDERCO 80309 ITESM CTR SISTEMAS MFGMEXICO CITY 64849MEXICO

The multilevel generalized assignment problem (MGAP) differs from the classical GAP in that agents can perform tasks at more than one efficiency level. Important manufacturing problems, such as lot sizing, can be formulated as MGAPs;however, the large number of variables in the related 0-1 integer program makes the use of commercial optimization packages impractical. In this paper, we present a heuristic approach to the solution of the MGAP, which consists of a novel application of tabu search (TS). Our TS method employs neighborhoods defined by ejection chains, that produce moves of greater power without significantly increasing the computational effort.

关键词： TABU SEARCH generalized assignment problem LOT SIZING RESOURCE ALLOCATION

来源：评论

学校读者我要写书评

暂无评论

A SET PARTITIONING HEURISTIC FOR THE generalized assignment problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1994年第1期72卷 167-174页

作者： CATTRYSSE, DG SALOMON, M VANWASSENHOVE, LN ERASMUS UNIV ROTTERDAM POB 1738 3000 DR ROTTERDAM NETHERLANDS KATHOLIEKE UNIV LEUVEN B-3001 LOUVAIN BELGIUM INSEAD F-77305 FONTAINEBLEAU FRANCE

This paper discusses a heuristic for the generalized assignment problem (GAP). The objective of GAP is to minimize the costs of assigning J jobs to M capacity constrained machines, such that each job is assigned to exactly one machine. The problem is known to be NP-Hard, and it is hard from a computational point of view as well. The heuristic proposed here is based on column generation techniques, and yields both upper and lower bounds. On a set of relatively hard test problems the heuristic is able to find solutions that are on average within 0.13% from optimality.

关键词： generalized assignment problem SET PARTITIONING COLUMN GENERATION DUAL ASCENT

来源：评论

学校读者我要写书评

暂无评论

ALGORITHMS FOR THE MULTI-RESOURCE generalized assignment problem

引用

MANAGEMENT SCIENCE 1991年第6期37卷 695-713页

作者： GAVISH, B PIRKUL, H OHIO STATE UNIV COLL BUSINESSCOLUMBUSOH 43210

The multi-resource generalized assignment problem is encountered when a set of tasks have to be assigned to a set of agents in a way that permits assignment of multiple tasks to an agent subject to the availability of a set of multiple resources consumed by that agent. This problem differs from the generalized assignment problem in that an agent consumes not just one but a variety of resources in performing the tasks assigned to him. This paper develops effective solution procedures for the multi-resource generalized assignment problem. Various relaxations of the problem are studied and theoretical relations among these relaxations are pointed out. Rules for reducing problem size are discussed and are shown to be effective through computational experiments. Heuristic solution procedures and an efficient branch and bound procedure are developed. Results of computational experiments testing these procedures are reported.

关键词： combinatorial optimization Lagrangian relaxation subgradient optimization generalized assignment problem

来源：评论

学校读者我要写书评

暂无评论

Algorithms for the Min-max Regret generalized assignment problem with Interval Data

Algorithms for the Min-max Regret Generalized Assignment Pro...

引用

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：