Gérard-Michel Cochard is Professor Emeritus at Université de Picardie Jules Verne, France, where he has held various senior positions. He has also served at the French Ministry of Education and the CNAM (Conservatoire National des Arts et Métiers). His research is conducted at the Eco-PRocédés, Optimisation et Aide à la Décision (EPROAD) laboratory, France.Mhand Hifi is Professor of Computer Science at Université de Picardie Jules Verne, France, where he heads the EPROAD UR 4669 laboratory and manages the ROD team. As an expert in operations research and NP-hard problem-solving, he actively contributes to numerous international conferences and journals in the field.

• Preface ixChapter 1. Linear Modeling for Two-Dimensional Data 11.1. Basic statistics 11.2. Linear adjustment 31.3. Linear correlation 7Chapter 2. Multidimensional Data Analysis 132.1. Multidimensional tables 142.2. Analysis of a point cloud 242.2.1. Spatial analysis of individuals 242.2.2. Analysis in variable space 302.2.3. Link between the two spaces 322.3. Principal component factor analysis 352.3.1. Principles 352.3.2. Principal component factor analysis in practice 412.4. Appendix: useful software 482.5. Tanagra software 482.6. R software 56Chapter 3. Introduction to Automatic Classification 653.1. Similarity and distance 663.1.1. Similarity, dissimilarity 663.1.2. Distance 673.2. Basics of information theory 693.3. Classification methods 783.4. Classification by partitioning 803.4.1. Partitioning principle 803.4.2. Inertia 813.4.3. Mobile center algorithm 823.5. Hierarchical classification 893.5.1. Principle 893.5.2. Aggregation strategies 903.5.3. Ward's aggregation strategy 983.6. Appendices 1013.6.1. Huygens–König theorem 1013.6.2. Classification software 103Chapter 4. Linear Programming 1094.1. An introductory example 1104.2. General formulation 1134.3. Geometry of a linear program 1164.4. Simplex algorithm 1184.5. Two-phase method. 1294.6. Duality 1354.7. Degeneracy 1394.8. Introduction to integer linear programming 1404.8.1. Gomory cuts 1404.8.2. Branch and Bound algorithm 151Chapter 5. Elements of Graph Theory 1595.1. Definition and representations of a graph 1605.1.1. Graphical representation 1605.1.2. Tables associated with a graph 1615.2. Main concepts and technology 1625.2.1. Elements of a graph 1635.2.2. Analysis of graph structure 1685.3. Transitive closure of a graph's vertices 1725.4. Decomposition of a directed graph into strongly connected components 1735.5. Trees 1755.5.1. Introduction 1755.5.2. Trees in a graph 1755.5.3. Spanning tree in a graph 1775.6. Finding a fundamental system of independent cycles of a connected graph 1795.7. Extremum spanning tree 1805.7.1. General information 1805.7.2. Extremum spanning tree search algorithms 180Chapter 6. Path Optimization 1876.1. Extremal-length paths 1886.1.1. General information 1886.1.2. Solving algorithms 1896.1.3. Searching for ε -extremal paths 2046.2. Hamiltonian path search 2056.2.1. Decomposition into strongly connected components 2056.2.2. Branch and Bound algorithm 207Chapter 7. Transportation Problems 2197.1. Maximum flow 2207.1.1. General 2207.1.2. Ford–Fulkerson theorem 2237.1.3. Ford–Fulkerson algorithm 2247.1.4. Practical solution method 2307.2. Least cost transportation 2367.2.1. Issues 2367.2.2. Northwest Corner algorithm 2387.2.3. Least cost method 2407.2.4. Balas-Hammer or Vogel's algorithm 2437.2.5. Stepping stone algorithm 2467.2.6. Inequality of supply and demand 2567.2.7. Unconnected graph and degeneration 2577.2.8. Potentials and dual program 2617.3. Assignment problems 2637.3.1. Issues 2637.3.2. Hungarian algorithm 269Chapter 8. Scheduling Problems 2798.1. Planning a project 2808.1.1. Introduction 2808.1.2. Earliest and latest date method 2838.1.3. Gantt chart 2898.2. Flow-shop problem 2918.2.1. Johnson's algorithm for two machines 2938.2.2. Case of three machines 2978.3. The job-shop problem 306References 311List of Authors 313Index 315

