Free Access

Technical Note—An Improved Dual Based Algorithm for the Generalized Assignment Problem

Monique Guignard
Monique Guignard
University of Pennsylvania, Philadelphia, Pennsylvania
Search for more papers by this author
,
Moshe B. Rosenwein
Moshe B. Rosenwein
AT&T Bell Laboratories, Holmdel, New Jersey
Search for more papers by this author

Monique Guignard

University of Pennsylvania, Philadelphia, Pennsylvania

Search for more papers by this author

Moshe B. Rosenwein

AT&T Bell Laboratories, Holmdel, New Jersey

Search for more papers by this author

Published Online:1 Aug 1989https://doi.org/10.1287/opre.37.4.658

Cited by
- An application of semi-Lagrangian relaxation to the generalised assignment problem
  Operations Research Letters, Vol. 67
- QuIP: Experimental design for expensive simulators with many Qualitative factors via Integer Programming
  8 May 2026 | Journal of Computational and Graphical Statistics
- (Pareto)-Optimization and greedy algorithm-based solutions for review and panel assignments
  20 February 2026 | Journal of Combinatorial Optimization, Vol. 51, No. 2
- AI-Driven Panel Assignment Optimization via Document Similarity and Natural Language Processing
  1 August 2025 | AI, Vol. 6, No. 8
- Generalized Assignment Problem
  24 February 2012
- Matheuristics: survey and synthesis
  15 April 2023 | International Transactions in Operational Research, Vol. 30, No. 6
- Dual-Based Method for Global Optimization of Impulsive Orbital Maneuvers
  28 November 2022 | The Journal of the Astronautical Sciences, Vol. 69, No. 6
- A new extended formulation of the Generalized Assignment Problem and some associated valid inequalities
  Discrete Applied Mathematics, Vol. 271
- A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems
- A transportation branch and bound algorithm for solving the generalized assignment problem
  11 February 2015 | International Journal of System Assurance Engineering and Management, Vol. 6, No. 3
- Managing RFID events in large-scale distributed RFID infrastructures
  3 February 2011 | Information Technology and Management, Vol. 12, No. 3
- On the usage of Lagrangean Relaxation for the convoy movement problem
  21 December 2017 | Journal of the Operational Research Society, Vol. 62, No. 4
- Decomposition Methods for Integer Programming
  15 February 2011
- Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization Technique
  European Journal of Operational Research, Vol. 206, No. 1
- Using an enhanced integer NSGA-II for solving the multiobjective Generalized Assignment Problem
- Generalized cover facet inequalities for the generalized assignment problem
  Optimization, Vol. 59, No. 2
- The Generation of Experimental Data for Computational Testing in Optimization
  26 October 2010
- Synthetic Optimization Problem Generation: Show Us the Correlations!
  Charles H. Reilly,
  29 June 2009 | INFORMS Journal on Computing, Vol. 21, No. 3
- An algorithm for the generalized quadratic assignment problem
  15 November 2007 | Computational Optimization and Applications, Vol. 40, No. 3
- Generalized Assignment Problem
- A Survey of the Generalized Assignment Problem and Its Applications
  18 January 2017 | INFOR: Information Systems and Operational Research, Vol. 45, No. 3
- En hommage à Joseph-Louis Lagrange et à Pierre Huard
  2 December 2006 | Annals of Operations Research, Vol. 149, No. 1
- Novel and Effective Integer Optimization Approach for the NSF Panel-Assignment Problem: A Multiresource and Preference-Constrained Generalized Assignment Problem
  12 November 2005 | Industrial & Engineering Chemistry Research, Vol. 45, No. 1
- An Algorithm for the Generalized Assignment Problem with Special Ordered Sets
  Journal of Heuristics, Vol. 11, No. 4
- The Generalized Assignment Problem and Extensions
- The elastic generalized assignment problem
  21 December 2017 | Journal of the Operational Research Society, Vol. 55, No. 12
- Effective algorithm and heuristic for the generalized assignment problem
  European Journal of Operational Research, Vol. 153, No. 1
- Lagrangean relaxation
  Top, Vol. 11, No. 2
- Logic cuts for multilevel generalized assignment problems
  European Journal of Operational Research, Vol. 151, No. 1
- Solving the Generalized Assignment Problem: An Optimizing and Heuristic Approach
  Robert M. Nauss,
  1 August 2003 | INFORMS Journal on Computing, Vol. 15, No. 3
- A Path Relinking Algorithm for the Generalized Assignment Problem
- An investigation of the relationship between problem characteristics and algorithm performance: a case study of the GAP
  IIE Transactions, Vol. 34, No. 3
- Combinatorial Optimisation Problems of the Assignment Type and a Partitioning Approach
- Generating Experimental Data for the Generalized Assignment Problem
  H. Edwin Romeijn,
  Dolores Romero Morales,
  1 December 2001 | Operations Research, Vol. 49, No. 6
