The generalized assignment problem: Valid inequalities and facets

1. V. Balachandran, “An integer generalized transportation model for optimal job assignment of computer networks,”Operations Research 24 (1976) 742–759.

   Google Scholar 

2. E. Balas, “Facets of the knapsack polytope,”Mathematical Programming 8 (1975) 146–164.

   Google Scholar 

3. E. Balas and E. Zemel, “Facets of the knapsack polytope from minimal covers,”SIAM Journal on Applied Mathematics 34 (1978) 119–148.

   Google Scholar 

4. D.C. Cho, E.L. Johnson, M.W. Padberg and M.R. Rao, “On the uncapacitated plant location problem I: Valid inequalities and facets,”Mathematics of Operations Research 8 (1983) 579–589.

   Google Scholar 

5. D.C. Cho, M.W. Padberg and M.R. Rao “On the uncapacitated plant location problem II: Facets and lifting theorems,”Mathematics of Operations Research 8 (1983) 590–612.

   Google Scholar 

6. H. Crowder, E.L. Johnson and M.W. Padberg, “Solving large-scale zero-one linear programming problems.“Operations Research 31 (1983) 803–834.

   Google Scholar 

7. G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963).

   Google Scholar 

8. A. DeMaio and C. Roveda, “An all zero-one algorithm for a class of transportation problems,”Operations Research 19 (1971) 1406–1418.

   Google Scholar 

9. M.R. Garey, R.L. Graham, D.S. Johnson and A.C. Yao, “Resource constrained scheduling as generalized bin packing.“Journal of Combinatorial Theory A 21 (1976) 257–298.

   Google Scholar 

10. M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman Press, San Francisco, CA, 1979)

    Google Scholar 

11. E.S. Gottlieb, “Contributions to the polyhedral approach to generalized assignment problems,” Ph.D. Thesis, Graduate School of Business Administration, New York University (New York, 1985).

    Google Scholar 

12. E.S. Gottlieb and M.R. Rao, “The generalized assignment problem II: Three classes of facets,” Technical Report #8622-Stat, Baruch College, The City University of New York (New York, 1986).

    Google Scholar 

13. E.S. Gottlieb and M.R. Rao, “(1,k) - Configuration facets for the generalized assignment problem,”Mathematical Programming 46 (1990) 53–60, this issue.

    Google Scholar 

14. M. Grötschel, M. Jünger and G. Reinelt, “Optimal triangulation of large real world input-output matrices,” WP 82228-OR, Institute for Operations Research, University of Bonn (Bonn, 1982).

    Google Scholar 

15. M. Grötschel, M. Jünger and G. Reinelt, “A cutting plane algorithm for the linear ordering problem,”Operations Research 32 (1984) 1195–1220.

    Google Scholar 

16. P.L. Hammer, E.L. Johnson and U.N. Peled, “Facets of regular 0-1 polytopes,”Mathematical Programming 8 (1975) 179–206.

    Google Scholar 

17. E.J. Johnson, M.K. Kostreva and U.H. Suhl, “Solving 0-1 integer programming problems arising from large scale planning models,”Operations Research 33 (1985) 803–819.

    Google Scholar 

18. E.L. Lawler,Combinatorial Optimization: Networks and Matroids (Holt, Rinehart and Winston, New York, 1976).

    Google Scholar 

19. E.L. Lawler, “Recent results in the theory of machine scheduling,” in: A. Bachem, M. Götschel, B. Korte, eds.,Mathematical Programming the State of the Art (Springer, Berlin, 1983) pp. 202–234.

    Google Scholar 

20. H.M. Markowitz, “Concepts and computing procedures for certainX _ij programming problems,” in: H.A. Antosiewicz, ed.,Proceedings of the Second Symposium in Linear Programming, Vol. 2 (National Bureau of Standards and Directorate of Management Analysis, The RAND Corporation, 1955) pp. 509–565.

21. S. Martello and P. Toth, “An algorithm for the generalized assignment problem,” in: J.P. Brans, ed.,Operational Research, Vol. 81 (North-Holland, Amsterdam, 1981) pp. 589–603.

    Google Scholar 

22. M.W. Padberg, “On the facial structure of set packing polyhedra,”Mathematical Programming 5 (1973) 199–215.

    Google Scholar 

23. M.W. Padberg, “A note on zero-one programming,”Operations Research 23 (1975) 833–837.

    Google Scholar 

24. M.W. Padberg, “(1,k)-Configurations and facets for packing problems,”Mathematical Programming 18 (1980) 94–99.

    Google Scholar 

25. M.W. Padberg and G. Rinaldi, “Optimization of a 532-city symmetric traveling salesman problem by branch-and-cut,” Working Paper (1986).

26. U.N. Peled, “Properties of facets of binary polytopes,”Annals of Discrete Mathematics 1 (1977) 435–456.

    Google Scholar 

27. G.T. Ross and R.M. Soland, “A branch and bound algorithm for the generalized assignment problem,”Mathematical Programming 8 (1975) 91–103.

    Google Scholar 

28. G.T. Ross and R.M. Soland “Modeling facility location problems as generalized assignment problems,”Management Science 24 (1977) 345–357.

    Google Scholar 

29. V. Srinivasan and G. Thompson, “An algorithm for assigning uses to sources in a special class of transportation problems,”Operations Research 21 (1973) 284–295.

    Google Scholar 

30. L.A. Wolsey, “Faces for a linear inequality in 0-1 variables,”Mathematical Programming 8 (1975) 165–178.

    Google Scholar 

31. L.A. Wolsey, “Facets and strong valid inequalities for integer programs,”Operations Research 24 (1976) 367–372.

    Google Scholar 

32. L.A. Wolsey “Valid inequalities and superadditivity for 0-1 integer programs,”Mathematics of Operations Research 2 (1977) 66–77.

    Google Scholar 

33. E. Zemel, “Lifting the facets of zero-one polytopes,”Mathematical Programming 15 (1978) 268–277.

    Google Scholar 

Download references