Optimization: principles and algorithms, by Michel Bierlaire
intro.m
Go to the documentation of this file.
1 %> \mainpage Optimization: principles and algorithms
2 %>
3 %> <img alt="Optimization: Principles and Algorithms From Michel Bierlaire - PPUR" border="0" height="240" src="http://www.ppur.org/images/thumbnails/0000/2865/978-2-94022-278-0_large.jpg" title="Optimization: Principles and Algorithms From Michel Bierlaire - PPUR" width="160">
4 %> <em>The book <a href="http://www.ppur.org/en/product/740/9782940222780/Optimization Principles and Algorithms" target="_blank">''Optimization: principles and algorithms''</a> has been published in September 2015 by <a href="http://www.epflpress.org" target="_blank">EPFL Press </a>.</em>
5 %>
6 %> This website contains online material related to the book <em>Optimization: principles and algorithms</em>, by <a href="http://people.epfl.ch/michel.bierlaire">Michel Bierlaire</a> (\cite Bier15-book).
7 %> The algorithms presented in the book are coded in <a href="https://www.gnu.org/software/octave/" target="_blank">GNU Octave</a>,
8 %> a high-level interpreted language, primarily intended for numerical computations.
9 %> 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 \ref 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.
10 %>
11 %> The source code is available from the menu "Modules" or "Files". In the "Modules" menu, it is organized into \ref Algorithms, containing the algorithms themselves, \ref Examples, containing various examples of problems to be solved, and \ref Running, containing the code that calls a given algorithm to solve a given problem. The files are also grouped by chapters of the book.
12 %>
13 %> Corrections of mistakes in the book are listed on the page \ref errata.
14 %>
15 %> The entire set of files can be downloaded from <a href="optimizationPrinciplesAlgorithms.zip">here</a>.
16 %>
17 %> \section author The author
18 %>
19 %> <img src="http://transp-or.epfl.ch/images/people/BIERLAIRE.jpg"> Belgian, born in 1967, Michel Bierlaire holds a PhD in Mathematical Sciences
20 %> from the Facult├ęs Universitaires Notre-Dame de la Paix, Namur, Belgium
21 %> (University of Namur). Between 1995 and 1998, he was research
22 %> associate and project manager at the Intelligent Transportation
23 %> Systems Program of the Massachusetts Institute of Technology
24 %> (Cambridge, Ma, USA). Between 1998 and 2006, he was a junior
25 %> faculty in the Operations Research group ROSO within the Institute
26 %> of Mathematics at the Ecole Polytechnique F&eacute;d&eacute;rale de Lausanne (EPFL). In 2006, he was appointed associate
27 %> professor in the School of Architecture, Civil and Environmental
28 %> Engineering at the EPFL, where he became the director of the Transport
29 %> and Mobility laboratory. Since 2009, he is the director of TraCE,
30 %> the Transportation Center, and the director of Doctoral Program in
31 %> Civil and Environmental Engineering at the EPFL. In 2012, he was
32 %> appointed full professor at the EPFL. He has been teaching optimization and
33 %> operations research at the EPFL since 1998.
34 %>
35 %> <a href="http://people.epfl.ch/cgi-bin/people?id=118332&op=bio&lang=en&cvlang=en" target="_blank">Biography</a>
36 %>
37 %> <a href="http://transp-or.epfl.ch/personnal.php?Person=BIERLAIRE" target="_blank">List of publications</a>
38 %>
39 %> \section book The book
40 %>
41 %> Optimization algorithms are important tools for engineers, but
42 %> difficult to use. In fact, none of them is universal, and a good
43 %> understanding of the different methods is necessary in order to
44 %> identify the most appropriate one in the context of specific
45 %> applications. Designed to teach undergraduate engineering students
46 %> about optimization, this book also provides the professionals
47 %> employing optimization methods with significant elements to identify
48 %> the methods that are appropriate for their applications, and to
49 %> understand the possible failures of certain methods on their
50 %> problem. The content is meant to be formal, in the sense that the
51 %> results presented are proven in detail, and all described algorithms
52 %> have been implemented and tested by the author. In addition, the
53 %> many numeric and graphic illustrations constitute a significant base
54 %> for understanding the methods. The book features eight parts. The
55 %> first part focuses on the formulation and the analysis of the
56 %> optimization problem. It describes the modeling process that leads to
57 %> an optimization problem, as well as the transformations of the
58 %> problem into an equivalent formulation. The properties of the problem
59 %> and corresponding hypotheses are
60 %> discussed independently of the algorithms. Subsequently, the
61 %> optimality conditions, the theoretical foundations that are essential
62 %> for properly mastering the algorithms, are analyzed in detail in Part
63 %> II. Before
64 %> explaining the methods for unconstrained continuous optimization in
65 %> Part IV, algorithms for
66 %> solving systems of non linear equations, based on Newton's method,
67 %> are described in Part III. The algorithms for
68 %> constrained continuous optimization constitute
69 %> the fifth part. Part VI addresses optimization
70 %> problems based on network structures, elaborating more specifically
71 %> on the shortest path
72 %> problem, and the maximum flow problem. Discrete optimization problems,
73 %> where the variables are constrained to take integer values, are
74 %> introduced in Part VII, where both exact methods and
75 %> heuristics are presented.
76 %> The last part is an appendix containing the
77 %> definitions and theoretical results used in the book.
78 %>
79 %> \section toc Table of contents
80 %>
81 %> <ul>
82 %> <li>Part I: Formulation and analysis of the problem
83 %> <ul>
84 %> <li>Chapter 1: Formulation</li>
85 %> <li>Chapter 2: Objective function</li>
86 %> <li>Chapter 3: Constraints</li>
87 %> <li>Chapter 4: Introduction to duality</li>
88 %> </ul>
89 %> </li>
90 %> <li>Part II: Optimality conditions
91 %> <ul>
92 %> <li>Chapter 5: Unconstrained optimization</li>
93 %> <li>Chapter 6: Constrained optimization</li>
94 %> </ul></li>
95 %> <li>Part III: Solving equations
96 %> <ul>
97 %> <li>Chapter 7: Newton's method</li>
98 %> <li>Chapter 8: Quasi-Newton methods</li>
99 %> </ul></li>
100 %> <li>Part IV: Unconstrained optimization
101 %> <ul>
102 %> <li>Chapter 9: Quadratic problems</li>
103 %> <li>Chapter 10: Newton's local method</li>
104 %> <li>Chapter 11: Descent methods and line search</li>
105 %> <li>Chapter 12: Trust region</li>
106 %> <li>Chapter 13: Quasi-Newton methods</li>
107 %> <li>Chapter 14: Least squares problem</li>
108 %> <li>Chapter 15: Direct search methods</li>
109 %> </ul></li>
110 %> <li>Part V: Constrained optimization
111 %> <ul>
112 %> <li>Chapter 16: The simplex method</li>
113 %> <li>Chapter 17: Newton's method for constrained optimization</li>
114 %> <li>Chapter 18: Interior point methods</li>
115 %> <li>Chapter 19: Augmented Lagrangian method</li>
116 %> <li>Chapter 20: Sequential quadratic programming</li>
117 %> </ul></li>
118 %> <li>Part VI: Networks
119 %> <ul>
120 %> <li>Chapter 21: Introduction and definitions</li>
121 %> <li>Chapter 22: The transhipment problem</li>
122 %> <li>Chapter 23: Shortest paths</li>
123 %> <li>Chapter 24: Maximum flow</li>
124 %> </ul></li>
125 %> <li>Part VII: Discrete optimization</li>
126 %> <ul>
127 %> <li>Chapter 25: Introduction to discrete optimization</li>
128 %> <li>Chapter 26: Exact methods for discrete optimization</li>
129 %> <li>Chapter 27: Heuristics</li>
130 %> </ul></li>
131 %> <li>Part VIII: Appendices
132 %> <ul>
133 %> <li>Appendix A: Notations</li>
134 %> <li>Appendix B: Definitions</li>
135 %> <li>Appendix C: Theorems</li>
136 %> <li>Appendix D: Projects</li>
137 %> <li>References</li>
138 %> </ul>
139 %> </li>
140 %> </ul>
141 
function transhipment(in adj, in cost, in lb, in ub, in supply, in useGlpk)
Solve the transhipment problem with bound constraints.
Copyright 2015-2016 Michel Bierlaire