# A New Algorithm for Minimum Cost MRGAP

### Journal Name:

- European Journal of Economic and Political Studies

### Publication Year:

- 2009

### Key Words:

Author Name | University of Author |
---|---|

### REFERENCES

Alfandri L., Plateau, A. and Tolla, P. (2003) “A Path Relinking Algorithm for the GAP.”

Metaheuristics: Computer Decision-Making, 1-17.

Arora, S. and M. Puri. (1999) “Minimization of Makespan in Generalized Assignment

Problems.” Operations Research 36, 360-373.

Balachandran, V. (1976) “An Integer Generalized Transportation Model for Optimal

Job Assignment in Computer Networks.” Operations Research 24, 742-759.

Balachandran, B. V. and A. Zoltners. (1981) “An Interactive Audit-Staff Scheduling

Decision Support System.” The Accounting Review 16(4), 801-812.

Balas, E., and C. Martin. (1980) “Pivot and Complement – A Heuristic for 0-1

Programming.” Management Science 26(1), 86-96.

Balas, E., and E. Zemel. (1980) “An Algorithm for Large Zero-One Knapsack

Problems.” Operations Research 28, 1130-1154.

Barcello, J. and J. Casanovas. (1984) “A Heuristic Lagrangean Algorithm for the

Capacitated Plant Location Problem.” European Journal of Operational Research

15, 212-226.

Ban Hadj-Alouane, A., J. C. Bian, and K. G. Murty. (1999) “A Hybrid

Genetic/Optimization Algorithm for a Task Allocation Problem.” Journal of

Scheduling 2, 189-201.

Cattrysse, D., M. Salomon and L. Van Wassenhove. (1994) “A Set Partitioning Heuristic

for the Generalized Assignment Problem.” European Journal of Operational

Research 72, 167-174.

Chalmet, K. and L. Gelders. (1976) “Lagrangean Relaxations for a Generalized

Assignment Type Problem.” Proceedings of Second European Congress on

Operations Research, 103-109.

Chalmet, K. and L. Gelders. (1977) “Lagrangean Relaxations for a Generalized

Assignment Type Problem.” Advances in Operations Research, 103-109.

Chu, P., and J. Beasley. (1997) “A Genetic Algorithm for the Generalized Assignment

Problem.” Computers and Operations Research 24, 17-23.

DeMaio, A. and C. Roveda. (1971) “An All Zero-One Algorithm for a Certain Class of

Transportation Problems.” Operations Research 19, 1406-1418.

Erlenkotter, D. (1978) “A Dual Based Procedure for Uncapacitated Facility Location.”

Operations Research 26, 992-1009.

Ernst, A., H. Jiang, and M. Krishnamoorthy. (2001). “Exact Solutions to Task Allocation

Problems.”

Everett, H. (1963) “Generalized Lagrange Multiplier Method for Solving Problems of

Optimum Allocation of Resources.” Operations Research 11, 399-417.

Fisher, M., and R. Jaikumar. (1981) “A Generalized Assignment Heuristic for Vehicle

Routing.” Networks 11, 109-124.

Fisher, M., L. (1985) “An Applications Oriented Guide to Lagrangean Relaxation.”

Management Science 15(2), 10-21.

Fisher, M., R. Jaikumar and L. Van Wassenhove. (1986) “A Multiplier Adjustment

Algorithm for the Generalized Assignment Problem.” Management Science

32(9), 1095-1103.

French, A., P., and J. Wilson. (2002) “Heuristic Solution Methods for the Multilevel

Generalized Assignment Problem.” Journal of Heuristics 8, 143-153.

Freville, A. and Plateau, G. (1991) “An Exact Search for the Solution of the Surrogate

Dual of the 0 – 1 Bidimensional Knapsack Problem.” European Journal of

Operational Research 68, 413-421.

Gavish, B., and H. Pirkul. (1982) “Allocation of Databases and Processors in a

Distributed Computer System.” Management of Distributed Data Processing, J.

Akota ed., North Holland Publishing Company, 215-231.

Gavish, B. and H. Pirkul. (1985) “Efficient Algorithms for Solving Multiconstraint Zero-

One Knapsack Problems to Optimality.” Mathematical Programming 31, 78-105.

Gavish, B. and H. Pirkul. (1986) “Computer and Database Location in Distributed

Computer Systems.” IEEE Transactions on Computers 35(7), 583-590.

Gavish, B. and H. Pirkul. (1991) “Algorithms for the Multi-Resource Generalized

Assignment Problem.” Management Science 37(6), 695-713.

Gavish, B., Glover, F. and Pirkul, H. (1991) “Surrogate Constraints in Integer

Programming.” Journal of Information & Optimization Sciences 12, No. 2, 219-

228.

Geoffrion, A. (1974) “Lagrangean Relaxation and its Uses in Integer Programming.”

Mathematical Programming Study 2, 82-114.

Gilmore, P. and R. Gomory. (1966) “Theory and Computation of Knapsack Problems.”

Operations Research 14, 1045-1074.

Glover, F. (1965) “A Multiphase-Dual Algorithm for the Zero-One Integer

Programming Problem.” Operations Research 19, 1406-1418.

Glover. F. (1968) “Surrogate Constraints.” Operations Research 16, 741-749.

Glover. F. (1975) “Surrogate Constraint Duality in Mathematical Programming.”

Operations Research 23, 434-451.

Glover, F. (1998) “A Template for Scatter Search and Path Relinking.” Artificial

Evolution, Lecture Notes in Computer Science 1363, 13-54.

Glover, F., Laguna, M. and Marti, R. (2000) “Fundamentals of Scatter Search and Path

Relinking.” Control and Cybernetics 39, 653-684.

Glover, F. (2003) “Tutorial on Surrogate Constraint Approaches for Optimization in