Gérard-Michel Cochard is Professor Emeritus at Université de Picardie Jules Verne, France, where he has held various senior positions. He has also served at the French Ministry of Education and the CNAM (Conservatoire National des Arts et Métiers). His research is conducted at the Eco-PRocédés, Optimisation et Aide à la Décision (EPROAD) laboratory, France.Mhand Hifi is Professor of Computer Science at Université de Picardie Jules Verne, France, where he heads the EPROAD UR 4669 laboratory and manages the ROD team. As an expert in operations research and NP-hard problem-solving, he actively contributes to numerous international conferences and journals in the field.

• Preface ixChapter 1. Linear Modeling for Two-Dimensional Data 11.1. Basic statistics 11.2. Linear adjustment 31.3. Linear correlation 7Chapter 2. Multidimensional Data Analysis 132.1. Multidimensional tables 142.2. Analysis of a point cloud 242.2.1. Spatial analysis of individuals 242.2.2. Analysis in variable space 302.2.3. Link between the two spaces 322.3. Principal component factor analysis 352.3.1. Principles 352.3.2. Principal component factor analysis in practice 412.4. Appendix: useful software 482.5. Tanagra software 482.6. R software 56Chapter 3. Introduction to Automatic Classification 653.1. Similarity and distance 663.1.1. Similarity, dissimilarity 663.1.2. Distance 673.2. Basics of information theory 693.3. Classification methods 783.4. Classification by partitioning 803.4.1. Partitioning principle 803.4.2. Inertia 813.4.3. Mobile center algorithm 823.5. Hierarchical classification 893.5.1. Principle 893.5.2. Aggregation strategies 903.5.3. Ward's aggregation strategy 983.6. Appendices 1013.6.1. Huygens–König theorem 1013.6.2. Classification software 103Chapter 4. Linear Programming 1094.1. An introductory example 1104.2. General formulation 1134.3. Geometry of a linear program 1164.4. Simplex algorithm 1184.5. Two-phase method. 1294.6. Duality 1354.7. Degeneracy 1394.8. Introduction to integer linear programming 1404.8.1. Gomory cuts 1404.8.2. Branch and Bound algorithm 151Chapter 5. Elements of Graph Theory 1595.1. Definition and representations of a graph 1605.1.1. Graphical representation 1605.1.2. Tables associated with a graph 1615.2. Main concepts and technology 1625.2.1. Elements of a graph 1635.2.2. Analysis of graph structure 1685.3. Transitive closure of a graph's vertices 1725.4. Decomposition of a directed graph into strongly connected components 1735.5. Trees 1755.5.1. Introduction 1755.5.2. Trees in a graph 1755.5.3. Spanning tree in a graph 1775.6. Finding a fundamental system of independent cycles of a connected graph 1795.7. Extremum spanning tree 1805.7.1. General information 1805.7.2. Extremum spanning tree search algorithms 180Chapter 6. Path Optimization 1876.1. Extremal-length paths 1886.1.1. General information 1886.1.2. Solving algorithms 1896.1.3. Searching for ε -extremal paths 2046.2. Hamiltonian path search 2056.2.1. Decomposition into strongly connected components 2056.2.2. Branch and Bound algorithm 207Chapter 7. Transportation Problems 2197.1. Maximum flow 2207.1.1. General 2207.1.2. Ford–Fulkerson theorem 2237.1.3. Ford–Fulkerson algorithm 2247.1.4. Practical solution method 2307.2. Least cost transportation 2367.2.1. Issues 2367.2.2. Northwest Corner algorithm 2387.2.3. Least cost method 2407.2.4. Balas-Hammer or Vogel's algorithm 2437.2.5. Stepping stone algorithm 2467.2.6. Inequality of supply and demand 2567.2.7. Unconnected graph and degeneration 2577.2.8. Potentials and dual program 2617.3. Assignment problems 2637.3.1. Issues 2637.3.2. Hungarian algorithm 269Chapter 8. Scheduling Problems 2798.1. Planning a project 2808.1.1. Introduction 2808.1.2. Earliest and latest date method 2838.1.3. Gantt chart 2898.2. Flow-shop problem 2918.2.1. Johnson's algorithm for two machines 2938.2.2. Case of three machines 2978.3. The job-shop problem 306References 311List of Authors 313Index 315

