A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations

 Access to full text

 Full (PDF)

1. Y. P. ANEJA, An Integer Linear Programming Approach to the Steiner Problem in Graphs, Networks, Vol. 10, 1980, pp. 167-178. Zbl0445.90087MR569008
2. E. BALAS and M. W. PADBERG, On the Set Covering Problem, II. An Algorithm for Set Partitioning, Operations Research, Vol. 23, 1975, pp. 74-90. Zbl0324.90045MR411622
3. E. BALAS and M. W. PADBERG, Set Partitioning: a Survey in Combinatorial Optimizaion, N. CHRISTOFIDES, A. MINGOZZI, P. TOTH and C. SANDI Eds., J. Wiley and Sons, 1979, pp. 151-210. Zbl0413.90047
4. E. BALAS and Ho, Set Covering Algorithms Using Cutting Planes, Heuristics, and Subgradient Optimization: A Computational Study, Mathematical Programming Study, Vol. 12, 1980, pp. 37-60. Zbl0435.90074MR571854
5. C. BERGE, Graphes et Hypergraphes, Dunod, Paris, 1970. Zbl0213.25702MR357173
6. A. BILLIONNET and M. MINOUX, Maximizing a Supermodular Pseudoboolean Function: Polynomial Algorithm for Supermodular Cubic Functions, Discrete Applied Mathematics, Vol. 12, 1985, pp. 1-11. Zbl0583.90067MR798006
7. A. BILLIONNET and M. MINOUX, Bounds and Efficient Algorithms for Submodular Pseudoboolean Function Minimization, 1984, To appear under the title: Duality Results and related Algorithms for Submodular function minimization. 
8. G. B. DANTZIG, Linear Programming and Extensions, Princeton University Press, Princeton, 1963. Zbl0997.90504MR201189
9. G. B. DANTZIG and P. WOLFE, The Decomposition Algorithm for Linear Programming, Econometrica, Vol. 29, No. 4, 1961, pp. 767-778. Zbl0104.14305MR138506
10. J. DELORME, Contribution à la résolution du problème de recouvrement : méthodes de troncatures, Thèse de Docteur Ingénieur, Université Paris-VI, 1974. 
11. J. DESROSIERS, F. SOUMIS and M. DESROCHERS, Routing with Time Windows by Column Generation, Networks, Vol 14, 1984, pp. 545-565. Zbl0571.90088
12. E. A. DINIC, Algorithm for Solution of a Problem of Maximum Flow in a Network with Power Estimation, Soviet Math. Dokl., Vol. 11, 1970, pp.1277-1280. Zbl0219.90046
13. J. EDMONDS, Maximum Matching and a Polyhedron with 0-1 Vertices, Journal Res. Nat. Bureau Standards, Vol. 69-B, Nos. 1-2, 1965, pp. 125-130. Zbl0141.21802MR183532
14. J. EDMONDS, Optimum Branchings, J. Res. Nat. Bur. Stand. B. Vol. 71, 1967, pp. 233-240. Zbl0155.51204MR227047
15. J. EDMONDS, Submodular Functions, Matroïds, and Certain Polyhedra in Combinatorial tructures and their Applications, R. GUY Ed., Gordon and Breach, New York, 1970, pp. 69-87. Zbl0268.05019MR270945
16. J. EDMONDS, Matroïds and the Greedy Algorithm, Mathematical Programming, Vol. 1, 1971, pp. 127-136. Zbl0253.90027MR297357
17. M. L. FISCHER, G. L. NEMHAUSER and L. A. WOLSEY, An Analysis of Approximations for Maximizing Submodular Set Functions I, Math. Programming Vol. 14, 1978, pp. 265-294. Zbl0374.90045MR503866
18. H. N. GABOW, Implementations of Algorithms for Maximum Matchings on Non-Bipartite Graphs, Ph. D. Dessertation, Computer Sc. Departement, Stanford University, California, 1973. 
19. M. R. GAREY and D. S. JOHNSON, Computers and Intractability. An Introduction to the Theory of NP-Complteteness, W. H. Freeman and Co., San Francisco, 1979. Zbl0411.68039MR519066
20. R. S. GARFINKEL and G. L. NEMHAUSER, The Set Partitioning Problem: Set Covering with Equality Constraints, Operations Research, Vol. 17, 1969, pp. 848-856. Zbl0184.23101
21. P. C. GILMORE and R. E. GOMORY, A Linear Programming Approach to the Cutting-Stock Problem. Part II, Operations Research, Vol. 11, 1963, pp. 863-888. Zbl0124.36307
22. R. E. GOMORY and T. C. Hu, An Application of Generalized Linear Programming to Network Flows, Journal S.I.A.M., Vol. 10, No. 2, 1962, pp. 260-283. Zbl0105.12805MR204155
23. M. GONDRAN and M. MINOUX, Graphes et Algorithmes, Eyrolles, Paris, 1979, English translation, J. Wiley and Sons, 1983. Zbl0497.05023MR615739
24. M. GROTSCHEL, L. LOVÂSZ and SCHRIJVER, The Ellipsoïd Method and its Consequences in Combinatorial Optimization, Combinatorica, Vol. 1, No. 2, 1981, pp. 169-197. Zbl0492.90056MR625550
25. S. L. HAKIMI, Optimum Location of Switching Centers and the Absolute Centers and Medians of a Graph, Operations Research, Vol. 12, 1964, pp. 450-459. Zbl0123.00305
26. J. HALPERN and I. PRIESS, Shortest Path with Time Constraints on Movement and Parking, Networks, Vol. 4, 1974, pp. 241-253. Zbl0284.90077MR347378
27. P. HANSEN, D. PEETERS and J. F. THISSE, Facility Location Analysis, Rutcor Research Report 4-85, Rutgers University (NJ), 1985, Encyclopedia of Economics (to appear). Zbl0618.90028
28. P. HANSEN, Private communication, 1986. 
29. I. HOLYER, The NP-Completeness of Edge-Coloring, S.I.A.M. J. Comput., Vol. 10, No. 4, 1981, pp. 718-720. Zbl0473.68034MR635430
30. T. INUKAI, Comments on Analysis of a Switch Matrix for an SS/TDMA System, Proceedings of the I.E.E.E., Vol. 66, No. 12, 1978, pp. 1669-1670. 
31. Y. ITO, Y. URANO, T. MURATANI and M. YAMAGUCHI, Analysis of a Switch Matrix for an SS/TDMA System, Proceedings of the I.E.E.E., Vol. 65, No. 3, 1977, pp. 411-419. MR434597
32. A. V. KARZANOV, Determining the Maximal Flow in a Network by the Method of Preflows, Soviet Math. Dokl., Vol. 15, 1974, pp. 434-437. Zbl0303.90014
33. L. G. KHACHIAN, A Polvnomial Algorithm in Linear Programming, Soviet Math Dokl., Vol. 20, No. 1, 1979, pp. 191-194. Zbl0414.90086
34. L. S. LASDON, Optimization Theory for Large Systems, Macmillan series for Operations Research, 1970. Zbl0224.90038MR337317
35. S. LAVOIE, M. MINOUX and E. ODIER, A new Approach of Crew Pairing Problems by Column Generation and Application to Air Transports, 1985(to Appear). Zbl0636.90041
36. E. LAWLER, Combinatorial Optimization. Networks and Matroïds, Holt, Rinehart and Winston, 1976. Zbl0413.90040MR439106
37. C. E. H. LEMKE, M. SALKIN and K. SPIELBERG, Set Covering by Single Branch Enumeration with Linear Programming Subproblems, Operations Research, Vol. 19, 1971, pp . 998-1022. Zbl0232.90033MR418914
38. N. MACULAN, The Steiner Problem in Graphs, in Surveys in Combinatorial Optimization, S. MARTELLO, G. LAPORTE, M. MINOUX and C. RIBEIRO Eds., North Holland, 1987. Zbl0622.90029MR878773
39. V. M. MALHOTRA, M. P. KUMAR and S. N. MAHESHWARI, An O (IVI3 ) Algorithm for finding Maximum Flows in Networks, Information Processing Letters, Vol.7, No. 6, 1978, pp. 277-278. Zbl0391.90041MR509428
40. F. E. MARANZANA, On the Location of Supply Points to Minimize Transport Costs, Operational Research Quarterly, Vol. 15, 1964, pp. 261-270. 
41. R. E. MARSTEN, An Algorithm for Large Set Partitioning Problems, Management Science, Vol. 20, 1974, pp.779-787. Zbl0304.90077MR342177
42. M. MINOUX, Plus court chemin avec contraintes, algorithmes et applications, Annales des Télécommunications, Vol. 30, Nos. 11-12, 1975, pp. 383-394. Zbl0347.90065
43. M. MINOUX, Programmation Mathématique: Théorie et Algorithmes, Dunod Paris, 1983, English Translation, J. Weley and Sons, 1986. Zbl0546.90056MR2571910
44. M. MINOUX, Optimal Traffic Assignment in a SS/TDMA Frame: A New Approach by Set Covering and Column Generation, O.R.S.A./T.I.M.S. meeting, Dallas, Texas, 1984a, R.A.I.R.O., Vol. 20, No. 4, 1986, pp. 1-13. Zbl0608.90076
45. M. MINOUX, Column Generation Techniques in Combinatorial Optimization: A New Application to Crew-Pairing Problems, XXIVth AGIFORS Symposium, 1984 b, Strasbourg, France, september 1984. 
46. M. MINOUX, New Lower Bounds to the Graph Partitioning Problem through Generalized Linear Programming and Network Flows, 1986a (to be published). Zbl0657.90095
47. M. MINOUX, Solving Combinatorial Problems with Combined Min-Max-Min-Sum objective, 1986a (under preparation). Zbl0682.90076
48. C. St. J. A. NASH-WILLIAMS, Decomposition of Finite Graphs into Forests, Journal London Math. Soc, Vol. 39, 1964, p. 12. Zbl0119.38805MR161333
49. C. St. J. A. NASH-WILLIAMS, An Application of Matroïds to Graph Theory in Theorie des Graphes, Proceedings Internat. Symposium, Rome, Italy, 1966, Dunod, Paris, 1967. Zbl0188.55903
50. R. C. PRIM, Shortest Connection Networks and Some Generalizations, Bell Syst. Techn. J., Vol. 36, 1957, p. 1389. 
51. F. RENDL, On the Complexity of Decomposing Matrices Arising in Satellite Communications, Bericht 84-47, Technische Universität, Graz, Austria, 1984. Zbl0569.90064
52. J. M. W. RHYS, A Selection Problem of Shared Fixed Costs and Network Flows, Management Science, Vol. 17, No. 3, 1970, pp. 200-207. Zbl0203.52505MR309537
53. C. RIBEIRO, M. MINOUX and C. PENNA, A Hybrid Branch and Bound/Column Generation Approach to Very Large Scale Set Covering Problems with Special Structure, O.R.S.A./T.I.M.S. meeting, Miami, Florida, November 1986 (to Appear). MR858854
54. N. Z. SHOR, Cut-off Methods with Space Extension in Convex Programming Problems, Kibernetika, Vol. 13, No. 1, 1977, pp. 94-95, English Translation in Cybernetics, Vol. 13, No. 1, 1977, pp. 94-96. Zbl0365.90104
55. R. E. TARJAN, A simple Version of Karzanov's Blocking Flow Algorithm, Operations Research Letters, Vol. 2, No.6, 1984, pp. 265-268. Zbl0542.05057MR739677
56. L. VISMARA, Piano di accesso dei messaggi insistemi SS/TDMA: un metodo di enumerazione implicita per minimizzare il tempo di transmissione, Tesi di laurea, politechnico di Milano, Departamento di Elettronica (Paolo Camerini i Francesco Maffioli Relatori), 1982. 

1. Y. Crama, J. Van De Klundert, Approximation algorithms for integer covering problems via greedy column generation
2. M. Minoux, E. Pinson, Lower bounds to the graph partitioning problem through generalized linear programming and network flows
3. Nelson Maculan, Marcos de Mendonça Passini, José André de Moura Brito, Irene Loiseau, Column-generation in integer linear programming
4. Nelson Maculan, Marcos de Mendonça Passini, José André de Moura Brito, Irene Loiseau, Column-Generation in Integer Linear Programming