Optimization: principles and algorithms, by Michel Bierlaire
This website contains online material related to the book Optimization: principles and algorithms, by Michel Bierlaire (). The algorithms presented in the book are coded in GNU Octave, a high-level interpreted language, primarily intended for numerical computations. These codes are provided for illustration only. They are by no means designed to be efficient, and have not been thoroughly tested under all conditions (see Disclaimer). All the examples have been run on GNU Octave, version 3.8.1. on a MacBook Pro running OS X Yosemite 10.10.2.
The source code is available from the menu "Modules" or "Files". In the "Modules" menu, it is organized into Algorithms, containing the algorithms themselves, Problems to solve, containing various examples of problems to be solved, and Code to run the examples, containing the code that calls a given algorithm to solve a given problem. The files are also grouped by chapters of the book.
Corrections of mistakes in the book are listed on the page Errata.
The entire set of files can be downloaded from here.
Belgian, born in 1967, Michel Bierlaire holds a PhD in Mathematical Sciences from the Facultés Universitaires Notre-Dame de la Paix, Namur, Belgium (University of Namur). Between 1995 and 1998, he was research associate and project manager at the Intelligent Transportation Systems Program of the Massachusetts Institute of Technology (Cambridge, Ma, USA). Between 1998 and 2006, he was a junior faculty in the Operations Research group ROSO within the Institute of Mathematics at the Ecole Polytechnique Fédérale de Lausanne (EPFL). In 2006, he was appointed associate professor in the School of Architecture, Civil and Environmental Engineering at the EPFL, where he became the director of the Transport and Mobility laboratory. Since 2009, he is the director of TraCE, the Transportation Center, and the director of Doctoral Program in Civil and Environmental Engineering at the EPFL. In 2012, he was appointed full professor at the EPFL. He has been teaching optimization and operations research at the EPFL since 1998.
Optimization algorithms are important tools for engineers, but difficult to use. In fact, none of them is universal, and a good understanding of the different methods is necessary in order to identify the most appropriate one in the context of specific applications. Designed to teach undergraduate engineering students about optimization, this book also provides the professionals employing optimization methods with significant elements to identify the methods that are appropriate for their applications, and to understand the possible failures of certain methods on their problem. The content is meant to be formal, in the sense that the results presented are proven in detail, and all described algorithms have been implemented and tested by the author. In addition, the many numeric and graphic illustrations constitute a significant base for understanding the methods. The book features eight parts. The first part focuses on the formulation and the analysis of the optimization problem. It describes the modeling process that leads to an optimization problem, as well as the transformations of the problem into an equivalent formulation. The properties of the problem and corresponding hypotheses are discussed independently of the algorithms. Subsequently, the optimality conditions, the theoretical foundations that are essential for properly mastering the algorithms, are analyzed in detail in Part II. Before explaining the methods for unconstrained continuous optimization in Part IV, algorithms for solving systems of non linear equations, based on Newton's method, are described in Part III. The algorithms for constrained continuous optimization constitute the fifth part. Part VI addresses optimization problems based on network structures, elaborating more specifically on the shortest path problem, and the maximum flow problem. Discrete optimization problems, where the variables are constrained to take integer values, are introduced in Part VII, where both exact methods and heuristics are presented. The last part is an appendix containing the definitions and theoretical results used in the book.