- Heuristics for the multi‐resource generalized assignment problem
  3 August 2001 | Naval Research Logistics (NRL), Vol. 48, No. 6
- A Tabu search heuristic for the generalized assignment problem
  European Journal of Operational Research, Vol. 132, No. 1
- A Technical Review of Column Generation in Integer Programming
  Optimization and Engineering, Vol. 2, No. 2
- The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance
  Raymond R. Hill,
  Charles H. Reilly,
  1 February 2000 | Management Science, Vol. 46, No. 2
- Multivariate composite distributions for coefficients in synthetic optimization problems
  European Journal of Operational Research, Vol. 121, No. 1
- Integer-programming based algorithms and computational performance for terminal-drop zone assignment problems
- SOLVING LARGE REPLACEMENT PROBLEMS WITH BUDGET CONSTRAINTS
  31 May 2007 | The Engineering Economist, Vol. 45, No. 4
- A decomposition approach to a multi-period vehicle scheduling problem
  Omega, Vol. 27, No. 4
- Lagrangean/surrogate relaxation for generalized assignment problems
  European Journal of Operational Research, Vol. 114, No. 1
- A Lagrangian Dual-Based Branch-and-Bound Algorithm for the Generalized Multi-Assignment Problem
  June S. Park,
  Byung Ha Lim,
  Youngho Lee,
  1 December 1998 | Management Science, Vol. 44, No. 12-part-2
- Heuristic sensitivity analysis in a combinatoric environment: An exposition and case study
  European Journal of Operational Research, Vol. 108, No. 3
- Branch-and-Price: Column Generation for Solving Huge Integer Programs
  Cynthia Barnhart,
  Ellis L. Johnson,
  George L. Nemhauser,
  Martin W. P. Savelsbergh,
  Pamela H. Vance,
  1 June 1998 | Operations Research, Vol. 46, No. 3
- Evaluation of the growth of a new pulmonary trunk after the reconstruction of right ventricular outflow tract without using an external conduit
  1 May 1998 | The Japanese Journal of Thoracic and Cardiovascular Surgery, Vol. 46, No. 5
- Empirical comparison between two k -shortest path methods for the generalized assignment problem
  Journal of Information and Optimization Sciences, Vol. 19, No. 2
- Efficient cuts in Lagrangean ‘Relax-and-cut’ schemes
  European Journal of Operational Research, Vol. 105, No. 1
- A multiplier adjustment technique for the capacitated concentrator location problem
  Optimization Methods and Software, Vol. 10, No. 1
- A simple dual algorithm for the generalised assignment problem
  Journal of Heuristics, Vol. 2, No. 4
- Generating coefficients for optimization test problems with implicit correlation induction
- A two-stage heuristic approach for the newspaper delivery problem
  Computers & Industrial Engineering, Vol. 30, No. 3
- Relaxation heuristics for a generalized assignment problem
  European Journal of Operational Research, Vol. 91, No. 3
- Auxiliary tool allocation in flexible manufacturing systems
  European Journal of Operational Research, Vol. 89, No. 3
- Heuristics for the generalised assignment problem: simulated annealing and tabu search approaches
  1 December 1995 | Operations-Research-Spektrum, Vol. 17, No. 4
- The bottleneck generalized assignment problem
  European Journal of Operational Research, Vol. 83, No. 3
- Tabu search for the multilevel generalized assignment problem
  European Journal of Operational Research, Vol. 82, No. 1
- A GAP Formulation for Solving Production Planning Problems in Telecom Industry
- A set partitioning heuristic for the generalized assignment problem
  European Journal of Operational Research, Vol. 72, No. 1
- Lagrangean heuristics for location problems
  European Journal of Operational Research, Vol. 65, No. 3
- Solving large scale generalized assignment problems — An aggregation / disaggregation approach
  European Journal of Operational Research, Vol. 64, No. 1
- A survey of algorithms for the generalized assignment problem
  European Journal of Operational Research, Vol. 60, No. 3
- Personnel placement in a fuzzy environment
  Computers & Operations Research, Vol. 19, No. 2
- Generalized assignment problems
  9 June 2005
- A parallel insertion heuristic for vehicle routing with side constraints
  29 April 2008 | Statistica Neerlandica, Vol. 44, No. 3

Volume 37, Issue 4

July-August 1989

Pages 514-673

Article Information

Metrics

Information

Published Online:August 01, 1989

Cite as

Monique Guignard, Moshe B. Rosenwein, (1989) Technical Note—An Improved Dual Based Algorithm for the Generalized Assignment Problem. Operations Research 37(4):658-663.

https://doi.org/10.1287/opre.37.4.658

Keywords

programming, integer: an algorithm for the GAP

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Technical Note—An Improved Dual Based Algorithm for the Generalized Assignment Problem

Volume 37, Issue 4

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News