Abstract
This paper investigates a real world assignment problem, which slightly differs from the classical generalized assignment problem (GAP). The large-scale number of variables in the related 0-1 linear program makes the use of commercial optimization packages impractical. We present here a metaheuristic using simulated annealing. It is based on successive reductions of the search space by identification of locally active constraints. Our approach employs a heuristic procedure to compute an initial (feasible or infeasible) 0/1 solution, and a double-criterion acceptance rule. The performance of the algorithm is demonstrated on real data sets.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aarts, E. and Lenstra, J.K. (1997). Local search in combinatorial optimization. John Wiley & Sons Publishers.
Aarts, E.H.L. and Van Laarhoven, P.J.M. (1987). Simulated Annealing: Theory and Applications. Kluwer Academic Publishers.
Aboudi, R. and Jörnsten, K. (1994). Tabu search for general zero-one integer programs using the Pivot and Complement heuristic. ORSA Journal on Computing, 6(1):82-93.
Balas, E. and Martin, C.H. (1980). Pivot and Complement-A heuristic for zero-one programming. Management Science, 26:89-96.
Cerny, V. (1985). A thermodynamical approach to the travellong salesman problem: an efficient simulated annealing. Journal of Optim. Theory Appl., 45:41–51.
Creutz, M. (1983). Microcanonical Monte Carlo simulation. Physic Rev. Lett. 50(19):1411-1414.
Glover, F. (1977). Heuristics in Integer Programming using surrogate constraints. Decision Sciences, 8(1):156-166.
Glover, F. (1990). Tabu search: a tutorial. Interfaces, 20(4):74-94.
Glover, F. and Laguna, M.. (1995). Tabu search. In C. Reeves (ed.), Modern heuristics for combinatorial problems. Blackwell Scientific Publishing (pp 70-151).
Glover, F. and Laguna, M. (1997). Tabu search. Kluwer Academic Publishing, Norwell, MA.
Hérault, L. and Horaud, R. (1993). Figure-Ground Discrimination: A combinatorial optimization approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(9):899-914.
Hérault, L. (1998). Rescaled simulated annealing. In Proceedings of the 1998 IEEE International Conference on Neural Networks, Anchorage, Alaska, May 1998.
Hérault, L. (1998). Rescaled Simulated Annealing-Accelerating convergence of Simulated Annealing by rescaling the states energies. Submitted to Journal of Heuristics. Kluwer Academic Publishers.
Kirkpatrick, S., Gelatt, C.D. and Vecchi, M.P. (1982). Optimization by simulated annealing. IBM research report RC9355.
Kropaczek, D.J. and Turinsky, P.J. (1991). In-core nuclear fuel management optimization for pressurized water reactors utilizing simulated annealing Nuclear Technology, 95:9-32.
Kuik, R., Salomon, M., Wassenhove, L.N. and Maes, J. (1993). Linear programming, Simulated annealing and tabu search heuristics for lotsizing bottleneck assembly systems. IIE Transactions, 25(1):62-72.
Laguna, M., Kelly, J.P., Gonzáles-Velarde, J.L. and Glover, F. (1995). Tabu search for the multivel generalized assignment problem. European Journal of Operational Research, 82:176-189.
Liegeois, B., Pirlot, M., Teghem, J., Trauwaert, E. and Tuyttens, D. (1992). Balanced grouping through simulated annealing. In R. Vidal (ed.), Lecture notes in economics and mathematical systems(pp 275-290). Springer Verlag.
Løkketangen, A., Jörnsten, K. and Storoy, S. (1994). Tabu search within a Pivot and Complement framework. International Transactions in Operations Research, 1(3):305-316.
Løkketangen, A. and Glover, F. (1996). Solving zero-one mixed integer programming problems using tabu search. European Journal of Operational Research-Special Issue on Tabu Search. To appear.
Mahlers, Y.P. (1995). Core loading pattern optimization based on simulated annealing and successive linear programming. Annals of Nuclear Energy, 22(1):223-227.
Martello, S. and Toth, P. (1990). Knapsack problems: Algorithms and Computer Implementations. Wiley, New York.
Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A. and Teller, E. (1953). Equation of state calculations by fast computing machines. Journal of Chem. Physics, 21:1087-1092.
Niquil, Y. and Voskanian, A. (1995). POMAR: un prototype d'optimisation de la gestion du stock de plutonium. Internal report EDF Clamart, HI23/95004.
Osman, I.H. (1991). Metastrategy simulated annealing and tabu search for combinatorial optimization. The management school, Imperial College of London.
Pirlot, M. (1992). General local search heuristics in combinatorial optimization: a tutorial. JORBEL Belgian Journal of Operations Research, 32(1-2):7-67.
Privault, C. and Hérault, L. (1998). Constraints satisfaction through recursive neural networks with mixed penalties. Neural Processing Letters. To appear.
Tuyttens, D., Pirlot, M., Teghem, J., Trauwaert, E. and Liegeois, B. (1994). Homogeneous grouping of nuclear fuel cans through simulated annealing and tabu search. Annals of Operations Research, 50:575- 607.
Vernekar, A. and Anandalingam, G. and Dorny, C.N. (1990). Optimization of resource location in hierarchical computer networks. Computers and Operations Research, 50:375-388.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Privault, C., Herault, L. Solving a Real World Assignment Problem with a Metaheuristic. Journal of Heuristics 4, 383–398 (1998). https://doi.org/10.1023/A:1009618009594
Issue Date:
DOI: https://doi.org/10.1023/A:1009618009594