Combinatorial Programming: Methods and Applications

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

Proceedings of the NATO Advanced Study Institute, Versailles, France, September 2-13, 1975

Inhalt
I: General Methodology.- Modelling Techniques and Heuristics for Combinatorial Problems.- 1. Objectives of the paper.- 2. Morphology of combinatorial problems.- 3. The general approach to solving combinatorial problems.- 4. Integer programming formulations.- 5. Explicit enumeration.- 6. Tree search (branch and bound) methods, implicit enumeration.- 7. Heuristic methods.- 8. Conclusions.- References.- Les Procedures D'exploration et D'optimisation par Separation et Evaluation: a survey.- I. Classification et forme des tests.- 1. Introduction.- 2. Classification des tests.- 3. Formes des tests.- Bibliographie.- II. Séparations et formes standards.- 1. Introduction.- 2. Principe de séparation.- 3. Formes standards.- 4. Efficience et separations.- Bibliographie.- III. Fonctions d'évaluation et pénalités.- 1. Introduction.- 2. Reformulation d'un problème.- 3. Obtention de fonctions d'évaluation et de penalties en deux phases.- 4. Formulation implicite et relaxations.- 5. Choix des tests.- Bibliographie.- Boolean Elements in Combinatorial Optimization: a survey.- I. Elements of Boolean Algebra.- II. The resolvent.- III. Algorithms.- IV. Equivalent forms of 01 programs.- V. Packing and knapsack problems.- VI. Coefficient transformation.- VII. Polytopes in the unit cube.- VIII. Pseudo-Boolean functions and game theory.- References.- Fourier-Motzkin Elimination and its Dual with Application to Integer Programming.- II: Paths and Circuits.- Chemins et Circuits: Enumeration et Optimisation: a survey.- I. Introduction.- II. Procédures algébriques.- 1. Algèbre des chemins.- a) Définition et interprétation de (L, $$ \rlap{--}{\lambda} $$, E).- b) Hypothèses restrictives.- c) Exemples.- 2. Principaux résultats.- a) Structure matricielle (Mn(L), $$ \rlap{--}{\lambda} $$, E).- b) Résultats fondamentaux.- c) A propos d'algorithmes.- III. Procédures par séparation.- 1. Arborescence des chemins.- a) Définition et propriété de ?.- b) Sous-arborescences particulières.- 2. Fondements des principales procédures.- a) Principe de séparation.- b) Enchaînement des séparations 130 Références.- Path Algebra and Algorithms.- 1. Path algebra.- 1.1. Definition of the algebra.- 1.2. Properties of the path algebra.- 2. General algorithms.- 2.1. Iterative methods.- 2.2. Direct methods.- References.- Hamiltonian Circuits and the Travelling Salesman Problem: a survey.- 1. Introduction.- 2. Hamiltonian circuits in a graph.- 2.1. The enumeration method of Roberts and Flores.- 2.2. The multi-path method.- 2.3. Computational results.- 3. The travelling salesman problem.- 4. The TSP and the SST.- 4.1. The vertex penalty algorithm for SST transformations.- 4.2. Convergence of the vertex-penalty method.- 4.3. The closed TSP.- 5. The TSP and AP.- 5.1. A tree-search algorithm for circuit elimination.- 5.2. A tighter bound from the AP.- References.- The Peripatetic Salesman and some related Unsolved Problems.- 1. Introduction.- 2. The peripatetic salesman problem.- 3. Hamiltonian numbers and perfect r-Hamiltonian graphs.- 4. PSP's with r=2.- 5. Minimum spanning trees.- 6. Discussion.- 7. Suggestions for future research.- 8. Acknowledgments.- References.- 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.- 1. Introduction.- 2. Notation and results.- 3. Labeling procedures.- 4. Order-constrained one-trees and matroid extensions.- References.- III: Set Partitioning, Covering and Packing.- Set Partitioning: a survey.- 1. Background.- 1.1. Set partitioning and its uses.- 1.2. Set packing and set covering.- 1.3. Edge matching and covering, node packing and covering.- 1.4. Node packing, set packing, clique covering.- 2. Theory.- 2.1. Facets of the set packing polytope.- 2.2. Facets of relaxed polytopes: cuts from Disjunctions.- 2.3. Adjacent vertices of the set partitioning and set packing polytopes.- 3. Algorithms.- 3.1. Implicit enumeration.- 3.2. Simplex-based cutting plane methods.- 3.3. A column generating algorithm.- 3.4. A symmetric subgradient cutting plane method.- 3.5. Set partitioning via node covering.- References.- Appendix: A bibliography of applications.- An Algorithm for Large Set Partitioning Problems.- 1. Introduction.- 2. Method of solution.- 2.1. Ordering the matrix.- 2.2. Separating the feasible solutions.- 2.3. Computing the lower bounds.- 2.4. The algorithm.- 3. Computational experience 265 References.- Le Probleme De Partition Sous Contrainte.- 1. Introduction.- 2. Introduction d'une contrainte $$ \sum\limits_1^n {{x_j} = N} $$.- 3. Introduction d autres types de contraintes.- Références.- 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.- 1. Introduction and summary.- 2. Edge coloring.- 3. Node coloring.- 4. Hypergraph coloring.- 5. Balancing the colorings.- References.- Problemes Extremaux Concernant Le Nombre Des Colorations Des Sommets D'un Graphe Fini.- A few Remarks on Chromatic Scheduling.- 1. Introduction and summary.- 2. Colorings of parallel nodes.- 3. Applications 341 References.- Minimizing Total Costs in One-Machine Scheduling.- 1. Introduction.- 2. Description of the algorithm.- 3. Computational experiments.- 4. Concluding remarks.- References.- The Quadratic Assignment Problem: A Brief Review.- 1. Problem statement.- 2. Applications and problem formulations.- 3. Methods of solution.- 4. One dimensional module placement problem.- 5. Special case due to Pratt.- 6. Another special case: network flows.- 7. The special case of trees.- 8. Rooted trees: a special case of Adolphson and Hu.- References.- Fonctions D'evaluation et Penalites Pour Les Programmes Quadratiques en Variables 01.- 1. Introduction.- 2. Fonctions d'évaluation et pénalités.- 3. Algorithmes et essais sur ordinateur.- Bibliographie.- Solution of the Machine Loading Problem with Binary Variables.- 1. Introduction.- 2. The problem.- 3. The method.- 4. Computational experience.- 5. Bibliograpy.- The Role of Puzzles in Teaching Combinatorial Programming.- 1. The use of puzzles in teaching combinatorial programming.- 2. Number puzzles (arithmogriphs).- 3. A discrete step dynamic process.- 4. Puzzles with true and false information (Liar puzzles).- 5. Conclusions.