×

Some thoughts on combinatorial optimisation. (English) Zbl 0904.90137

Summary: A group of young researchers from the ESI X summer school, HEC, Jouy-en-Josas 1994, give their personal views on the current status of, and prospects for, combinatorial optimisation. Several issues are considered and discussed with emphasis on a selected number of techniques: heuristics and polyhedral approaches, and problems: knapsack, quadratic 0-1 programming, machine scheduling, routing and network design.

MSC:

90C27 Combinatorial optimization

Keywords:

personal views
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aarts, E.; Korst, J., Simulated Annealing and Boltzmann Machines (1989), Wiley: Wiley Chichester, UK · Zbl 0674.90059
[2] Arora, S.; Lund, J.; Motwani, R.; Sudan, M.; Szegedy, M., On the intractability of approximation problems (1992), Manuscript
[3] Baker, K. R., Introduction to Sequencing and Scheduling (1974), Wiley: Wiley New York
[4] Balakrishman, A.; Magnanti, T. L.; Wong, R. T., A dual-ascent procedure for large-scale uncapacitated network design, Operations Research, 37, 716-740 (1989) · Zbl 0681.90083
[5] Balas, E.; Zemel, E., An algorithm for large zero-one Knapsack Problems, Operations Research, 28, 1130-1154 (1980) · Zbl 0449.90064
[6] Barahona, F.; Jünger, M.; Reinelt, G., Experiments in quadratic 0-1 programming, Mathematical Programming, 44, 127-137 (1989) · Zbl 0677.90046
[7] Barahona, F.; Mahjoub, A. R., On the cut polytope, Mathematical Programming, 36, 57-173 (1986) · Zbl 0616.90058
[8] Carraresi, P., Malucelli, F., and Pappalardo, M., “Testing optimality for quadratic 0-1 unconstrained problems”, ZOR Mathamtical Methods of Operations Research; Carraresi, P., Malucelli, F., and Pappalardo, M., “Testing optimality for quadratic 0-1 unconstrained problems”, ZOR Mathamtical Methods of Operations Research · Zbl 0841.90095
[9] Chvátal, V., Hard Knapsack Problems, Operations Research, 28, 1402-1411 (1980) · Zbl 0447.90063
[10] Cornuejols, G.; Nharche, F., Polyhedral study of the Capacitated Vehicle Routing Problem, Mathematical Programming, 60, 21-52 (1993) · Zbl 0790.90029
[11] Desrosiers, J., Dumas, Y., Solomon, M., and Soumis, F., “Time constrained routing and scheduling”, in M. Ball, C. Monma, T. Magnanti and G. Nemhauser (eds.) Handbooks in Operations Research and Management Science; Desrosiers, J., Dumas, Y., Solomon, M., and Soumis, F., “Time constrained routing and scheduling”, in M. Ball, C. Monma, T. Magnanti and G. Nemhauser (eds.) Handbooks in Operations Research and Management Science · Zbl 0861.90052
[12] Edmonds, J., Matching and a polyhedron with 0-1 vertices, Journal of Research of the National Bureau of Standards, 69B, 125-130 (1965) · Zbl 0141.21802
[13] French, S., Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop (1982), Horwood: Horwood Chichester, UK · Zbl 0479.90037
[14] Gavish, B., Topological design of computer communication networks — The overall design problem, European Journal of Operational Research, 58, 149-172 (1992) · Zbl 0792.68005
[15] Gavish, B., Topological design of telecommunication networks — Local access design methods, Annals of Operations Research, 33, 17-71 (1991) · Zbl 0736.90030
[16] Giannessi, F.; Nicolucci, F., Connections between nonlinear and integer programming problems, (Symposia Mathematica, Vol. XIX (1976), Academic Press: Academic Press New York), 161-176
[17] Glover, F., Tabu Search, Part I, ORSA Journal on Computing, 1, 3, 190-206 (1989) · Zbl 0753.90054
[18] Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0721.68056
[19] Golden, B. L.; Assad, A. A., Vehicle Routing: Methods and Studies, (Studies in Management Science and Systems, Vol. 16 (1988), North-Holland: North-Holland Amsterdam) · Zbl 0638.00043
[20] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric Algorithms and Combinatorial Optimization (1988), Springer-Verlag: Springer-Verlag Berlin · Zbl 0634.05001
[21] Grötschel, M.; Holland, O., Solution of large-scale Travelling Salesman Problems, Mathematical Programming, 51, 141-202 (1991) · Zbl 0733.90047
[22] Grötschel, M., Monma, C.L., and Stoer, M., “Design of survivable networks”, in: M. Ball, C. Monma, T. Magnanti and G. Nemhauser (eds.), Handbooks in Operations Research and Management Science; Grötschel, M., Monma, C.L., and Stoer, M., “Design of survivable networks”, in: M. Ball, C. Monma, T. Magnanti and G. Nemhauser (eds.), Handbooks in Operations Research and Management Science · Zbl 0839.90132
[23] Grötschel, M.; Padberg, M. W., Polyhedral theory, (Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., The Traveling Salesman Problem (1985), Wiley: Wiley New York) · Zbl 0587.90073
[24] Hammer, P. L., Some network flow problems solved with pseudo-boolean programming, Operations Research, 13, 388-399 (1965) · Zbl 0132.13804
[25] Hammer, P. L.; Hansen, P.; Simeone, B., Roof duality, complementation and persistency in quadratic 0-1 optimization, Mathematical Programming, 28, 121-155 (1984) · Zbl 0574.90066
[26] Hoffman, K. L.; Padberg, M. W., Solving airline crew scheduling problems by branch-and-cut, Management Science, 39, 657-682 (1993) · Zbl 0783.90051
[27] Horowitz, E.; Sahni, S., Computing partitions with applications to the Knapsack Problem, Journal of the ACM, 21, 277-292 (1974) · Zbl 0329.90046
[28] Khachiyan, L. G., A polynomial algorithm for linear programming, Doklady Akademii Nauk USSR, 244, 1093-1096 (1979) · Zbl 0414.90086
[29] Kindervater, G. A.P.; Lenstra, J. K., An introduction to parallelism in combinatorial optimization, Discrete Applied Mathematics, 14, 135-156 (1986) · Zbl 0593.90047
[30] Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., The Traveling Salesman Problem (1985), Wiley: Wiley New York · Zbl 0563.90075
[31] Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., Sequencing and scheduling: Algorithms and complexity, (Handbooks in Operations Research and Management Science, Vol. 4: Logistics of Production and Inventory (1993), North-Holland: North-Holland Amsterdam), 445-524
[32] Magnanti, T. L.; Wong, R. T., Network design and transportation planning: Models and algorithms, Transportation Science, 18, 1-55 (1984)
[33] Martello, S.; Toth, P., Knapsack Problems: Algorithms and Computer Implementations (1990), Wiley: Wiley Chichester, UK · Zbl 0708.68002
[34] Martello, S.; Toth, P., Upper bounds and algorithms for hard 0-1 Knapsack Problems, (OR/93/04, Research Report DEIS (1993), University of Bologna) · Zbl 0902.90125
[35] Minoux, M., Network synthesis and dynamic network optimization, Annals of Discrete Mathematics, 31, 283-324 (1987)
[36] Minoux, M., Network synthesis and optimum network design problems: Models, solution methods and applications, Networks, 19, 313-360 (1989) · Zbl 0666.90032
[37] Morton, T. E.; Pentico, D. W., Heuristic Scheduling Systems (1993), Wiley: Wiley New York
[38] Padberg, M., Quadric polytype: Some characteristics and facets, Mathematical Programming, 45, 139-172 (1989) · Zbl 0675.90056
[39] Padberg, M. W.; Grötschel, M., Polyhedral computation, (Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., The Traveling Salesman Problem (1985), Wiley: Wiley New York) · Zbl 0587.90073
[40] Padberg, M. W.; Rinaldi, G., A branch-and-cut algorithm for the solution of large-scale Traveling Salesman Problems, SIAM Review, 33, 1-41 (1991)
[41] Plateau, G.; Elkihel, M., A hybrid method for the 0-1 knapsack problem, Methods of Operations Research, 49, 277-293 (1985) · Zbl 0564.90037
[42] Potvin, J.-Y.; Shen, Y.; Rosseau, J.-M., Neural network for automated vehicle dispatching, Computers & Operations Research, 19, 3-4, 267-276 (1992) · Zbl 0825.90352
[43] Psaraftis, H. N., Review standards for OR/MS papers, OR/MS Today, 54-57 (June 1994)
[44] Pulleyblank, W. R., Polyhedral combinatorics, (Nemhauser, J. L.; Rinnooy Kan, A. H.G.; Todd, M. J., Handbooks in Operations Research and Management Science, Vol. 1: Optimization (1989), North-Holland: North-Holland Amsterdam) · Zbl 0566.90063
[45] Roberts, F. S., Meaningfulness of conclusions from combinatorial optimization, Discrete Applied Mathematics, 29, 221-242 (1990) · Zbl 0713.90067
[46] Rhys, J., A selection problem of shared fixed costs and networks, Management Science, 17, 200-207 (1970) · Zbl 0203.52505
[47] Vaessens, R. J.M.; Aarts, E. H.L.; Lenstra, J. K., Job shop scheduling by local search, (Memorandum COSOR 94-05 (1994), Eindhoven University of Technology) · Zbl 0863.90094
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.