Gérard-Michel Cochard is Professor Emeritus at Université de Picardie Jules Verne, France, where he has held various senior positions. He has also served at the French Ministry of Education and the CNAM (Conservatoire National des Arts et Métiers). His research is conducted at the Eco-PRocédés, Optimisation et Aide à la Décision (EPROAD) laboratory, France.Mhand Hifi is Professor of Computer Science at Université de Picardie Jules Verne, France, where he heads the EPROAD UR 4669 laboratory and manages the ROD team. As an expert in operations research and NP-hard problem-solving, he actively contributes to numerous international conferences and journals in the field.

• Preface ixChapter 1. Linear Modeling for Two-Dimensional Data 11.1. Basic statistics 11.2. Linear adjustment 31.3. Linear correlation 7Chapter 2. Multidimensional Data Analysis 132.1. Multidimensional tables 142.2. Analysis of a point cloud 242.2.1. Spatial analysis of individuals 242.2.2. Analysis in variable space 302.2.3. Link between the two spaces 322.3. Principal component factor analysis 352.3.1. Principles 352.3.2. Principal component factor analysis in practice 412.4. Appendix: useful software 482.5. Tanagra software 482.6. R software 56Chapter 3. Introduction to Automatic Classification 653.1. Similarity and distance 663.1.1. Similarity, dissimilarity 663.1.2. Distance 673.2. Basics of information theory 693.3. Classification methods 783.4. Classification by partitioning 803.4.1. Partitioning principle 803.4.2. Inertia 813.4.3. Mobile center algorithm 823.5. Hierarchical classification 893.5.1. Principle 893.5.2. Aggregation strategies 903.5.3. Ward's aggregation strategy 983.6. Appendices 1013.6.1. Huygens–König theorem 1013.6.2. Classification software 103Chapter 4. Linear Programming 1094.1. An introductory example 1104.2. General formulation 1134.3. Geometry of a linear program 1164.4. Simplex algorithm 1184.5. Two-phase method. 1294.6. Duality 1354.7. Degeneracy 1394.8. Introduction to integer linear programming 1404.8.1. Gomory cuts 1404.8.2. Branch and Bound algorithm 151Chapter 5. Elements of Graph Theory 1595.1. Definition and representations of a graph 1605.1.1. Graphical representation 1605.1.2. Tables associated with a graph 1615.2. Main concepts and technology 1625.2.1. Elements of a graph 1635.2.2. Analysis of graph structure 1685.3. Transitive closure of a graph's vertices 1725.4. Decomposition of a directed graph into strongly connected components 1735.5. Trees 1755.5.1. Introduction 1755.5.2. Trees in a graph 1755.5.3. Spanning tree in a graph 1775.6. Finding a fundamental system of independent cycles of a connected graph 1795.7. Extremum spanning tree 1805.7.1. General information 1805.7.2. Extremum spanning tree search algorithms 180Chapter 6. Path Optimization 1876.1. Extremal-length paths 1886.1.1. General information 1886.1.2. Solving algorithms 1896.1.3. Searching for ε -extremal paths 2046.2. Hamiltonian path search 2056.2.1. Decomposition into strongly connected components 2056.2.2. Branch and Bound algorithm 207Chapter 7. Transportation Problems 2197.1. Maximum flow 2207.1.1. General 2207.1.2. Ford–Fulkerson theorem 2237.1.3. Ford–Fulkerson algorithm 2247.1.4. Practical solution method 2307.2. Least cost transportation 2367.2.1. Issues 2367.2.2. Northwest Corner algorithm 2387.2.3. Least cost method 2407.2.4. Balas-Hammer or Vogel's algorithm 2437.2.5. Stepping stone algorithm 2467.2.6. Inequality of supply and demand 2567.2.7. Unconnected graph and degeneration 2577.2.8. Potentials and dual program 2617.3. Assignment problems 2637.3.1. Issues 2637.3.2. Hungarian algorithm 269Chapter 8. Scheduling Problems 2798.1. Planning a project 2808.1.1. Introduction 2808.1.2. Earliest and latest date method 2838.1.3. Gantt chart 2898.2. Flow-shop problem 2918.2.1. Johnson's algorithm for two machines 2938.2.2. Case of three machines 2978.3. The job-shop problem 306References 311List of Authors 313Index 315