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

M. Minoux

RAIRO - Operations Research - Recherche Opérationnelle (1987)

  • Volume: 21, Issue: 2, page 105-136
  • ISSN: 0399-0559

How to cite

top

Minoux, M.. "A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations." RAIRO - Operations Research - Recherche Opérationnelle 21.2 (1987): 105-136. <http://eudml.org/doc/104917>.

@article{Minoux1987,
author = {Minoux, M.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {column generation; very large size set covering; set partitioning; linear relaxations; generalized linear programming; plant location; forests; graph partitioning; chromatic index problem; clustering; k-center-sum; minimum weighted partitioning of a matroid; NP-complete; lower bounds; satellite communications; crew scheduling},
language = {eng},
number = {2},
pages = {105-136},
publisher = {EDP-Sciences},
title = {A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations},
url = {http://eudml.org/doc/104917},
volume = {21},
year = {1987},
}

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
PB - EDP-Sciences
VL - 21
IS - 2
SP - 105
EP - 136
LA - eng
KW - column generation; very large size set covering; set partitioning; linear relaxations; generalized linear programming; plant location; forests; graph partitioning; chromatic index problem; clustering; k-center-sum; minimum weighted partitioning of a matroid; NP-complete; lower bounds; satellite communications; crew scheduling
UR - http://eudml.org/doc/104917
ER -

References

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

Citations in EuDML Documents

top
  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

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.