Optimization: principles and algorithms, by Michel Bierlaire
errata.m
Go to the documentation of this file.
1 %> \page errata Errata
2 %>
3 %> \section errors Errors
4 %>
5 %> -# Page 16: Equation (1.31) is ambiguous. It should be
6 %> \f[
7 %> \argmin{_{x \in X \subseteq \R^n}} f(x) = \argmin{_{x \in X \subseteq \R^n}} h(x),
8 %> \f]
9 %> where \f$h(x)=g(f(x))\f$.
10 %>
11 %> -# Page 86. Theorem 3.40. The correct statement is 'Let \f$\mathcal{P}= \{ x \in \mathbb{R}^n | Ax = b, x \geq 0 \}\f$ be a polyhedron such that each feasible basic solution is non degenerate. The point \f$x^* \in \mathcal{P}\f$ is a vertex of \f$\mathcal{P}\f$ if and only if it is a feasible basic solution.'
12 %>
13 %> -# Page 86. Proof of Theorem 3.40. Replace 'Consider \f$m \f$ linearly independent columns of \f$A\f$, chosen arbitrarily, which form an invertible matrix \f$B\f$,...' by 'As \f$x^*\f$ is not a feasible basic solution, there are strictly more than \f$m\f$ non zero components in \f$x^*\f$. Consider \f$m\f$ linearly independent columns of \f$A\f$, corresponding to non zero components of \f$x^*\f$, which form an invertible matrix \f$B\f$,...
14 %>
15 %> -# Page 99. After Eq. (4.15). 'Therefore, we can eliminate \f$\mu_1\f$ and \f$\mu_2\f$ so that
16 %> \f$17 %> X_q = \{ \lambda | \lambda \leq 1 \}, 18 %> \f$
19 %> and the dual function becomes
20 %> \f$21 %> q(\lambda) = \lambda. 22 %> \f$
23 %> The dual problem is written as
24 %> \f$25 %> \max \lambda 26 %> \f$
27 %> subject to
28 %> \f$29 %> \lambda \leq 1 30 %> \f$'
31 %>
32 %> -# Page 388: 'The algorithm may detect an unbounded problem at step 15, or produce an optimal solution \f$x^*,x_a^*\f$. Consequently, one of the following three possibilities occurs:'. It should be 'The algorithm cannot detect an unbounded problem at step 15, as the objective function of \f$(\mathcal{A}\f$) is bounded below by 0. It always produces an optimal solution \f$x^*,x_a^*\f$. Consequently, one of the following two possibilities occurs:'
33 %>
34 %> -# Page 388: 'In summary, if the original problem is bounded, solving the auxiliary problem....' should be 'In summary, solving the auxiliary problem....'
35 %>
36 %> -# Page 546: Example 22.14: 'The best deal is obtained by selling .... for a total of 32,000.01 kEuros' should be 'The best deal is obtained by selling the Botticelli to Harry, the Bruegel to Giny, the Kandinsky to Ron and the last one to Hermione, for a total of 34,000.01 kEuros.'
37 %>
38 %> \section typos Typos
39 %>
40 %> <table>
41 %> <tr><td> Page 20</td><td> Section 1.3</td><td> 'Korte and Vygen, 2007'</td><td> should be</td><td> 'Korte and Vygen (2007)'</td></tr>
42 %> <tr><td> Page 51</td><td> Definition 3.1</td><td> 'this concept is sometimes called a<em>feasible solution</em>'</td><td> should be</td><td> 'this concept is sometimes called a <em>feasible solution</em>'</td></tr>
43 %> <tr><td>Page 82</td><td> proof of Theorem 3.37</td><td> 'for any \f$i \in \mathcal{A}(x^*)\f$'</td><td> should be</td><td> 'for any \f$i \in \mathcal{A}(x_0)\f$'</td></tr>
44 %> <tr><td>Page 83</td><td> Definition 3.38</td><td> 'If, moreover, \f$x=B^{-1}b \geq 0\f$'</td><td> should be</td><td> 'If, moreover, \f$x_B=B^{-1}b \geq 0\f$'</td></tr>
45 %> <tr><td>Page 166</td><td>After Eq. (6.160)</td><td>'\f$b\in \R^n\f$'</td><td>should be</td><td>'\f$b\in \R^m\f$'</td>
46 %> <tr><td>Page 159</td><td>Example 6.23</td><td>'\f$x_1^2+ 4x_1 +3 = 0 \f$'</td><td>should be</td><td>'\f$x_1^2+ 4x_1 -x_2+3 = 0 \f$'</td>
47 %> <tr><td>Page 263</td><td>Introduction to Section 11.3</td><td>'a one-dimensional optimization problems'</td><td>should be</td><td>'a one-dimensional optimization problem'</td>
48 %> <tr><td>Page 265</td><td>Last paragraph</td><td>'the improvement of objective function'</td><td>should be</td><td>'the improvement of the objective function'</td>
49 %> <tr><td>Page 371</td><td>Algorithm 16.2, step 22</td><td>'\f$\alpha_q = \min_i \lambda_i \f$'</td><td>should be</td><td>'\f$\alpha_q = \min_i \alpha_i \f$'</td></tr>
50 %> <tr><td> Page 494</td><td> Definition 21.4</td><td> 'where \f$\mathcal{M} \subseteq \mathcal{N}\f$'</td><td> should be</td><td> 'where \f$\mathcal{M} \subset \mathcal{N}\f$'</td></tr>
51 %> <tr><td>Page 501</td><td> biography of Leonhard Euler</td><td> '..., and became friends with his two sons'</td><td> should be </td><td>'..., and became friend with his two sons'</td></tr>
52 %> <tr><td>Page 506</td><td> Theorem 21.14</td><td> 'a subset of nodes \f$\mathcal{M} \subseteq \mathcal{N}\f$'</td><td> should be</td><td> 'a subset of nodes \f$\mathcal{M} \subset \mathcal{N}\f$'.</td></tr>
53 %> <tr><td> Page 535</td><td> Section 22.2</td><td> 'The Karush-Kuhn-Tucker conditions (see Theorem 6.13) significantly simplify the transhipment problem'</td><td> should be</td><td> 'The Karush-Kuhn-Tucker conditions (see Theorem 6.13) are significantly simpler for the transhipment problem'</td></tr>
54 %> </table>
function transhipment(in adj, in cost, in lb, in ub, in supply, in useGlpk)
Solve the transhipment problem with bound constraints.