Graphs.” Journal of Heuristics 9, 175-227.

Gottlieb, J. (2001) “On the Feasibility Problem of Penalty-Based Evolutionary

Algorithms for Knapsack Problems.” EvoWorkshop 2001, LNCS 2037, 50-59.

Greenberg, H. and W. P. Pierskalla. (1970) “Surrogate Mathematical Programming.”

Operations Research 18, 924-939.

Held, M. and R. Karp. (1970) “The Traveling Salesman Problem and Minimum

Spanning Trees.” Operations Research 18, 1138-1162.

Hill, R. R. and Reilly, C. H. (2000) “The Effects of Coefficient Correlation Structure in

Two-Dimensional Knapsack Problems on Solution Procedure Performance.”

Management Science 46, No. 2, 302-317.

Jornsten, K. and M. Nasberg. (1986) “A New Lagrangean Relaxation Approach to the

Generalized Assignment Problem.” European Journal of Operations Research

27, 313-323.

Laguna, M., J. Kelly, J. L. Gonzalez-Velarde and F. Glover. (1995) “Tabu Search for the

Multilevel Generalized Assignment Problem.” European Journal of Operations

Research 82, 176-189.

Lewis, M., Alidaee, B. and Kochenberger, G. (2004) “Modeling and Solving the Task

Allocation Problem As an Unconstrained Quadratic Binary Program.” Operations

Research Letter.

Lorena, L.A. and F.B. Lopez. (1994) “A Surrogate Heuristic for Set Covering

Problems.” European Journal of Operational Research 79, 138-450.

Martello, S. and P. Toth. (1981) “An Algorithm for the Generalized Assignment

Problem.” Operational Research, J.P. Brans, ed. North-Holland, 589-603.

Martello, S. and P. Toth. (1987) “Linear Assignment Problems.” Annals of Discrete

Mathematics 31, 259-282.

Martello, S. and P. Toth. (2003) “An Exact Algorithm for the Two-Constraint 0 – 1

Knapsack Problem.” Operations Research 51, No. 5. 826-835.

Mazzola, J., and S. Wilcox. (2001) “Heuristics for the Multi-Resource Generalized

Assignment Problem.” Naval Research Logistics 48, 468-483.

Murphy, R. A. (1986) “A Private Fleet Model with Multi-Stop Backhaul.” Optimal

Decision Systems.

Nakagawa, Y., and Miyazaki, S. (1981) “Surrogate Constraints Algorithm for Reliability

Optimization Problems with Two Constraints.” IEEE Transactions on Reliability

R-30, No.2, 175-180.

Narciso, M., and L. A. Lorena. (1999) “Lagrangean/Surrogate Relaxation for

Generalized Assignment Problems.” European Journal of Operational Research

114, 165-177.

Osorio. M. A., Glover, F. and P. Hammer. (2000) “Cutting and Surrogate Constraint

Analysis for Improved Multidimensional Knapsack Solutions.”

Rego, C. 2003. “Private Communication.”

Rego, C. and Leao, P. (2004) “A Scatter Search Tutorial for Graph-Based Permutation

Problems.” Metaheuristic Optimization via Memory and Evolution: Tabu Search

and Scatter Search, C. Rego and B. Alidaee (eds), Kluwer Academic Publishers,

1-24.

Rego, C. (2004) “RAMP: New Metaheuristic Framework for Combinatorial

Optimization.” Metaheuristic Optimization via Memory and Evolution: Tabu

Search and Scatter Search, C. Rego and B. Alidaee, Kluwer Academic

Publishers, 441-460.

Romeijn, H., and N. Piersma. (2000) “A Probabilistic Feasibility and Value Analysis of

the Generalized Assignment Problem.” Journal of Combinatorial Optimization 4,

325-355.

Resende, M. and Riberio, C. (2001) “A GRASP with Path Relinking for Private Virtual

Circuit Routing.” AT&T Labs Research Technical Report.

Resende, M. and Riberio, C. (2003) “GRASP with Path Relinking: Recent Advances and

Applications.” AT&T Labs Research Technical Report.

Ross, G. T. and R. M. Soland. (1975) “A Branch and Bound Algorithm for the

Generalized Assignment Problem.” Mathematical Programming 8, 91-103.

Ross, G. T. and R. M. Soland. (1977) “Modeling Facility Location Problems as

Generalized Assignment Problems.” Management Science 24(3), 345-356.

Ross, G. T. and R. M. Soland, and A. Zoltners. (1979) “Weighted Assignment Models

and Their Application.” Management Science 25(7), 683-696.

Ross, G. T. and R. M. Soland. (1980) “A Multi-criteria Approach to the Location of

Public Utilities.” European Journal of Operations Research 4, 307-321.

Shih, W. (1979) “A Branch and Bound Method for the Multi Constraint Zero-One

Knapsack Problem.” Journal of Operational Research Society 30, 369-378.

Shtub, A., and K. Kogan. (1998) “Capacity planning by the Dynamic Multi-Resource

Generalized Assignment Problem.” European Journal of Operational Research

105, 91-99.

Yagiura, M., T. Ibaraki, and F. Glover. (2004) “A Path Relinking Approach with Ejection

Chains for the Generalized Assignment Problem.” European Journal of

Operational Research, to appear.

Yagiura, M., T. Ibaraki, and F. Glover. (2004) “An Ejection Chain Approach for the

Generalized Assignment Problem.” INFORMS Journal on Computing 16(2), 133-

151.

Yagiura. M., S. Iwasaki, T. Ibaraki and Glover, F. (2004) “A Very Large-Scale

Neighborhood Search Algorithm for the Multi-Resource Generalized

Assignment Problem.” Discrete Optimization 1, 87-98.