Combinatorial Programming: Methods and Applications -

. .

Résumé :
Combinatorial Programming are two words whose juxtaposition still strike us as unusual, nevertheless their association in recent years adequately reflects the preoccupations underlying differing work fields, and their importance will increase both from methodology and application view points. To those who like definitions and consider the function of this book to furnish one for combinatorial programming, I will simply say that it is precise? ly this which is exclusively treated here and which in the eyes of the autors is the heart of this branch of applied mathematics. Such was the initial intention of those who in the spring of 1973 gathered tog~ther in Paris to state the work of the Advanced Study Institute from which this book arises. As young as combinatorial programming is, it was easy to see that a two week school was insufficient to cover the subject in an exhaustive manner. Finally the decision had to be taken to reduce to book form, and to organise within this particular means of expression, the essential syntheses and communications. Unfortunately the discussions, the round tables, and the majority of the case studies could not be included in this book which is more of a hand-book on the subject. XIV PREFACE The choice and orientation of the surveys has been guided by two criteria : the importance of already accomplished work, and the originality of the survey to be undertaken.

Sommaire:
I: General Methodology.- Modelling Techniques and Heuristics for Combinatorial Problems.- Les Procedures D'exploration et D'optimisation par Separation et Evaluation: a survey.- Boolean Elements in Combinatorial Optimization: a survey.- Fourier-Motzkin Elimination and its Dual with Application to Integer Programming.- II: Paths and Circuits.- Chemins et Circuits: Enumeration et Optimisation: a survey.- Path Algebra and Algorithms.- Hamiltonian Circuits and the Travelling Salesman Problem: a survey.- The Peripatetic Salesman and some related Unsolved Problems.- Some Results on the Convex Hull of the Hamiltonian Cycles of Symetric Complete Graphs.- Finding Minimum Spanning Trees with a Fixed Number of Links at a Node.- III: Set Partitioning, Covering and Packing.- Set Partitioning: a survey.- An Algorithm for Large Set Partitioning Problems.- Le Probleme De Partition Sous Contrainte.- Characterisations of Totally Unimodular, Balanced and Perfect Matrices.- Some Well-Solved Problems in Combinatorial Optimization.- IV: Other Combinatorial Programming Topics.- How to Color a Graph: a survey.- Problemes Extremaux Concernant Le Nombre Des Colorations Des Sommets D'un Graphe Fini.- A few Remarks on Chromatic Scheduling.- Minimizing Total Costs in One-Machine Scheduling.- The Quadratic Assignment Problem: A Brief Review.- Fonctions D'evaluation et Penalites Pour Les Programmes Quadratiques en Variables 0-1.- Solution of the Machine Loading Problem with Binary Variables.- The Role of Puzzles in Teaching Combinatorial Programming.