A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations
RAIRO - Operations Research - Recherche Opérationnelle, Volume 21 (1987) no. 2, p. 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},
publisher = {EDP-Sciences},
volume = {21},
number = {2},
year = {1987},
pages = {105-136},
zbl = {0644.90061},
mrnumber = {897292},
language = {en},
url = {http://www.numdam.org/item/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, Volume 21 (1987) no. 2, pp. 105-136. http://www.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 569008 | Zbl 0445.90087

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 411622 | Zbl 0324.90045

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 0413.90047

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 571854 | Zbl 0435.90074

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

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 798006 | Zbl 0583.90067

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 201189 | Zbl 0997.90504

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

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 0571.90088

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 0219.90046

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 183532 | Zbl 0141.21802

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

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 270945 | Zbl 0268.05019

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

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 503866 | Zbl 0374.90045

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 519066 | Zbl 0411.68039

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 0184.23101

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 0124.36307

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 204155 | Zbl 0105.12805

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

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 625550 | Zbl 0492.90056

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 0123.00305

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

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 635430 | Zbl 0473.68034

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 434597

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 0303.90014

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

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

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 0636.90041

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

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 418914 | Zbl 0232.90033

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 878773 | Zbl 0622.90029

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 509428 | Zbl 0391.90041

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 342177 | Zbl 0304.90077

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 0347.90065

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

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 0608.90076

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 0657.90095

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

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

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 0188.55903

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 0569.90064

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 309537 | Zbl 0203.52505

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 858854

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 0365.90104

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

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.