Combinatorial Programming: Methods and Applications

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 0–1 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 0–1.- 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.