Buradasınız

A New Algorithm for Minimum Cost MRGAP

Journal Name:

Publication Year:

Abstract (2. Language): 
This paper introduces an algorithm based on independent and combined strategies of surrogate constraint relaxation and scatter search coupled with simple Tabu search, subgradient optimization, and Lagrangean relaxation. The key contribution of this research is the development of effective RAMP and Primal-Dual RAMP algorithms for the MRGAP. Assignment problems involve assigning a set of jobs at hand to another set of agents which are limited in resources. Depending on the number of constraints, several different types of assignment problems can be formulated. The paper discusses the formulation of such a problem and an algorithm produced to solve these problems. Computational results are provided as a basis of comparison with several algorithms.

REFERENCES

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.

Thank you for copying data from http://www.arastirmax.com