A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations
RAIRO - Operations Research - Recherche Opérationnelle, Tome 21 (1987) no. 2, pp. 105-136. 
@article{RO_1987__21_2_105_0,
     author = {Minoux, M.},
     title = {A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {105--136},
     publisher = {EDP-Sciences},
     volume = {21},
     number = {2},
     year = {1987},
     mrnumber = {897292},
     zbl = {0644.90061},
     language = {en},
     url = {http://archive.numdam.org/item/RO_1987__21_2_105_0/}
}
TY  - JOUR
AU  - Minoux, M.
TI  - A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 1987
SP  - 105
EP  - 136
VL  - 21
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/RO_1987__21_2_105_0/
LA  - en
ID  - RO_1987__21_2_105_0
ER  - 
%0 Journal Article
%A Minoux, M.
%T A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 1987
%P 105-136
%V 21
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/item/RO_1987__21_2_105_0/
%G en
%F RO_1987__21_2_105_0
Minoux, M. A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations. RAIRO - Operations Research - Recherche Opérationnelle, Tome 21 (1987) no. 2, pp. 105-136. http://archive.numdam.org/item/RO_1987__21_2_105_0/

Y. P. Aneja, An Integer Linear Programming Approach to the Steiner Problem in Graphs, Networks, Vol. 10, 1980, pp. 167-178. | MR | Zbl

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. | MR | Zbl

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. | Zbl

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. | MR | Zbl

C. Berge, Graphes et Hypergraphes, Dunod, Paris, 1970. | MR | Zbl

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. | MR | Zbl

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.

G. B. Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, 1963. | MR | Zbl

G. B. Dantzig and P. Wolfe, The Decomposition Algorithm for Linear Programming, Econometrica, Vol. 29, No. 4, 1961, pp. 767-778. | MR | Zbl

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.

J. Desrosiers, F. Soumis and M. Desrochers, Routing with Time Windows by Column Generation, Networks, Vol 14, 1984, pp. 545-565. | Zbl

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. | Zbl

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. | MR | Zbl

J. Edmonds, Optimum Branchings, J. Res. Nat. Bur. Stand. B. Vol. 71, 1967, pp. 233-240. | MR | Zbl

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. | MR | Zbl

J. Edmonds, Matroïds and the Greedy Algorithm, Mathematical Programming, Vol. 1, 1971, pp. 127-136. | MR | Zbl

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. | MR | Zbl

H. N. Gabow, Implementations of Algorithms for Maximum Matchings on Non-Bipartite Graphs, Ph. D. Dessertation, Computer Sc. Departement, Stanford University, California, 1973.

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. | MR | Zbl

R. S. Garfinkel and G. L. Nemhauser, The Set Partitioning Problem: Set Covering with Equality Constraints, Operations Research, Vol. 17, 1969, pp. 848-856. | Zbl

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. | Zbl

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. | MR | Zbl

M. Gondran and M. Minoux, Graphes et Algorithmes, Eyrolles, Paris, 1979, English translation, J. Wiley and Sons, 1983. | MR | Zbl

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. | MR | Zbl

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. | Zbl

J. Halpern and I. Priess, Shortest Path with Time Constraints on Movement and Parking, Networks, Vol. 4, 1974, pp. 241-253. | MR | Zbl

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).

P. Hansen, Private communication, 1986.

I. Holyer, The NP-Completeness of Edge-Coloring, S.I.A.M. J. Comput., Vol. 10, No. 4, 1981, pp. 718-720. | MR | Zbl

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.

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. | MR

A. V. Karzanov, Determining the Maximal Flow in a Network by the Method of Preflows, Soviet Math. Dokl., Vol. 15, 1974, pp. 434-437. | Zbl

L. G. Khachian, A Polvnomial Algorithm in Linear Programming, Soviet Math Dokl., Vol. 20, No. 1, 1979, pp. 191-194. | Zbl

L. S. Lasdon, Optimization Theory for Large Systems, Macmillan series for Operations Research, 1970. | MR | Zbl

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). | Zbl

E. Lawler, Combinatorial Optimization. Networks and Matroïds, Holt, Rinehart and Winston, 1976. | MR | Zbl

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. | MR | Zbl

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. | MR | Zbl

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. | MR | Zbl

F. E. Maranzana, On the Location of Supply Points to Minimize Transport Costs, Operational Research Quarterly, Vol. 15, 1964, pp. 261-270.

R. E. Marsten, An Algorithm for Large Set Partitioning Problems, Management Science, Vol. 20, 1974, pp.779-787. | MR | Zbl

M. Minoux, Plus court chemin avec contraintes, algorithmes et applications, Annales des Télécommunications, Vol. 30, Nos. 11-12, 1975, pp. 383-394. | Zbl

M. Minoux, Programmation Mathématique: Théorie et Algorithmes, Dunod Paris, 1983, English Translation, J. Weley and Sons, 1986. | MR | Zbl

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. | Numdam | Zbl

M. Minoux, Column Generation Techniques in Combinatorial Optimization: A New Application to Crew-Pairing Problems, XXIVth AGIFORS Symposium, 1984 b, Strasbourg, France, september 1984.

M. Minoux, New Lower Bounds to the Graph Partitioning Problem through Generalized Linear Programming and Network Flows, 1986a (to be published). | Numdam | Zbl

M. Minoux, Solving Combinatorial Problems with Combined Min-Max-Min-Sum objective, 1986a (under preparation). | Zbl

C. St. J. A. Nash-Williams, Decomposition of Finite Graphs into Forests, Journal London Math. Soc, Vol. 39, 1964, p. 12. | MR | Zbl

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. | Zbl

R. C. Prim, Shortest Connection Networks and Some Generalizations, Bell Syst. Techn. J., Vol. 36, 1957, p. 1389.

F. Rendl, On the Complexity of Decomposing Matrices Arising in Satellite Communications, Bericht 84-47, Technische Universität, Graz, Austria, 1984. | Zbl

J. M. W. Rhys, A Selection Problem of Shared Fixed Costs and Network Flows, Management Science, Vol. 17, No. 3, 1970, pp. 200-207. | MR | Zbl

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). | MR

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. | Zbl

R. E. Tarjan, A simple Version of Karzanov's Blocking Flow Algorithm, Operations Research Letters, Vol. 2, No.6, 1984, pp. 265-268. | MR | Zbl

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.