×

Exact solutions to a class of stochastic generalized assignment problems. (English) Zbl 1113.90082

Summary: This paper deals with a stochastic Generalized Assignment Problem with recourse. Only a random subset of the given set of jobs will require to be actually processed. An assignment of each job to an agent is decided a priori, and once the subset of jobs which have to be executed is known, reassignments can be performed if there are overloaded agents.We construct a convex approximation of the objective function that is sharp at all feasible solutions. We then present three versions of an exact algorithm to solve this problem, based on branch and bound techniques, optimality cuts, and a special purpose lower bound. Numerical results are reported.

MSC:

90B80 Discrete location and assignment
90C15 Stochastic programming
90C10 Integer programming

Software:

CPLEX
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ahmed, S.; Tawarmalani, M.; Sahinidis, N. V., A finite branch-and-bound algorithm for two-stage stochastic integer programs, Mathematical Programming, 100, 2, 355-377 (2004) · Zbl 1068.90084
[2] Albareda Sambola, M.; Fernández, E., The stochastic generalised assignment problem with Bernoulli demands, TOP, 8, 2, 165-190 (2000) · Zbl 0982.90035
[3] V. Balachandran, An integer generalized transportation problem for optimal job assignment in computer networks, Technical Report 43-72-3, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, 1972.; V. Balachandran, An integer generalized transportation problem for optimal job assignment in computer networks, Technical Report 43-72-3, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, 1972.
[4] Berman, O.; Simchi-Levi, D., Finding the optimal a priori tour and location of a traveling salesman with nonhomogeneous customers, Transportation Science, 22, 2, 148-154 (1988) · Zbl 0653.90082
[5] Birge, J. R.; Louveaux, F. V., Introduction to stochastic programming (1997), Wiley: Wiley New York · Zbl 0892.90142
[6] Carøe, C. C.; Tind, J., L-shaped decomposition of two-stage stochastic programs with integer recourse, Mathematical Programming, 83, 3, 451-464 (1998) · Zbl 0920.90107
[7] Carøe, C. C.; Schultz, R., Dual decomposition in stochastic integer programming, Operations Research Letters, 24, 1-2, 37-45 (1999) · Zbl 1063.90037
[8] Cattrysse, D. G.; Van Wassenhove, L. N., A survey of algorithms for the generalized assignment problem, European Journal of Operational Research, 60, 260-272 (1992) · Zbl 0760.90071
[9] CPLEX Optimization, Inc. Using the CPLEX callable library, Manual, 2000.; CPLEX Optimization, Inc. Using the CPLEX callable library, Manual, 2000.
[10] Kall, P.; Wallace, S. W., Stochastic programming (1994), Wiley: Wiley Chichester etc. · Zbl 0812.90122
[11] Klein Haneveld, W. K.; Stougie, L.; van der Vlerk, M. H., An algorithm for the construction of convex hulls in simple integer recourse programming, Annals of Operations Research, 64, 67-81 (1996), Stochastic programming, algorithms and models (Lillehammer, 1994) · Zbl 0854.90110
[12] Klein Haneveld, W. K.; van der Vlerk, M. H., Stochastic integer programming: General models and algorithms, Annals of Operations Research, 85, 39-57 (1999) · Zbl 0920.90110
[13] Kuhn, H. W., The Hungarian method for the assignment problem, Naval Research Logistics Quarterly, 2, 83-97 (1955) · Zbl 0143.41905
[14] Laporte, G.; Louveaux, F.; Mercure, H., An exact solution for the a priori optimization of the probabilistic traveling salesman problem, Operations Research, 39, 71-78 (1994)
[15] Laporte, G.; Louveaux, F. V., The integer L-shaped method for stochastic integer programs with complete recourse, Operations Research Letters, 13, 133-142 (1992) · Zbl 0793.90043
[16] Louveaux, F. V.; van der Vlerk, M. H., Stochastic programming with simple integer recourse, Mathematical Programming, 61, 301-325 (1993) · Zbl 0792.90053
[17] Martello, S.; Toth, P., Knapsack problems, algorithms and computer implementations (1990), Wiley · Zbl 0708.68002
[18] Mine, H.; Fukushima, M.; Ishikawa, K.; Sawa, I., An algorithm for the assignment problem with stochastic side constraints, Memoirs of the Faculty of Engineering, XLV, part 4 (1983)
[19] Nemhauser, G. L.; Wolsey, L. A., Integer and combinatorial optimization (1988), Wiley: Wiley New York · Zbl 0469.90052
[20] Norkin, V. I.; Ermoliev, Yu. M.; Ruszczyński, A., On optimal allocation of indivisibles under uncertainty, Operations Research, 46, 3, 381-395 (1998) · Zbl 0987.90064
[21] Prékopa, A., Stochastic programming (1995), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0834.90098
[22] Schultz, R., Continuity properties of expectation functions in stochastic integer programming, Mathematics of Operations Research, 18, 578-589 (1993) · Zbl 0804.90100
[23] Schultz, R.; Stougie, L.; van der Vlerk, M. H., Two-stage stochastic integer programming: A survey, Statistica Neerlandica, 50, 3, 404-416 (1996) · Zbl 0909.90222
[24] Schultz, R.; Stougie, L.; van der Vlerk, M. H., Solving stochastic programs with complete integer recourse: A framework using Gröbner bases, Mathematical Programming, 83, 2, 229-252 (1998) · Zbl 0920.90114
[25] Stougie, L.; van der Vlerk, M. H., Stochastic integer programming, (Dell’Amico, M.; Maffioli, F.; Martello, S., Annotated bibliographies in combinatorial optimization (1997), Wiley), 127-141, (Chapter 9) · Zbl 1068.90523
[26] Stubbs, R. A.; Mehrotra, S., A branch-and-cut method for 0-1 mixed convex programming, Mathematical Programming, 86, 3, 515-532 (1999) · Zbl 0946.90054
[27] B. Toktas, addressing capacity uncertainty in resource-constrained assignment problems, PhD thesis, University of Washington, 2003.; B. Toktas, addressing capacity uncertainty in resource-constrained assignment problems, PhD thesis, University of Washington, 2003. · Zbl 1088.90047
[28] M.H. van der Vlerk, Stochastic programming bibliography, World Wide Web. Available from: <http://mally.eco.rug.nl/spbib.html; M.H. van der Vlerk, Stochastic programming bibliography, World Wide Web. Available from: <http://mally.eco.rug.nl/spbib.html
[29] van der Vlerk, M. H., Convex approximations for complete integer recourse models, Mathematical Programming, 99, 2, 297-310 (2004) · Zbl 1068.90086
[30] Van Slyke, R.; Wets, R., L-shaped linear programs with applications to optimal control and stochastic linear programs, SIAM Journal on Applied Mathematics, 17, 638-663 (1969) · Zbl 0197.45602
[31] Wollmer, R. D., Two stage linear programming under uncertainty with 0-1 integer first stage variables, Mathematical Programming, 19, 279-288 (1980) · Zbl 0442.90076
[32] Wolsey, L. A., Integer programming (1998), John Wiley & Sons Inc.: John Wiley & Sons Inc. New York · Zbl 0299.90012
[33] Yudin, D. B.; Tsoy, E. V., Integer-valued stochastic programming, Engineering Cybernetics, 12, 1-8 (1974)
[34] Zimokha, V. A.; Rubinshtein, M. I., R&D planning and the generalized assignment problem, Automation and Remote Control, 49, 484-492 (1988) · Zbl 0659.90058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.