← Back to the site

Question bank

336 fixed questions · 29 generated questions

Fixed questions (336)

Part: Tools (90)

1. Introduction to the course (24)

nlpm-f-001 · level facile · notes
The course classifies its models as LP, QP or NLP. Which class has a quadratic objective function and only linear constraints?
  1. LP
  2. NLP with conic constraints
  3. QP
  4. Stochastic LP
Explanation. QP (*Quadratic Programming*): quadratic objective, linear constraints. In an LP everything is linear; in an NLP the objective or the constraints are general nonlinear functions.
nlpm-f-002 · level facile · notes
In the course notes an optimization problem is called *convex* when:
  1. every local minimum is also a global minimum
  2. all its constraints are linear functions
  3. its optimal solution is unique
  4. its objective is differentiable everywhere
Explanation. This is the working definition of the notes: for LPs it always holds, for QPs and NLPs it depends on the functions. Linearity, uniqueness and differentiability are different properties.
nlpm-f-074 · level facile · notes
The course classifies models as LP (everything linear), QP (quadratic objective, linear constraints) and NLP (general nonlinear objective or constraints). A model with a linear objective and the constraint $x_1^2 + x_2^2 \le d^2$ is:
  1. an LP, because the objective is linear
  2. a QP, because it contains quadratic terms
  3. an NLP, because a constraint is nonlinear
  4. not classifiable in these three classes
Explanation. A QP requires linear constraints; a quadratic constraint makes the model an NLP (here a convex one, like the conic constraints of the location chapter).
nlpm-f-075 · level facile · notes
The course turns managerial problems into continuous optimization models and solves them with Gurobi. According to the notes, what is the right question at the end of every lab session?
  1. What is the optimal value of the model?
  2. Which solver finds the optimum fastest?
  3. Which decision do we recommend, and how robust is it?
  4. How many variables and constraints does the model have?
Explanation. The value of a model lies in the quality of the recommendation it supports: the optimum is the starting point, not the answer.
nlpm-f-076 · level facile · notes
In the course a solved model is not only read but *interrogated*. Which of these is an example of interrogating a production plan?
  1. How much is one more hour of capacity worth?
  2. How many simplex iterations did Gurobi need?
  3. Which Python version ran the script?
  4. How many decimal digits does the solver print?
Explanation. Interrogating means asking economic questions of the solution: the value of a resource (shadow prices), the robustness to data changes, the trade-offs to recommend.
nlpm-f-107 · level facile · notes
The course uses mathematical programming as a *decision* tool. According to the notes, where does the value of a model lie?
  1. In the precision of the optimal value it computes
  2. In the speed of the solver that solves it
  3. In the quality of the recommendation it makes possible
  4. In the number of variables and constraints it handles
Explanation. The notes say it explicitly: the value of a model lies in the quality of the recommendation it allows us to formulate; the optimal value is only the starting point.
nlpm-f-108 · level facile · notes
After solving a course model we *interrogate* it with three kinds of questions: marginal value, robustness, compromise. Which question is about **robustness**?
  1. Does the solution hold if the data change by 5%?
  2. How much is one more hour of capacity worth?
  3. Which compromise would we advise the decision maker?
  4. What is the optimal value of the objective?
Explanation. Robustness asks whether the recommendation survives a perturbation of the data. One more hour of capacity is a marginal value (a shadow price), the compromise is a trade-off, the optimal value is not an interrogation at all.
nlpm-f-109 · level facile · notes
The course classifies its models as LP (all linear), QP (quadratic objective, linear constraints) and NLP (general nonlinear functions). For which class do the notes say that convexity (every local minimum is global) **always** holds?
  1. QP
  2. NLP
  3. None: it must always be checked
  4. LP
Explanation. For an LP convexity always holds; for QPs and NLPs it depends on the functions (for a QP, on the matrix $\mathbf Q$), and the notes point it out chapter by chapter.
nlpm-f-223 · level facile · notes
In the map of the models of NLP Modelling, which class does least-squares regression belong to?
  1. Non-convex NLP
  2. Convex QP
  3. Scenario LP
  4. Convex NLP with conic constraints
Explanation. The sum of the squared residuals is a convex quadratic function and the constraints defining the residuals are linear: it is a convex QP.
nlpm-f-224 · level facile · notes
Three chapters of NLP Modelling (production, EV charging, least squares) are variants of cases covered in LP Modelling. What changes with respect to the linear case?
  1. The data, which are generated anew
  2. The variables, which become integer
  3. The constraints, which become quadratic
  4. The objective, with a quadratic term
Explanation. Data, variables and constraints stay those of the linear case: the objective changes, with a convex quadratic term added (or substituted).
nlpm-f-225 · level facile · notes
In the map of the models of NLP Modelling, which application is a non-convex NLP?
  1. Pricing with price-dependent demand
  2. The Markowitz portfolio with caps on the weights
  3. Weber's location with conic constraints
  4. The soft-margin SVM with a linear kernel
Explanation. In pricing the revenue $p \cdot q$ is bilinear and the model is not convex; Markowitz and the SVM are convex QPs, Weber is a convex NLP with conic constraints.
nlpm-f-226 · level facile · notes
The essential path of NLP Modelling has four sessions. What does the first one cover?
  1. Production with quadratic smoothing
  2. Pricing or the advertising budget
  3. The Markowitz portfolio
  4. A project of your choice
Explanation. The first session is Markowitz (convex QP and frontier), the second production with smoothing, the third pricing or budget, the fourth a project.
nlpm-f-227 · level facile · notes
In the second session of NLP Modelling (production with smoothing), which learning objective is central?
  1. Formulating a multi-period LP from scratch
  2. Reading and verifying the multipliers of a QP
  3. Estimating a quantile regression
  4. Using binary variables for the changes of pace
Explanation. The session adds a quadratic term to a known linear model and teaches how to read the multipliers of the QP and verify them by perturbation.
nlpm-f-228 · level facile · notes
NLP Modelling assumes another course of the series for notation, general solver commands and the sensitivity protocol. Which one?
  1. LP Modelling
  2. MIP Modelling
  3. Heuristic Algorithms
  4. Dynamic Programming
Explanation. The course follows LP Modelling, from which it takes the notation, the general Gurobi commands and the sensitivity protocol; Convex Optimization provides the notions of convexity.
nlpm-f-301 · level ipotesi · notes
A model has a linear objective and the constraint $x_1^2 + x_2^2 \le d^2$. Under which assumption on $d$ is the problem convex?
  1. Only for integer $d$, like count data
  2. Only for $d > 1$, so that the disc does not degenerate
  3. For every $d$: $x_1^2 + x_2^2 \le d^2$ is a disc
  4. Never: a quadratic constraint is never convex
Explanation. The constraint describes a disc (a point for $d = 0$), which is convex; with a linear objective the problem is convex: a convex NLP, not a QP.
nlpm-f-311 · level facile · notes
What does every application chapter of NLP Modelling start from?
  1. From a theorem to be proved
  2. From an algorithm to be coded
  3. From a concrete managerial problem
  4. From a past exam exercise
Explanation. Every chapter starts from a concrete managerial problem, turns it into a nonlinear model, solves it with Gurobi and queries it.
nlpm-f-312 · level facile · notes
How are the models of the course run with nothing to install?
  1. With the Colab notebook of the chapter
  2. Only on the lab computers
  3. With a spreadsheet
  4. They cannot: Gurobi is always needed locally
Explanation. Every chapter has its own notebook that opens in Colab and runs in the browser, with nothing to install.
nlpm-f-313 · level facile · notes
In which part of the course is the chapter on the Support Vector Machine?
  1. Tools, with the theory and the solver
  2. Deterministic models
  3. The course, with the organization
  4. Optimization and machine learning
Explanation. The parts are Tools, Deterministic models and Optimization and machine learning; the SVM and least squares are in the third one.
nlpm-f-314 · level facile · notes
In the syllabus of the course, what kind of model is the continuous location of a service?
  1. An LP
  2. A convex NLP
  3. A non-convex NLP
  4. An integer programming problem
Explanation. Weber location has conic constraints $d_x^2 + d_y^2 \le d^2$: it is a convex NLP, solved to global optimality.
nlpm-f-315 · level facile · notes
How many application chapters and how many tool chapters does NLP Modelling have?
  1. 5 application and 5 tool chapters
  2. 13 application and no tool chapters
  3. 10 application and 3 tool chapters
  4. 8 application and 2 tool chapters
Explanation. The course has 10 application chapters (from production to least squares) and 3 tool chapters (introduction, theory, solver).
nlpm-f-316 · level facile · notes
Which of these elements makes a model of the course an NLP rather than a QP?
  1. A term $\log(1 + k\,x)$, as in the budget
  2. An objective $\sum_i r_i^2$ with linear constraints
  3. A linear flow-balance constraint
  4. A free variable, with no sign restriction
Explanation. A QP has a quadratic objective and linear constraints; a function such as the logarithm of the budget response makes the model an NLP.
nlpm-f-317 · level facile · notes
Which course of the series covers convex sets and functions, recalled in NLP Modelling?
  1. Dynamic Programming
  2. Convex Optimization
  3. Approximation Algorithms
  4. Network Optimization
Explanation. The prerequisites are LP Modelling and Convex Optimization; the latter covers convex sets and functions.
nlpm-f-324 · level teorema · notes
A QP has objective $\tfrac12 \mathbf x'\mathbf Q\mathbf x + \mathbf c'\mathbf x$ with $\mathbf Q \succeq 0$ and linear constraints. What can be said of a point satisfying the KKT conditions?
  1. It is only a stationary point, perhaps a saddle
  2. It is a global optimum
  3. It is a local optimum but not necessarily global
  4. It is feasible but not optimal
Explanation. With $\mathbf Q \succeq 0$ the QP is convex: the KKT conditions are also sufficient and every KKT point is a global optimum.
nlpm-f-332 · level ipotesi · notes
An equality constraint $h(\mathbf x) = 0$ appears in a model. Under which assumption on $h$ is the set it defines surely convex?
  1. $h$ convex in all the variables
  2. $h$ continuously differentiable
  3. $h$ quadratic with a matrix $\succeq 0$
  4. $h$ affine (linear plus a constant)
Explanation. An equality with a nonlinear function, for instance $x_1 x_2 = 1$, defines in general a non-convex set; with $h$ affine the set is a hyperplane.

2. Background: convexity, QP and KKT (23)

nlpm-f-003 · level teorema · notes
Problem $\min f(x)$ subject to $g_i(x) \le 0$ and $h_k(x) = 0$, with differentiable functions. Which statement about the KKT conditions is correct?
  1. Every point satisfying them is a global optimum, whatever $f$, $g_i$ and $h_k$
  2. They hold at every regular local optimum, and under convexity they are also sufficient
  3. They are necessary and sufficient as soon as all the constraints are linear
  4. They guarantee global optimality whenever all the multipliers are strictly positive
Explanation. The KKT conditions are necessary at regular optima and become sufficient when the problem is convex. Linear constraints do not make a non-convex $f$ harmless. For an LP they reduce to complementary slackness.
nlpm-f-004 · level teorema · notes
A QP has objective $\tfrac12 \sum_{i}\sum_{j} q_{ij} x_i x_j + \sum_j c_j x_j$ (to be minimized) and linear constraints. It is convex:
  1. if and only if the matrix $Q = (q_{ij})$ is positive semidefinite
  2. always, because its constraints are linear
  3. if and only if all the entries $q_{ij}$ are non-negative
  4. if and only if $Q$ is diagonal with positive entries
Explanation. The feasible set is a polyhedron (convex); the quadratic objective is convex exactly when $Q \succeq 0$. Non-negative entries are neither necessary nor sufficient, and diagonal is only a special case.
nlpm-f-005 · level ipotesi · notes
A point satisfies the KKT conditions of $\min f(x)$ subject to $g_i(x) \le 0$, $h_k(x) = 0$ (multipliers $\lambda_i \ge 0$ for the $g_i$). What is needed to conclude that it is a **global** optimum?
  1. The problem must be convex: $f$ and the $g_i$ convex, the $h_k$ affine
  2. All the inequality constraints $g_i$ must be active at the point
  3. All the multipliers $\lambda_i$ must be strictly positive
  4. It suffices that $f$ be differentiable at the point
Explanation. Convexity makes the KKT conditions sufficient. Active constraints or positive multipliers do not guarantee globality in a non-convex problem.
nlpm-f-077 · level facile · notes
Convex QP: $\min x_1^2 + 2x_2^2$ subject to $x_1 + x_2 \ge 6$, $x_1, x_2 \ge 0$. At the optimum the constraint is active and the partial derivatives equal its multiplier $\lambda$: $2x_1 = 4x_2 = \lambda$. What are $\tilde x$, the optimal value and $\lambda$?
  1. $\tilde x = (3, 3)$, value $27$, $\lambda = 6$
  2. $\tilde x = (4, 2)$, value $24$, $\lambda = 8$
  3. $\tilde x = (2, 4)$, value $36$, $\lambda = 16$
  4. $\tilde x = (6, 0)$, value $36$, $\lambda = 12$
Explanation. $x_1 = 2x_2$ and $x_1 + x_2 = 6$ give $(4, 2)$, value $16 + 8 = 24$, $\lambda = 8$. By perturbation, with right-hand side 7 the value becomes $32.67 \approx 24 + 8$.
nlpm-f-110 · level media · notes
For which values of the parameter $\gamma$ is $f(x_1, x_2) = x_1^2 + \gamma x_1x_2 + x_2^2$ convex? (A quadratic function $\tfrac12\mathbf x'\mathbf Q\mathbf x$ is convex if and only if $\mathbf Q \succeq 0$.)
  1. For every $\gamma \ge 0$
  2. For $|\gamma| \le 1$
  3. For $|\gamma| \le 2$
  4. For every real $\gamma$
Explanation. Here $\mathbf Q = \begin{pmatrix} 2 & \gamma \\ \gamma & 2 \end{pmatrix}$: diagonal entries positive and $\det\mathbf Q = 4 - \gamma^2 \ge 0$, i.e. $|\gamma| \le 2$. Forgetting the factor $\tfrac12$ gives $|\gamma| \le 1$.
nlpm-f-111 · level facile · notes
Convex QP $\min\ x_1^2 + 2x_2^2$ subject to $x_1 + x_2 \ge d$, $x \ge 0$: with $d = 6$ the optimal value is $24$ and the multiplier $\lambda = 8$. With $d = 7$ the optimal value is $32.67$, not $24 + 8 = 32$. Why?
  1. The multiplier is exact only at the margin (curvature)
  2. The solver uses too loose a feasibility tolerance
  3. With $d = 7$ the constraint is no longer active
  4. The multiplier of a QP is never a marginal value
Explanation. Here $\tilde f(d) = \tfrac23 d^2$, so $\tilde f(6 + \varepsilon) = 24 + 8\varepsilon + \tfrac23\varepsilon^2$: the multiplier gives the first-order term, and the quadratic term of the curvature adds $0.67$ for $\varepsilon = 1$.
nlpm-f-112 · level facile · notes
KKT conditions for $\min f(\mathbf x)$ subject to $g_i(\mathbf x) \le 0$ ($i = 1, \dots, m$) and $h_j(\mathbf x) = 0$ ($j = 1, \dots, q$). How is the Lagrangian written in the course notes?
  1. $f - \sum_i\lambda_ig_i - \sum_j\nu_jh_j$, with $\lambda_i \le 0$
  2. $f + \sum_i\lambda_ig_i + \sum_j\nu_jh_j$, with $\nu_j \ge 0$ and $\lambda_i$ free
  3. $\sum_i\lambda_ig_i + \sum_j\nu_jh_j$, with $\lambda_i \ge 0$
  4. $f + \sum_i\lambda_ig_i + \sum_j\nu_jh_j$, with $\lambda_i \ge 0$
Explanation. $L = f + \sum_i\lambda_ig_i + \sum_j\nu_jh_j$: the multipliers of the inequalities $g_i \le 0$ are nonnegative, those of the equalities free. Stationarity asks $\partial L/\partial x_k = 0$, complementarity $\lambda_ig_i = 0$.
nlpm-f-113 · level teorema · notes
What do the KKT conditions become when applied to an LP (written as $\min$ with constraints $g_i \le 0$)?
  1. They lose meaning, because an LP has no derivatives
  2. Exactly complementary slackness, with dual feasibility
  3. Only the primal feasibility conditions of the LP
  4. Weaker conditions, necessary but never sufficient
Explanation. For an LP the multipliers $\lambda_i$ are the duals $\pi_i$, those of the sign constraints are the reduced costs; stationarity is dual feasibility and complementarity is complementary slackness. And since an LP is convex, they are also sufficient.
nlpm-f-114 · level media · notes
Solve with the KKT conditions $\min\ (x - 3)^2 + (y - 1)^2$ subject to $x + 2y \le 2$, $x, y \ge 0$. Which is the optimum, with its active constraints?
  1. $(2; 0)$: active $x + 2y \le 2$ and $y \ge 0$, both multipliers $= 2$
  2. $(2.4; -0.2)$: active $x + 2y \le 2$ only, multiplier $1.2$
  3. $(3; 1)$: no active constraint, all multipliers zero
  4. $(0; 1)$: active $x + 2y \le 2$ and $x \ge 0$, multiplier $0$
Explanation. The free minimum $(3, 1)$ violates $x + 2y \le 2$; projecting on the line gives $(2.4, -0.2)$, which violates $y \ge 0$. With $y = 0$ and $x = 2$: $2(x - 3) + \lambda = 0$ gives $\lambda = 2$, and $2(y - 1) + 2\lambda - \mu = 0$ gives $\mu = 2 \ge 0$. The problem is convex, so the KKT point is the global optimum (value $2$).
nlpm-f-115 · level ipotesi · notes
The KKT theorem of the notes holds «at a **regular** optimal point». What can happen at an optimum where the regularity hypothesis fails?
  1. The point cannot be a local minimum at all
  2. The multipliers exist but are all equal to zero
  3. KKT multipliers may fail to exist
  4. The conditions become sufficient without convexity
Explanation. Regularity (a constraint qualification) is what guarantees the existence of the multipliers: without it an optimum may fail to satisfy stationarity for any choice of $\lambda_i \ge 0$, $\nu_j$.
nlpm-f-291 · level ipotesi · notes
For the problem $\min f(x)$ with constraints $g_i(x) \le 0$, under which assumption are the KKT conditions also *sufficient* for the global optimum?
  1. That the constraints are all equalities
  2. That the problem is convex: $f$ and the $g_i$ convex
  3. That the multipliers are all positive
  4. That the point lies in the interior of the region
Explanation. In a convex problem a point satisfying the KKT conditions is a global optimum; without convexity the KKT conditions are only necessary (at a regular point).
nlpm-f-292 · level ipotesi · notes
In the Lagrangian $L = f + \sum_i \lambda_i g_i$ for constraints $g_i(x) \le 0$ of a minimization problem, which sign must the multipliers $\lambda_i$ have?
  1. Any sign
  2. $\lambda_i \le 0$
  3. $\lambda_i = 0$ for every active constraint
  4. $\lambda_i \ge 0$
Explanation. For inequality constraints in the form $g_i \le 0$ the multipliers are non-negative; only those of equality constraints $h_j = 0$ are free.
nlpm-f-293 · level ipotesi · notes
KKT complementarity says $\lambda_i\, g_i(\tilde x) = 0$. What does it imply for a constraint that is *not active* at the optimum ($g_i(\tilde x) < 0$)?
  1. That its multiplier is zero
  2. That its multiplier is positive
  3. That the point is not optimal
  4. That the constraint must be removed from the model
Explanation. If $g_i(\tilde x) < 0$ the product can vanish only with $\lambda_i = 0$: a constraint with slack has no marginal value.
nlpm-f-294 · level ipotesi · notes
QP with objective $\tfrac12 \mathbf x'\mathbf Q\mathbf x + \mathbf c'\mathbf x$ and linear constraints. Which assumption on $\mathbf Q$ makes the QP convex?
  1. Any sign, depending on the type of constraint
  2. $\lambda_i \le 0$ for every constraint
  3. $\lambda_i = 0$ for every active constraint
  4. $\lambda_i \ge 0$
Explanation. The QP is convex if and only if $\mathbf Q \succeq 0$; non-negative entries or invertibility are not enough (for instance a large $q_{12}$ breaks convexity).
nlpm-f-295 · level teorema · notes
Why can optimality be *certified* in convex problems, while in non-convex ones a local method guarantees little?
  1. Because in convex problems the region is always bounded
  2. Because in a convex problem every local minimum is global
  3. Because convex problems always have a unique solution
  4. Because convex problems are always linear
Explanation. The key property is that in convex problems every local minimum is global; uniqueness and boundedness are not guaranteed in general.
nlpm-f-296 · level teorema · notes
For an LP, what do the KKT conditions reduce to?
  1. To a condition on the gradient of the objective only
  2. To primal feasibility only
  3. To nothing: the KKT conditions do not hold for LPs
  4. To dual feasibility and complementary slackness
Explanation. For an LP stationarity of the Lagrangian is dual feasibility and complementarity is complementary slackness: the KKT conditions generalize LP theory.
nlpm-f-303 · level facile · notes
The function $f(x_1, x_2) = x_1^2 + \gamma x_1 x_2 + x_2^2$ has matrix $\mathbf Q = \begin{pmatrix} 2 & \gamma \\ \gamma & 2 \end{pmatrix}$. For which $\gamma$ is it convex?
  1. For $|\gamma| \le 2$
  2. For $\gamma \ge 0$
  3. For every $\gamma$
  4. For $|\gamma| \le 1$
Explanation. $\mathbf Q \succeq 0$ if and only if the principal minors are non-negative: $2 \ge 0$ and $4 - \gamma^2 \ge 0$, that is $|\gamma| \le 2$.
nlpm-f-304 · level facile · notes
QP $\min\ x_1^2 + 2x_2^2$ with $x_1 + x_2 \ge 6$, $x_1, x_2 \ge 0$. What are the optimal solution and the optimal value?
  1. $(3, 3)$, value $27$
  2. $(6, 0)$, value $36$
  3. $(4, 2)$, value $24$
  4. $(2, 4)$, value $36$
Explanation. The constraint is active and the partial derivatives coincide at the optimum: $2x_1 = 4x_2$, with $x_1 + x_2 = 6$ one gets $(4, 2)$ and $16 + 8 = 24$.
nlpm-f-305 · level facile · notes
In the same QP ($\min\ x_1^2 + 2x_2^2$, $x_1 + x_2 \ge 6$) why are the partial derivatives $2x_1$ and $4x_2$ equal at the optimum?
  1. Because the feasible region is symmetric about the bisector
  2. Otherwise it would pay to shift quantity between the variables
  3. Because the two coefficients of the objective are equal
  4. Because the threshold constraint is not active at the optimum
Explanation. If one derivative were smaller, shifting some quantity to the variable that is cheaper at the margin would reduce the objective while staying on the constraint; the common derivative is the multiplier, $8$.
nlpm-f-306 · level facile · notes
With the KKT conditions one solves $\min\ (x-3)^2 + (y-1)^2$ with $x + 2y \le 2$, $x, y \ge 0$. Which point is optimal?
  1. $(3, 1)$, the centre of the level curves
  2. $(0, 1)$, on the constraint $x + 2y = 2$
  3. $(1.6;\ 0.2)$, projection without the bounds
  4. $(2, 0)$, with $x + 2y \le 2$ and $y \ge 0$ active
Explanation. The centre $(3, 1)$ is not feasible; with only $x + 2y \le 2$ active one would get $y < 0$. With $y \ge 0$ active too: $(2, 0)$, multipliers $\lambda = 2$ and $\mu = 2$, both non-negative.
nlpm-f-325 · level teorema · notes
In the QP $\min\ x_1^2 + 2x_2^2$ with $x_1 + x_2 \ge d$ the optimal value is $\tilde f(d) = \tfrac23 d^2$. What is the multiplier of the constraint at $d = 6$?
  1. $24$
  2. $4$
  3. $8$
  4. $\tfrac23$
Explanation. The multiplier is the derivative of the optimal value with respect to the right-hand side: $\tilde f'(d) = \tfrac43 d = 8$ at $d = 6$, as $\lambda = 2\tilde x_1 = 4\tilde x_2$.
nlpm-f-330 · level ipotesi · notes
A method finds a local minimum of $\min f(\mathbf x)$ over a feasible set $X$. Which assumption guarantees that it is also global?
  1. That $f$ is differentiable everywhere
  2. That $f$ and $X$ are convex
  3. That $X$ is closed and bounded
  4. That the local minimum is unique
Explanation. In a convex problem (convex objective minimized over a convex set) every local minimum is global.
nlpm-f-331 · level ipotesi · notes
A multiplier is estimated by perturbation: $\tilde f(d + \varepsilon) \approx \tilde f(d) + \lambda\,\varepsilon$. Under which assumption is the approximation good in a QP?
  1. $\varepsilon$ small: the curvature is negligible
  2. $\varepsilon$ large: numerical errors weigh less
  3. The perturbed constraint is not active at the optimum
  4. The QP is not convex, so the estimate is linear
Explanation. In the example QP $\tilde f(6 + \varepsilon) = 24 + 8\varepsilon + \tfrac23\varepsilon^2$: the quadratic term is negligible only for small $\varepsilon$.

3. The solver for nonlinear models (25)

nlpm-f-006 · level facile · notes
A gurobipy model contains the product $p \cdot q$ of two decision variables (price times quantity, a bilinear term). Which parameter must be set for Gurobi to solve it?
  1. `m.Params.NonConvex = 2`
  2. `m.Params.FuncNonlinear = 1`
  3. `m.Params.QCPDual = 1`
  4. None: bilinear terms are convex
Explanation. Bilinear (non-convex) terms require `NonConvex = 2`; `FuncNonlinear = 1` is for the general functions introduced with `addGenConstrLog/Exp/Pow`.
nlpm-f-007 · level facile · notes
The objective of a gurobipy model must contain $\log(1 + k x)$, with $x$ a decision variable and $k > 0$ a datum. How is this term introduced?
  1. Directly in `setObjective`, writing `gp.log(1 + k*x)`
  2. With a piecewise-linear approximation of the log written by hand
  3. With auxiliary variables $g = 1 + kx$, $z$ and the constraint `m.addGenConstrLog(g, z)`
  4. It cannot: Gurobi accepts only linear and quadratic expressions
Explanation. Nonlinear functions enter as function constraints on auxiliary variables; with `FuncNonlinear = 1` they are handled exactly and the optimum is certified global.
nlpm-f-008 · level facile · notes
For a gurobipy model with function constraints (e.g. `addGenConstrLog`) the solver returns no duals. How is the multiplier of a constraint estimated?
  1. It is taken as zero, since such constraints have no dual
  2. Raise the right-hand side by $\varepsilon$, re-optimize, take the incremental ratio
  3. From the reduced costs `RC` of the variables in the constraint
  4. From the attributes `SARHSLow` and `SARHSUp` of the constraint
Explanation. Perturbation is the general tool of the course: new optimum $\approx$ old optimum $+$ multiplier $\cdot\,\varepsilon$.
nlpm-f-009 · level facile · notes
The course uses a single solver, Gurobi, for all its models, including the non-convex ones (pricing). Why?
  1. Because local solvers are slower on convex problems, the most common ones
  2. Because it certifies a global optimum also for non-convex models, with one syntax
  3. Because Gurobi reformulates every model as an equivalent LP
  4. Because Gurobi returns the duals for every class of model
Explanation. With a local solver every result would carry the doubt “is it only a local optimum?”. Duals are not available with function or bilinear constraints.
nlpm-f-078 · level facile · notes
A convex QP (e.g. Markowitz) is solved with gurobipy, and the attribute `Pi` of its linear constraints is not available. What does the course suggest?
  1. Declare the model with `NonConvex = 2`
  2. Read `SARHSLow`/`SARHSUp` instead of `Pi`
  3. Set `m.Params.QCPDual = 1`, or check the multiplier by perturbation
  4. Assume all multipliers are zero
Explanation. For QPs the LP duals are not returned by default: `QCPDual = 1` asks for them, and perturbing the right-hand side by $\varepsilon$ checks them.
nlpm-f-079 · level facile · notes
Gurobi handles nonlinear models through special parameters: `NonConvex = 2` for bilinear terms, `FuncNonlinear = 1` for functions such as $\log$. Which course model needs neither, being purely conic?
  1. Pricing, with the term $p \cdot q$
  2. The advertising budget, with $\log(1 + k_ix_i)$
  3. The M/M/1 queue, with the constraint $w(\mu - \lambda) = 1$
  4. Weber location, with $d_x^2 + d_y^2 \le d_i^2$
Explanation. Convex quadratic or conic structures (a convex QCP) need nothing special; bilinear terms need `NonConvex = 2`, function constraints `FuncNonlinear = 1`.
nlpm-f-116 · level facile · notes
A course model contains the mean time in an M/M/1 queue, $w = 1/(\mu - \lambda)$, with capacity $\mu$ a decision variable. How is it written for Gurobi?
  1. Directly as `w == 1/(mu - lam)` in `addConstr`
  2. With `addGenConstrLog` applied to $\mu - \lambda$
  3. With the bilinear constraint $w(\mu - \lambda) = 1$
  4. By fixing $\mu$ and solving one LP per value of $\mu$
Explanation. Ratios are reformulated with an auxiliary variable and a bilinear constraint, `m.addQConstr(w * (mu - lam) == 1)`, which requires `NonConvex = 2`; gurobipy does not accept a division by a variable.
nlpm-f-117 · level facile · notes
A course script estimates differences between two close optimal values (a marginal analysis). Which Gurobi parameters do the notes tighten to $10^{-9}$?
  1. `TimeLimit` and `OutputFlag`
  2. `FeasibilityTol` and `OptimalityTol`
  3. `NonConvex` and `FuncNonlinear`
  4. `Threads` and `Seed` of the solver
Explanation. For accurate marginal analyses the tolerances are tightened: `MIPGap`, `FeasibilityTol` and `OptimalityTol` at $10^{-9}$. The other parameters control time, log and nonlinear features.
nlpm-f-118 · level facile · notes
A pricing model with constant-elasticity demand needs the constraint $q \le A\,p^{-\varepsilon}$ ($p$ price, $q$ quantity, $\varepsilon > 1$), where $p^{-\varepsilon}$ is tiny. How do the notes rewrite it?
  1. As $q\cdot r \le A$ with an auxiliary $r = p^{\varepsilon}$
  2. As $\log q \le \log A + \varepsilon\log p$
  3. As $q \le A$, dropping the price term
  4. As $q\,p \le A$, a bilinear constraint
Explanation. Scaling: with $r = p^{\varepsilon}$ (a power constraint) the condition becomes $q\,r \le A$, which keeps the numbers in a healthy range. The logarithmic form has the wrong sign of the exponent.
nlpm-f-119 · level facile · notes
A multiplier is estimated by perturbation: the right-hand side is raised by $\varepsilon$, the model is solved again and the difference of the two optimal values is divided by $\varepsilon$. Why do the course scripts tighten the solver tolerances to $10^{-9}$ for this?
  1. Because otherwise Gurobi refuses to solve twice
  2. Because the multiplier must be an integer
  3. To make the two solves faster
  4. Otherwise numerical error dominates the difference
Explanation. The incremental ratio divides a small difference by a small $\varepsilon$: with default tolerances (around $10^{-6}$) the numerical noise of each optimum can be comparable to the difference itself.
nlpm-f-120 · level facile · notes
A model with a functional constraint (`addGenConstrLog`) gives no duals. The budget constraint is raised from $100$ to $100.1$ and the optimal value goes from $500$ to $501.2$. What is the perturbation estimate of its multiplier?
  1. $1.2$
  2. $12$
  3. $0.12$
  4. $120$
Explanation. Incremental ratio: $(501.2 - 500)/0.1 = 12$ per unit of right-hand side. Forgetting to divide by $\varepsilon = 0.1$ gives $1.2$.
nlpm-f-229 · level facile · notes
In a convex QP with linear constraints solved with gurobipy, where is the KKT multiplier of a linear constraint read?
  1. In the `RC` attribute of the variable
  2. It is not read: it must always be estimated by perturbation
  3. In the `Pi` attribute of the constraint
  4. In the `SARHSUp` attribute of the constraint
Explanation. In convex QPs with linear constraints Gurobi returns the multipliers as in LPs: the `Pi` attribute of each constraint is the KKT multiplier.
nlpm-f-230 · level facile · notes
What is needed in gurobipy to obtain the multipliers of the *quadratic* constraints of a convex problem?
  1. `m.Params.NonConvex = 2` and the `Pi` attribute
  2. `m.Params.QCPDual = 1` and the `QCPi` attribute
  3. `m.Params.FuncNonlinear = 1` and the `RC` attribute
  4. Nothing: they are read like the others with `Pi`
Explanation. For quadratic constraints the dual is requested with `QCPDual = 1` and read in the `QCPi` attribute; `Pi` concerns linear constraints.
nlpm-f-231 · level teorema · notes
QP $\min\ x_1^2 + 2x_2^2$ with $x_1 + x_2 \ge d$: the optimal value is $\tilde f(d) = \tfrac{2}{3}d^2$ and the multiplier at $d = 6$ is $8$. Re-optimizing with $d = 7$ the value rises from $24$ to $32.67$, not to $32$. Why?
  1. Because the multiplier of a QP holds only if the constraint is not active
  2. Because Gurobi returns QP multipliers with a numerical error
  3. Because with $d = 7$ the constraint stops being active
  4. Because the optimal value has curvature: the multiplier is exact only at the margin
Explanation. $\tilde f(6 + \varepsilon) = 24 + 8\varepsilon + \tfrac{2}{3}\varepsilon^2$: the multiplier gives the linear term, the curvature adds $\tfrac23$ for $\varepsilon = 1$. This is why the check uses a small $\varepsilon$.
nlpm-f-297 · level ipotesi · notes
A gurobipy model has a bilinear term $p \cdot q$ (price times quantity). What is needed for Gurobi to solve it to global optimality?
  1. Nothing: every quadratic term is convex
  2. `m.Params.QCPDual = 1`
  3. `m.Params.NonConvex = 2`
  4. `m.Params.FuncNonlinear = 1` and a functional constraint
Explanation. A bilinear term is not convex; with `NonConvex = 2` Gurobi solves it with global techniques. `QCPDual` concerns duals, `FuncNonlinear` functions such as log and exp.
nlpm-f-298 · level ipotesi · notes
A model contains the functional constraint $z = \log(1 + k x)$ written with `addGenConstrLog`. One wants the multiplier of the bound $x \le b$: how is it obtained?
  1. By perturbation: $b$ slightly higher, then the difference quotient
  2. From the `Pi` attribute of the bound $x \le b$ at the optimum
  3. From the `RC` attribute of the auxiliary variable $z$
  4. From the `QCPi` attribute of the functional constraint
Explanation. With functional constraints the solver provides no duals: the multiplier is estimated by perturbation.
nlpm-f-299 · level ipotesi · notes
One wants to compare two very close optima of a nonlinear model (to estimate a multiplier by difference). Which device does the course recommend?
  1. Reducing the number of auxiliary variables of the model
  2. Using a local solver faster than Gurobi
  3. Rounding all the data to the second decimal digit
  4. Tightening Gurobi's tolerances to $10^{-9}$
Explanation. Differences between two close optima are small: with the default tolerances the numerical error may exceed them, so they are tightened to $10^{-9}$.
nlpm-f-300 · level teorema · notes
Why does the course use a single solver (Gurobi) also for non-convex problems, instead of a local solver?
  1. Because local solvers do not accept linear constraints
  2. Because Gurobi certifies the global optimum also in non-convex problems
  3. Because the non-convex problems of the course are actually linear
  4. Because a local solver does not compute multipliers
Explanation. With a local solver every result would come with the question ``is it only a local optimum?''; Gurobi gives a certified global optimum with the same syntax.
nlpm-f-307 · level facile · notes
In gurobipy how is a function such as $z = \log(g)$ inserted into a model?
  1. With the functional constraint `m.addGenConstrLog(g, z)`
  2. Writing `z == math.log(g)` inside `addConstr`
  3. With `m.setObjective(math.log(g))` and `NonConvex = 2`
  4. It cannot: Gurobi only accepts linear models
Explanation. Nonlinear functions enter as functional constraints on auxiliary variables; with `FuncNonlinear = 1` Gurobi handles them exactly.
nlpm-f-308 · level facile · notes
The mean time in an M/M/1 queue is $1/(\mu - \lambda)$. How is it written in a gurobipy model?
  1. As the linear constraint $w \le \mu - \lambda$, no auxiliaries
  2. With the functional constraint `addGenConstrLog`
  3. With an auxiliary and the bilinear constraint $w(\mu - \lambda) = 1$
  4. It is not written: it is estimated by simulation
Explanation. Ratios are reformulated with an auxiliary variable and a bilinear constraint (`addQConstr`), with `NonConvex = 2`.
nlpm-f-309 · level facile · notes
Why is it better to rewrite $q \le A\,p^{-\varepsilon}$ as $q \cdot r \le A$ with $r = p^{\varepsilon}$?
  1. To make the demand constraint linear
  2. To avoid tiny quantities and badly scaled numbers
  3. To remove the price variable $p$ altogether
  4. Because Gurobi does not accept negative exponents
Explanation. With negative exponents very small numbers appear and worsen the scaling; the reformulation keeps the coefficients in a healthy range.
nlpm-f-310 · level facile · notes
A convex QP has the linear constraint `v = m.addConstr(x1 + x2 >= 6)`. After `m.optimize()`, `v.Pi` equals $8$. What does it mean?
  1. That the constraint has 8 units of slack at the optimum
  2. That the problem has 8 different optimal solutions
  3. That the value of the objective at the optimum is 8
  4. That the optimum grows by about 8 per unit of right-hand side
Explanation. `Pi` is the KKT multiplier: the marginal change of the optimal value per unit of right-hand side (here exact only at the margin).
nlpm-f-326 · level teorema · notes
In a convex QP with linear constraints `Pi` is the KKT multiplier of the constraint. For which increments of the right-hand side is the estimate $\Delta f \approx \pi\,\Delta$ exact?
  1. Only at the margin, for small increments
  2. For every increment, as happens in LPs
  3. Within the `SARHSLow`–`SARHSUp` range
  4. For none: in QPs `Pi` has no meaning
Explanation. Unlike LPs, where the optimal value is piecewise linear, in QPs it is curved: the multiplier is exact only at the margin.
nlpm-f-333 · level ipotesi · notes
One wants the multiplier of a *quadratic* constraint (for instance $d_x^2 + d_y^2 \le d^2$). What is needed for Gurobi to return it?
  1. Nothing: reading the `Pi` attribute is enough
  2. Setting `NonConvex = 2` before optimizing
  3. `QCPDual = 1`, then the `QCPi` attribute
  4. Rewriting it as a functional constraint `addGenConstrPow`
Explanation. For quadratic constraints the duals are requested with `QCPDual = 1` and read in `QCPi`; otherwise the multiplier is estimated by perturbation.
nlpm-f-334 · level ipotesi · notes
A model contains $z = \log(g)$ written with `addGenConstrLog`. Under which setting does Gurobi handle the function exactly, with a global optimum?
  1. `m.Params.MIPGap = 1`
  2. `m.Params.FuncNonlinear = 1`
  3. `m.Params.NonConvex = 0`
  4. `m.Params.Method = 2`
Explanation. With `FuncNonlinear = 1` the functions of functional constraints are handled exactly and the optimum stays certified global.

14. Organization of the course (18)

nlpm-f-071 · level facile · notes
The course notes close with a checklist of the most frequent mistakes made with gurobipy and the models. Which of these is in that checklist?
  1. Checking `m.Status` before reading the solution
  2. Quoting each shadow price with its validity range
  3. Reading `.X` or `.Pi` without checking `m.Status`
  4. Writing the model to a `.lp` file for debugging
Explanation. The other three are good practices recommended by the notes.
nlpm-f-072 · level facile · notes
How must the hyperparameters of the course models be chosen ($C$ and $\gamma$ of the SVM, the weight $\lambda$ of a risk or regularization term)?
  1. On validation data, never on the test set or the decision scenarios
  2. By maximizing the accuracy on the test set
  3. Always equal to $1$, the neutral value
  4. On the same scenarios later used to decide
Explanation. Choosing them on the test set (or on the decision scenarios) gives optimistic results that do not transfer to new data.
nlpm-f-073 · level facile · notes
A parameter estimated from data (e.g. an expected return) changes at the second decimal digit when the sample changes slightly. How many digits should a lab report show?
  1. Six, to be as precise as possible
  2. Few: six decimals of an estimate wobbling at the second mislead
  3. None: estimates should not be reported
  4. As many as the solver prints
Explanation. Spurious precision is in the checklist of mistakes: the digits shown must reflect the reliability of the estimate.
nlpm-f-284 · level facile · notes
In the essential path of NLP Modelling, what is done in the fourth session?
  1. A multi-period LP is formulated from scratch
  2. A quantile regression is estimated on the data
  3. A MIP with binary variables is solved
  4. A project of your choice, presented to managers
Explanation. The fourth session is a project of your choice (supply chain, location, EV charging, queues, SVM or least squares) with a presentation of the results.
nlpm-f-285 · level facile · notes
In the third session of NLP Modelling (pricing or budget) what are the learning objectives?
  1. Nonlinear functions, concavity and checking the KKT conditions
  2. Read the shadow prices and reduced costs of an LP
  3. Trace the efficient frontier of Markowitz
  4. Estimate the parameters of an SVM with a kernel
Explanation. Pricing and budget have nonlinear functions (bilinear revenue, concave responses): concavity is studied and the KKT conditions are verified numerically.
nlpm-f-286 · level facile · notes
In an edition of NLP Modelling oriented towards machine learning, which chapters can replace the third session?
  1. Production with smoothing and EV charging
  2. Pricing and advertising budget
  3. SVM and least squares
  4. Supply chain and queues
Explanation. The optimization and machine learning chapters (SVM and least squares) can replace session 3 or become individual projects.
nlpm-f-287 · level facile · notes
An item of the checklist of mistakes of NLP Modelling concerns the multipliers of QPs. Which one?
  1. Reading them with the `RC` attribute instead of `Pi`
  2. Using them for large increments: they are exact only at the margin
  3. Requesting them with `QCPDual = 1` also for linear constraints
  4. Reading them before having declared the variables
Explanation. The optimal value of a QP has curvature: the multiplier is the derivative and for large increments the true change is different.
nlpm-f-288 · level facile · notes
What does the script that runs all the scripts of the course (`run_all.py`, in Italian `esegui_tutti.py`) do?
  1. It runs the scripts and regenerates results, figures and notebooks
  2. It compiles the lecture notes and the slides into PDF
  3. It publishes the course website on GitHub Pages
  4. It downloads the data from the LP Modelling repository
Explanation. The script runs the chapter scripts in sequence (results and figures) and then regenerates the Colab notebooks.
nlpm-f-289 · level facile · notes
Which Python packages are needed to redo all the results of NLP Modelling?
  1. Only `scipy` and `numpy`, with no solver
  2. `cvxpy`, `numpy` and `pandas`
  3. `gurobipy`, `matplotlib` and `pandas`
  4. `scikit-learn`, `numpy` and `gurobipy`
Explanation. Every model is solved with Gurobi (`gurobipy`); `matplotlib` makes the figures and `pandas` handles the tables.
nlpm-f-290 · level facile · notes
Where are the notebooks of NLP Modelling and how are they used?
  1. In the PDF lecture notes, to be copied by hand
  2. In `notebooks/`, one per chapter, to open in Colab
  3. Only in the slides, as images of the code
  4. In the LP Modelling repository, together with the data
Explanation. Every chapter with a model has its notebook in `notebooks/`, generated from the script; it opens in Colab from the badge of the page.
nlpm-f-302 · level teorema · notes
An item of the checklist of mistakes is ``believing a problem convex when it is not''. Why is it serious?
  1. Because Gurobi always rejects non-convex problems
  2. Because the multipliers all become zero
  3. Because the model becomes infeasible
  4. Because a local optimum is mistaken for a global one
Explanation. Without convexity a stationary point may be only a local optimum; declaring non-convexity (`NonConvex = 2`) makes the solver search for the global one.
nlpm-f-318 · level facile · notes
What are the learning objectives of the first session (Markowitz)?
  1. Writing a multi-period LP and reading its shadow prices
  2. Using binary variables to choose which assets to keep
  3. Training an SVM with the RBF kernel and choosing $C$
  4. Building a convex QP, tracing the frontier, discussing the estimates
Explanation. The first session builds the convex Markowitz QP, traces its frontier and discusses how fragile the return estimates are.
nlpm-f-319 · level facile · notes
One item of the checklist of mistakes is forgetting `lb=-GRB.INFINITY` on free variables. In which models of the course does it happen?
  1. For $b$ of the SVM and for the least-squares residuals
  2. For the quantities produced in the production plan
  3. For the portfolio weights without short selling
  4. For the prices of the pricing model
Explanation. In gurobipy the default lower bound is 0: the intercept $b$ of the SVM and the least-squares residuals must be allowed to be negative.
nlpm-f-320 · level facile · notes
Which Gurobi parameter is often forgotten in models with bilinear terms such as $p \cdot q$?
  1. `MIPGap = 0`
  2. `QCPDual = 1`
  3. `NonConvex = 2`
  4. `FuncNonlinear = 0`
Explanation. With bilinear terms the model is not convex: `NonConvex = 2` is needed for Gurobi to solve it to global optimality.
nlpm-f-321 · level facile · notes
Why is it a mistake to read `.X` or `.Pi` right after `m.optimize()`, without looking at `m.Status`?
  1. Because `.X` is read only before calling `m.optimize()`
  2. Because the model may have no optimum to read
  3. Because reading `m.Status` changes the values of the variables
  4. Because `.Pi` exists only in models with integer variables
Explanation. First check that the status is optimal: if the model is infeasible, unbounded or interrupted there is no optimal solution to read.
nlpm-f-322 · level facile · notes
How are the solutions of the exercises of NLP Modelling distributed?
  1. In class
  2. In the notebook of each chapter
  3. At the bottom of each page of the website
  4. In the self-assessment quiz
Explanation. The organization page says it explicitly: the solutions of the exercises are distributed in class.
nlpm-f-323 · level facile · notes
A problem has two conflicting objectives (risk and return). What does the checklist recommend instead of optimizing only one?
  1. Adding them with equal weights and reporting a single optimum
  2. Keeping only the objective with the largest value
  3. Turning both of them into equality constraints
  4. Studying the trade-off, tracing the frontier
Explanation. Optimizing a single objective when there are two is in the checklist of mistakes: one studies the trade-off, like the Markowitz frontier.
nlpm-f-336 · level ipotesi · notes
In gurobipy the constraint `x + 5 <= 10` is stored as $x \le 5$. Under which condition is the value assigned to `c.RHS` exactly the number on the right of the constraint as it was written?
  1. Always: `RHS` is the number written on the right of the constraint
  2. Only if the model is convex and has no bilinear terms
  3. Only after calling `m.update()` on the model
  4. Only if the constraint has all the constants on the right
Explanation. Constants on the left are moved into the right-hand side: here `RHS` equals 5, not 10, and setting it to 12 gives $x \le 12$. It is mistake 5 of the checklist.

Part: Deterministic models (186)

4. Production with quadratic smoothing (19)

nlpm-f-010 · level facile · notes
Minimum-cost production-inventory LP (products $i$, months $t$; $x_{it}$ = units produced, $s_{it}$ = inventory at the end of month $t$, $d_{it}$ = demand). The term $\gamma \sum_{t=2}^{m} (v_t - v_{t-1})^2$, with $\gamma > 0$ and $v_t = \sum_i x_{it}$ the total production of month $t$, is added to the minimized cost. What is it for?
  1. To penalize the inventory held at the end of each month
  2. To keep the problem an LP while adding a cost
  3. To smooth the plan, penalizing changes of pace between months
  4. To reduce the demand to be served in the peak months
Explanation. It is the QP variant: in the case study, with $\gamma = 0.5$ the profile becomes almost flat at a cost of only $0.35\%$.
nlpm-f-080 · level facile · notes
Minimum-cost production-inventory LP (products $i$, months $t$; $x_{it}$ = units produced, $s_{it}$ = inventory at the end of month $t$, $d_{it}$ = demand). The smoothing variant adds $\gamma\sum_{t=2}^m (v_t - v_{t-1})^2$, with $v_t = \sum_i x_{it}$ and $\gamma > 0$, to the linear cost. To which class does the resulting model belong?
  1. A non-convex QP, because of the squares
  2. An LP, because the constraints are linear
  3. A non-convex NLP that needs `NonConvex = 2`
  4. A convex QP: a sum of squares with $\gamma > 0$ plus linear terms
Explanation. Each $(v_t - v_{t-1})^2$ is the square of a linear function, hence convex; with $\gamma > 0$ and linear constraints the model is a convex QP and its optimum is global.
nlpm-f-232 · level facile · notes
In the production and inventory case the minimum-cost linear plan has a total production going from 219.5 to 389.0 units per month. Why is a quadratic penalty on the jumps added?
  1. Because every change of pace has costs the linear model does not see
  2. Because the linear model is infeasible in the peak months
  3. Because the penalty reduces the demand to serve
  4. Because without the penalty Gurobi does not find the global optimum
Explanation. Overtime, shifts to reorganize and suppliers to realign make changes of pace costly; the linear model ignores them, the penalty prices them.
nlpm-f-233 · level facile · notes
Quadratic penalty $\gamma \sum_t (v_t - v_{t-1})^2$ on the jumps of total production. Compared with a jump of 10 units, how much does a jump of 20 units cost?
  1. The same, because the penalty only counts sign changes
  2. Twice as much
  3. Four times as much
  4. Eight times as much
Explanation. The cost is proportional to the square of the jump: $20^2 / 10^2 = 4$. This is why the model prefers many small adjustments to a few large jumps.
nlpm-f-234 · level facile · notes
In the production model with smoothing, what stays the same as in the linear model of LP Modelling?
  1. Only the objective
  2. Data, variables and constraints
  3. Only the capacity constraints
  4. Nothing: the case is new
Explanation. A single datum is added, the weight $\gamma$; data, variables $x_{it}$, $s_{it}$ and balance and capacity constraints stay those of the linear case.
nlpm-f-235 · level teorema · notes
Production with smoothing: $\gamma \sum_{t=2}^{m} (\sum_i x_{it} - \sum_i x_{i,t-1})^2$ with $\gamma \ge 0$ is added to the linear objective; the constraints are linear. Which property guarantees that every local minimum is global?
  1. The balance constraints are equalities, not inequalities
  2. The production and stock variables are non-negative
  3. The number of months of the horizon is finite and small
  4. The square of a linear function is convex, so is the weighted sum
Explanation. Every jump is linear in the variables, its square is convex and a non-negatively weighted sum of convex functions is convex: with linear constraints the QP is convex.
nlpm-f-236 · level ipotesi · notes
In the production QP with smoothing the term is $\gamma \sum_t (v_t - v_{t-1})^2$. For which values of $\gamma$ does the model stay a convex QP?
  1. Only for $\gamma > 1$
  2. For every $\gamma \ge 0$
  3. Only for $\gamma \le 1/160$
  4. For every real value of $\gamma$
Explanation. With $\gamma \ge 0$ a convex function is added; with $\gamma < 0$ a square would be subtracted and the problem would become non-convex (it would reward jumps).
nlpm-f-237 · level facile · notes
One product, two months: $d_1 = 60$, $d_2 = 100$, $c = 10$, $h = 1$, ample capacity, objective $f(s_1) = 1600 + s_1 + \gamma (40 - 2 s_1)^2$. What is the optimal stock $s_1$ with $\gamma = 0.5$?
  1. $19.75$
  2. $20.00$
  3. $19.50$
  4. $15.00$
Explanation. $f'(s_1) = 1 - 4\gamma(40 - 2s_1) = 0$ gives $s_1 = 20 - 1/(8\gamma) = 20 - 0.25 = 19.75$.
nlpm-f-238 · level ipotesi · notes
In the same example (one product, two months, $h = 1$, jump $40 - 2s_1$) the derivative at $s_1 = 0$ is $f'(0) = 1 - 160\gamma$. For which values of $\gamma$ does it pay to keep stock?
  1. For every $\gamma > 0$
  2. Only for $\gamma \ge 1$
  3. Only for $\gamma > 1/160$
  4. Never: holding always costs
Explanation. If $f'(0) \ge 0$ (that is $\gamma \le 1/160$) increasing $s_1$ does not pay and the optimum is $s_1 = 0$; with $\gamma = 0.004$ the solver indeed gives zero stock.
nlpm-f-239 · level teorema · notes
Two-month example with smoothing ($h = 1$): at the optimum with positive stock the multipliers of the two balances are $\tilde\pi_1 = 9.5$ and $\tilde\pi_2 = 10.5$. What do the KKT conditions say about their difference?
  1. That it equals $\gamma$
  2. That it equals the holding cost $h$
  3. That it is zero, because the stock is free
  4. That it equals the optimal jump
Explanation. Stationarity with respect to $s_1 > 0$ gives $h + \tilde\pi_1 - \tilde\pi_2 = 0$: one more unit of demand in month 2 costs one holding period more than one in month 1.
nlpm-f-240 · level facile · notes
In the production script with smoothing `tot[t]` is the total production of month $t$ and `costo` the linear cost. How is the objective written in gurobipy?
  1. `m.addConstr(costo + gamma * salti <= 0)` with `salti` the sum of the squared jumps
  2. `m.setObjective(costo, GRB.MINIMIZE)` and then `m.Params.NonConvex = 2` for the jumps
  3. `m.addGenConstrPow(salti, costo, 2)` and then `m.setObjective(costo, GRB.MINIMIZE)`
  4. `m.setObjective(costo + gamma * salti, GRB.MINIMIZE)` with `salti` the sum of the squared jumps
Explanation. The quadratic term is written as a product of linear expressions and added to the cost in the objective; the QP is convex and no special parameter is needed.
nlpm-f-241 · level facile · notes
The production script with smoothing does not read the data from a file: it writes them in the code with the same values as the linear case. Why?
  1. Because it also runs in Colab; the CSVs live in the LP Modelling repository
  2. Because Gurobi cannot read the CSV files of the case studies
  3. Because the data of the quadratic case differ from the linear ones
  4. Because Colab notebooks cannot import pandas
Explanation. The data live in a single repository (LP Modelling); the NLP script writes them again with the same values, so it is self-contained also in Colab.
nlpm-f-242 · level facile · notes
After `m.optimize()` on the production QP with smoothing one wants the multipliers of the capacity constraints `v_cap`. What is written?
  1. `[v_cap[t].RC for t in mesi]`
  2. `[v_cap[t].X for t in mesi]`
  3. `[v_cap[t].Pi for t in mesi]`
  4. `m.computeIIS()`
Explanation. In convex QPs with linear constraints the `Pi` attribute of each constraint is its KKT multiplier.
nlpm-f-243 · level facile · notes
Production case study: the linear plan costs €32,889.33; with $\gamma = 0.5$ the production and holding cost is €33,000.96 and the largest jump falls from 81.4 to 1.2 units. How much does smoothness cost, in percent?
  1. About 3.4%
  2. About 0.34%
  3. About 34%
  4. Nothing: the cost does not change
Explanation. $33{,}000.96 - 32{,}889.33 = 111.63$ €, that is $0.34\%$ of the linear cost: an almost flat plan costs very little.
nlpm-f-244 · level teorema · notes
With smoothing ($\gamma = 0.5$) mostly product 1 goes to stock ($a_1 = 0.9$ hours per unit), while in the linear plan the stock built in advance was that of product 3 ($a_3 = 2.1$). Why?
  1. Because product 1 has the highest holding cost of the three
  2. Because the penalty reduces the demand to serve of product 3
  3. Because in the QP product 3 can never be held in stock
  4. Because the penalty counts units: product 1 gives more per hour
Explanation. The quadratic term levels total production in *units*; to raise the units of the first months for the same hours the product using fewer hours per unit pays, product 1.
nlpm-f-245 · level facile · notes
In the production case, as $\gamma$ grows (0, 0.5, 2) how does the monthly total production change?
  1. It becomes almost flat, around 325 units per month
  2. It follows the demand of each month more and more closely
  3. It drops to zero in the peak months of demand
  4. It stays identical to the plan of the linear model
Explanation. Already with $\gamma = 0.5$ the profile goes from 323.3 to 326.1 units; with $\gamma = 2$ the largest jump is 0.4 units.
nlpm-f-246 · level ipotesi · notes
Production QP with $\gamma = 0.5$: the multiplier of the capacity of month 6 is $-3.134$ €/hour. With one more hour the optimal value falls by $3.060$; with $0.01$ hours the difference quotient is $-3.133$. What can be concluded?
  1. That Gurobi computes the multipliers of convex QPs wrongly
  2. That the capacity constraint of month 6 is not active
  3. That the multiplier holds at the margin: check it with a small $\varepsilon$
  4. That the multiplier must be multiplied by the weight $\gamma$
Explanation. The optimal value of a QP has curvature: for finite increments the change departs from the multiplier, which is the derivative. With $\varepsilon = 0.01$ the quotient goes back to the multiplier.
nlpm-f-247 · level facile · notes
With smoothing ($\gamma = 0.5$) the capacity multipliers of months 1–3 are zero, while in the linear model those of months 2 and 3 were negative. Why?
  1. Because in the QP the multipliers of the first months are not computed
  2. Because the levelled plan does not saturate the hours in the first months
  3. Because the capacity of the first months was increased in the QP
  4. Because the demand of the first three months is zero
Explanation. The smooth plan produces about 325 units every month and in the first months it does not use all the hours: the capacity constraints are not active and, by complementarity, their multiplier is zero.
nlpm-f-248 · level facile · notes
Cost-smoothness frontier of production: with $\gamma = 0.01$ the sum of the squared jumps falls from 13,699 to 2,075 and the cost rises by €48. What shape does the frontier have?
  1. Linear: every reduction of the jumps always costs the same
  2. Flat: smoothness costs nothing at any level
  3. Increasing at first and then decreasing to the right
  4. Steep at first: the first steps towards smoothness cost little
Explanation. The first reductions of the jumps cost very little; reaching an almost flat plan costs about €112 in all out of 33,000.

5. Supply chain with congestion and sustainability (27)

nlpm-f-011 · level facile · notes
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. In the flow conservation constraint $\sum_{j:(i,j)\in A} x_{ij} - \sum_{j:(j,i)\in A} x_{ji} = b_i$ (outgoing minus incoming flow), a market, i.e. a demand node, has:
  1. $b_i > 0$
  2. $b_i < 0$
  3. $b_i = 0$
  4. $b_i = \sum_{j:(j,i)\in A} u_{ji}$
Explanation. Out minus in equals the balance: positive at plants (supply), negative at markets (demand), zero at hubs (transit).
nlpm-f-012 · level facile · notes
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. The congestion term $\alpha\,c_{ij}\,x_{ij}^2/u_{ij}$, with $\alpha > 0$, is added to the cost of every arc. What is its effect on the optimal flows?
  1. It saturates the cheapest routes even more
  2. It makes the model non-convex and harder to solve
  3. It spreads the flow over several routes instead of saturating one
  4. It reduces the total demand that must be served
Explanation. The term is convex and grows with the utilization $x_{ij}/u_{ij}$: in the case study no arc stays saturated, as a prudent planner would choose.
nlpm-f-013 · level facile · notes
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. An internal CO$_2$ price $\tau$ (€/kg) is added to the arc costs, $c_{ij} + \tau e_{ij}$ ($e_{ij}$ = emissions per unit). As $\tau$ grows, the cost-emissions frontier of the LP proceeds by jumps. Why?
  1. LP optima lie at vertices: the optimum stays on a vertex, then jumps to another
  2. The emissions data $e_{ij}$ are rounded to whole kilograms
  3. The solver stops before the optimum for some values of $\tau$
  4. The capacities $u_{ij}$ change with $\tau$ in steps
Explanation. In the case study nothing changes up to $\tau = 1$ €/kg and the main jump happens at $\tau = 1.25$. A strictly convex model (with congestion) would move continuously.
nlpm-f-014 · level facile · notes
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. At the optimum an arc with cost $c_{ij} = 7$ €/unit carries no flow and has reduced cost $+2$ (Gurobi attribute `RC`). Below which cost would it start carrying flow?
  1. Above $9$ €/unit
  2. Below $7$ €/unit
  3. It never would: positive `RC` means useless
  4. Below $5$ €/unit
Explanation. In a minimization the reduced cost of a variable at zero is the improvement it needs: threshold $7 - 2 = 5$ €/unit (`SAObjLow`); above it the arc stays unused.
nlpm-f-015 · level facile · notes
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. $e_{ij}$ are the kg of CO$_2$ emitted per unit sent on arc $(i,j)$. How is an internal CO$_2$ price $\tau$ (€/kg) introduced in the model?
  1. With a binary variable for each polluting arc
  2. Replacing $c_{ij}$ with $c_{ij} + \tau\,e_{ij}$ in the objective
  3. Adding the constraint $\sum e_{ij}x_{ij} = \tau$
  4. Multiplying every capacity $u_{ij}$ by $\tau$
Explanation. This is the “weight” approach, with no new constraints; the alternative imposes $\sum e_{ij}x_{ij} \le \bar e$ and reads the dual of that constraint.
nlpm-f-016 · level facile · notes
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. The “pure” minimax utilization model minimizes $z$ subject to $x_{ij}/u_{ij} \le z$ on every arc and the flow constraints. Why is it not used alone?
  1. Any routing with utilization at most $\tilde z$ is optimal, even a very expensive one
  2. It is non-convex because of the ratios $x_{ij}/u_{ij}$
  3. It is always infeasible when some arc is saturated
  4. Gurobi cannot solve problems with a minimax objective
Explanation. The pure minimax is degenerate in the cost; in practice one minimizes cost $+\,\rho\, z$ or bounds $z$ and minimizes the cost.
nlpm-f-017 · level facile · notes
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. The demand of each market is a flow conservation constraint. In the case study the shadow prices of these constraints range between $8$ and $10.50$ €/unit. What do they represent?
  1. The selling prices charged in the markets
  2. The residual capacities of the arcs entering the markets
  3. The marginal cost of serving one more unit in each market
  4. The CO$_2$ emitted per unit delivered to each market
Explanation. They are the marginal costs of service: the number to compare with the commercial margin before accepting new orders.
nlpm-f-018 · level ipotesi · notes
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. With the congestion term $\alpha c_{ij}x_{ij}^2/u_{ij}$ ($\alpha > 0$) the optimal flows move continuously as the data change, while in the LP they can jump. Which property is responsible?
  1. The linearity of the flow conservation constraints
  2. The strict convexity of the objective, which gives a unique optimum
  3. The non-negativity of the flows $x_{ij}$
  4. The integrality of the capacities $u_{ij}$
Explanation. With a strictly convex objective the optimum is unique and varies continuously with the data; an LP can have its optimum jump between vertices.
nlpm-f-081 · level facile · notes
Supply chain with congestion: 100 units go on two routes; route 1 costs $2x_1 + x_1^2/40$ (cost $c_1 = 2$, capacity $u_1 = 80$, $\alpha = 1$), route 2 costs $5$ €/unit with ample capacity. At the optimum the marginal costs are equal. What is the split $(x_1, x_2)$?
  1. $(80, 20)$
  2. $(100, 0)$
  3. $(60, 40)$
  4. $(50, 50)$
Explanation. Marginal cost of route 1: $2 + x_1/20$; setting it equal to $5$ gives $x_1 = 60$, $x_2 = 40$. The LP without congestion would fill route 1 up to its capacity, $(80, 20)$.
nlpm-f-082 · level facile · notes
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. Node balances $b_i$ are positive at plants (supply), negative at markets (demand), zero at hubs. Which condition on the balances is necessary for the model to be feasible?
  1. $\sum_{i \in N} b_i \ge 0$: total supply covers total demand
  2. $b_i \le u_{ij}$ for every arc leaving $i$
  3. $\sum_{i \in N} b_i < 0$: demand exceeds supply
  4. All $b_i$ must be integers
Explanation. If total demand exceeds total supply no flow can satisfy all conservation constraints; capacities can make the model infeasible even when the balance condition holds.
nlpm-f-083 · level facile · notes
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. $e_{ij}$ = kg of CO$_2$ per unit on arc $(i,j)$. Instead of an internal price, the company imposes a cap $\sum e_{ij}x_{ij} \le \bar e$ on total emissions. What does the shadow price of this constraint represent?
  1. The emissions saved per euro spent
  2. The total cost of the network divided by $\bar e$
  3. The emissions of the cheapest route
  4. The implicit CO$_2$ price: cost change per kg of extra allowance
Explanation. The dual of the cap is the marginal cost of abatement: it is the internal price $\tau$ that would produce the same routing with the “weight” approach.
nlpm-f-084 · level ipotesi · notes
Minimum-cost flow LP of the supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$. Congestion version: each arc costs $c_{ij}x_{ij} + \alpha c_{ij}x_{ij}^2/u_{ij}$. Which facts make this model convex?
  1. The flows are integers and the capacities are positive
  2. $\alpha \ge 0$, $c_{ij} \ge 0$, $u_{ij} > 0$: convex quadratic terms, linear constraints
  3. The network has no cycles
  4. Every arc is used at the optimum
Explanation. $x_{ij}^2$ is convex and is multiplied by the non-negative coefficient $\alpha c_{ij}/u_{ij}$; the conservation and capacity constraints are linear, so the feasible set is a polyhedron.
nlpm-f-146 · level facile · notes
The supply-chain chapter of the course asks three managerial questions about a network with costs, capacities and CO$_2$ footprints. Which one concerns CO$_2$?
  1. How many plants should be opened or closed?
  2. Which market should be dropped first?
  3. How much should each arc be taxed by the state?
  4. Which CO$_2$ price makes clean routes pay?
Explanation. The three questions: how to route flows at minimum cost, what changes when congestion is penalized, and how high an internal CO$_2$ price must be for the «clean» routes to become convenient.
nlpm-f-147 · level facile · notes
According to the course notes, why is the network-flow structure of the supply-chain model worth learning well?
  1. It is the only structure Gurobi can solve
  2. It is among the most reusable OR structures
  3. It always has integer optimal solutions
  4. It needs no capacities on the arcs
Explanation. Routes, loads per arc, capacity investments and carbon accounting all share the same structure; flow models reappear across logistics, energy and telecommunications.
nlpm-f-148 · level facile · notes
In the supply-chain chapter, the effective cost of a route «grows rapidly as it approaches saturation». What does this represent in practice?
  1. Overtime, queues, insurance premiums
  2. Taxes on CO$_2$ emissions
  3. The fixed cost of opening a new route
  4. Discounts granted for large volumes
Explanation. Congestion costs grow more than linearly with the use of an arc; the chapter models them with a convex quadratic term $\alpha c_{ij}x_{ij}^2/u_{ij}$.
nlpm-f-149 · level facile · notes
Which daily decisions of a logistics manager does the supply-chain chapter of the course address?
  1. Hiring and firing the truck drivers
  2. Setting the selling prices of the products
  3. Routes, arc loads, capacity, carbon
  4. Scheduling the maintenance of trucks
Explanation. Routing, deciding how much to load each arc, evaluating capacity investments and reporting the carbon footprint: all readable from the flow model and its duals.
nlpm-f-150 · level facile · notes
Minimum-cost flow LP of a supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$, balances $b_i$ (supply $> 0$, demand $< 0$, transit $= 0$). One market demands $100$ units; route 1 costs $2$ €/unit with capacity $80$, route 2 costs $5$ €/unit with ample capacity. What does the pure LP do, and at what cost?
  1. Splits 50–50, cost $350$ €
  2. Fills route 1, overflows: $260$ €
  3. Uses only route 2, cost $500$ €
  4. Uses only route 1, cost $200$ €
Explanation. The cheap route is saturated ($x_1 = 80$) and the rest goes on route 2 ($x_2 = 20$): $2\cdot 80 + 5\cdot 20 = 260$ €. Route 1 alone cannot carry 100 units.
nlpm-f-151 · level facile · notes
Minimum-cost flow LP of a supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$, balances $b_i$ (supply $> 0$, demand $< 0$, transit $= 0$). One market demands $100$; route 1 ($2$ €/unit, capacity $80$) is saturated, route 2 ($5$ €/unit) carries 20. What are the shadow prices of the demand and of the capacity of route 1?
  1. Demand $2$, capacity $5$
  2. Demand $3$, capacity $-2$
  3. Demand $0$, capacity $0$
  4. Demand $5$, capacity $-3$
Explanation. The 101st unit would travel on route 2, costing 5; one more unit of capacity on route 1 moves a unit from route 2 to route 1, saving $5 - 2 = 3$ (dual $-3$ for a $\le$ capacity in a minimum).
nlpm-f-152 · level facile · notes
Minimum-cost flow LP of a supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$, balances $b_i$ (supply $> 0$, demand $< 0$, transit $= 0$). Two routes for 100 units; with congestion ($\alpha = 1$) the cheap route carries $60$ units instead of $80$ although its capacity is 80. Why does the model leave it unsaturated?
  1. Marginal costs of the routes equalize
  2. A hidden capacity constraint at 60 units
  3. The solver stops before the optimum
  4. Because congestion makes route 1 more expensive on average than route 2
Explanation. With the quadratic term the marginal cost of route 1, $2 + x_1/20$, grows with the flow; at $x_1 = 60$ it equals the 5 € of route 2, and moving more flow would cost more: a safety margin, as a prudent planner would keep.
nlpm-f-153 · level facile · notes
Minimum-cost flow LP of a supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$, balances $b_i$ (supply $> 0$, demand $< 0$, transit $= 0$). Case-study network: 2 plants (supply 260 and 240), 2 hubs, 4 markets (total demand 450), 12 arcs; cheap arcs «by road» (polluting), expensive ones «by rail» (clean). In the gurobipy code the plants are written `x.sum(s, '*') <= offerta[s]`. Why an inequality?
  1. Because plants can also receive flow
  2. Because Gurobi does not accept equalities on sums
  3. Total supply 500 exceeds demand 450
  4. Because supply is uncertain
Explanation. With supply larger than demand, forcing every plant to ship all its supply would make the model infeasible; the hubs instead are written as equalities (in = out).
nlpm-f-154 · level facile · notes
Minimum-cost flow LP of a supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$, balances $b_i$ (supply $> 0$, demand $< 0$, transit $= 0$). Case-study network: 2 plants (supply 260 and 240), 2 hubs, 4 markets (total demand 450), 12 arcs; cheap arcs «by road» (polluting), expensive ones «by rail» (clean). In the code the arc capacities are given as variable bounds, `x = m.addVars(A, ub=U)`, not as constraints. Where is the value of one more unit of capacity on a saturated arc then read?
  1. In the reduced cost `RC` of the arc variable
  2. In the `Pi` of a capacity constraint
  3. In the `Slack` of the hub constraint
  4. Nowhere: bounds have no dual
Explanation. For a variable at its upper bound, `RC` is the shadow price of the bound: a saturated arc in a minimum has $\texttt{RC} < 0$, the saving per extra unit of capacity.
nlpm-f-155 · level facile · notes
Minimum-cost flow LP of a supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$, balances $b_i$ (supply $> 0$, demand $< 0$, transit $= 0$). Case-study network: 2 plants (supply 260 and 240), 2 hubs, 4 markets (total demand 450), 12 arcs; cheap arcs «by road» (polluting), expensive ones «by rail» (clean). How are costs and emissions of the arcs chosen in the case study, and why?
  1. Proportional, to keep the LP simple
  2. All equal, to isolate the effect of capacity
  3. Random, to test robustness
  4. Not proportional: road cheap, rail clean
Explanation. If emissions were proportional to costs, minimizing cost would also minimize emissions and there would be no trade-off; the case is built so that cost and CO$_2$ conflict.
nlpm-f-156 · level facile · notes
Minimum-cost flow LP of a supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$, balances $b_i$ (supply $> 0$, demand $< 0$, transit $= 0$). Case-study network: 2 plants (supply 260 and 240), 2 hubs, 4 markets (total demand 450), 12 arcs; cheap arcs «by road» (polluting), expensive ones «by rail» (clean). In the code the hubs are written `x.sum('*', h) == x.sum(h, '*')`. What does it express?
  1. Each hub ships its full capacity
  2. Hubs hold no stock: what enters leaves
  3. Each hub receives from one plant only
  4. Hubs have a positive balance
Explanation. It is the conservation constraint of a transit node, balance $b_h = 0$: inflow equals outflow.
nlpm-f-157 · level facile · notes
Minimum-cost flow LP of a supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$, balances $b_i$ (supply $> 0$, demand $< 0$, transit $= 0$). Case-study network: 2 plants (supply 260 and 240), 2 hubs, 4 markets (total demand 450), 12 arcs; cheap arcs «by road» (polluting), expensive ones «by rail» (clean). The shadow prices of the four market demands are $8.00$, $9.50$, $10.00$ and $10.50$ €/unit. What is the managerial use of these numbers?
  1. They are the selling prices to charge
  2. They are the average transport costs
  3. Marginal costs of serving each market
  4. They measure the CO$_2$ of each market
Explanation. Each is the cost of serving one more unit of that market; M4 costs $31\%$ more than M1. They are also the right basis for an internal transfer price.
nlpm-f-158 · level facile · notes
Minimum-cost flow LP of a supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$, balances $b_i$ (supply $> 0$, demand $< 0$, transit $= 0$). Case-study network: 2 plants (supply 260 and 240), 2 hubs, 4 markets (total demand 450), 12 arcs; cheap arcs «by road» (polluting), expensive ones «by rail» (clean). Case results: pure LP cost $3385$ €, max utilization $100\%$; with congestion ($\alpha = 1$) cost $3702.81$ €, max utilization $90\%$; minimax: $58.4\%$. What is the $58.4\%$?
  1. The lowest achievable maximum utilization
  2. The share of arcs used by the plan
  3. The utilization of the cheapest arc
  4. The cost increase of the minimax plan
Explanation. The minimax model $\min z$ with $x_{ij}/u_{ij} \le z$ finds the routing that keeps the most loaded arc as empty as possible: no plan can load every arc below $58.4\%$.
nlpm-f-159 · level facile · notes
Minimum-cost flow LP of a supply chain on a network $G = (N, A)$: flows $x_{ij}$ on the arcs, unit costs $c_{ij}$, capacities $u_{ij}$, balances $b_i$ (supply $> 0$, demand $< 0$, transit $= 0$). Case-study network: 2 plants (supply 260 and 240), 2 hubs, 4 markets (total demand 450), 12 arcs; cheap arcs «by road» (polluting), expensive ones «by rail» (clean). Internal CO$_2$ price $\tau$ (€/kg) added to the arc costs: up to $\tau = 1$ nothing changes; the main jump happens at $\tau = 1.25$ €/kg. What does this mean for the manager?
  1. Emissions fall linearly with $\tau$
  2. Any positive $\tau$ changes the routes
  3. $\tau$ has no effect at all on an LP
  4. Below it nothing changes; above, a jump
Explanation. LP optima sit at vertices: the solution stays on one vertex and then jumps. A CO$_2$ price below the threshold changes nothing; above it, the whole network moves toward rail.
nlpm-f-215 · level teorema · notes
Minimum-cost flow LP with costs $c_{ij} + \tau e_{ij}$ ($\tau$ = internal CO$_2$ price, $e_{ij}$ = kg per unit): as $\tau$ grows, emissions stay constant on intervals and then drop in jumps. Which LP property explains it?
  1. The LP has a unique solution for every $\tau$
  2. An optimal vertex always exists
  3. The objective is convex in the flows
  4. The flows are always integer numbers
Explanation. For each $\tau$ an optimal vertex exists; it stays optimal on an interval of $\tau$ and is then replaced by an adjacent vertex. A strictly convex model (congestion) would move continuously instead.

6. The Markowitz portfolio (26)

nlpm-f-019 · level facile · notes
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. Where does diversification come from?
  1. From the covariances $q_{ij}$ in the variance, which reward weakly correlated assets
  2. From the return constraint, which forces several assets into the portfolio
  3. From the caps $x_i \le u_i$, which forbid investing everything in one asset
  4. From the budget constraint $\sum_i x_i = 1$, which spreads the capital
Explanation. The variance contains the covariances: combining weakly correlated assets lowers the risk below that of each component, even without caps.
nlpm-f-020 · level facile · notes
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. Without the return constraint, the minimum-variance portfolio already has expected return $11.06\%$. What is the multiplier of the constraint “expected return at least $\bar r = 8\%$”?
  1. Positive, because every point of return costs variance
  2. Negative, because the constraint is a lower bound
  3. Zero, because the constraint is not active
  4. Undefined, because the model is a QP
Explanation. The constraint does not bite up to $11.06\%$, so by complementarity its multiplier is zero; only beyond that threshold every extra point of return is paid in variance.
nlpm-f-021 · level facile · notes
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. The inputs $\mu_i$ and $q_{ij}$ are estimated from 60 months of returns. What is the main practical lesson of the case study about these estimates?
  1. Covariances are much harder to estimate than expected returns
  2. Expected returns are far less stable than covariances, and the optimum chases their errors
  3. Sixty months of data give estimates accurate enough to trust the optimum
  4. The caps $x_i \le u_i$ remove the estimation errors from the inputs
Explanation. An asset with a true expected return of $11\%$ shows an estimated $1.6\%$ over 60 months. Remedies: caps, shrinkage, or the minimum-variance portfolio only.
nlpm-f-022 · level facile · notes
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. The efficient frontier collects the portfolios of minimum variance for each $\bar r$. In the case study, how does the equally weighted portfolio $x_i = 1/n$ compare with it?
  1. It lies exactly on the efficient frontier
  2. It coincides with the minimum-variance portfolio
  3. It lies above the frontier, dominating it
  4. It is dominated: similar return, almost twice the volatility
Explanation. The “I know nothing” strategy is clearly dominated; the minimum-variance portfolio has volatility $6\%$ and return $11\%$.
nlpm-f-023 · level facile · notes
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. Varying $\bar r$ traces the efficient frontier. Which formulation does **not** trace the same frontier?
  1. $\max \sum_i\mu_ix_i - \lambda\sum_i\sum_j q_{ij}x_ix_j$, varying $\lambda \ge 0$
  2. $\max \sum_i \mu_i x_i$, with no risk term and no bound on the variance
  3. $\max \sum_i\mu_ix_i$ with variance at most $\bar\sigma^2$, varying $\bar\sigma$
  4. $\min$ variance with expected return exactly $\bar r$ on the upper branch
Explanation. Threshold on the return, mean-variance and bound on the variance trace the same frontier; maximizing the return alone gives only one extreme point.
nlpm-f-024 · level facile · notes
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. A mandate adds the cap $x_i \le 30\%$ for every asset. What is the effect on the efficient frontier?
  1. It cuts the upper part: the highest returns become unreachable
  2. It shifts the whole frontier upwards, improving every portfolio
  3. It has no effect, since optimal portfolios are already diversified
  4. It lowers the minimum attainable variance
Explanation. Mandate constraints restrict the feasible set, so they can only worsen the frontier; their cost is the distance between the two frontiers, largest at high returns.
nlpm-f-025 · level teorema · notes
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. Which statement about this QP is correct?
  1. It is convex only if short selling is forbidden ($x_i \ge 0$)
  2. It is convex only if the assets are uncorrelated ($q_{ij} = 0$ for $i \ne j$)
  3. Every covariance matrix is positive semidefinite, so the QP is convex and its optimum global
  4. Every covariance matrix is positive definite, so the optimal portfolio is unique
Explanation. Covariance matrices are $\succeq 0$, not necessarily $\succ 0$: convexity holds with any linear constraints, uniqueness is not guaranteed.
nlpm-f-026 · level ipotesi · notes
Markowitz model with two uncorrelated assets of variances $\sigma_1^2$, $\sigma_2^2$, no return constraint: minimize $\sigma_1^2x_1^2 + \sigma_2^2x_2^2$ with $x_1 + x_2 = 1$. Which steps prove that $x_1 = \sigma_2^2/(\sigma_1^2 + \sigma_2^2)$ is optimal?
  1. The return constraint must be active at the optimum
  2. Strong LP duality between the QP and its dual
  3. The caps $x_i \le u_i$ must be inactive at the optimum
  4. Substitute $x_2 = 1 - x_1$: a convex parabola, whose stationary point is the minimum
Explanation. $f(x_1) = \sigma_1^2x_1^2 + \sigma_2^2(1-x_1)^2$ is convex, so $f'(x_1) = 0$ gives the global minimum; here it falls in $[0, 1]$.
nlpm-f-085 · level facile · notes
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. The lower bounds $x_i \ge \ell_i$ close the model. What does the choice $\ell_i = 0$ for every asset express?
  1. That every asset must be in the portfolio
  2. That the expected returns are non-negative
  3. That the covariances are non-negative
  4. That short selling is forbidden
Explanation. A negative share would be a short sale; with $\ell_i = 0$ only non-negative shares are allowed, while $\ell_i > 0$ would force a minimum holding.
nlpm-f-086 · level facile · notes
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. In the case study (eight sector ETFs) the least risky single asset has volatility $7.53\%$, while the minimum-variance portfolio has volatility $6.03\%$. What does this show?
  1. An estimation error: no portfolio can beat its best asset
  2. Diversification: combining assets lowers risk below the safest one
  3. That the safest asset should get $100\%$ of the capital
  4. That the covariances were set to zero
Explanation. With imperfectly correlated assets the portfolio variance is below that of every component; the minimum-variance portfolio still returns $11\%$.
nlpm-f-087 · level facile · notes
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. In the case study the minimum-variance portfolio puts $58.3\%$ in the utilities ETF (UTL), the asset with the lowest volatility ($7.53\%$). Why not $100\%$?
  1. Because a mandate caps every asset at $58.3\%$
  2. Because UTL has the lowest expected return
  3. Because adding weakly correlated assets lowers the variance further
  4. Because the return constraint is active
Explanation. Moving away from the single safest asset towards weakly correlated ones reduces the variance, until the marginal variance contributions are balanced.
nlpm-f-088 · level facile · notes
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_j q_{ij}x_ix_j$ with $\sum_i x_i = 1$ and expected return at least $\bar r$. In the case study, at $\bar r = 12\%$ the multiplier of the return constraint is about $0.022$. How is it read?
  1. The portfolio volatility is $2.2\%$
  2. The expected return grows by $0.022$ per unit of variance
  3. $2.2\%$ of the capital is in the riskiest asset
  4. Raising $\bar r$ by one unit raises the minimum variance by about $0.022$
Explanation. The multiplier is $d(\text{variance})/d\bar r$: beyond $11.06\%$ every extra point of required return is paid in variance, and the price grows along the frontier.
nlpm-f-160 · level facile · notes
The Markowitz model of the course does not return a single number but an efficient frontier. What is it for?
  1. It gives the single best portfolio for everyone
  2. It lists the assets sorted by return
  3. A menu of risk–return trade-offs
  4. It shows the history of past returns
Explanation. Each point is a minimum-variance portfolio for a required return; the decision maker picks one according to his own risk aversion.
nlpm-f-161 · level facile · notes
Beyond finance, where does the structure of the Markowitz model reappear, according to the course notes?
  1. In R&D project mixes and similar choices
  2. Only in the management of pension funds
  3. In the routing of vehicles on a network
  4. In the scheduling of jobs on machines
Explanation. The structure is «allocate a budget among risky, correlated alternatives»: R&D portfolios, client portfolios, even production capacity across volatile markets.
nlpm-f-162 · level facile · notes
The course calls Markowitz «the natural bridge between optimization and statistics». Why?
  1. Because it uses integer variables
  2. Because it has no constraints at all
  3. Because it is solved by regression
  4. Its data are estimates
Explanation. Expected returns and covariances are estimated from historical data; the optimizer takes them as true, so estimation errors flow into the portfolio.
nlpm-f-163 · level facile · notes
What is the decision of an investor in the Markowitz model of the course?
  1. Which single asset to buy
  2. The share invested in each asset
  3. The number of shares to sell short
  4. The moment at which to sell the assets
Explanation. The variables are the shares $x_i$ (they sum to 1); the objective is the variance of the portfolio return, with a minimum expected return and per-asset bounds.
nlpm-f-164 · level facile · notes
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_jq_{ij}x_ix_j$ with $\sum_ix_i = 1$, expected return at least $\bar r$ and bounds $\ell_i \le x_i \le u_i$. Two uncorrelated assets with volatilities $\sigma_1 = 20\%$, $\sigma_2 = 30\%$, no return constraint. What is the minimum-variance share $x_1$?
  1. $x_1 = 2/5 = 40\%$
  2. $x_1 = 9/13 \approx 69.2\%$
  3. $x_1 = 1/2$
  4. $x_1 = 3/5 = 60\%$
Explanation. Minimizing $0.04x_1^2 + 0.09(1 - x_1)^2$: $x_1 = 0.09/(0.04 + 0.09) = 9/13$. Weights are inversely proportional to the variances (not to the volatilities, which would give $60\%$).
nlpm-f-165 · level facile · notes
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_jq_{ij}x_ix_j$ with $\sum_ix_i = 1$, expected return at least $\bar r$ and bounds $\ell_i \le x_i \le u_i$. Two uncorrelated assets, $\sigma_1 = 20\%$, $\sigma_2 = 30\%$: the minimum-variance portfolio has variance $0.0277$. What is its volatility, compared with the two assets?
  1. $25\%$, between the two
  2. $20\%$, as the safer asset
  3. $30\%$, as the riskier asset
  4. $16.6\%$, below both
Explanation. $\sqrt{0.0277} \approx 16.6\% < 20\%$: the portfolio is less risky than either asset, diversification in its purest form.
nlpm-f-166 · level facile · notes
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_jq_{ij}x_ix_j$ with $\sum_ix_i = 1$, expected return at least $\bar r$ and bounds $\ell_i \le x_i \le u_i$. In the two-asset example ($\sigma_1 = 20\%$, $\sigma_2 = 30\%$, uncorrelated, $x_2 = 1 - x_1$), how is the optimal share found by hand?
  1. Zero derivative of the variance in $x_1$
  2. Taking the asset with the higher return
  3. Splitting the capital in equal parts
  4. Solving an LP on the two shares
Explanation. After substituting the budget, the variance is a convex parabola in $x_1$: $0.08x_1 - 0.18(1 - x_1) = 0$ gives $x_1 = 9/13$.
nlpm-f-167 · level facile · notes
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_jq_{ij}x_ix_j$ with $\sum_ix_i = 1$, expected return at least $\bar r$ and bounds $\ell_i \le x_i \le u_i$. Case study: eight sector ETFs (Exchange Traded Funds, quoted funds that track a sector basket), 60 simulated monthly returns. How are $\mu_i$ and $q_{ij}$ obtained?
  1. They are given exactly by the fund managers
  2. They are set equal for all assets
  3. They are estimated from the 60 monthly returns
  4. They come from the solver
Explanation. As in practice, the inputs are estimated from data (then annualized): this is why the chapter ends with a warning on the fragility of the estimates.
nlpm-f-168 · level facile · notes
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_jq_{ij}x_ix_j$ with $\sum_ix_i = 1$, expected return at least $\bar r$ and bounds $\ell_i \le x_i \le u_i$. In the gurobipy code the shares are created with `x = m.addVars(n, ub=u)`. Which constraint of the model does `ub=u` implement?
  1. The per-asset caps $x_i \le u_i$
  2. The budget $\sum_ix_i = 1$
  3. The minimum return $\sum_i\mu_ix_i \ge \bar r$
  4. The ban on short selling only
Explanation. The caps are given as upper bounds of the variables; the default lower bound $0$ is the ban on short selling ($\ell_i = 0$). Budget and return are explicit constraints.
nlpm-f-169 · level facile · notes
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_jq_{ij}x_ix_j$ with $\sum_ix_i = 1$, expected return at least $\bar r$ and bounds $\ell_i \le x_i \le u_i$. Case-study statistics (annualized): TEC has $\mu = 1.58\%$ and volatility $29.27\%$, UTL $\mu = 11.99\%$ and volatility $7.53\%$. Which asset is the least risky on its own?
  1. TEC, the most volatile
  2. MAT, with the highest return
  3. ENE, with a high return
  4. UTL, with volatility $7.53\%$
Explanation. UTL has the lowest volatility of the eight ETFs; the minimum-variance portfolio puts $58.3\%$ in it and still goes below its risk (6.03%) by diversifying.
nlpm-f-170 · level facile · notes
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_jq_{ij}x_ix_j$ with $\sum_ix_i = 1$, expected return at least $\bar r$ and bounds $\ell_i \le x_i \le u_i$. In the gurobipy code the objective is `quicksum(Q[i, j]*x[i]*x[j] for i in range(n) for j in range(n))`. What kind of model does Gurobi receive?
  1. An LP, since the constraints are linear
  2. A convex QP
  3. A nonconvex QP needing `NonConvex = 2`
  4. An NLP with functional constraints only
Explanation. A covariance matrix is positive semidefinite, so the quadratic objective is convex and Gurobi certifies a global optimum without special parameters.
nlpm-f-171 · level facile · notes
Markowitz model: shares $x_i$ of capital in assets $i$, expected returns $\mu_i$, covariances $q_{ij}$; minimize the variance $\sum_i\sum_jq_{ij}x_ix_j$ with $\sum_ix_i = 1$, expected return at least $\bar r$ and bounds $\ell_i \le x_i \le u_i$. Case study: up to $\bar r = 11\%$ the volatility stays $6.03\%$; at $\bar r = 12\%$ it becomes $6.10\%$ with multiplier about $0.022$. What does the multiplier measure?
  1. The return gained per unit of variance
  2. The share invested in the best asset
  3. Variance paid per point of return
  4. The volatility of the min-variance portfolio
Explanation. It is $\partial(\text{variance})/\partial\bar r$ for the active return constraint; below $11.06\%$ the constraint is inactive and the multiplier is zero.
nlpm-f-216 · level teorema · notes
Markowitz with two uncorrelated assets of variances $\sigma_1^2$ and $\sigma_2^2$, budget $x_1 + x_2 = 1$, no return constraint. Which statement about the minimum-variance shares is correct?
  1. $x_1 = \sigma_2^2/(\sigma_1^2 + \sigma_2^2)$
  2. $x_i$ is proportional to $\sigma_i^2$
  3. $x_i$ is inversely proportional to $\sigma_i$
  4. $x_1 = x_2 = 1/2$, whatever the variances
Explanation. Setting the derivative of $\sigma_1^2x_1^2 + \sigma_2^2(1 - x_1)^2$ to zero gives $x_1\sigma_1^2 = x_2\sigma_2^2$: weights inversely proportional to the variances, and portfolio variance below both.
nlpm-f-217 · level ipotesi · notes
The Markowitz QP minimizes $\sum_i\sum_jq_{ij}x_ix_j$; the notes call it convex because $\mathbf Q = (q_{ij})$ is a covariance matrix. If $\mathbf Q$ were patched together from estimates on different samples and lost positive semidefiniteness, what would fail?
  1. Nothing: any symmetric matrix gives a convex QP
  2. Only the budget constraint of the model
  3. Convexity of the QP
  4. The linearity of the return constraint
Explanation. The QP is convex if and only if $\mathbf Q \succeq 0$; a genuine covariance matrix always is, but an inconsistent patchwork may not, and then the objective can be nonconvex (even unbounded below along some direction).

7. Pricing and revenue management (22)

nlpm-f-027 · level facile · notes
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). Where does the non-convexity of this model come from?
  1. From the capacity constraint $q \le k$
  2. From the bilinear term $p \cdot q$ in the objective
  3. From the non-negativity of the price $p$
  4. From the demand constraint, even when $d$ is linear
Explanation. The product of two variables is non-convex. With linear demand, substituting $q = a - bp$, the reduced problem is a concave parabola in $p$.
nlpm-f-028 · level facile · notes
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). With linear demand $d(p) = a - b\,p$ and no capacity limit, what is the optimal price $p^\circ$?
  1. $p^\circ = (a/b + c)/2$
  2. $p^\circ = a/b$
  3. $p^\circ = c$
  4. $p^\circ = (a - c)/b$
Explanation. The profit $(p - c)(a - bp)$ is a concave parabola: setting its derivative to zero gives $p^\circ = (a/b + c)/2$, halfway between $c$ and the choke price $a/b$.
nlpm-f-029 · level facile · notes
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). Concert example: $d(p) = 1200 - 5p$, $c = 20$ €, $k = 400$ seats, optimal price $\tilde p = 160$ €. The value of one more seat, $d\Pi/dk$ with $\Pi(k)$ the optimal profit, is $60$ €, not the margin $\tilde p - c = 140$ €. Why?
  1. Because the marginal cost $c$ grows with the capacity $k$
  2. Because the extra seat would stay empty at the price $\tilde p$
  3. Because the capacity constraint becomes inactive at $k = 401$
  4. Because the price falls for everybody: $d\Pi/dk = (\tilde p - c) + k\,d\tilde p/dk = 140 - 80$
Explanation. With $\tilde p = (a - k)/b$ the price falls by $1/b$ per extra seat, on all $k$ tickets. Ignoring it is a classic mistake in evaluating capacity investments.
nlpm-f-030 · level facile · notes
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). With constant-elasticity demand $d(p) = \theta p^{-\varepsilon}$ ($\varepsilon > 1$) and binding capacity, the optimum is $\tilde p = (\theta/k)^{1/\varepsilon}$, where $d(\tilde p) = k$. What kind of optimum is it?
  1. A stationary point of the profit $(p - c)\,d(p)$
  2. A local minimum of the profit
  3. A corner point, where no derivative of the profit vanishes
  4. An unbounded solution cut off by the capacity
Explanation. Below $\tilde p$ the capacity sells out anyway (better raise the price), above it the profit falls: with constraints the optimum must not be sought among stationary points only.
nlpm-f-031 · level facile · notes
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). Concert example $d(p) = 1200 - 5p$, $c = 20$ €: without capacity the optimal quantity is $q^\circ = 550$ seats. What happens to the value of capacity $d\Pi/dk$ for $k > 550$?
  1. It keeps growing linearly with $k$
  2. It is zero: capacity is no longer binding
  3. It becomes negative: empty seats cost money
  4. It equals the full margin $p^\circ - c$
Explanation. Beyond the unconstrained optimal quantity the optimal profit curve $\Pi(k)$ is flat: additional capacity is worth nothing.
nlpm-f-032 · level facile · notes
Pricing model with two seat categories (stalls and balcony) and substitution: the demand of each category depends on both prices $p_1, p_2$. Why must the two prices be decided jointly?
  1. Because each demand depends on both prices: one at a time loses profit
  2. Because the two categories have the same marginal cost
  3. Because the two categories have the same capacity
  4. Because with two products the model becomes an LP
Explanation. Raising the stalls price pushes part of the demand towards the balcony: the joint model keeps the stalls expensive to exploit the substitution.
nlpm-f-033 · level facile · notes
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). With a general demand function $d(p)$ (e.g. logistic) the profit may not be concave. What does the course recommend before trusting the solver's answer?
  1. Replacing $d(p)$ with a linear demand fitted to the data
  2. Removing the capacity constraint, a source of corner points
  3. Setting the price equal to the marginal cost $c$
  4. Studying domain and derivatives and plotting the profit
Explanation. Gurobi certifies the global optimum, but understanding the shape of the profit (domain, derivatives, plot over the relevant interval, several starting points) remains part of the work.
nlpm-f-034 · level ipotesi · notes
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). The model writes $q \le d(p)$ rather than $q = d(p)$. Which assumption guarantees that, at the optimum, $\tilde q = \min\{d(\tilde p), k\}$?
  1. $k > d(p)$ for every price $p$
  2. The demand $d(p)$ is linear in $p$
  3. $\tilde p > c$: every extra unit sold adds profit
  4. $\tilde p = c$: the margin is zero
Explanation. With a positive unit margin each extra unit sold increases the profit, so $q$ is pushed up to the smaller of demand and capacity.
nlpm-f-089 · level facile · notes
Two-category pricing (stalls 1, balcony 2) with demands $d_1 = 500 - 2p_1 + 0.6\,p_2$ and $d_2 = 900 + 0.8\,p_1 - 4p_2$. What does the positive coefficient $0.6$ of $p_2$ in $d_1$ express?
  1. That the stalls are 60% full
  2. That stalls demand falls when the balcony price rises
  3. That the two categories are complements
  4. Substitution: a dearer balcony moves demand to the stalls
Explanation. A positive cross coefficient means substitute products; this is why the two prices must be chosen jointly.
nlpm-f-090 · level facile · notes
Two-category pricing: maximize $\sum_i (p_i - c_i)q_i$ with $q_i \le d_i(p_1, p_2)$ (linear demands) and $q_i \le k_i$. Which Gurobi setting does this model need?
  1. None: with linear demands it is an LP
  2. `NonConvex = 2`, because of the bilinear terms $p_i q_i$
  3. `FuncNonlinear = 1`, because of the demand functions
  4. `QCPDual = 1`, to make it convex
Explanation. The objective contains the products of two variables $p_iq_i$, as in the single-product case: bilinear, non-convex, solved globally with `NonConvex = 2`.
nlpm-f-091 · level facile · notes
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). Constant-elasticity demand $d(p) = \theta p^{-\varepsilon}$ with $\varepsilon = 2.2$ and $c = 20$ €: without capacity the optimal price would be $c\,\varepsilon/(\varepsilon - 1) = 36.67$ €. Why is the optimum with capacity $k$ instead $\tilde p = 79.11$ €?
  1. At $36.67$ € demand far exceeds $k$: the price rises until $d(p) = k$
  2. Because the formula $c\varepsilon/(\varepsilon - 1)$ holds only for $\varepsilon < 1$
  3. Because the solver stops at a local optimum
  4. Because at $36.67$ € the margin $p - c$ is negative
Explanation. Selling $k$ anyway at a higher price increases profit: the optimum is the corner point where demand equals capacity, $\tilde p = (\theta/k)^{1/\varepsilon}$.
nlpm-f-092 · level ipotesi · notes
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). With linear demand $d(p) = a - bp$ ($b > 0$) and no capacity, which facts make $p^\circ = (a/b + c)/2$ the global optimum?
  1. With $q = a - bp$ the profit $(p - c)(a - bp)$ is concave in $p$: stationary means global
  2. The bilinear term $p\,q$ is convex, so every stationary point is a global optimum
  3. The demand constraint is inactive at the optimum, so the model reduces to an LP
  4. Strong duality between the pricing model and its dual, with equal optimal values
Explanation. The coefficient of $p^2$ is $-b < 0$: the reduced profit is concave in $p$ and $\Pi'(p) = 0$ gives its global maximum.
nlpm-f-172 · level facile · notes
What is new in the pricing chapter of the course compared with the previous models?
  1. The demand is a fixed datum of the model
  2. The price is a decision variable
  3. The model has integer variables
  4. The capacity is assumed unlimited
Explanation. With the price as a decision, the quantity sold depends on it and the profit $p\cdot q$ contains a bilinear term: the course meets nonconvexity for the first time.
nlpm-f-173 · level facile · notes
Revenue management, born in the airlines, adds a capacity constraint to pricing. What makes capacity special in this setting?
  1. It can be stored in a warehouse
  2. It is always unlimited in practice
  3. It costs nothing to expand
  4. Unsold seats are lost
Explanation. Seats, rooms and rental slots perish: what is not sold by the deadline is lost, so price and capacity must be decided together.
nlpm-f-174 · level facile · notes
Why do the course notes call the price «perhaps the business decision with the highest impact on margin»?
  1. Price moves the margin of every unit
  2. Because prices never change
  3. Because costs do not depend on volume
  4. Because demand is insensitive to price
Explanation. A price change hits the margin of every unit sold, while a volume change affects only the extra units; hence the attention to pricing models.
nlpm-f-175 · level facile · notes
One learning goal of the pricing chapter is to recognize «corner optima». What are they?
  1. Optima of linear programs only
  2. Optima found by rounding a solution
  3. Optima where no derivative vanishes
  4. Local optima of nonconvex functions
Explanation. With capacity binding, the optimum can sit where $d(p) = k$: the profit has no stationary point there, so searching only among stationary points would miss it.
nlpm-f-176 · level facile · notes
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). Linear demand $d(p) = a - bp$. Substituting $q = a - bp$, what does the profit $(p - c)(a - bp)$ become as a function of $p$?
  1. A convex parabola: the problem is hard
  2. A linear function: the optimum is at a bound
  3. A concave parabola: the reduced problem is easy
  4. A cubic with two local maxima
Explanation. The reduced profit is a concave quadratic in $p$, maximized at $p^\circ = (a/b + c)/2$ without capacity; the bilinear version is still solved globally by Gurobi with `NonConvex = 2`.
nlpm-f-177 · level facile · notes
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). How do the notes treat the general demand functions (constant elasticity $\theta p^{-\varepsilon}$, logistic) in Gurobi?
  1. With functional constraints
  2. By linearizing them around the optimum
  3. With a local NLP solver from a guess
  4. By replacing them with linear demand
Explanation. Gurobi's functional constraints (`addGenConstrPow`, `addGenConstrExp`) handle them in the same solver, still with a global optimum.
nlpm-f-178 · level facile · notes
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). Concert case ($d(p) = 1200 - 5p$, $c = 20$, $k = 400$): Gurobi gives $p^* = 160$, profit $56{,}000$ €; resolving with $k = 401$ estimates the value of one more seat at $59.80$ € (theory: $60$). Why is the value estimated by re-solving?
  1. Because the LP duals are too slow to read
  2. Because the capacity constraint is inactive
  3. Because the result must be an integer
  4. Nonconvex QPs give no duals: perturbation is used
Explanation. With the bilinear objective (`NonConvex = 2`) Gurobi returns no `Pi`; the script sets `v_cap.RHS = K + 1`, re-optimizes and takes the difference.
nlpm-f-179 · level facile · notes
Pricing model: choose price $p$ and quantity sold $q$ to maximize $p\,q - c\,q$ subject to $q \le d(p)$ (demand at price $p$) and $q \le k$ (capacity). Logistic demand $d(p) = m/(1 + e^{-\alpha + \beta p})$ with $m = 900$, $\alpha = 6$, $\beta = 0.045$, $c = 20$, $k = 400$: the solver gives $p^* = 138.29$ €. What do the notes recommend before trusting such a result?
  1. Nothing: Gurobi is always right
  2. Study and plot the profit curve
  3. Round the price to the nearest euro first
  4. Replace the logistic with a linear demand
Explanation. With general demand functions the profit may not be concave: study domain and derivatives, plot the profit on the relevant interval, and with local solvers try several starting points.
nlpm-f-218 · level teorema · notes
Pricing with linear demand $d(p) = a - bp$, cost $c$, capacity $k$ binding: $p^* = (a - k)/b$ and profit $\Pi(k) = (p^* - c)k$. Why is one more seat worth less than the full margin $p^* - c$?
  1. Because the cost $c$ grows with $k$
  2. Because demand becomes infinite
  3. Because the capacity constraint becomes inactive
  4. Filling it lowers the price for all
Explanation. $dp^*/dk = -1/b$, so $d\Pi/dk = (p^* - c) + k\,dp^*/dk$; in the concert ($a = 1200$, $b = 5$, $c = 20$, $k = 400$) it is $140 - 80 = 60$ €, not 140.
nlpm-f-219 · level teorema · notes
Pricing with constant-elasticity demand $d(p) = \theta p^{-\varepsilon}$ ($\varepsilon > 1$), cost $c$, capacity $k$; the unconstrained optimum $c\varepsilon/(\varepsilon - 1)$ would exceed capacity. Why is the optimum at $p^* = (\theta/k)^{1/\varepsilon}$, where $d(p) = k$?
  1. It is the only stationary point of the profit
  2. Below it profit rises, above it falls
  3. Because the profit is linear in $p$
  4. Because the elasticity equals 1 there
Explanation. For $p < p^*$ demand exceeds $k$, sales stay at $k$ and $(p - c)k$ grows; for $p > p^*$ the profit $(p - c)\theta p^{-\varepsilon}$ decreases (we are past its unconstrained peak). The optimum is a corner where no derivative vanishes.

8. Advertising budget allocation (26)

nlpm-f-035 · level facile · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). What holds at the optimum for every channel with $0 < \tilde x_i < u_i$?
  1. $r_i'(\tilde x_i) = \lambda$: the last euro yields the same in all such channels
  2. $\tilde x_i = b/n$: the budget is split evenly among the channels
  3. $r_i(\tilde x_i) = \lambda$: every channel yields the same total response
  4. $r_i'(\tilde x_i) = 0$: every channel is pushed to its saturation point
Explanation. If the marginal returns differed, moving one euro from the low one to the high one would improve the total response.
nlpm-f-036 · level facile · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). A channel is left at zero in the optimal allocation, $\tilde x_i = 0$. What can be said about it?
  1. Its marginal return $r_i'(0)$ equals $\lambda$
  2. Its cap $u_i$ is too small to be useful
  3. Its initial marginal return $r_i'(0)$ is at most $\lambda$
  4. The budget constraint is not active
Explanation. A channel at zero is not worth even the first euro: $r_i'(0) \le \lambda$. Channels at the cap may instead have marginal return $\ge \lambda$.
nlpm-f-037 · level facile · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). In the case study the caps are $u = (60, 80, 120, 35)$ thousand € and $\lambda$ drops to zero when the budget reaches $b = 300$. Why?
  1. Because the responses $r_i$ become linear for large spends
  2. Because the solver fails for large budgets
  3. Because the budget constraint becomes an equality
  4. Because all channels are at their caps: $60 + 80 + 120 + 35 = 295 < 300$
Explanation. With every channel at its cap the budget constraint is no longer active, so its multiplier is zero. The budget value curve is concave: $\lambda$ falls as $b$ grows.
nlpm-f-038 · level facile · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). The responses are $r_i(x) = a_i\log(1 + k_ix)$. In the case study TV gets less than social media although its cap $u_i$ is higher. What explains it?
  1. The cap of TV is active at the optimum
  2. The saturation speed $k_i$ of each channel, not its size
  3. A numerical error of the solver
  4. The scale coefficient $a_i$ alone
Explanation. What matters is how fast the marginal return $a_ik_i/(1 + k_ix)$ decreases, governed by $k_i$: a large channel that saturates quickly gets less.
nlpm-f-039 · level facile · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). With $r_i(x) = a_i\log(1 + k_ix)$, how is the objective $\sum_i a_i\log(1 + k_ix_i)$ handled in Gurobi?
  1. Auxiliary $g_i = 1 + k_ix_i$, $z_i = \log g_i$ (function constraints), objective $\sum_i a_iz_i$
  2. By replacing each logarithm with its tangent line at $x_i = 0$
  3. By setting `NonConvex = 2` and writing the logarithms directly
  4. By solving the KKT conditions by hand and fixing the $x_i$
Explanation. The function constraints make the objective linear in the $z_i$; the optimum is certified global and the KKT conditions are then checked on the numbers.
nlpm-f-040 · level facile · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). What does the multiplier $\lambda$ of the budget constraint tell a CFO?
  1. The total response of the campaign at the optimum
  2. The cap of the channel with the best response
  3. The extra response bought by one more euro of budget
  4. The average response per euro spent
Explanation. $\lambda$ is the marginal value of the budget: it is worth adding budget as long as $\lambda$ exceeds the value of a euro invested elsewhere, and $\lambda$ falls as the budget grows.
nlpm-f-041 · level teorema · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). Which statement justifies that this model has a certifiable global optimum?
  1. Every NLP with linear constraints has a unique optimum
  2. A sum of concave functions is maximized over a polyhedron: local maxima are global
  3. Every separable function is linear on a polyhedron
  4. The objective is increasing, so the budget is active
Explanation. The objective is separable and a sum of concave functions, the constraints are linear: the problem is convex and every local maximum is global.
nlpm-f-042 · level ipotesi · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). Which ingredients yield the condition $r_i'(\tilde x_i) = \lambda$ for a channel at the optimum?
  1. Only the activity of the budget constraint
  2. The linearity of the response functions $r_i$
  3. Strong LP duality applied to the budget constraint
  4. KKT stationarity, $r_i$ differentiable, and $0 < \tilde x_i < u_i$ (null bound multipliers)
Explanation. For channels on a bound, the multipliers of $x_i \ge 0$ or $x_i \le u_i$ enter the stationarity condition and the equality with $\lambda$ no longer holds.
nlpm-f-093 · level facile · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). The responses $r_i$ are increasing. What would happen without the budget constraint $\sum_i x_i \le b$?
  1. The model would become infeasible
  2. Every channel would get the same spend
  3. The model would become non-convex
  4. Every channel would go to its cap $u_i$
Explanation. The budget is the only constraint linking the channels: with increasing responses and no budget, each channel is pushed independently to its cap.
nlpm-f-094 · level facile · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). In the case study, with $b = 100$ thousand €, all four channels lie strictly between $0$ and their caps and their marginal returns $r_i'(\tilde x_i)$ all equal $8.2693$. What does this confirm?
  1. That the solver stopped too early
  2. That the budget constraint is not active
  3. The KKT condition $r_i'(\tilde x_i) = \lambda$, with $\lambda = 8.2693$
  4. That the four responses are identical
Explanation. For interior channels stationarity gives $r_i'(\tilde x_i) = \lambda$: the last euro yields the same everywhere, and the common value is the multiplier of the budget.
nlpm-f-095 · level facile · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). In the case study $\lambda = 8.2693$; adding $1$ (thousand €) to the budget and re-solving, the response grows by $8.244$. Why slightly less than $\lambda$?
  1. A numerical error of the function constraints
  2. Because one channel reaches its cap
  3. Because the multiplier is wrong by about $0.3\%$
  4. Concavity: the marginal value falls as the budget grows
Explanation. The optimal response $V(b)$ is concave: the finite increment over $[b, b + 1]$ is below the slope $\lambda$ at $b$. The check still confirms the reading of the multiplier.
nlpm-f-096 · level teorema · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_i r_i(x_i)$ subject to $\sum_i x_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). Let $V(b)$ be the optimal total response as a function of the budget $b$. Which statement is correct?
  1. $V(b)$ is concave, with slope $\lambda(b)$ non-increasing in $b$
  2. $V(b)$ is convex, so $\lambda(b)$ grows with the budget
  3. $V(b)$ is linear, so $\lambda$ is the same for every budget
  4. $V(b)$ is decreasing once all channels are active
Explanation. Maximizing a concave function with the budget as right-hand side gives a concave value function: in the case study $\lambda$ falls from $19$ ($b = 20$) to $4$ ($b = 260$).
nlpm-f-180 · level facile · notes
Why is the response of an advertising channel modelled as a concave function of the spend in the course?
  1. Because concave functions are linear
  2. Because spend must be an integer
  3. Because every channel saturates at once
  4. The first euros yield much, the next ones less
Explanation. Diminishing marginal returns: each extra euro on a channel adds less response than the previous one, which is exactly concavity.
nlpm-f-181 · level facile · notes
The budget chapter calls the allocation among uses with diminishing returns a «universal scheme». Which example fits it?
  1. Routing trucks on a road network
  2. Funds among projects, time among activities
  3. Choosing one supplier out of three
  4. Sequencing jobs on a machine
Explanation. Marketing channels, funds among projects, time among activities, fertilizer among fields: the same model and the same optimality rule apply.
nlpm-f-182 · level facile · notes
What «strong and verifiable» statement does the theory make about the optimal budget allocation, according to the course notes?
  1. Marginal returns are equal at the optimum
  2. All channels get the same spend
  3. The largest channel gets everything
  4. The spend is proportional to the caps
Explanation. At the optimum the marginal returns of the active channels coincide, and the solver returns exactly that, digit by digit (the case study shows $8.2693$ for all four channels).
nlpm-f-183 · level facile · notes
How will the multiplier $\lambda$ of the budget constraint be used, according to the goals of the budget chapter?
  1. To set the caps of the channels
  2. To choose the response functions
  3. To negotiate the size of the budget
  4. To round the spends
Explanation. $\lambda$ is the extra response per extra euro of budget; the curve of $\lambda$ against the budget is the quantitative argument for deciding how much to give to marketing.
nlpm-f-184 · level media · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_ir_i(x_i)$ subject to $\sum_ix_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). Two channels, $r_1(x) = 100\log(1 + 0.2x)$, $r_2(x) = 60\log(1 + 0.1x)$, budget $b = 50$ (thousand €), no caps. What is the optimal split?
  1. $x_1 = 25$, $x_2 = 25$
  2. $x_1 = 35.6$, $x_2 = 14.4$
  3. $x_1 = 50$, $x_2 = 0$
  4. $x_1 = 31.25$, $x_2 = 18.75$
Explanation. Equal marginals: $20/(1 + 0.2x_1) = 6/(1 + 0.1x_2)$ with $x_2 = 50 - x_1$ gives $120 - 2x_1 = 6 + 1.2x_1$, so $x_1 = 114/3.2 = 35.6$, $x_2 = 14.4$.
nlpm-f-185 · level facile · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_ir_i(x_i)$ subject to $\sum_ix_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). Two channels, $r_1(x) = 100\log(1 + 0.2x)$, $r_2(x) = 60\log(1 + 0.1x)$, $b = 50$: the optimum is $x_1 = 35.6$, $x_2 = 14.4$. What is the shadow price of the budget?
  1. $\lambda = 20.0$
  2. $\lambda = 6.0$
  3. $\lambda = 0.0$
  4. $\lambda = 2.46$
Explanation. $\lambda = r_1'(35.6) = 20/(1 + 0.2\cdot 35.6) = 2.46$, the same as $r_2'(14.4) = 6/2.44$: one more euro of budget yields about $2.46$ units, whichever channel it enters.
nlpm-f-186 · level facile · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_ir_i(x_i)$ subject to $\sum_ix_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). Two-channel example with no caps and $b = 50$. Why can the budget constraint be used as an equality, $x_2 = 50 - x_1$?
  1. Unspent budget would be wasted
  2. Because the caps force it here
  3. Because $\lambda = 0$ at the optimum
  4. Because the two channels are identical
Explanation. With increasing responses an unspent euro could always add response somewhere, so the budget is active at the optimum (and $\lambda > 0$).
nlpm-f-187 · level facile · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_ir_i(x_i)$ subject to $\sum_ix_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). Two channels with $r_1'(0) = 20$ and $r_2'(0) = 6$ (marginal response of the first euro). What does the optimal rule imply for channel 2 when the budget is very small?
  1. It always gets half of the budget
  2. It gets everything, being the cheaper one
  3. It stays at zero until $r_1'$ falls to 6
  4. It gets the same spend as channel 1
Explanation. Money goes first where the marginal return is highest; channel 2 enters only when channel 1's marginal, decreasing with spend, has dropped to its initial marginal of 6.
nlpm-f-188 · level facile · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_ir_i(x_i)$ subject to $\sum_ix_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). In the gurobipy code, with $r_i(x) = a_i\log(1 + k_ix)$, the script creates `g = m.addVars(4, lb=1.0)` and `z = m.addVars(4, lb=-GRB.INFINITY)`, with `g[i] == 1 + k[i]*x[i]` and `addGenConstrLog(g[i], z[i])`. Why is `z` free?
  1. Because $z_i$ must be negative
  2. Because Gurobi requires free variables in objectives
  3. Because a logarithm can be negative in general
  4. Because $z_i$ is a binary variable
Explanation. `addGenConstrLog` imposes $z = \log g$; the default bound $z \ge 0$ would cut values where $g < 1$. Here $g \ge 1$ so $z \ge 0$ anyway, but declaring it free avoids a hidden restriction.
nlpm-f-189 · level facile · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_ir_i(x_i)$ subject to $\sum_ix_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). In the gurobipy code of the budget case the script sets `m.Params.FuncNonlinear = 1`. What does it do?
  1. Treats the logarithm exactly
  2. Turns the model into an LP
  3. Allows integer spends on channels
  4. Prints the log of the solver
Explanation. With `FuncNonlinear = 1` the functional constraints are handled exactly (not by a fixed piecewise approximation), so the optimum is certified global.
nlpm-f-190 · level facile · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_ir_i(x_i)$ subject to $\sum_ix_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). In the budget code the objective is `quicksum(a[i] * z[i] for i in range(4))`, with $z_i = \log(1 + k_ix_i)$ imposed by functional constraints. Why does this work?
  1. Because $\log$ is linear in $x_i$
  2. Because Gurobi approximates $\log$ by a line
  3. Because the caps make $z_i$ constant
  4. It is linear in the auxiliary $z_i$
Explanation. All the nonlinearity is moved into the constraints $z_i = \log g_i$, $g_i = 1 + k_ix_i$; the objective is then a linear combination of the $z_i$.
nlpm-f-191 · level facile · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_ir_i(x_i)$ subject to $\sum_ix_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). Case study: total response $1449.8$, four channels with marginals all equal to $8.2693$; adding 1000 € of budget raises the response by $8.244$. What does this check?
  1. That the caps of the channels are active
  2. That $\lambda$ is the value of budget
  3. That the responses are linear
  4. That one channel should be dropped
Explanation. The KKT condition $r_i'(x_i) = \lambda$ appears in the numbers, and the actual gain of one more unit of budget, $8.244$, confirms the reading of the multiplier (slightly less, by concavity).
nlpm-f-192 · level facile · notes
Advertising budget model: spend $x_i$ on channel $i$, concave response $r_i(x_i)$, maximize $\sum_ir_i(x_i)$ subject to $\sum_ix_i \le b$ (budget, multiplier $\lambda \ge 0$) and $0 \le x_i \le u_i$ (caps). Case study: $\lambda = 18.97$ at $b = 20$, $8.24$ at $b = 100$, $4.05$ at $b = 260$, and $0$ at $b = 300$ (caps $60 + 80 + 120 + 35 = 295$). Why does $\lambda$ collapse to zero at $b = 300$?
  1. Because the responses become convex
  2. Because the solver fails
  3. All channels are at their caps
  4. Because the budget is spent on one channel
Explanation. With $b \ge 295$ every channel is at its cap, so an extra euro cannot be used: the budget constraint is slack and its multiplier is zero.
nlpm-f-220 · level ipotesi · notes
Advertising budget model: maximize $\sum_ir_i(x_i)$ (concave) with $\sum_ix_i \le b$ (multiplier $\lambda$) and $0 \le x_i \le u_i$. The rule $r_i'(\tilde x_i) = \lambda$ holds for channels strictly inside $(0, u_i)$. What happens for a channel at its cap $u_i$?
  1. $r_i'(u_i) \ge \lambda$
  2. $r_i'(u_i) = \lambda$ in any case
  3. $r_i'(u_i) \le \lambda$
  4. $r_i'(u_i) = 0$ at the cap
Explanation. Stationarity reads $r_i'(\tilde x_i) = \lambda + \mu_i$ with $\mu_i \ge 0$ the multiplier of $x_i \le u_i$: a capped channel would deserve more money but cannot take it. Dropping the hypothesis «interior» changes the condition.

9. Continuous location of a service (26)

nlpm-f-043 · level facile · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Which objective has a closed-form optimum?
  1. Weber: weighted sum of the distances
  2. Minimax: maximum distance
  3. Weighted sum of the squared distances
  4. None of the three objectives
Explanation. Setting the gradient of $\sum_i w_i[(x - a_i)^2 + (y - b_i)^2]$ to zero gives the weighted centroid $\tilde x = \sum_i w_ia_i/\sum_i w_i$ (and similarly for $y$).
nlpm-f-044 · level facile · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Which property characterizes the optimum of the minimax model (minimize the distance of the farthest district)?
  1. It is the centre of the smallest circle containing all the districts
  2. It is the weighted centroid of the districts
  3. It is the weighted median of the districts, coordinate by coordinate
  4. It always coincides with the Weber point
Explanation. It depends only on the extreme districts and ignores the weights: this is why the minimax protects the outskirts, regardless of their population.
nlpm-f-045 · level facile · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Weber model: minimize $\sum_i w_i\,d_i$, with $d_i$ the Euclidean distance from district $i$. Which condition holds at the optimum, when it is not a district point?
  1. The facility is equidistant from all the districts
  2. The gradient of the squared distances vanishes
  3. The maximum distance $\max_i d_i$ is minimal
  4. $\sum_i w_i\,\mathbf u_i = \mathbf 0$, with $\mathbf u_i$ the unit vector towards district $i$
Explanation. The weighted unit “pulls” balance; the function is not differentiable at the district points and has no closed form.
nlpm-f-046 · level facile · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). How are the Euclidean distances written in the Gurobi model of the case study?
  1. With a piecewise-linear approximation of the square root
  2. With a variable $d_i$ and the convex conic constraint $(x - a_i)^2 + (y - b_i)^2 \le d_i^2$
  3. With `NonConvex = 2` and the squared distances in the objective
  4. With binary variables that select the nearest district
Explanation. Weber minimizes $\sum_i w_id_i$, the minimax a variable $z$ with $d_i \le z$: purely conic (convex) structures need no special parameter in Gurobi.
nlpm-f-047 · level facile · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). The efficiency-equity frontier plots the weighted mean distance against the maximum distance. In the case study it is almost flat. What does it mean?
  1. Efficiency and equity are in strong conflict
  2. The model with both objectives is infeasible
  3. Lowering the maximum distance costs very little mean distance
  4. The Weber and minimax points coincide
Explanation. Guaranteeing $0.63$ km less to the farthest district costs only $47$ metres of mean distance: a strong argument in a public discussion.
nlpm-f-048 · level facile · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). How is the efficiency-equity frontier (mean distance versus maximum distance) built with the $\varepsilon$-constraint method?
  1. Minimize the mean distance with a cap $D$ on every distance, varying $D$
  2. Minimize the sum of the mean distance and of the maximum distance
  3. Solve Weber and minimax separately and average the two locations
  4. Vary the weights $w_i$ of the districts and re-solve Weber
Explanation. Each value of $D$ gives one point of the frontier; the extremes are the minimax solution (smallest feasible $D$) and the Weber point (large $D$).
nlpm-f-049 · level teorema · notes
Location on a line: customers at positions $a_i$ with weights $w_i \ge 0$. Which statement about $\min_x \sum_i w_i|x - a_i|$ (Weber in one dimension) is correct?
  1. The optimum is the weighted mean $\sum_i w_ia_i/\sum_i w_i$
  2. An optimum is the weighted median: at least half of the weight on each side
  3. The optimum is the midpoint of the two extreme customers
  4. The optimum is the unweighted median of the positions
Explanation. Moving away from the weighted median increases the cost on the heavier side faster than it decreases on the other. The weighted mean solves the squared distances, the midpoint the minimax.
nlpm-f-050 · level ipotesi · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Which facts make the Weber objective $\sum_i w_i\sqrt{(x - a_i)^2 + (y - b_i)^2}$ convex in $(x, y)$?
  1. It is differentiable everywhere in the plane
  2. The squared distance is convex and the square root is increasing
  3. The districts are finitely many and numbered
  4. Norm of an affine map is convex, $w_i \ge 0$, sums of convex functions are convex
Explanation. Each term is the Euclidean norm of an affine function of $(x, y)$; the weights are non-negative. Differentiability fails at the district points, but convexity holds. Note: increasing $\circ$ convex is convex only if the outer function is also convex, and the square root is concave.
nlpm-f-097 · level facile · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). The facility must lie within distance $r$ of an electrical substation at $(a_0, b_0)$. How is this constraint written, and is it convex?
  1. $|x - a_0| + |y - b_0| \ge r$, non-convex
  2. $(x - a_0)^2 + (y - b_0)^2 \le r^2$, convex
  3. $(x - a_0)^2 + (y - b_0)^2 \ge r^2$, convex
  4. $x \le a_0 + r$ only, linear
Explanation. A disc is a convex set; adding it to any convex location objective keeps the problem convex. The $\ge$ version would describe the outside of a disc, which is not convex.
nlpm-f-098 · level facile · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). In the case study the facility must be within 2 km of a substation; the constrained Weber optimum lies on the boundary of that disc and costs only $+0.2\%$. What is the managerial lesson?
  1. The constraint is inactive and could be removed
  2. The Weber model is not suited to constrained problems
  3. Equity and efficiency are in strong conflict
  4. A feared constraint may turn out almost free: measure it
Explanation. The constraint is active (optimum on the boundary) but its cost is tiny: discovering it is a result as important as the optimum itself.
nlpm-f-099 · level facile · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). In the case study (12 districts) the Weber point $(4.886, 5.310)$ almost coincides with the weighted centroid $(4.897, 5.397)$, while the minimax point moves half a kilometre away. Why are Weber and centroid so close?
  1. Because the weights are fairly evenly distributed around the centre
  2. Because Weber and centroid always coincide
  3. Because the minimax ignores the weights
  4. Because the substation constraint is active
Explanation. Weber (sum of distances) and centroid (sum of squared distances) differ when a few heavy or far districts pull differently; with balanced weights they are close, while the minimax follows the extreme districts.
nlpm-f-100 · level facile · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). The efficiency-equity frontier plots the minimum mean distance against a cap $D$ on the maximum distance. What would a **steep** frontier mean?
  1. That equity is almost free
  2. That the model is badly scaled
  3. That Weber and minimax coincide
  4. A real conflict: each km less for the farthest costs much mean distance
Explanation. In the case study the frontier is almost flat (equity almost free); a steep one would signal that protecting the outskirts has a high efficiency cost.
nlpm-f-193 · level facile · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). The chapter compares three meanings of «close to the demand». Which objective expresses **equity** toward the worst-off user?
  1. The weighted mean distance (Weber)
  2. The weighted squared distance
  3. The maximum distance (minimax)
  4. The number of districts served
Explanation. Mean distance measures efficiency, the squared distance leads to the barycenter, and the maximum distance protects the farthest district.
nlpm-f-194 · level facile · notes
Why do the course notes stress that location decisions deserve a careful model?
  1. They are costly to correct
  2. They can be changed every week
  3. They never involve trade-offs
  4. They always have closed-form answers
Explanation. A hub in the wrong place stays there for years; the continuous version of the problem makes the efficiency–equity conflict visible.
nlpm-f-195 · level facile · notes
Which facilities does the course cite as examples for the continuous location model?
  1. Warehouses chosen from a fixed list
  2. Machines on a production line
  3. Bank branches to close down
  4. A charging station or a micro-hub
Explanation. In the continuous version the coordinates are free on the plane: a charging station, a logistic micro-hub or a health post placed «close» to the demand.
nlpm-f-196 · level facile · notes
How is the efficiency–equity frontier of the location chapter built?
  1. By averaging Weber and minimax points
  2. With a cap on the max distance
  3. By solving the quadratic model only
  4. By enumerating all the districts
Explanation. Minimize the mean distance subject to a cap $D$ on the maximum distance, and vary $D$ between the minimax and the Weber values.
nlpm-f-197 · level facile · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Three customers on a road at km $0$, $4$ and $10$, weights $1$, $1$ and $3$. What is the barycenter (weighted squared distance)?
  1. $x = 4.67$, the plain mean
  2. $x = 6.8$
  3. $x = 10$
  4. $x = 5$
Explanation. $(1\cdot 0 + 1\cdot 4 + 3\cdot 10)/5 = 34/5 = 6.8$: unlike the median it depends on how far the points are, not only on which side.
nlpm-f-198 · level facile · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Three customers on a road at km $0$, $4$ and $10$, weights $1$, $1$ and $3$. Where is the minimax location (smallest maximum distance)?
  1. $x = 10$
  2. $x = 6.8$
  3. $x = 4$
  4. $x = 5$
Explanation. The midpoint of the extreme customers, $(0 + 10)/2 = 5$, whatever the weights: three reasonable objectives give $10$, $6.8$ and $5$.
nlpm-f-199 · level facile · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Three customers on a road at km $0$, $4$, $10$, weights $1$, $1$, $3$: Weber (sum of weighted distances) gives $x = 10$. Why does moving left from $10$ by $\delta$ make things worse?
  1. The first two save $2\delta$, the third pays $3\delta$
  2. All three customers pay more
  3. The cost function is constant there
  4. The road ends at km 10
Explanation. Moving left lowers the distances of the two customers on the left (weight 2 in all) and raises that of the customer with weight 3: net $+\delta$. The optimum is the weighted median.
nlpm-f-200 · level facile · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Case study: in the gurobipy code each distance is a variable $d_k$ with `dx[k]**2 + dy[k]**2 <= d[k]*d[k]`. What kind of constraint is it?
  1. A linear constraint in $d_k$
  2. A nonconvex bilinear constraint
  3. A convex conic constraint
  4. A functional constraint on a logarithm
Explanation. $\sqrt{d_x^2 + d_y^2} \le d_k$ is a second-order cone: convex, handled by Gurobi without `NonConvex`; minimizing $\sum_kw_kd_k$ pushes each $d_k$ down to the true distance.
nlpm-f-201 · level facile · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Case study: twelve districts, and the station must stay within $r = 2$ km of the electrical substation at $(7, 6)$. How is this written?
  1. $(x - 7)^2 + (y - 6)^2 \le 4$
  2. $|x - 7| + |y - 6| = 2$
  3. $x \le 7$ and $y \le 6$, a box
  4. As a penalty in the objective
Explanation. A disc around the substation is a convex region, so the constrained Weber problem stays convex; the constraint is a quadratic inequality.
nlpm-f-202 · level facile · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Case study: how does the minimax model use the distance variables $d_k$?
  1. It minimizes $\sum_kw_kd_k$
  2. It minimizes $\sum_kd_k^2$
  3. It fixes every $d_k$ to the same value
  4. It minimizes $z$, with $d_k \le z$
Explanation. Same conic distances as Weber, but the objective is an auxiliary $z$ bounded below by every distance: the largest distance is minimized.
nlpm-f-203 · level facile · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Case results: Weber $(4.886, 5.310)$ with mean $3.344$ km and max $6.314$ km; minimax $(5.496, 5.029)$ with mean $3.391$ km and max $5.680$ km. How is the move of the minimax point read?
  1. An error: the two should coincide
  2. It moves toward the peripheral districts
  3. It moves toward the most populated district
  4. It moves to the substation
Explanation. The minimax point shifts over half a km south-east to protect the outlying districts, cutting the maximum distance by $0.63$ km at a small cost in mean distance.
nlpm-f-204 · level facile · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Case results: Weber constrained to stay within 2 km of the substation lies on the boundary of the disc and costs $+0.2\%$ of total distance. What is the managerial lesson?
  1. The constraint should be removed
  2. The substation is badly placed
  3. The constrained model is infeasible
  4. A feared constraint may be cheap
Explanation. The constraint is active (optimum on the boundary) but costs very little: discovering that is a result as important as the optimum itself.
nlpm-f-205 · level facile · notes
Continuous location of one facility at $(x, y)$ serving districts $i$ at $(a_i, b_i)$ with weights $w_i$ (population). Efficiency–equity frontier of the case: cap $D = 5.680$ km gives mean $3.391$, $D = 5.997$ gives $3.351$, $D = 6.314$ gives $3.344$. What does a frontier this flat mean?
  1. Equity costs very little in efficiency
  2. Efficiency and equity are in strong conflict
  3. The minimax solution is infeasible
  4. The mean distance is independent of the cap
Explanation. Guaranteeing $0.63$ km less to the farthest district costs only $47$ m of mean distance: the fair solution is «almost free»; a steep frontier would signal a real conflict.
nlpm-f-221 · level teorema · notes
Continuous location with the weighted squared distance $\sum_iw_i[(x - a_i)^2 + (y - b_i)^2]$ ($w_i > 0$ weights, $(a_i, b_i)$ district coordinates). Which statement is correct?
  1. The optimum is the weighted median
  2. The optimum has no closed form
  3. The weighted barycenter
  4. The optimum is the center of the smallest enclosing circle
Explanation. The objective is a strictly convex quadratic; setting its gradient to zero, $\sum_iw_i(x - a_i) = 0$, gives the barycenter (and similarly for $y$): the only one of the three objectives with a closed form.

10. Electric vehicle charging with a smooth profile (18)

nlpm-f-249 · level facile · notes
In minimum-cost overnight charging the total draw rises to 103.4 kW and changes by up to 54.9 kW from one hour to the next. What does the QP variant add?
  1. A constraint on the maximum peak of the draw
  2. A quadratic penalty on the hourly jumps of the total draw
  3. Binary variables switching the chargers on
  4. A fixed cost for every plugged-in vehicle
Explanation. The QP variant adds $\gamma \sum_t (z_t - z_{t-1})^2$ to the objective: it penalizes every change of the draw, not only the peak.
nlpm-f-250 · level facile · notes
EV charging with a smooth profile: what distinguishes it from the peak shaving of the linear model?
  1. Peak shaving is a QP, while the smooth profile is an LP
  2. The smooth profile ignores the base load altogether
  3. Peak shaving penalizes every ramp, the QP only the maximum
  4. Peak shaving only looks at the maximum, the QP at every ramp
Explanation. Linear peak shaving minimizes the maximum of the draw; the quadratic term softens all the ramps, including those far from the peak.
nlpm-f-251 · level facile · notes
In the charging model with a smooth profile, which datum is added to those of the linear model?
  1. The weight $\gamma$ of the jumps of the total draw
  2. The hourly price of energy in every hour of the night
  3. The maximum power of the charger of each vehicle
  4. The charging efficiency $\eta$ of the vehicles
Explanation. Prices, powers, availability, energy, base load, meter and efficiency are those of the linear case; only $\gamma$ (€ per kW$^2$) is added.
nlpm-f-252 · level facile · notes
In the charging QP the total draw is $z_t = b_t + \sum_v x_{vt}$. What is $z_t$ in the model?
  1. A binary variable telling whether the hour is a peak hour
  2. An observed datum, exactly like the base load
  3. A linear expression of the variables, not a variable
  4. The multiplier of the grid constraint of hour $t$
Explanation. $z_t$ is written as a linear combination of the $x_{vt}$ plus the constant $b_t$; its squared jumps enter the objective.
nlpm-f-253 · level teorema · notes
The charging QP penalizes the jumps of the *total* draw $z_t = b_t + \sum_v x_{vt}$, base load included. What consequence does this have on the charging profile?
  1. Charging ignores the ramps of the building and follows the prices
  2. Charging can also soften the ramps of the base load
  3. The base load becomes a decision variable
  4. The problem becomes non-convex and needs `NonConvex = 2`
Explanation. Since $b_t$ enters the jumps, shifting charging to the hours in which the base load rises or falls reduces the penalty: charging offsets the ramps of the building.
nlpm-f-254 · level ipotesi · notes
The charging QP has objective $\sum_{v,t} \pi_t x_{vt} + \gamma \sum_t (z_t - z_{t-1})^2$ and linear constraints. Which assumption is needed for it to be a convex QP?
  1. That the prices $\pi_t$ are all positive
  2. That the meter $k$ exceeds the base load
  3. That the availability windows are contiguous
  4. That the weight $\gamma$ is non-negative
Explanation. With $\gamma \ge 0$ a convex function (a sum of squares of linear functions) is added to a linear objective; prices and windows do not affect convexity.
nlpm-f-255 · level facile · notes
One vehicle, two hours: $e = 10$ kWh, $\eta = 1$, prices $0.10$ and $0.20$ €/kWh, $\bar p = 12$ kW, zero base load, $\gamma = 0.01$. With $x_1 = 5 + d$ the objective is $1.5 - 0.1 d + 4\gamma d^2$. What is $x_1$ at the optimum?
  1. $6.25$
  2. $10.00$
  3. $5.00$
  4. $7.50$
Explanation. The minimum is at $d = 0.1/(8\gamma) = 1/(80\gamma) = 1.25$, hence $x_1 = 6.25$ and $x_2 = 3.75$.
nlpm-f-256 · level teorema · notes
Same example (prices $0.10$ and $0.20$, active energy constraint, both hours used). Stationarity gives $0.10 - 2\gamma(x_2 - x_1) = \lambda = 0.20 + 2\gamma(x_2 - x_1)$. What is the multiplier $\lambda$ of the requirement?
  1. $0.10$, the price of the cheap hour, for every $\gamma$
  2. $0.20$, the price of the expensive hour, for every $\gamma$
  3. $0.15$, the average price, for every $\gamma \ge 1/400$
  4. $2\gamma$, twice the weight of the penalty
Explanation. Adding the two equalities gives $2\lambda = 0.30$: $\lambda = 0.15$, independent of $\gamma$ as long as both hours are used ($\gamma \ge 1/400$).
nlpm-f-257 · level ipotesi · notes
In the two-hour example the interior optimum is $x_1 = 5 + 1/(80\gamma)$. What happens for $\gamma < 1/400$?
  1. The optimum still stays $x_1 = 5 + 1/(80\gamma)$
  2. All in the cheap hour: $x_1 = 10$, $x_2 = 0$
  3. Everything is charged in the expensive hour, the second
  4. The problem becomes infeasible because of the energy constraint
Explanation. For $\gamma < 1/400$ the formula would give $x_1 > 10$ and hence $x_2 < 0$: the bound $x_2 \ge 0$ becomes active and everything is charged in hour 1, as in the linear model.
nlpm-f-258 · level facile · notes
In the charging script with a smooth profile, how is the total draw `z[t]` built in gurobipy?
  1. With a binary variable `m.addVar(vtype=GRB.BINARY)`
  2. With a functional constraint `addGenConstrPow`
  3. As a linear expression: sum of the `x[v, t]` plus `base[t]`
  4. With a quadratic constraint `addQConstr`
Explanation. `z[t]` is a linear expression (`gp.quicksum(x[v, t] for v in veicoli) + base[t]`); its squared jumps enter the objective.
nlpm-f-259 · level facile · notes
The charging script with a smooth profile writes the objective `spesa + gamma * salti`. What kind of model does Gurobi solve?
  1. An LP, because the constraints are linear
  2. A convex QP
  3. A non-convex NLP with `NonConvex = 2`
  4. A MIQP with integer variables
Explanation. The spend is linear, `salti` is a sum of squares of linear expressions, the constraints are linear: a convex QP, solved with no special parameter.
nlpm-f-260 · level facile · notes
To verify the requirement multiplier of V1 in the charging QP, what is done?
  1. One reads the `RC` attribute of the variables `x['V1', t]` at the optimum
  2. One removes the grid constraint and re-optimizes the model
  3. One multiplies the price of the marginal hour by the efficiency $\eta$
  4. One increases $e_1$ by a small $\varepsilon$ and takes the difference quotient
Explanation. With $\varepsilon = 0.01$ kWh and $\gamma = 0.01$ the difference quotient is $0.0916$, equal to the multiplier read in `Pi`.
nlpm-f-261 · level facile · notes
Fleet charging with $\gamma = 0.01$: spend €24.67 against €20.36 of the linear model, peak 68.0 kW against 103.4 kW. What is observed about the peak?
  1. It reaches the lowest possible value, that of peak shaving
  2. It exceeds the meter limit in the night hours
  3. It stays equal to that of the linear model
  4. It falls below the base load of the building
Explanation. 68 kW is the lowest possible peak found by linear peak shaving: the QP reaches it by softening all the ramps, with €4.31 more per night.
nlpm-f-262 · level facile · notes
The linear compromise cost $+\,\rho\,$peak of LP Modelling reaches the 68 kW peak spending less than the QP with $\gamma = 0.01$. Why does the QP spend more?
  1. Because the QP uses a smaller meter than the linear model
  2. Because the QP cannot use the cheapest night hours
  3. Because the QP softens every ramp, not only the maximum
  4. Because the QP has a worse charging efficiency
Explanation. The linear compromise only looks at the maximum of the draw; the QP penalizes every hourly jump and moves charging also where it does not reduce the peak.
nlpm-f-263 · level facile · notes
Fleet charging: with $\gamma = 0.001$ the largest hourly jump of the draw goes from 54.9 kW (linear model) to which value?
  1. $54.9$ kW
  2. $15.4$ kW
  3. $0$ kW
  4. $103.4$ kW
Explanation. With $\gamma = 0.001$ the largest jump is 15.4 kW, the spend €21.76 and the peak 77.3 kW.
nlpm-f-264 · level teorema · notes
In the linear model the requirement multipliers of the six vehicles are 0.0842 or 0.0947 €/kWh; in the QP with $\gamma = 0.01$ they are all 0.0916. Why do they coincide in the QP?
  1. Because in the QP the vehicles have the same availability window
  2. Because the QP ignores the charging efficiency
  3. Because in the QP the energy constraint is not active
  4. Because the penalty links the vehicles through the total draw
Explanation. The quadratic term depends only on the sum of the powers: one more kWh for any vehicle is obtained by redistributing the charging of all, at the same marginal cost.
nlpm-f-265 · level facile · notes
Spend-jitter frontier of charging: with $\gamma = 0.0005$ the spend rises by €1.15 and the sum of the squared jumps falls from 7,268 to 1,563. What does this stretch of the frontier say?
  1. That the first smoothing steps cost little
  2. That smoothness costs more and more at every equal step
  3. That the QP does not improve the profile
  4. That the spend falls as $\gamma$ grows
Explanation. The frontier is steep at first: with little more than one euro per night the sum of the squared jumps falls by almost five times.
nlpm-f-266 · level facile · notes
Charging with $\gamma = 0.5$: the spend reaches €43.80 per night, more than twice the linear model. Why does smoothing cost so much beyond a certain threshold?
  1. Because the meter becomes too small for the fleet
  2. Because with large $\gamma$ the problem becomes non-convex
  3. Because to follow the ramps of the building it charges in costly hours
  4. Because the vehicles charge more energy than needed
Explanation. The morning and evening ramps come from the building; to offset them charging must move to hours with high prices.

11. Service capacity and waiting times (22)

nlpm-f-051 · level facile · notes
M/M/1 capacity model: arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. What is the optimal utilization $\rho = \lambda/\tilde\mu$?
  1. $100\%$, because unused capacity is waste
  2. Below $100\%$: spare capacity keeps the queue short
  3. Exactly $50\%$, whatever the data
  4. Undefined, because the cost diverges
Explanation. In the worked example $\lambda = 8$, $c = 2$, $h = 4$: $\tilde\mu = 12$, $\rho = 66.7\%$; with $\mu = 9$ ($\rho = 89\%$) the cost rises from $32$ to $50$ €/h.
nlpm-f-052 · level facile · notes
M/M/1 capacity model: arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. The optimum has safety margin $\tilde\mu - \lambda = \sqrt{h\lambda/c}$. How does it grow with the demand $\lambda$?
  1. Like $\sqrt{\lambda}$: large systems need proportionally less buffer
  2. Linearly in $\lambda$: the buffer is a fixed share of demand
  3. Like $\lambda^2$: queues explode with demand
  4. It does not depend on $\lambda$
Explanation. Capacity = demand + safety margin, and the margin grows less than proportionally to demand: economies of scale in the buffer (pooling).
nlpm-f-053 · level facile · notes
M/M/1 queue (Poisson arrivals at rate $\lambda$, exponential service at rate $\mu > \lambda$, one server). Which formulas give the mean time in the system $w$ and the mean number of customers in the system $l$?
  1. $w = 1/\mu$, $l = \lambda/\mu$
  2. $w = \lambda/(\mu - \lambda)$, $l = 1/(\mu - \lambda)$
  3. $w = 1/(\mu - \lambda)$, $l = \lambda/(\mu - \lambda)$
  4. $w = \mu/\lambda$, $l = \mu - \lambda$
Explanation. $w = 1/(\mu - \lambda)$ and, by Little's law, $l = \lambda\,w$; $1/\mu$ is only the mean service time.
nlpm-f-054 · level facile · notes
M/M/1 capacity model: arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. Marketing promises a mean time in the system $w = 1/(\mu - \lambda)$ of at most $w_{\max}$. Which constraint on the capacity follows?
  1. $\mu \le \lambda + 1/w_{\max}$
  2. $\mu \ge \lambda\,w_{\max}$
  3. $\mu \ge 1/w_{\max}$
  4. $\mu \ge \lambda + 1/w_{\max}$
Explanation. From $1/(\mu - \lambda) \le w_{\max}$; the constraint matters only when it is tighter than the economic optimum $\tilde\mu$.
nlpm-f-055 · level facile · notes
M/M/1 capacity model: arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. In the case study $\lambda$ is uncertain in $[36, 48]$ and the optimum computed for the nominal demand is $\tilde\mu = 46.58$. Why is sizing the system on it dangerous?
  1. Because $C(\mu)$ is not convex for uncertain $\lambda$
  2. Because with $\lambda = 48 > \tilde\mu$ the queue is unstable
  3. Because $\tilde\mu$ is larger than any likely demand
  4. Because the formula of $\tilde\mu$ holds only for $\lambda < 36$
Explanation. With $\mu \le \lambda$ the queue grows without bound and the cost diverges. Minimizing the worst-case cost gives $\mu = 52.90$: an insurance premium of about $13\%$.
nlpm-f-056 · level media · notes
M/M/1 capacity model: arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. When the promise $w \le w_{\max}$ is active, $\mu = \lambda + 1/w_{\max}$ and the cost is $C(w_{\max}) = c\lambda + c/w_{\max} + h\lambda\,w_{\max}$. With $c = 3$, $h = 1.5$, $\lambda = 42$ and $w_{\max} = 0.1$ h, what is $dC/dw_{\max}$?
  1. $-237$ €/h per hour of promise
  2. $+63$ €/h per hour of promise
  3. $-300$ €/h per hour of promise
  4. $-30$ €/h per hour of promise
Explanation. $dC/dw_{\max} = -c/w_{\max}^2 + h\lambda = -3/0.01 + 63 = -237$: relaxing the promise saves money, the number to give marketing before signing the SLA.
nlpm-f-057 · level facile · notes
M/M/1 queue with utilization $\rho = \lambda/\mu$ and mean time in the system $w = 1/(\mu - \lambda)$. The “utilization wall” plot shows $w$ as $\rho$ grows, for a fixed $\mu$. What does it show?
  1. The total cost decreases as $\rho$ grows
  2. The waiting time does not depend on $\rho$
  3. From $\rho = 90\%$ to $\rho = 99\%$ the time $w$ is multiplied by ten
  4. The optimal utilization is $99\%$
Explanation. $w = 1/(\mu(1 - \rho))$ explodes like a hyperbola as $\rho \to 1$: saturating resources and giving good service are in mathematical conflict.
nlpm-f-058 · level teorema · notes
M/M/1 capacity model: arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. Which statement about $C(\mu)$ on $\mu > \lambda$ is correct?
  1. It is concave, so its stationary point is a maximum
  2. It is linear in $\mu$, so the optimum is at a bound
  3. It has no minimum on $(\lambda, +\infty)$
  4. It is convex there, so $\tilde\mu = \lambda + \sqrt{h\lambda/c}$ is the global minimum
Explanation. $C''(\mu) = 2h\lambda/(\mu - \lambda)^3 > 0$; the cost tends to $+\infty$ both as $\mu \to \lambda^+$ and as $\mu \to +\infty$.
nlpm-f-059 · level ipotesi · notes
M/M/1 capacity model: arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. To claim that $\tilde\mu = \lambda + \sqrt{h\lambda/c}$ is the optimal capacity, which facts are used?
  1. Strong LP duality
  2. $C'(\tilde\mu) = 0$, convexity of $C$ on $(\lambda, +\infty)$ and $\tilde\mu > \lambda$
  3. That the arrival rate $\lambda$ is an integer
  4. That the utilization at the optimum is $100\%$
Explanation. The derivative vanishes at $\tilde\mu$, which satisfies the stability requirement; convexity turns the stationary point into the global minimum.
nlpm-f-101 · level facile · notes
M/M/1 capacity model: arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. Case study: $\lambda = 42$ per hour, $c = 3$, $h = 1.5$: $\tilde\mu = 46.58$, utilization $90.2\%$, mean time in the system $13.1$ minutes. Marketing proposes to promise a mean time of at most $15$ minutes. What does this promise cost?
  1. Nothing: $13.1 < 15$, the promise is not binding
  2. It forces $\mu \ge \lambda + 15 = 57$ per hour
  3. It forces $\mu = \lambda + 4 = 46$, saving money
  4. It is infeasible at this demand
Explanation. The constraint $\mu \ge \lambda + 1/w_{\max}$ is already satisfied by the economic optimum: a promise looser than $13.1$ minutes is free.
nlpm-f-102 · level facile · notes
M/M/1 capacity model: arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. In the Gurobi model of the case study the mean time $w$ is a variable linked to $\mu$ by the constraint $w(\mu - \lambda) = 1$. Which parameter does this require?
  1. `FuncNonlinear = 1`, for the function $1/x$
  2. `QCPDual = 1`, to get the multipliers
  3. No parameter: the constraint is linear
  4. `NonConvex = 2`, because $w\mu$ is a bilinear term
Explanation. The product $w\mu$ of two variables is bilinear (non-convex as an equality); Gurobi solves it to global optimality with `NonConvex = 2` and matches the analytical $\tilde\mu$.
nlpm-f-103 · level facile · notes
M/M/1 capacity model: arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\,\mu + h\lambda/(\mu - \lambda)$. In the case study, tightening the promise on the mean time in the system from 12 to 9 minutes costs $1.85$ €/h, while going from 3 to 2 minutes costs $28.95$ €/h. What does this show?
  1. That short promises are cheaper to keep
  2. That the cost of the promise is linear in $w_{\max}$
  3. That the price of the promise grows explosively as $w_{\max}$ shrinks
  4. That the promise is never binding
Explanation. With the promise active, $C(w_{\max}) = c\lambda + c/w_{\max} + h\lambda w_{\max}$: the term $c/w_{\max}$ makes the marginal cost explode for short promises.
nlpm-f-206 · level facile · notes
What is the central, counter-intuitive message of the course chapter on service capacity and waiting times?
  1. Capacity should always be minimized
  2. Waiting times do not depend on capacity
  3. The optimal utilization is not 100%
  4. Queues disappear at 100% utilization
Explanation. Capacity costs money but so does waiting; the optimum leaves part of the capacity idle, which is what keeps queues short.
nlpm-f-207 · level facile · notes
Which services share the capacity–waiting dilemma of the queues chapter?
  1. Call centers, ERs, help desks, cloud APIs
  2. Only the counters of bank branches
  3. Only manufacturing assembly lines
  4. Services with deterministic arrivals
Explanation. Any service with random arrivals: capacity costs, waiting costs too; queueing theory gives the exact relation between the two.
nlpm-f-208 · level facile · notes
In the queues chapter, what is new compared with classical queueing theory?
  1. New formulas for the M/M/1 queue
  2. Simulation instead of formulas
  3. Several servers instead of one
  4. Capacity $\mu$ becomes a variable
Explanation. The M/M/1 formulas are standard; the chapter treats the service rate as a decision and chooses it by minimizing capacity cost plus waiting cost.
nlpm-f-209 · level facile · notes
What does the notation M/M/1 mean in the queues chapter of the course?
  1. Mean arrivals, mean service, one hour of work
  2. Poisson arrivals, exponential service, 1 server
  3. Multiple queues, multiple servers, one line
  4. A Markov chain with a single state only
Explanation. Markovian arrivals (Poisson process), Markovian (exponential) service times and a single server: the simplest queue, with closed-form formulas.
nlpm-f-210 · level facile · notes
M/M/1 capacity model (Poisson arrivals, exponential service, one server): arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\mu + h\lambda/(\mu - \lambda)$, whose optimum is $\tilde\mu = \lambda + \sqrt{h\lambda/c}$. Desk with $\lambda = 8$ customers/h, $c = 2$ €, $h = 4$ €/h. What are $\tilde\mu$ and the optimal cost?
  1. $\tilde\mu = 10$, cost $36$ €/h
  2. $\tilde\mu = 12$, cost $32$ €/h
  3. $\tilde\mu = 16$, cost $36$ €/h
  4. $\tilde\mu = 9$, cost $50$ €/h
Explanation. $\tilde\mu = 8 + \sqrt{4\cdot 8/2} = 12$; $C = 2\cdot 12 + 4\cdot 8/4 = 32$ €/h, with utilization $8/12 = 66.7\%$.
nlpm-f-211 · level facile · notes
M/M/1 capacity model (Poisson arrivals, exponential service, one server): arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\mu + h\lambda/(\mu - \lambda)$, whose optimum is $\tilde\mu = \lambda + \sqrt{h\lambda/c}$. Desk with $\lambda = 8$/h, $c = 2$ €, $h = 4$ €/h, optimum $\tilde\mu = 12$. What is the mean time in the system $w = 1/(\mu - \lambda)$?
  1. $7.5$ minutes
  2. $4$ minutes
  3. $12$ minutes
  4. $15$ minutes
Explanation. $w = 1/(12 - 8) = 0.25$ h $= 15$ minutes; with $\mu = 9$ it would be a full hour.
nlpm-f-212 · level facile · notes
M/M/1 capacity model (Poisson arrivals, exponential service, one server): arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\mu + h\lambda/(\mu - \lambda)$, whose optimum is $\tilde\mu = \lambda + \sqrt{h\lambda/c}$. Desk with $\lambda = 8$/h, $c = 2$ €, $h = 4$ €/h: the optimum $\tilde\mu = 12$ costs $32$ €/h. What does the «more efficient» $\mu = 9$ (utilization $89\%$) cost?
  1. $50$ €/h: far worse
  2. $18$ €/h: cheaper
  3. $32$ €/h: the same
  4. $26$ €/h: slightly cheaper
Explanation. $C(9) = 2\cdot 9 + 4\cdot 8/1 = 18 + 32 = 50$ €/h: the apparent waste of the optimum (a third of the capacity idle) is what keeps the queue short.
nlpm-f-213 · level facile · notes
M/M/1 capacity model (Poisson arrivals, exponential service, one server): arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\mu + h\lambda/(\mu - \lambda)$, whose optimum is $\tilde\mu = \lambda + \sqrt{h\lambda/c}$. Desk with $\lambda = 8$/h, $c = 2$ €, $h = 4$ €/h. What is the utilization $\rho = \lambda/\tilde\mu$ at the optimum?
  1. $100\%$
  2. $89\%$
  3. $66.7\%$
  4. $50\%$
Explanation. $\tilde\mu = 12$, so $\rho = 8/12 = 66.7\%$: one third of the capacity stays idle on average, by design.
nlpm-f-214 · level facile · notes
M/M/1 capacity model (Poisson arrivals, exponential service, one server): arrival rate $\lambda$, capacity (service rate) $\mu > \lambda$, cost $c$ per unit of capacity, value $h$ of one hour of a customer in the system; minimize $C(\mu) = c\mu + h\lambda/(\mu - \lambda)$, whose optimum is $\tilde\mu = \lambda + \sqrt{h\lambda/c}$. Case study ($\lambda = 42$/h, $c = 3$, $h = 1.5$): the «utilization wall» plots $w$ against $\rho$. Between $\rho = 90\%$ and $\rho = 99\%$ the waiting time is multiplied by about:
  1. $1.1$
  2. $10$
  3. $2$
  4. $100$
Explanation. $w = 1/(\mu - \lambda) = \rho/(\lambda(1 - \rho))$: $1 - \rho$ goes from $0.10$ to $0.01$, so $w$ grows about tenfold. Saturating resources and serving well conflict mathematically.
nlpm-f-222 · level ipotesi · notes
M/M/1 capacity model $\min\ c\mu + h\lambda/(\mu - \lambda)$, $\mu > \lambda$, with the promise $1/(\mu - \lambda) \le w_{\max}$. In the case study the economic optimum has $w = 13.1$ minutes. For which promises is $\tilde\mu = \lambda + 1/w_{\max}$ the optimum?
  1. For every $w_{\max}$
  2. Only for $w_{\max} > 13.1$ minutes
  3. Only when the promise binds
  4. Only when $c = h$ in the model
Explanation. If $w_{\max} \ge 13.1$ min the economic optimum already keeps the promise and $\tilde\mu = \lambda + \sqrt{h\lambda/c}$ is unchanged; the formula $\lambda + 1/w_{\max}$ needs the hypothesis that the constraint is active.

Part: Optimization and machine learning (60)

12. Support Vector Machine (37)

nlpm-f-060 · level facile · notes
SVM: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. Hard margin: $\min\tfrac12\sum_j w_j^2$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1$. Why does this maximize the margin?
  1. The distance between the hyperplanes $\mathbf w'\mathbf x + b = \pm 1$ is $2/\|\mathbf w\|$
  2. The distance between the hyperplanes $\mathbf w'\mathbf x + b = \pm 1$ is $\|\mathbf w\|$
  3. Because the intercept $b$ is a free variable
  4. Because the labels are $\pm 1$ and cancel out
Explanation. A smaller $\|\mathbf w\|$ means a wider margin; the constraints keep each point on its side, at least one unit away in the scale of $\mathbf w$.
nlpm-f-061 · level facile · notes
SVM: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. What does $\tilde\xi_i > 1$ mean for observation $i$?
  1. It lies exactly on the margin
  2. It is a support vector with $\alpha_i = 0$
  3. It is on the wrong side of the hyperplane
  4. It is correctly classified beyond the margin
Explanation. $0 < \xi_i \le 1$ is a margin violation on the correct side; $\xi_i > 1$ puts the point on the wrong side of the hyperplane (misclassified).
nlpm-f-062 · level facile · notes
SVM: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. What is the effect of a small $C$?
  1. A narrow margin and zero training errors
  2. A wide margin, accepting many points inside it
  3. An infeasible model
  4. No effect on the width of the margin
Explanation. $C$ is the price of violations: a small $C$ buys a wide margin, a large $C$ chases every training point. It must be chosen on validation data.
nlpm-f-063 · level facile · notes
SVM: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Its dual has multipliers $0 \le \alpha_i \le C$. What does $0 < \tilde\alpha_i < C$ say about observation $i$?
  1. It lies strictly beyond the margin
  2. It is misclassified
  3. It does not influence the hyperplane
  4. It lies exactly on the margin, and $b$ is recovered from it
Explanation. KKT complementarity: $\alpha_i = 0$ beyond the margin, $0 < \alpha_i < C$ on the margin ($\xi_i = 0$), $\alpha_i = C$ pays a slack $\xi_i \ge 0$.
nlpm-f-064 · level facile · notes
SVM: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Its dual has multipliers $0 \le \alpha_i \le C$. Which feature of the dual opens the door to kernels $K(\mathbf x_i, \mathbf x_j)$?
  1. It depends on the data only through the inner products $\mathbf x_i'\mathbf x_j$
  2. It has the bound constraints $\alpha_i \le C$
  3. It is a maximization problem
  4. It has a single equality constraint
Explanation. Replacing $\mathbf x_i'\mathbf x_j$ with $K(\mathbf x_i, \mathbf x_j)$ classifies in a transformed space without building it.
nlpm-f-065 · level facile · notes
SVM: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Its dual has multipliers $0 \le \alpha_i \le C$. With the RBF kernel $K(\mathbf x_i, \mathbf x_j) = e^{-\gamma\|\mathbf x_i - \mathbf x_j\|^2}$ and $\gamma = 5$, the boundary breaks into islands and 61 of the 90 points are support vectors. What is happening?
  1. The training QP has become non-convex
  2. The model is too simple (underfitting)
  3. Overfitting: the model memorizes the training set
  4. The kernel is not a valid kernel
Explanation. Training remains a convex QP: convexity and ability to generalize are different properties. $C$ and $\gamma$ are chosen together by cross-validation.
nlpm-f-066 · level facile · notes
SVM: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. With unbalanced classes (few defaulters among loan applicants) the slacks of the two classes get different costs $C_-$ and $C_+$. How should they be chosen?
  1. Proportional to the class frequencies
  2. To reflect the costs of the two wrong decisions
  3. Always equal to each other
  4. By maximizing the accuracy on the test set
Explanation. The costs should mirror the decisions (a loan to a defaulter versus a good customer turned down): with a $10\times$ cost on defaulters none escapes, at the price of a few more false alarms.
nlpm-f-067 · level teorema · notes
SVM: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Its dual has multipliers $0 \le \alpha_i \le C$. Which primal-dual relation holds at the optimum?
  1. $\tilde{\mathbf w} = \sum_i \tilde\alpha_i\,\mathbf x_i$
  2. $\tilde{\mathbf w} = \sum_i \tilde\xi_i\,y_i\,\mathbf x_i$
  3. $\tilde{\mathbf w} = \sum_i \tilde\alpha_i\,y_i\,\mathbf x_i$
  4. $\tilde{\mathbf w} = C\sum_i y_i\mathbf x_i$
Explanation. Only the points with $\tilde\alpha_i > 0$ (support vectors) enter $\tilde{\mathbf w}$. The points with $\tilde\alpha_i = 0$ could disappear without changing anything: in the case study 7 support vectors out of 90.
nlpm-f-068 · level ipotesi · notes
SVM: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Its dual has multipliers $0 \le \alpha_i \le C$. The inner products $\mathbf x_i'\mathbf x_j$ of the dual are replaced by a kernel $K(\mathbf x_i, \mathbf x_j)$. Under which condition does training remain a convex QP?
  1. $\gamma < 1$ in the RBF kernel
  2. The two classes are balanced
  3. $C$ is small
  4. The kernel matrix $(K(\mathbf x_i, \mathbf x_j))$ is positive semidefinite
Explanation. With a positive semidefinite kernel matrix the dual objective is concave; the boundary in the original space can be arbitrarily curved.
nlpm-f-069 · level ipotesi · notes
SVM: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. Soft margin: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Its dual has multipliers $0 \le \alpha_i \le C$. From which condition does the dual constraint $\sum_i \alpha_i y_i = 0$ come?
  1. From the bound $\alpha_i \le C$
  2. From stationarity of the Lagrangian in the free intercept $b$
  3. From the non-negativity of the slacks $\xi_i$
  4. From the classes being balanced
Explanation. $\partial L/\partial b = -\sum_i\alpha_iy_i = 0$; stationarity in $\mathbf w$ gives $\mathbf w = \sum_i\alpha_iy_i\mathbf x_i$ and in $\xi_i$ the bound $\alpha_i \le C$.
nlpm-f-104 · level facile · notes
SVM: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. Hard margin: $\min\tfrac12\|\mathbf w\|^2$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1$ for every $i$. What happens when the two classes overlap (no line separates them)?
  1. The optimum has $\mathbf w = \mathbf 0$
  2. The model becomes unbounded
  3. The model is infeasible: slacks are needed (soft margin)
  4. Gurobi returns the best separating line anyway
Explanation. No hyperplane satisfies all the constraints, so the QP has no feasible solution; the soft margin adds slacks $\xi_i \ge 0$ paid in the objective.
nlpm-f-105 · level facile · notes
Support Vector Regression: $\min\tfrac12\|\mathbf w\|^2 + C\sum_i(\xi_i + \xi_i^*)$ with $|y_i - (\mathbf w'\mathbf x_i + b)| \le \varepsilon + \xi_i^{(*)}$, i.e. errors within a tube of width $\varepsilon$ are free. Which observations determine the fitted line?
  1. Only those on or outside the tube
  2. All the observations equally
  3. Only those strictly inside the tube
  4. Only the observation with the largest $y_i$
Explanation. Points strictly inside the tube have null multipliers, like the points beyond the margin in the SVM; in the case study 14 points out of 40 lie outside the tube.
nlpm-f-121 · level facile · notes
In the course chapter on Support Vector Machines, the labels $y_i \in \{-1, +1\}$ of the training observations (e.g. reliable / defaulting client) are:
  1. binary decision variables of the QP
  2. continuous variables between $-1$ and $+1$
  3. observed data, not variables
  4. multipliers of the classification constraints
Explanation. The labels are observed data; the variables (coefficients $w_j$, intercept $b$, slacks $\xi_i$, multipliers $\alpha_i$) are all continuous, so the SVM stays within the continuous models of the course.
nlpm-f-122 · level facile · notes
The course trains its Support Vector Machines without any machine-learning library: every classifier is a QP written and solved with Gurobi. Why?
  1. To understand what a classifier actually optimizes
  2. Because libraries cannot handle the kernel
  3. Because Gurobi is faster than any ML library
  4. Because libraries give only local optima
Explanation. The point of the chapter is to see the SVM as an optimization problem (a convex QP with its dual and multipliers), not as a black box; speed or library limits are not the reason.
nlpm-f-123 · level facile · notes
A Support Vector Machine is a binary classifier obtained by solving a QP. Which managerial question is a classification problem suited to it?
  1. How many loaves will be sold tomorrow?
  2. Which price maximizes the profit of a concert?
  3. How much should be produced in each month?
  4. Will this client repay the loan or default?
Explanation. Credit risk, churn, predictive maintenance, quality control and fraud are the applications of the notes: each observation gets one of two labels. Predicting a quantity is regression, choosing prices or production plans is optimization.
nlpm-f-124 · level facile · notes
The course chapter on Support Vector Machines says it «closes the circle» of the course. In what sense?
  1. It introduces integer variables for the first time
  2. Convex QPs and duality drive a classifier
  3. It replaces Gurobi with a machine-learning library
  4. It shows that optimization is not needed in machine learning
Explanation. Convex QPs, duality and multipliers, used for production, logistics and finance, are the engine of the SVM: the support vectors are read through complementary slackness, as shadow prices were.
nlpm-f-125 · level media · notes
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Hard margin: $\min\ \tfrac12\|\mathbf w\|^2$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1$. Two observations: $\mathbf x_1 = (0; 0)$ with $y_1 = -1$ and $\mathbf x_2 = (4; 0)$ with $y_2 = +1$. What are $\tilde{\mathbf w}$, $\tilde b$ and the margin $2/\|\tilde{\mathbf w}\|$?
  1. $\mathbf w = (1; 0)$, $b = -1$, margin $2$
  2. $\mathbf w = (0.5; 0)$, $b = -1$, margin $4$
  3. $\mathbf w = (0.25; 0)$, $b = -0.5$, margin $8$
  4. $\mathbf w = (0.5; 0.5)$, $b = -1$, margin $2.83$
Explanation. Constraints: $-b \ge 1$ and $4w_1 + b \ge 1$; minimizing $w_1^2 + w_2^2$ gives $w_2 = 0$ and both constraints active: $b = -1$, $w_1 = 0.5$. The hyperplane $x_1 = 2$ is the bisector of the segment, and the margin $2/0.5 = 4$ equals the distance between the two points.
nlpm-f-126 · level facile · notes
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Hard margin with $n$ observations and $p$ features: $\min\ \tfrac12\sum_j w_j^2$ subject to $y_i(\sum_j w_jx_{ij} + b) \ge 1$. How many variables and constraints does the QP have?
  1. $n$ variables and $p + 1$ constraints
  2. $p$ variables and $n + 1$ constraints
  3. $n + p$ variables and $n$ constraints
  4. $p + 1$ variables and $n$ constraints
Explanation. The variables are the $p$ coefficients $w_j$ and the intercept $b$, all free; there is one classification constraint per observation. The slacks $\xi_i$ (another $n$ variables) appear only in the soft margin.
nlpm-f-127 · level ipotesi · notes
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Hard margin: $\min\ \tfrac12\|\mathbf w\|^2$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1$ for every $i$. Under which hypothesis on the data does this QP have an optimal solution?
  1. The two classes are linearly separable
  2. The two classes have the same number of points
  3. The features are standardized
  4. There are more observations than features
Explanation. If some hyperplane separates the classes, scaling it gives a feasible $(\mathbf w, b)$; the objective is convex and bounded below by $0$, so an optimum exists. Without separability the feasible set is empty: this is why the soft margin is needed.
nlpm-f-128 · level facile · notes
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. At the optimum an observation has $0 < \tilde\xi_i < 1$. Where is it?
  1. Exactly on its margin line
  2. On the wrong side of the hyperplane
  3. On the right side, but inside the margin
  4. Far beyond its margin line
Explanation. $y_i(\mathbf w'\mathbf x_i + b) = 1 - \tilde\xi_i$ lies strictly between $0$ and $1$: the point is correctly classified but violates the margin. With $\tilde\xi_i > 1$ it would be misclassified, with $\tilde\xi_i = 0$ on or beyond the margin.
nlpm-f-129 · level teorema · notes
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. For fixed $(\mathbf w, b)$, what is the optimal value of each slack $\xi_i$?
  1. $\xi_i = 1 - y_i(\mathbf w'\mathbf x_i + b)$, whatever its sign
  2. $\xi_i = \max\{0,\ 1 - y_i(\mathbf w'\mathbf x_i + b)\}$
  3. $\xi_i = |\mathbf w'\mathbf x_i + b|$
  4. $\xi_i = \max\{0,\ y_i(\mathbf w'\mathbf x_i + b) - 1\}$
Explanation. $\xi_i$ must satisfy $\xi_i \ge 1 - y_i(\mathbf w'\mathbf x_i + b)$ and $\xi_i \ge 0$, and costs $C > 0$: it takes the smallest admissible value, the hinge loss. So the soft margin minimizes $\tfrac12\|\mathbf w\|^2$ plus $C$ times the total hinge loss.
nlpm-f-130 · level facile · notes
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Credit-risk case (90 clients, 2 indicators): $C = 0.05$ gives margin $2.42$ with 2 errors and 22 points inside the margin; $C = 20$ gives margin $0.36$, 0 errors, 3 points inside. Is $C = 20$ the best choice?
  1. Yes: it makes no error on the training set
  2. Yes: a larger $C$ always generalizes better
  3. No: the smallest $C$ is always the best
  4. Not necessarily: $C$ is chosen on validation data
Explanation. A large $C$ chases every training point (zero errors, very narrow margin); a small one buys a wide margin. It is the regularization–fit trade-off: $C$ is chosen on validation data, never on the training errors or on the test set.
nlpm-f-131 · level ipotesi · notes
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. When does the soft margin, for $C$ large enough, return the hard-margin solution ($\min\ \tfrac12\|\mathbf w\|^2$ with $y_i(\mathbf w'\mathbf x_i + b) \ge 1$)?
  1. Always, whatever the data
  2. Never: the two models differ for every $C$
  3. When the classes are linearly separable
  4. Only when there is a single feature, $p = 1$
Explanation. If the classes are separable the hard margin is feasible, and for a large enough $C$ paying any slack costs more than shrinking the margin: all $\xi_i = 0$. With overlapping classes the hard margin is infeasible and the slacks stay positive for every $C$.
nlpm-f-132 · level facile · notes
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Its dual: $\max\ \sum_i\alpha_i - \tfrac12\sum_i\sum_j\alpha_i\alpha_jy_iy_j\mathbf x_i'\mathbf x_j$ subject to $\sum_i\alpha_iy_i = 0$, $0 \le \alpha_i \le C$. At the optimum an observation has $\tilde\alpha_i = C$. What does complementary slackness say about it?
  1. $\tilde\xi_i > 0$: inside the margin or misclassified
  2. It lies exactly on the margin line
  3. It lies beyond the margin and does not affect the solution
  4. It must be removed from the training set
Explanation. The KKT conditions organize the points: $\alpha_i = 0$ beyond the margin, $0 < \alpha_i < C$ exactly on it, $\alpha_i = C$ when the constraint pays a slack $\xi_i > 0$ (inside the margin, or on the wrong side if $\xi_i > 1$).
nlpm-f-133 · level facile · notes
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Its dual: $\max\ \sum_i\alpha_i - \tfrac12\sum_i\sum_j\alpha_i\alpha_jy_iy_j\mathbf x_i'\mathbf x_j$ subject to $\sum_i\alpha_iy_i = 0$, $0 \le \alpha_i \le C$. Credit-risk case with $C = 1$: 83 of the 90 clients have $\tilde\alpha_i = 0$. What happens to the classifier if those 83 points are removed and the QP is solved again?
  1. It changes completely, both $\mathbf w$ and $b$
  2. It becomes infeasible for the remaining points
  3. It stays the same
  4. Only the intercept $b$ changes
Explanation. $\tilde{\mathbf w} = \sum_i\tilde\alpha_iy_i\mathbf x_i$ uses only the 7 points with $\tilde\alpha_i > 0$, the support vectors; the other 83 are beyond the margin and could disappear without changing the solution.
nlpm-f-134 · level teorema · notes
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Its dual: $\max\ \sum_i\alpha_i - \tfrac12\sum_i\sum_j\alpha_i\alpha_jy_iy_j\mathbf x_i'\mathbf x_j$ subject to $\sum_i\alpha_iy_i = 0$, $0 \le \alpha_i \le C$. In the credit-risk case the solver reports dual value $4.7868$ = primal value $4.7868$. Which result guarantees this equality?
  1. Weak duality, which holds for every QP
  2. The kernel trick
  3. The uniqueness of the support vectors
  4. Strong duality for convex QPs
Explanation. The soft margin is a convex QP with linear constraints: the KKT conditions are necessary and sufficient and the dual optimum has the same value as the primal. Weak duality would only give an inequality.
nlpm-f-135 · level facile · notes
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Its dual: $\max\ \sum_i\alpha_i - \tfrac12\sum_i\sum_j\alpha_i\alpha_jy_iy_j\mathbf x_i'\mathbf x_j$ subject to $\sum_i\alpha_iy_i = 0$, $0 \le \alpha_i \le C$. With a kernel $K(\mathbf x_i, \mathbf x_j)$ in place of $\mathbf x_i'\mathbf x_j$ (e.g. RBF, $K(\mathbf x, \mathbf z) = e^{-\gamma\|\mathbf x - \mathbf z\|^2}$), how is a new point $\mathbf x$ classified?
  1. $\mathrm{sign}(\mathbf w'\mathbf x + b)$ with $\mathbf w$ computed in the original space
  2. $\mathrm{sign}\bigl(\sum_i\tilde\alpha_iy_iK(\mathbf x_i, \mathbf x) + b\bigr)$
  3. $\mathrm{sign}\bigl(\sum_iK(\mathbf x_i, \mathbf x)\bigr)$
  4. By the label of the nearest support vector
Explanation. The transformed space is never built: the classifier uses only kernel values between the new point and the support vectors ($\tilde\alpha_i > 0$), weighted by $\tilde\alpha_iy_i$, plus the intercept.
nlpm-f-136 · level facile · notes
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. With the RBF kernel $K(\mathbf x, \mathbf z) = e^{-\gamma\|\mathbf x - \mathbf z\|^2}$ the SVM has two hyperparameters, $C$ and $\gamma$. How do the notes choose them?
  1. $\gamma$ first on the training errors, then $C$
  2. The largest values that give zero training errors
  3. $C$ by duality, $\gamma$ by a rule of thumb
  4. Together, by cross-validation
Explanation. $C$ and $\gamma$ interact (both control how closely the frontier follows the training points), so they are chosen together by cross-validation; zero training errors is the overfitting signal, not a goal.
nlpm-f-137 · level facile · notes
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. «Ring» case with the RBF kernel: with $\gamma = 5$ the frontier breaks into islands and 61 of 90 points are support vectors, yet the training problem is still a convex QP. What does this show?
  1. Convexity and generalization are different things
  2. The QP is no longer convex for large $\gamma$
  3. The solver has stopped at a local optimum
  4. The RBF kernel is not a valid kernel for $\gamma > 1$
Explanation. The QP is convex for every valid kernel and its optimum is global, but a global optimum of the training problem can still memorize the data: generalization is judged on validation data.
nlpm-f-138 · level facile · notes
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. The rare class (e.g. defaulting clients, $y_i = +1$) costs more when misclassified. How do the notes change the objective?
  1. They duplicate the rare observations in the data
  2. They raise the margin requirement of the rare class to 2
  3. $\tfrac12\|\mathbf w\|^2 + C_-\sum_{i:y_i = -1}\xi_i + C_+\sum_{i:y_i = +1}\xi_i$
  4. They remove part of the frequent class
Explanation. It is enough to weigh the slacks of the two classes differently, with $C_+ > C_-$ for the class whose errors cost more; the model stays a convex QP.
nlpm-f-139 · level facile · notes
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. Credit-risk case: with equal costs, precision $1.00$ and recall of the defaulters $0.94$; with a cost 10 times higher on the defaulters' slacks, precision $0.97$ and recall $1.00$. How is the change read?
  1. The frontier moves toward the healthy class
  2. The classifier got worse on every measure
  3. The frontier moves toward the defaulters: fewer false alarms
  4. Nothing changed: the differences are numerical noise
Explanation. Raising the cost of missing a defaulter pushes the frontier into the healthy region: recall reaches 100% and precision drops slightly because some good clients are flagged.
nlpm-f-140 · level facile · notes
SVM for binary classification: observations $\mathbf x_i \in \mathbb R^p$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$ ($\mathbf w$, $b$ free). Soft margin: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i\xi_i$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1 - \xi_i$, $\xi_i \ge 0$. In the credit-risk case, the recall of the defaulters is $1.00$. What does it mean?
  1. Every client flagged as defaulter really defaults
  2. The training error is zero
  3. All slacks $\xi_i$ are zero
  4. No actual defaulter is classified as reliable
Explanation. Recall = share of the actual defaulters that the classifier detects; precision = share of the flagged clients that really default. Recall 1 means no defaulter escapes, possibly at the price of false alarms.
nlpm-f-141 · level facile · notes
Support Vector Regression: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i(\xi_i + \xi_i^*)$ with $|y_i - (\mathbf w'\mathbf x_i + b)| \le \varepsilon + \xi_i^{(*)}$, where $\xi_i, \xi_i^* \ge 0$. What is the role of $\varepsilon$?
  1. The weight of the errors in the objective
  2. The half-width of a tube of free errors
  3. The largest admissible slope of the line
  4. The share of points allowed outside the tube
Explanation. Errors within $\pm\varepsilon$ of the estimate are ignored; only the points outside the tube pay, through $\xi_i$ (above) or $\xi_i^*$ (below), with weight $C$.
nlpm-f-142 · level facile · notes
Support Vector Regression on price–demand data (40 observations): with tube $\varepsilon = 8$, 14 points fall outside the tube. What happens to the number of points outside if $\varepsilon$ is enlarged?
  1. It grows, because the tube is stricter
  2. It stays 14, since it does not depend on $\varepsilon$
  3. It decreases: fewer points pay
  4. It becomes zero for every $\varepsilon > 0$
Explanation. A wider tube contains more points, which are then ignored; the estimate rests on the fewer points left outside (with $\varepsilon = 8$ the line was $-10.86p + 220.32$, against the true $-11p + 220$).
nlpm-f-143 · level teorema · notes
Support Vector Regression: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i(\xi_i + \xi_i^*)$ subject to $y_i - (\mathbf w'\mathbf x_i + b) \le \varepsilon + \xi_i$, $(\mathbf w'\mathbf x_i + b) - y_i \le \varepsilon + \xi_i^*$, $\xi_i, \xi_i^* \ge 0$. Which class of problem is it, and what follows?
  1. A convex QP: every local optimum is global
  2. An LP: its optimum is at a vertex
  3. A nonconvex QP: it needs `NonConvex = 2`
  4. An NLP with functional constraints
Explanation. Convex quadratic objective ($\tfrac12\|\mathbf w\|^2$ plus a linear term) and linear constraints: a convex QP, like the soft-margin SVM, with a certifiable global optimum.
nlpm-f-327 · level teorema · notes
The dual of the soft-margin SVM has objective $\sum_i \alpha_i - \tfrac12 \sum_i\sum_j \alpha_i\alpha_j y_i y_j\, \mathbf x_i'\mathbf x_j$. How does it depend on the data $\mathbf x_i$?
  1. On each coordinate $x_{ij}$ taken separately
  2. Only on the mean of all the observations
  3. Only on the observations labelled $y_i = +1$
  4. Only through the inner products $\mathbf x_i'\mathbf x_j$
Explanation. The dual depends on the data only through the inner products: replacing them with a kernel gives nonlinear boundaries with the same QP.
nlpm-f-328 · level teorema · notes
Soft-margin SVM: $\min\ \tfrac12\|\mathbf w\|^2 + C\sum_i \xi_i$. On separable data, what happens as $C$ grows?
  1. The margin widens and more points fall inside it
  2. One approaches the hard margin, with a narrower margin
  3. The optimal solution stays the same for every value
  4. The problem becomes non-convex and needs other solvers
Explanation. With a large $C$ violations are expensive: the model chases every training point (in the case study zero errors, margin 0.359).

13. Least-squares regression (23)

nlpm-f-070 · level facile · notes
A bakery fits sales against temperature in two ways: least absolute deviations (an LP) and least squares (a QP). The history contains five strike days with very low sales. Which fitted line moves more because of them?
  1. The absolute-deviation (LP) line
  2. The least-squares (QP) line, which pays deviations squared
  3. Neither line moves noticeably
  4. Both lines move by the same amount
Explanation. A deviation of $100$ weighs, squared, as much as ten thousand deviations of one: least squares is dragged down, the LP stays with the normal data.
nlpm-f-106 · level facile · notes
Bakery history with five strike days. On the 55 normal days the least-absolute-deviation (LP) line has mean error $13.08$ pieces, the least-squares (QP) line $14.81$; the QP refitted *without* the strikes has intercept $213.58$, from which the LP intercept differs by $3.81$ and the QP one by $11.24$. What is the lesson?
  1. The QP is better because it uses all the data
  2. Both methods need the strikes removed by hand
  3. The strikes do not affect either estimate
  4. The LP finds by itself the line the QP finds only after cleaning
Explanation. Paying each deviation once makes the LP robust to outliers: no one has to recognize and remove the strike days first.
nlpm-f-144 · level facile · notes
Bakery history (60 days, 5 strike days with about 20 loaves sold): the least-squares line is pulled down by the strikes, the least-absolute-deviations line is not. Why does one anomalous datum in ten move least squares so much?
  1. Because least squares has more variables
  2. Because the LP removes the outliers before estimating
  3. Because the QP is solved with a looser tolerance
  4. Because it pays each deviation squared
Explanation. The squared objective lets a large deviation dominate; the LP pays each deviation once, so the line stays where the normal data are, without anyone cleaning the history by hand.
nlpm-f-145 · level facile · notes
In the bakery case study, least squares is written as a QP to compare it with the LP of absolute deviations. How?
  1. $\min\sum_i(u_i + v_i)^2$ with $u_i, v_i \ge 0$ and no constraints
  2. $\min\sum_ir_i^2$, $r_i$ free, same equalities as the LP
  3. $\min\sum_i|r_i|$ with $r_i \ge 0$ and the same equalities
  4. $\max\sum_ir_i^2$ with $r_i$ free and no constraints
Explanation. One free residual per observation, defined by the same equality as in the LP, and a quadratic objective: a convex QP solved with the same solver.
nlpm-f-267 · level facile · notes
The robust regression of LP Modelling minimizes the sum of the absolute deviations (an LP). What does least squares minimize?
  1. The maximum of the absolute deviations
  2. The sum of the squared deviations
  3. The weighted sum of the deviations with weights $\tau$ and $1-\tau$
  4. The number of badly predicted observations
Explanation. Least squares minimizes $\sum_i r_i^2$: a convex QP; the maximum of the deviations would be a minimax LP, the weighted sum quantile regression.
nlpm-f-268 · level facile · notes
The least-squares case study uses the same data as the robust regression of LP Modelling. Which ones?
  1. Six electric vans, the hourly prices and the base load
  2. Eight sector securities and 60 simulated monthly returns
  3. Sixty days of a bakery, five of them with strikes
  4. Twelve districts weighted by their population
Explanation. They are the 60 days of the bakery (demand, temperature, price, weekend), with five days of transport strikes.
nlpm-f-269 · level facile · notes
Which advantage of least squares over absolute deviations does the chapter highlight?
  1. Closed-form normal equations and the estimate of the mean
  2. Robustness to the outliers in the history
  3. The possibility of estimating any quantile
  4. Automatic selection of the useful features
Explanation. On clean data least squares has the normal equations and estimates the mean; robustness, quantiles and selection are strengths of the linear models.
nlpm-f-270 · level facile · notes
In the least-squares QP $\min \sum_i r_i^2$ with $\sum_j w_j x_{ij} + b + r_i = y_i$, how are the residuals $r_i$ declared?
  1. Non-negative, like the deviations of the linear model
  2. Binary, to count the errors
  3. As two non-negative variables $u_i$ and $v_i$ per residual
  4. Free: the square does not distinguish the sign
Explanation. The square of a residual does not depend on its sign: one free variable per residual is enough, without the two positive parts of the linear model.
nlpm-f-271 · level facile · notes
Least squares without features ($p = 0$) on seven sales: 88, 96, 104, 112, 120, 132, 148. What is the optimal intercept $\tilde b$?
  1. $800/7 \approx 114.29$, the mean
  2. $112$, the median
  3. $120$, the $9/13$ quantile
  4. $118$, the midpoint between minimum and maximum
Explanation. Stationarity with respect to $b$ gives $\sum_i r_i = 0$: $\tilde b$ is the mean $800/7$. The median 112 is the optimum of absolute deviations.
nlpm-f-272 · level ipotesi · notes
In the same seven sales the last value goes from 148 to 248. How do the least-squares estimate (mean) and the absolute-deviation estimate (median) change?
  1. They both stay unchanged, because the data are few
  2. The mean rises by 14.29, the median stays at 112
  3. The median rises by 100, the mean stays the same
  4. They both rise by 100/7, that is by about 14.29
Explanation. The mean depends on every value: it rises by $100/7 = 14.29$. The median depends only on the order of the values and stays at 112.
nlpm-f-273 · level teorema · notes
Least-squares QP with free intercept $b$ and coefficients $w_j$. What do the KKT conditions say about the optimal residuals $\tilde r_i$?
  1. That they are all zero except at most $p + 1$ of them
  2. That they are all equal in absolute value
  3. That they sum to zero and are orthogonal to the features
  4. That they are all non-negative at the optimum
Explanation. Stationarity in $b$: $\sum_i \pi_i = 0$; in $w_j$: $\sum_i \pi_i x_{ij} = 0$; with $\pi_i = 2 r_i$ these are the normal equations.
nlpm-f-274 · level teorema · notes
In the least-squares QP the multiplier of the constraint of observation $i$ is $\tilde\pi_i = 2\tilde r_i$. What does it measure?
  1. How much the sum of squares grows if $y_i$ rises by one
  2. The probability that observation $i$ is an outlier
  3. The number of observations lying above the line
  4. The weight of feature $i$ in the forecast
Explanation. The multiplier is the derivative of the optimal value with respect to the right-hand side $y_i$: twice the residual. A distant datum weighs as much as it is distant.
nlpm-f-275 · level facile · notes
In absolute-deviation regression (LP) the duals are $\pm 1/2$ or an interior value; in least squares they are $2 r_i$. What consequence does this have on outliers?
  1. None: the two models weigh outliers in the same way
  2. Least squares ignores outliers altogether
  3. The LP gives outliers a weight proportional to the deviation
  4. In least squares an outlier weighs in proportion to the deviation
Explanation. In the LP only the sign of the residual matters (bounded weight); in least squares the weight grows with the residual, and a distant outlier pulls the line.
nlpm-f-276 · level facile · notes
Bakery, line with temperature alone on the 60 days: the sum of squares is 68,286.6. What share of it do the five strike days produce?
  1. About 8%
  2. About 71%
  3. About 30%
  4. About 99%
Explanation. The residuals of the strikes go from $-65$ to $-137$ items and produce 71.4% of the sum of squares, although they are 5 days out of 60.
nlpm-f-277 · level facile · notes
The newsvendor needs the $9/13$ quantile of demand. Starting from least squares (forecast mean $128.7$, standard deviation of the residuals $9.40$, $z = 0.5024$), which quantity is obtained assuming normal residuals?
  1. $128.7$ items
  2. $138.1$ items
  3. $133.5$ items
  4. $124.0$ items
Explanation. $128.7 + 0.5024 \cdot 9.40 = 133.5$ items; quantile regression, with no assumption on the shape of the errors, gives $132.1$.
nlpm-f-278 · level ipotesi · notes
To reach the newsvendor quantile a stock $z\sigma$ is added to the least-squares mean. Which assumption does this road require, and quantile regression does not?
  1. That the features are standardized
  2. That the strike days are included
  3. That the quantile is the median
  4. That the residuals are normal
Explanation. The formula mean $+\,z\sigma$ uses the quantile of the standard normal: it holds if the residuals are normal. Quantile regression estimates the quantile directly.
nlpm-f-279 · level facile · notes
On the typical day of the bakery (28 degrees, price 3.00, weekend) the mean forecast by least squares is 128.7 items. Why is producing 128.7 items not enough?
  1. Because with $c_u = 9$ and $c_o = 4$ the $9/13$ quantile is needed, above the mean
  2. Because the least-squares mean is underestimated by ten items
  3. Because the weekend must be excluded from the demand estimate
  4. Because the mean must always be rounded down
Explanation. With shortage cost 9 and excess cost 4 the critical fractile is $9/13 > 1/2$: it pays to produce more than the mean, that is a high quantile of demand.
nlpm-f-280 · level facile · notes
On the 55 normal days the share of days below the estimate ``least-squares mean $+\,z\sigma$'' is 0.709. What should it be compared with?
  1. With 0.5, the median
  2. With the critical fractile $9/13 \approx 0.692$
  3. With 0.95, the standard service level
  4. With 71.4%, the share of the strikes
Explanation. The estimate should leave 69.2% of the days below it (the $9/13$ quantile); 0.709 is close to the target.
nlpm-f-281 · level facile · notes
The demand of the hottest normal day (33.7 degrees) is moved down. How do the least-squares line and the absolute-deviation line react?
  1. They both stay still, whatever the shift
  2. They both move in proportion to the shift
  3. The LP line moves in proportion, the QP line only once
  4. The QP line moves in proportion, the LP line only once
Explanation. In least squares the slope changes by about 0.004 per item; in the LP only the sign of the residual matters and the estimate stays 211.63 $-$ 3.689 temperature.
nlpm-f-282 · level teorema · notes
Ridge regression: $\lambda \sum_j w_j^2$ is added to the least-squares objective. As $\lambda$ grows the coefficients shrink but none becomes exactly zero. Why?
  1. Because Gurobi rounds the small coefficients
  2. Because $2\lambda w_j$ vanishes at $w_j = 0$: no fixed push
  3. Because the features have been standardized
  4. Because the problem becomes non-convex for large $\lambda$
Explanation. Near zero the quadratic penalty no longer pushes: the coefficient approaches zero without reaching it. The budget on absolute values has a constant push instead and sets coefficients to zero.
nlpm-f-283 · level facile · notes
To select the useful features and to stabilize estimates with correlated features, which penalties does the chapter recommend, in this order?
  1. Quadratic to select, linear to stabilize the estimates
  2. No penalty, neither to select nor to stabilize
  3. Linear to select, quadratic (ridge) to stabilize
  4. Quadratic in both cases, with different weights
Explanation. The budget on absolute values sets the useless coefficients to zero; ridge shrinks them all, useful when the features are correlated.
nlpm-f-329 · level teorema · notes
Least-squares QP without features: $\min \sum_i r_i^2$ with $b + r_i = y_i$. What does stationarity with respect to $b$ give?
  1. $\sum_i |r_i| = 0$: the estimate is the median
  2. $r_i = 0$ for every observation $i$
  3. $\sum_i r_i = 0$: the estimate is the mean
  4. $b = \max_i y_i$, the largest value
Explanation. With $\pi_i = 2r_i$ stationarity with respect to $b$ gives $\sum_i r_i = 0$: the estimate $\tilde b$ is the mean of the data (114.29 for the seven sales).
nlpm-f-335 · level ipotesi · notes
In the least-squares QP the residuals $r_i$ are free variables. What happens if they keep the default gurobipy lower bound ($r_i \ge 0$)?
  1. The line must lie below all the data: biased estimate
  2. Nothing changes, because the square ignores the sign
  3. The model becomes non-convex and needs `NonConvex = 2`
  4. Gurobi stops and reports a syntax error
Explanation. With $r_i \ge 0$ every prediction must be at most the observed value: the model changes and the estimate is no longer the least-squares one.

Generated questions (29)

Each generator builds a new instance, with different numbers, at every start: a few examples here.

2. Background: convexity, QP and KKT (2)

Example 1 · nlpm-g-qp-kkt · level facile · notes
Convex QP: $\min\ 6x_1^2 + x_2^2$ subject to $x_1 + x_2 \ge 20$, $x_1, x_2 \ge 0$. At the optimum the constraint is active, the bounds are not, and stationarity of the Lagrangian $L = f + \lambda(20 - x_1 - x_2)$ holds. What are $\tilde x_1$ and the multiplier $\lambda$?
  1. $\tilde x_1 = 2.86$, $\lambda = 34.29$
  2. $\tilde x_1 = 10$, $\lambda = 120$
  3. $\tilde x_1 = 17.14$, $\lambda = 34.29$
  4. $\tilde x_1 = 2.86$, $\lambda = 17.14$
Explanation. Stationarity: $12x_1 = \lambda$ and $2x_2 = \lambda$, so $x_1 = \lambda/12$, $x_2 = \lambda/2$; the active constraint gives $\lambda = 34.29$, hence $\tilde x_1 = 2.86$, $\tilde x_2 = 17.14$. The variable with the smaller quadratic coefficient takes the larger share; $\lambda$ is the marginal cost of one more unit of $d$.
Example 2 · nlpm-g-qp-kkt · level facile · notes
Convex QP: $\min\ 3x_1^2 + 6x_2^2$ subject to $x_1 + x_2 \ge 9$, $x_1, x_2 \ge 0$. At the optimum the constraint is active, the bounds are not, and stationarity of the Lagrangian $L = f + \lambda(9 - x_1 - x_2)$ holds. What are $\tilde x_1$ and the multiplier $\lambda$?
  1. $\tilde x_1 = 4.5$, $\lambda = 27$
  2. $\tilde x_1 = 6$, $\lambda = 18$
  3. $\tilde x_1 = 3$, $\lambda = 36$
  4. $\tilde x_1 = 6$, $\lambda = 36$
Explanation. Stationarity: $6x_1 = \lambda$ and $12x_2 = \lambda$, so $x_1 = \lambda/6$, $x_2 = \lambda/12$; the active constraint gives $\lambda = 36$, hence $\tilde x_1 = 6$, $\tilde x_2 = 3$. The variable with the smaller quadratic coefficient takes the larger share; $\lambda$ is the marginal cost of one more unit of $d$.
Example 1 · nlpm-g-kkt-proiezione · level media · notes
Convex QP: $\min\ (x - 4)^2 + (y - 4)^2$ subject to $x + y \le 7$, $x, y \ge 0$; $\lambda \ge 0$ is the KKT multiplier of $x + y \le 7$ (Lagrangian $L = f + \lambda(x + y - 7)$). What are the optimum and $\lambda$?
  1. $(4; 4)$, $\lambda = 0$
  2. $(3.5; 3.5)$, $\lambda = 0.5$
  3. $(3.5; 3.5)$, $\lambda = 1$
  4. $(3.5; 3.5)$, $\lambda = 2$
Explanation. The free minimum $(4, 4)$ violates $x + y \le 7$, so the constraint is active. Stationarity: $2(x - 4) + \lambda = 0$, $2(y - 4) + \lambda = 0$, so $x = 4 - \lambda/2$, $y = 4 - \lambda/2$; with $x + y = 7$: $\lambda = 1$, optimum $(3.5; 3.5)$, both positive (bounds inactive). Convex problem: the KKT point is the global optimum.
Example 2 · nlpm-g-kkt-proiezione · level media · notes
Convex QP: $\min\ (x - 3)^2 + (y - 6)^2$ subject to $x + y \le 4$, $x, y \ge 0$; $\lambda \ge 0$ is the KKT multiplier of $x + y \le 4$ (Lagrangian $L = f + \lambda(x + y - 4)$). What are the optimum and $\lambda$?
  1. $(3.5; 0.5)$, $\lambda = 5$
  2. $(3; 6)$, $\lambda = 0$
  3. $(0.5; 3.5)$, $\lambda = 2.5$
  4. $(0.5; 3.5)$, $\lambda = 5$
Explanation. The free minimum $(3, 6)$ violates $x + y \le 4$, so the constraint is active. Stationarity: $2(x - 3) + \lambda = 0$, $2(y - 6) + \lambda = 0$, so $x = 3 - \lambda/2$, $y = 6 - \lambda/2$; with $x + y = 4$: $\lambda = 5$, optimum $(0.5; 3.5)$, both positive (bounds inactive). Convex problem: the KKT point is the global optimum.

3. The solver for nonlinear models (1)

Example 1 · nlpm-g-sv-perturbazione-nl · level facile · notes
A gurobipy model maximizes $20\log(1 + 1x)$ subject to $0 \le x \le b$, with the logarithm written through `addGenConstrLog`, so the solver returns no dual for the bound $x \le b$. Solving with $b = 5$ gives $35.8352$; with $b = 5.1$ it gives $36.1658$. What is the perturbation estimate of the multiplier of $x \le b$?
  1. $\approx 33.06$
  2. $\approx 7.17$
  3. $\approx 3.31$
  4. $\approx 0.33$
Explanation. Incremental ratio: $(36.1658 - 35.8352)/0.1 = 3.31$, close to the exact derivative $20\cdot 1/(1 + 1\cdot 5) = 3.33$ (the difference is the curvature). Forgetting to divide by $0.1$ is the typical slip.
Example 2 · nlpm-g-sv-perturbazione-nl · level facile · notes
A gurobipy model maximizes $50\log(1 + 1x)$ subject to $0 \le x \le b$, with the logarithm written through `addGenConstrLog`, so the solver returns no dual for the bound $x \le b$. Solving with $b = 7$ gives $103.9721$; with $b = 7.1$ it gives $104.5932$. What is the perturbation estimate of the multiplier of $x \le b$?
  1. $\approx 62.11$
  2. $\approx 14.85$
  3. $\approx 0.62$
  4. $\approx 6.21$
Explanation. Incremental ratio: $(104.5932 - 103.9721)/0.1 = 6.21$, close to the exact derivative $50\cdot 1/(1 + 1\cdot 7) = 6.25$ (the difference is the curvature). Forgetting to divide by $0.1$ is the typical slip.

4. Production with quadratic smoothing (1)

Example 1 · nlpm-g-prodq-scorta · level facile · notes
Production with quadratic smoothing, one product and two months: demand $d_1 = 60$ and $d_2 = 100$, holding cost $h = 2$ per unit, ample capacity, zero initial stock and weight $\gamma = 1$ on the squared jump $(x_2 - x_1)^2$. With $x_1 = d_1 + s_1$ and $x_2 = d_2 - s_1$, what is the optimal stock $\tilde s_1$?
  1. $\tilde s_1 = 19$
  2. $\tilde s_1 = 20$
  3. $\tilde s_1 = 19.5$
  4. $\tilde s_1 = 19.75$
Explanation. The jump is $40 - 2s_1$ and the objective (up to constants) is $h s_1 + \gamma(40 - 2s_1)^2$. Stationarity: $h - 4\gamma(40 - 2s_1) = 0$, so $\tilde s_1 = 40/2 - h/(8\gamma) = 19.75$: stock is built until the marginal saving on the penalty equals the holding cost.
Example 2 · nlpm-g-prodq-scorta · level facile · notes
Production with quadratic smoothing, one product and two months: demand $d_1 = 50$ and $d_2 = 110$, holding cost $h = 1$ per unit, ample capacity, zero initial stock and weight $\gamma = 0.05$ on the squared jump $(x_2 - x_1)^2$. With $x_1 = d_1 + s_1$ and $x_2 = d_2 - s_1$, what is the optimal stock $\tilde s_1$?
  1. $\tilde s_1 = 27.5$
  2. $\tilde s_1 = 20$
  3. $\tilde s_1 = 25$
  4. $\tilde s_1 = 30$
Explanation. The jump is $60 - 2s_1$ and the objective (up to constants) is $h s_1 + \gamma(60 - 2s_1)^2$. Stationarity: $h - 4\gamma(60 - 2s_1) = 0$, so $\tilde s_1 = 60/2 - h/(8\gamma) = 27.5$: stock is built until the marginal saving on the penalty equals the holding cost.

5. Supply chain with congestion and sustainability (2)

Example 1 · nlpm-g-sc-due-rotte · level facile · notes
Minimum-cost flow LP of a supply chain: a market demands $D = 140$ units, sent on two routes with flows $x_1, x_2 \ge 0$ and demand constraint $x_1 + x_2 \ge D$. Route 1 costs $c_1 = 4$ €/unit with capacity $x_1 \le 110$; route 2 costs $c_2 = 10$ €/unit with unlimited capacity. What are the optimal cost and the shadow price of the demand constraint (cost of serving one more unit)?
  1. cost 740 €, marginal cost 6 €/unit
  2. cost 740 €, marginal cost 4 €/unit
  3. cost 560 €, marginal cost 4 €/unit
  4. cost 740 €, marginal cost 10 €/unit
Explanation. The cheap route is saturated ($x_1 = 110$) and the rest goes on route 2: $4\cdot 110 + 10\cdot 30 = 740$ €. The next unit can only travel on route 2: the shadow price of the demand is $10$.
Example 2 · nlpm-g-sc-due-rotte · level facile · notes
Minimum-cost flow LP of a supply chain: a market demands $D = 110$ units, sent on two routes with flows $x_1, x_2 \ge 0$ and demand constraint $x_1 + x_2 \ge D$. Route 1 costs $c_1 = 2$ €/unit with capacity $x_1 \le 60$; route 2 costs $c_2 = 3$ €/unit with unlimited capacity. What are the optimal cost and the shadow price of the demand constraint (cost of serving one more unit)?
  1. cost 270 €, marginal cost 3 €/unit
  2. cost 270 €, marginal cost 1 €/unit
  3. cost 220 €, marginal cost 2 €/unit
  4. cost 270 €, marginal cost 2 €/unit
Explanation. The cheap route is saturated ($x_1 = 60$) and the rest goes on route 2: $2\cdot 60 + 3\cdot 50 = 270$ €. The next unit can only travel on route 2: the shadow price of the demand is $3$.
Example 1 · nlpm-g-sc-congestione · level media · notes
Supply chain with congestion: $D = 235$ units are split between two routes, $x_1 + x_2 = D$, $x_1, x_2 \ge 0$. Route 1 (unit cost $c_1 = 1$, nominal capacity $u_1 = 140$, congestion parameter $\alpha = 2$) costs $c_1x_1 + \alpha c_1x_1^2/u_1$ €; route 2 costs $c_2 = 6$ €/unit with ample capacity. Minimizing the total cost, what is the optimal split $(\tilde x_1; \tilde x_2)$?
  1. $(\tilde x_1; \tilde x_2) = (140; 95)$
  2. $(\tilde x_1; \tilde x_2) = (117.5; 117.5)$
  3. $(\tilde x_1; \tilde x_2) = (235; 0)$
  4. $(\tilde x_1; \tilde x_2) = (175; 60)$
Explanation. At the optimum the marginal costs are equal: $1 + 2\alpha\,1\,x_1/140 = 6$, so $x_1 = 175$ and $x_2 = 60$. The pure LP would saturate route 1; forgetting the factor 2 of the derivative doubles $x_1$.
Example 2 · nlpm-g-sc-congestione · level media · notes
Supply chain with congestion: $D = 370$ units are split between two routes, $x_1 + x_2 = D$, $x_1, x_2 \ge 0$. Route 1 (unit cost $c_1 = 5$, nominal capacity $u_1 = 200$, congestion parameter $\alpha = 0.5$) costs $c_1x_1 + \alpha c_1x_1^2/u_1$ €; route 2 costs $c_2 = 13$ €/unit with ample capacity. Minimizing the total cost, what is the optimal split $(\tilde x_1; \tilde x_2)$?
  1. $(\tilde x_1; \tilde x_2) = (185; 185)$
  2. $(\tilde x_1; \tilde x_2) = (200; 170)$
  3. $(\tilde x_1; \tilde x_2) = (320; 50)$
  4. $(\tilde x_1; \tilde x_2) = (370; 0)$
Explanation. At the optimum the marginal costs are equal: $5 + 2\alpha\,5\,x_1/200 = 13$, so $x_1 = 320$ and $x_2 = 50$. The pure LP would saturate route 1; forgetting the factor 2 of the derivative doubles $x_1$.

6. The Markowitz portfolio (4)

Example 1 · nlpm-g-mk-minvar · level facile · notes
Markowitz model with two uncorrelated assets of volatilities (standard deviations of the return) $\sigma_1 = 30\%$ and $\sigma_2 = 40\%$. The shares $x_1, x_2$ of capital, with $x_1 + x_2 = 1$, minimize the portfolio variance (no return constraint). What are the optimal share $\tilde x_1$ and the portfolio volatility $\sigma_p$ (square root of the variance)?
  1. $\tilde x_1 = 50\%$, $\sigma_p = 25\%$
  2. $\tilde x_1 = 57.1\%$, $\sigma_p = 24.2\%$
  3. $\tilde x_1 = 36\%$, $\sigma_p = 27.8\%$
  4. $\tilde x_1 = 64\%$, $\sigma_p = 24\%$
Explanation. Setting the derivative of $\sigma_1^2 x_1^2 + \sigma_2^2 (1 - x_1)^2$ to zero gives $x_1 = \sigma_2^2/(\sigma_1^2 + \sigma_2^2)$: the weights are inversely proportional to the variances (not to the volatilities). The volatility is below that of both assets.
Example 2 · nlpm-g-mk-minvar · level facile · notes
Markowitz model with two uncorrelated assets of volatilities (standard deviations of the return) $\sigma_1 = 20\%$ and $\sigma_2 = 40\%$. The shares $x_1, x_2$ of capital, with $x_1 + x_2 = 1$, minimize the portfolio variance (no return constraint). What are the optimal share $\tilde x_1$ and the portfolio volatility $\sigma_p$ (square root of the variance)?
  1. $\tilde x_1 = 50\%$, $\sigma_p = 22.4\%$
  2. $\tilde x_1 = 20\%$, $\sigma_p = 32.2\%$
  3. $\tilde x_1 = 80\%$, $\sigma_p = 17.9\%$
  4. $\tilde x_1 = 66.7\%$, $\sigma_p = 18.9\%$
Explanation. Setting the derivative of $\sigma_1^2 x_1^2 + \sigma_2^2 (1 - x_1)^2$ to zero gives $x_1 = \sigma_2^2/(\sigma_1^2 + \sigma_2^2)$: the weights are inversely proportional to the variances (not to the volatilities). The volatility is below that of both assets.
Example 1 · nlpm-g-mk-portafoglio · level facile · notes
Markowitz model, portfolio of two assets with shares of capital $x_1 = 0.5$, $x_2 = 0.5$; expected returns $\mu_1 = 5\%$, $\mu_2 = 12\%$; volatilities $\sigma_1 = 0.2$, $\sigma_2 = 0.25$; correlation $\rho = 0.75$, so $q_{ii} = \sigma_i^2$ and $q_{12} = q_{21} = \rho\sigma_1\sigma_2$. What are its expected return and its variance $\sum_{i}\sum_{j} q_{ij} x_i x_j$?
  1. expected return 8.5%, variance 0.0444
  2. expected return 8.5%, variance 0.0513
  3. expected return 8.5%, variance 0.0256
  4. expected return 8.5%, variance 0.035
Explanation. The return is linear, $\mu_1 x_1 + \mu_2 x_2$. The variance has three terms: $x_1^2\sigma_1^2 + x_2^2\sigma_2^2 + 2x_1x_2\rho\sigma_1\sigma_2$; the covariance appears twice ($q_{12}$ and $q_{21}$).
Example 2 · nlpm-g-mk-portafoglio · level facile · notes
Markowitz model, portfolio of two assets with shares of capital $x_1 = 0.4$, $x_2 = 0.6$; expected returns $\mu_1 = 8\%$, $\mu_2 = 13\%$; volatilities $\sigma_1 = 0.3$, $\sigma_2 = 0.15$; correlation $\rho = -0.5$, so $q_{ii} = \sigma_i^2$ and $q_{12} = q_{21} = \rho\sigma_1\sigma_2$. What are its expected return and its variance $\sum_{i}\sum_{j} q_{ij} x_i x_j$?
  1. expected return 11%, variance 0.0117
  2. expected return 11%, variance 0.0171
  3. expected return 11%, variance 0.0225
  4. expected return 11%, variance 0.0495
Explanation. The return is linear, $\mu_1 x_1 + \mu_2 x_2$. The variance has three terms: $x_1^2\sigma_1^2 + x_2^2\sigma_2^2 + 2x_1x_2\rho\sigma_1\sigma_2$; the covariance appears twice ($q_{12}$ and $q_{21}$).
Example 1 · nlpm-g-mk-correlati · level media · notes
Markowitz model with two assets of volatilities (standard deviations of the return) $\sigma_1 = 0.3$, $\sigma_2 = 0.4$ and correlation $\rho = -0.5$. The shares $x_1 + x_2 = 1$ minimize the portfolio variance $\sum_i\sum_j q_{ij}x_ix_j$, with covariance $q_{12} = \rho\sigma_1\sigma_2$ (no return constraint; the optimum has $x_1, x_2 > 0$). What are $\tilde x_1$ and the minimum variance $\sigma_p^2$?
  1. $\tilde x_1 = 59.5\%$, $\sigma_p^2 = 0.0292$
  2. $\tilde x_1 = 76.9\%$, $\sigma_p^2 = 0.0405$
  3. $\tilde x_1 = 64\%$, $\sigma_p^2 = 0.03$
  4. $\tilde x_1 = 40.5\%$, $\sigma_p^2 = 0.0424$
Explanation. With correlation $x_1 = (\sigma_2^2 - \rho\sigma_1\sigma_2)/(\sigma_1^2 + \sigma_2^2 - 2\rho\sigma_1\sigma_2) = 0.5946$; the variance is $x_1^2\sigma_1^2 + x_2^2\sigma_2^2 + 2x_1x_2\rho\sigma_1\sigma_2$ at that weight. Ignoring $\rho$ or flipping its sign gives the wrong weight.
Example 2 · nlpm-g-mk-correlati · level media · notes
Markowitz model with two assets of volatilities (standard deviations of the return) $\sigma_1 = 0.2$, $\sigma_2 = 0.4$ and correlation $\rho = -0.25$. The shares $x_1 + x_2 = 1$ minimize the portfolio variance $\sum_i\sum_j q_{ij}x_ix_j$, with covariance $q_{12} = \rho\sigma_1\sigma_2$ (no return constraint; the optimum has $x_1, x_2 > 0$). What are $\tilde x_1$ and the minimum variance $\sigma_p^2$?
  1. $\tilde x_1 = 25\%$, $\sigma_p^2 = 0.085$
  2. $\tilde x_1 = 87.5\%$, $\sigma_p^2 = 0.0288$
  3. $\tilde x_1 = 80\%$, $\sigma_p^2 = 0.0256$
  4. $\tilde x_1 = 75\%$, $\sigma_p^2 = 0.025$
Explanation. With correlation $x_1 = (\sigma_2^2 - \rho\sigma_1\sigma_2)/(\sigma_1^2 + \sigma_2^2 - 2\rho\sigma_1\sigma_2) = 0.75$; the variance is $x_1^2\sigma_1^2 + x_2^2\sigma_2^2 + 2x_1x_2\rho\sigma_1\sigma_2$ at that weight. Ignoring $\rho$ or flipping its sign gives the wrong weight.
Example 1 · nlpm-g-mk-due-titoli-r · level complessa · notes
Markowitz with two assets: expected returns $\mu_1 = 16\%$, $\mu_2 = 6\%$; volatilities $\sigma_1 = 27\%$, $\sigma_2 = 14\%$; correlation $\rho = -0.2$. Minimize the portfolio variance $x_1^2\sigma_1^2 + x_2^2\sigma_2^2 + 2x_1x_2\rho\sigma_1\sigma_2$ with $x_1 + x_2 = 1$, $x \ge 0$ and expected return at least $\bar r = 12\%$. What are the optimal share $x_1$ and the portfolio volatility?
  1. $x_1 = 60\%$, volatility $16.05\%$
  2. $x_1 = 60\%$, volatility $21.8\%$
  3. $x_1 = 25.2\%$, volatility $11.29\%$
  4. $x_1 = 60\%$, volatility $17.14\%$
Explanation. Minimum-variance share without the return constraint: $x_1 = (\sigma_2^2 - \rho\sigma_1\sigma_2)/(\sigma_1^2 + \sigma_2^2 - 2\rho\sigma_1\sigma_2) = 25.2\%$, with return $8.52\%$. It is below $\bar r$, so the constraint binds: $x_1\mu_1 + (1 - x_1)\mu_2 = \bar r$ gives $x_1 = 60\%$. Volatility $16.05\%$.
Example 2 · nlpm-g-mk-due-titoli-r · level complessa · notes
Markowitz with two assets: expected returns $\mu_1 = 14\%$, $\mu_2 = 8\%$; volatilities $\sigma_1 = 19\%$, $\sigma_2 = 8\%$; correlation $\rho = 0$. Minimize the portfolio variance $x_1^2\sigma_1^2 + x_2^2\sigma_2^2 + 2x_1x_2\rho\sigma_1\sigma_2$ with $x_1 + x_2 = 1$, $x \ge 0$ and expected return at least $\bar r = 12\%$. What are the optimal share $x_1$ and the portfolio volatility?
  1. $x_1 = 66.7\%$, volatility $12.94\%$
  2. $x_1 = 66.7\%$, volatility $15.33\%$
  3. $x_1 = 15.1\%$, volatility $7.37\%$
  4. $x_1 = 33.3\%$, volatility $8.28\%$
Explanation. Minimum-variance share without the return constraint: $x_1 = (\sigma_2^2 - \rho\sigma_1\sigma_2)/(\sigma_1^2 + \sigma_2^2 - 2\rho\sigma_1\sigma_2) = 15.1\%$, with return $8.9\%$. It is below $\bar r$, so the constraint binds: $x_1\mu_1 + (1 - x_1)\mu_2 = \bar r$ gives $x_1 = 66.7\%$. Volatility $12.94\%$.

7. Pricing and revenue management (2)

Example 1 · nlpm-g-pricing-ottimo · level facile · notes
Pricing model: choose the price $p$ and the quantity sold $q$ to maximize the profit $(p - c)\,q$ subject to $q \le d(p) = 1100 - 5p$ (demand) and $q \le k$ (capacity), with marginal cost $c = 66$ € and $k = 405$. What are the optimal price $p^*$ and the optimal profit?
  1. $p^* = 143$ €, profit 29645 €
  2. $p^* = 110$ €, profit 17820 €
  3. $p^* = 139$ €, profit 29565 €
  4. $p^* = 187$ €, profit 19965 €
Explanation. Without capacity $p^\circ = (a/b + c)/2 = 143$ with $q^\circ = 385 \le k$: the capacity constraint is inactive and $p^* = p^\circ$.
Example 2 · nlpm-g-pricing-ottimo · level facile · notes
Pricing model: choose the price $p$ and the quantity sold $q$ to maximize the profit $(p - c)\,q$ subject to $q \le d(p) = 1080 - 4p$ (demand) and $q \le k$ (capacity), with marginal cost $c = 32$ € and $k = 416$. What are the optimal price $p^*$ and the optimal profit?
  1. $p^* = 166$ €, profit 55744 €
  2. $p^* = 151$ €, profit 49504 €
  3. $p^* = 135$ €, profit 42848 €
  4. $p^* = 150$ €, profit 49088 €
Explanation. Without capacity $p^\circ = (a/b + c)/2 = 151$ with $q^\circ = 476 > k$: capacity bites, and the price that sells exactly $k$ is $p^* = (a - k)/b = 166$.
Example 1 · nlpm-g-pricing-posto · level media · notes
Pricing model: choose the price $p$ and the quantity sold $q$ to maximize $(p - c)\,q$ subject to $q \le d(p) = 1100 - 5p$ and $q \le k$, with $c = 66$ € and $k = 235$; the capacity constraint is active at the optimum. Let $\Pi(k)$ be the optimal profit as a function of the capacity. What is $d\Pi/dk$, the value of one more unit of capacity?
  1. 126 €
  2. 107 €
  3. 13 €
  4. 60 €
Explanation. With $p^* = (a - k)/b = 173$ the profit is $(p^* - c)\,k$, and $dp^*/dk = -1/b$: $d\Pi/dk = (p^* - c) - k/b = 60$. The full margin $p^* - c$ forgets that, to fill the extra seat, the price falls for everybody.
Example 2 · nlpm-g-pricing-posto · level media · notes
Pricing model: choose the price $p$ and the quantity sold $q$ to maximize $(p - c)\,q$ subject to $q \le d(p) = 1080 - 4p$ and $q \le k$, with $c = 32$ € and $k = 456$; the capacity constraint is active at the optimum. Let $\Pi(k)$ be the optimal profit as a function of the capacity. What is $d\Pi/dk$, the value of one more unit of capacity?
  1. 10 €
  2. 42 €
  3. -104 €
  4. 124 €
Explanation. With $p^* = (a - k)/b = 156$ the profit is $(p^* - c)\,k$, and $dp^*/dk = -1/b$: $d\Pi/dk = (p^* - c) - k/b = 10$. The full margin $p^* - c$ forgets that, to fill the extra seat, the price falls for everybody.

8. Advertising budget allocation (2)

Example 1 · nlpm-g-budget-due-canali · level media · notes
Advertising budget: the spends $x_1, x_2 \ge 0$ (thousands of €) on two channels maximize $r_1(x_1) + r_2(x_2)$ with $r_1(x) = 160\log(1 + 0.25x)$, $r_2(x) = 180\log(1 + 0.25x)$ (natural logarithm), subject to $x_1 + x_2 \le b = 20$, no caps. What are the optimal allocation and the multiplier $\lambda$ of the budget constraint (extra response per extra thousand €)?
  1. $\tilde x_1 = 9.2$, $\tilde x_2 = 10.8$, $\lambda = 12.14$
  2. $\tilde x_1 = 10$, $\tilde x_2 = 10$, $\lambda = 11.43$
  3. $\tilde x_1 = 9.4$, $\tilde x_2 = 10.6$, $\lambda = 11.93$
  4. $\tilde x_1 = 20$, $\tilde x_2 = 0$, $\lambda = 6.67$
Explanation. At the optimum the marginal returns are equal: $40/(1 + 0.25x_1) = 45/(1 + 0.25x_2)$ with $x_1 + x_2 = 20$, so $x_1 = 9.2$; $\lambda$ is the common marginal return, $12.14$. Splitting in proportion to $a_i k_i$ ignores the saturation.
Example 2 · nlpm-g-budget-due-canali · level media · notes
Advertising budget: the spends $x_1, x_2 \ge 0$ (thousands of €) on two channels maximize $r_1(x_1) + r_2(x_2)$ with $r_1(x) = 70\log(1 + 0.2x)$, $r_2(x) = 30\log(1 + 0.5x)$ (natural logarithm), subject to $x_1 + x_2 \le b = 50$, no caps. What are the optimal allocation and the multiplier $\lambda$ of the budget constraint (extra response per extra thousand €)?
  1. $\tilde x_1 = 34.9$, $\tilde x_2 = 15.1$, $\lambda = 1.75$
  2. $\tilde x_1 = 24.1$, $\tilde x_2 = 25.9$, $\lambda = 2.4$
  3. $\tilde x_1 = 25$, $\tilde x_2 = 25$, $\lambda = 2.33$
  4. $\tilde x_1 = 50$, $\tilde x_2 = 0$, $\lambda = 1.27$
Explanation. At the optimum the marginal returns are equal: $14/(1 + 0.2x_1) = 15/(1 + 0.5x_2)$ with $x_1 + x_2 = 50$, so $x_1 = 34.9$; $\lambda$ is the common marginal return, $1.75$. Splitting in proportion to $a_i k_i$ ignores the saturation.
Example 1 · nlpm-g-budget-tetto · level complessa · notes
Advertising budget: the spends $x_1, x_2 \ge 0$ (thousands of €) maximize $r_1(x_1) + r_2(x_2)$, with $r_1(x) = 160\log(1 + 0.25x)$ and $r_2(x) = 180\log(1 + 0.25x)$ (natural logarithm), subject to $x_1 + x_2 \le b = 30$ (multiplier $\lambda$) and the cap $x_1 \le u_1 = 10$ (multiplier $\mu_1$). KKT: $r_i'(\tilde x_i) = \lambda + \mu_i$, with $\mu_2 = 0$. What are the optimal allocation, $\lambda$ and $\mu_1$?
  1. $\tilde x_1 = 10$, $\tilde x_2 = 20$, $\lambda = 7.5$, $\mu_1 = 3.93$
  2. $\tilde x_1 = 10$, $\tilde x_2 = 20$, $\lambda = 7.5$, $\mu_1 = 11.43$
  3. $\tilde x_1 = 13.88$, $\tilde x_2 = 16.12$, $\lambda = 8.95$, $\mu_1 = 0$
  4. $\tilde x_1 = 10$, $\tilde x_2 = 20$, $\lambda = 11.43$, $\mu_1 = 0$
Explanation. Without the cap the marginal returns would be equal at $x_1 = 13.88 > u_1$: the cap binds, $\tilde x_1 = 10$ and $\tilde x_2 = 20$. Channel 2 is interior, so $\lambda = r_2'(20) = 45/(1 + 0.25\cdot 20) = 7.5$; channel 1 gives $\mu_1 = r_1'(10) - \lambda = 11.43 - 7.5 = 3.93$, the value of one more thousand € of cap.
Example 2 · nlpm-g-budget-tetto · level complessa · notes
Advertising budget: the spends $x_1, x_2 \ge 0$ (thousands of €) maximize $r_1(x_1) + r_2(x_2)$, with $r_1(x) = 70\log(1 + 0.2x)$ and $r_2(x) = 30\log(1 + 0.5x)$ (natural logarithm), subject to $x_1 + x_2 \le b = 60$ (multiplier $\lambda$) and the cap $x_1 \le u_1 = 34$ (multiplier $\mu_1$). KKT: $r_i'(\tilde x_i) = \lambda + \mu_i$, with $\mu_2 = 0$. What are the optimal allocation, $\lambda$ and $\mu_1$?
  1. $\tilde x_1 = 34$, $\tilde x_2 = 26$, $\lambda = 1.07$, $\mu_1 = 0.72$
  2. $\tilde x_1 = 34$, $\tilde x_2 = 26$, $\lambda = 1.79$, $\mu_1 = 0$
  3. $\tilde x_1 = 41.9$, $\tilde x_2 = 18.1$, $\lambda = 1.49$, $\mu_1 = 0$
  4. $\tilde x_1 = 34$, $\tilde x_2 = 26$, $\lambda = 1.07$, $\mu_1 = 1.79$
Explanation. Without the cap the marginal returns would be equal at $x_1 = 41.9 > u_1$: the cap binds, $\tilde x_1 = 34$ and $\tilde x_2 = 26$. Channel 2 is interior, so $\lambda = r_2'(26) = 15/(1 + 0.5\cdot 26) = 1.07$; channel 1 gives $\mu_1 = r_1'(34) - \lambda = 1.79 - 1.07 = 0.72$, the value of one more thousand € of cap.

9. Continuous location of a service (2)

Example 1 · nlpm-g-loc-weber-1d · level facile · notes
Location on a straight road: customers at positions $a_i$ with weights $w_i$: km 2 (weight 4), km 12 (weight 5), km 13 (weight 1), km 16 (weight 5), km 18 (weight 1). A facility at position $x$ (km) minimizes the weighted total distance $\sum_i w_i |x - a_i|$ (Weber model on a line). Where is the optimal position $x^*$?
  1. $x^* = 13$ km
  2. $x^* = 10$ km
  3. $x^* = 12$ km
  4. $x^* = 11.2$ km
Explanation. In one dimension Weber is the weighted median: the point that leaves at least half of the total weight ($16/2$) on each side, here km $12$. The centroid ($11.2$) is the optimum of the squared distances, the midpoint of the extremes ($10$) that of the minimax.
Example 2 · nlpm-g-loc-weber-1d · level facile · notes
Location on a straight road: customers at positions $a_i$ with weights $w_i$: km 4 (weight 1), km 9 (weight 3), km 12 (weight 5). A facility at position $x$ (km) minimizes the weighted total distance $\sum_i w_i |x - a_i|$ (Weber model on a line). Where is the optimal position $x^*$?
  1. $x^* = 10.1$ km
  2. $x^* = 9$ km
  3. $x^* = 12$ km
  4. $x^* = 8$ km
Explanation. In one dimension Weber is the weighted median: the point that leaves at least half of the total weight ($9/2$) on each side, here km $12$. The centroid ($10.1$) is the optimum of the squared distances, the midpoint of the extremes ($8$) that of the minimax.
Example 1 · nlpm-g-loc-minimax-2d · level media · notes
Minimax location in the plane: three districts at $(6; 6)$, $(8; 9)$, $(1; 8)$ (km). The facility at $(x, y)$ minimizes $z$, the largest Euclidean distance from it to a district (no weights). What are the optimal point $(x^*; y^*)$ and the optimal value $z^*$?
  1. $(x^*; y^*) = (4.5; 8.5)$, $z^* = 3.54$
  2. $(x^*; y^*) = (4.5; 7.5)$, $z^* = 3.81$
  3. $(x^*; y^*) = (5; 7.67)$, $z^* = 4.01$
  4. $(x^*; y^*) = (4.39; 9.24)$, $z^* = 3.61$
Explanation. The optimum is the centre of the smallest circle containing the three points. The triangle is obtuse: the circle having the longest side as diameter already contains the third point, so the centre is the midpoint of that side and $z^*$ is half its length, $3.54$. The circle through all three points would be larger.
Example 2 · nlpm-g-loc-minimax-2d · level media · notes
Minimax location in the plane: three districts at $(4; 9)$, $(3; 1)$, $(8; 7)$ (km). The facility at $(x, y)$ minimizes $z$, the largest Euclidean distance from it to a district (no weights). What are the optimal point $(x^*; y^*)$ and the optimal value $z^*$?
  1. $(x^*; y^*) = (4.44; 4.88)$, $z^* = 4.14$
  2. $(x^*; y^*) = (5; 5.67)$, $z^* = 5.08$
  3. $(x^*; y^*) = (3.5; 5)$, $z^* = 4.03$
  4. $(x^*; y^*) = (5.5; 5)$, $z^* = 4.72$
Explanation. The optimum is the centre of the smallest circle containing the three points. The triangle is acute: no circle built on one side contains the third point, so the optimum is the circumcentre, equidistant from the three districts, with $z^* = 4.14$. The centroid ignores the extreme districts.

10. Electric vehicle charging with a smooth profile (1)

Example 1 · nlpm-g-evq-due-ore · level media · notes
EV charging with a smooth profile, one vehicle and two hours: it needs $e = 20$ kWh ($\eta = 1$), prices $0.1$ and $0.2$ €/kWh, power limit large enough, zero base load, objective $\pi_1 x_1 + \pi_2 x_2 + \gamma (x_2 - x_1)^2$ with $\gamma = 0.05$ and constraint $x_1 + x_2 \ge 20$. Both hours are used at the optimum. What are $\tilde x_1$ and the multiplier $\lambda$ of the energy constraint?
  1. $\tilde x_1 = 10.5$, $\lambda = 0.15$
  2. $\tilde x_1 = 10.25$, $\lambda = 0.1$
  3. $\tilde x_1 = 20$, $\lambda = 0.1$
  4. $\tilde x_1 = 10.25$, $\lambda = 0.15$
Explanation. With $x_1 = 10 + d$ the objective is linear in $d$ with slope $-0.1$ plus $4\gamma d^2$: $d = (\pi_2 - \pi_1)/(8\gamma)$, so $\tilde x_1 = 10.25$. Stationarity gives $\pi_1 - 2\gamma(x_2 - x_1) = \lambda = \pi_2 + 2\gamma(x_2 - x_1)$, hence $\lambda = (\pi_1 + \pi_2)/2 = 0.15$: the marginal kWh costs the average price.
Example 2 · nlpm-g-evq-due-ore · level media · notes
EV charging with a smooth profile, one vehicle and two hours: it needs $e = 16$ kWh ($\eta = 1$), prices $0.12$ and $0.18$ €/kWh, power limit large enough, zero base load, objective $\pi_1 x_1 + \pi_2 x_2 + \gamma (x_2 - x_1)^2$ with $\gamma = 0.005$ and constraint $x_1 + x_2 \ge 16$. Both hours are used at the optimum. What are $\tilde x_1$ and the multiplier $\lambda$ of the energy constraint?
  1. $\tilde x_1 = 9.5$, $\lambda = 0.15$
  2. $\tilde x_1 = 11$, $\lambda = 0.15$
  3. $\tilde x_1 = 16$, $\lambda = 0.12$
  4. $\tilde x_1 = 9.5$, $\lambda = 0.12$
Explanation. With $x_1 = 8 + d$ the objective is linear in $d$ with slope $-0.06$ plus $4\gamma d^2$: $d = (\pi_2 - \pi_1)/(8\gamma)$, so $\tilde x_1 = 9.5$. Stationarity gives $\pi_1 - 2\gamma(x_2 - x_1) = \lambda = \pi_2 + 2\gamma(x_2 - x_1)$, hence $\lambda = (\pi_1 + \pi_2)/2 = 0.15$: the marginal kWh costs the average price.

11. Service capacity and waiting times (4)

Example 1 · nlpm-g-code-ottimo · level facile · notes
Capacity of an M/M/1 queue: arrival rate $\lambda = 25$ customers/hour; the service rate $\mu > \lambda$ (capacity) minimizes $C(\mu) = c\,\mu + h\,\lambda/(\mu - \lambda)$, where $c = 4$ €/h per unit of $\mu$, $h = 4$ € per hour a customer spends in the system and $\lambda/(\mu - \lambda)$ is the mean number of customers in the system. What are $\mu^*$ and $C(\mu^*)$?
  1. $\mu^* = 26$, $C = 204$ €/h
  2. $\mu^* = 50$, $C = 204$ €/h
  3. $\mu^* = 30$, $C = 140$ €/h
  4. $\mu^* = 27.5$, $C = 150$ €/h
Explanation. From $c - h\lambda/(\mu - \lambda)^2 = 0$: $\mu^* = \lambda + \sqrt{h\lambda/c} = 25 + 5 = 30$, with cost $4\cdot 30 + 4\cdot 25/5 = 140$.
Example 2 · nlpm-g-code-ottimo · level facile · notes
Capacity of an M/M/1 queue: arrival rate $\lambda = 27$ customers/hour; the service rate $\mu > \lambda$ (capacity) minimizes $C(\mu) = c\,\mu + h\,\lambda/(\mu - \lambda)$, where $c = 3$ €/h per unit of $\mu$, $h = 1$ € per hour a customer spends in the system and $\lambda/(\mu - \lambda)$ is the mean number of customers in the system. What are $\mu^*$ and $C(\mu^*)$?
  1. $\mu^* = 36$, $C = 111$ €/h
  2. $\mu^* = 27.58$, $C = 129.5$ €/h
  3. $\mu^* = 28$, $C = 111$ €/h
  4. $\mu^* = 30$, $C = 99$ €/h
Explanation. From $c - h\lambda/(\mu - \lambda)^2 = 0$: $\mu^* = \lambda + \sqrt{h\lambda/c} = 27 + 3 = 30$, with cost $3\cdot 30 + 1\cdot 27/3 = 99$.
Example 1 · nlpm-g-code-misure · level facile · notes
M/M/1 queue (Poisson arrivals, exponential service, one server) with arrival rate $\lambda = 18$ per hour and service rate $\mu = 24$ per hour. What are the utilization $\rho$, the mean time in the system $w$ and the mean number of customers in the system $l$?
  1. $\rho = 75\%$, $w = 2.5$ min, $l = 0.75$
  2. $\rho = 75\%$, $w = 10$ min, $l = 3$
  3. $\rho = 75\%$, $w = 180$ min, $l = 0.17$
  4. $\rho = 75\%$, $w = 10$ min, $l = 4$
Explanation. $\rho = \lambda/\mu$, $w = 1/(\mu - \lambda)$ hours $= 10$ minutes and, by Little's law, $l = \lambda\, w = \lambda/(\mu - \lambda) = 3$. $1/\mu$ is only the mean service time.
Example 2 · nlpm-g-code-misure · level facile · notes
M/M/1 queue (Poisson arrivals, exponential service, one server) with arrival rate $\lambda = 13$ per hour and service rate $\mu = 22$ per hour. What are the utilization $\rho$, the mean time in the system $w$ and the mean number of customers in the system $l$?
  1. $\rho = 59.1\%$, $w = 6.7$ min, $l = 2.44$
  2. $\rho = 59.1\%$, $w = 86.7$ min, $l = 0.11$
  3. $\rho = 59.1\%$, $w = 6.7$ min, $l = 1.44$
  4. $\rho = 59.1\%$, $w = 2.7$ min, $l = 0.59$
Explanation. $\rho = \lambda/\mu$, $w = 1/(\mu - \lambda)$ hours $= 6.7$ minutes and, by Little's law, $l = \lambda\, w = \lambda/(\mu - \lambda) = 1.44$. $1/\mu$ is only the mean service time.
Example 1 · nlpm-g-code-promessa · level media · notes
Capacity of an M/M/1 queue: arrival rate $\lambda = 16$ customers/hour; the service rate $\mu > \lambda$ minimizes $C(\mu) = c\,\mu + h\,\lambda/(\mu - \lambda)$ €/h, with $c = 2$ and $h = 8$; the mean time in the system is $w = 1/(\mu - \lambda)$ hours. Marketing promises $w \le w_{\max} = 6$ minutes. What are the optimal capacity under the promise and its cost $C$?
  1. $\mu = 26$, $C = 64.8$ €/h
  2. $\mu = 26$, $C = 52.8$ €/h
  3. $\mu = 24$, $C = 64$ €/h
  4. $\mu = 22$, $C = 65.33$ €/h
Explanation. Without the promise $\tilde\mu = \lambda + \sqrt{h\lambda/c} = 24$. The promise requires $\mu \ge \lambda + 1/w_{\max} = 16 + 60/6 = 26$ (with $w_{\max}$ in hours), tighter than $\tilde\mu$: since $C$ is convex, the optimum is on the constraint, with $C = 2\cdot 26 + 8\cdot 16\cdot 6/60 = 64.8$ €/h.
Example 2 · nlpm-g-code-promessa · level media · notes
Capacity of an M/M/1 queue: arrival rate $\lambda = 27$ customers/hour; the service rate $\mu > \lambda$ minimizes $C(\mu) = c\,\mu + h\,\lambda/(\mu - \lambda)$ €/h, with $c = 3$ and $h = 1$; the mean time in the system is $w = 1/(\mu - \lambda)$ hours. Marketing promises $w \le w_{\max} = 2$ minutes. What are the optimal capacity under the promise and its cost $C$?
  1. $\mu = 30$, $C = 99$ €/h
  2. $\mu = 29$, $C = 100.5$ €/h
  3. $\mu = 57$, $C = 171.03$ €/h
  4. $\mu = 57$, $C = 171.9$ €/h
Explanation. Without the promise $\tilde\mu = \lambda + \sqrt{h\lambda/c} = 30$. The promise requires $\mu \ge \lambda + 1/w_{\max} = 27 + 60/2 = 57$ (with $w_{\max}$ in hours), tighter than $\tilde\mu$: since $C$ is convex, the optimum is on the constraint, with $C = 3\cdot 57 + 1\cdot 27\cdot 2/60 = 171.9$ €/h.
Example 1 · nlpm-g-code-robusto · level complessa · notes
M/M/1 capacity model: choose the capacity $\mu$ to minimize $C(\mu, \lambda) = c\mu + h\lambda/(\mu - \lambda)$, with $c = 4$ € per unit of capacity and $h = 3$ €/h per customer in the system. The arrival rate is uncertain, $\lambda \in [31, 42]$ per hour, nominal value $36.5$. One sizes $\mu$ to minimize the worst-case cost over the interval. What are the robust $\mu$, its worst-case cost and its premium over the nominal optimal cost $C(\tilde\mu(36.5), 36.5)$?
  1. $\mu = 73.5$, worst-case cost $298$, premium $58.6\%$
  2. $\mu = 41.73$, worst-case cost $187.86$, premium $0\%$
  3. $\mu = 47.61$, worst-case cost $200.3$, premium $6.6\%$
  4. $\mu = 47.61$, worst-case cost $212.9$, premium $13.3\%$
Explanation. For fixed $\mu$ the cost grows with $\lambda$, so the worst case is $\lambda = 42$: $\mu_{\rm rob} = 42 + \sqrt{h\cdot 42/c} = 47.61$, worst-case cost $212.9$. The nominal optimum costs $187.86$: the insurance premium is $13.3\%$. Sizing on the nominal $\tilde\mu = 41.73 < 42$ would make the queue unstable at the top of the interval.
Example 2 · nlpm-g-code-robusto · level complessa · notes
M/M/1 capacity model: choose the capacity $\mu$ to minimize $C(\mu, \lambda) = c\mu + h\lambda/(\mu - \lambda)$, with $c = 2$ € per unit of capacity and $h = 1$ €/h per customer in the system. The arrival rate is uncertain, $\lambda \in [28, 42]$ per hour, nominal value $35$. One sizes $\mu$ to minimize the worst-case cost over the interval. What are the robust $\mu$, its worst-case cost and its premium over the nominal optimal cost $C(\tilde\mu(35), 35)$?
  1. $\mu = 46.58$, worst-case cost $102.33$, premium $18\%$
  2. $\mu = 63$, worst-case cost $128$, premium $47.6\%$
  3. $\mu = 46.58$, worst-case cost $96.19$, premium $10.9\%$
  4. $\mu = 39.18$, worst-case cost $86.73$, premium $0\%$
Explanation. For fixed $\mu$ the cost grows with $\lambda$, so the worst case is $\lambda = 42$: $\mu_{\rm rob} = 42 + \sqrt{h\cdot 42/c} = 46.58$, worst-case cost $102.33$. The nominal optimum costs $86.73$: the insurance premium is $18\%$. Sizing on the nominal $\tilde\mu = 39.18 < 42$ would make the queue unstable at the top of the interval.

12. Support Vector Machine (7)

Example 1 · nlpm-g-svm-due-punti · level facile · notes
Hard-margin SVM: $\min \tfrac12\|\mathbf w\|^2$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1$, with $\mathbf w \in \mathbb R^2$ and $b$ free. Two observations: $\mathbf x_1 = (0; 0)$ with label $y_1 = -1$ and $\mathbf x_2 = (2; 2)$ with label $y_2 = +1$. What are the optimal $\tilde{\mathbf w}$ and the margin $2/\|\tilde{\mathbf w}\|$?
  1. $\mathbf w = (0.25; 0.25)$, margin $5.657$
  2. $\mathbf w = (0.5; 0.5)$, margin $2.828$
  3. $\mathbf w = (2; 2)$, margin $0.707$
  4. $\mathbf w = (0.5; 0.5)$, margin $1.414$
Explanation. Both constraints are active: $b = -1$ and $\mathbf w'\mathbf x_2 + b = 1$; the minimum-norm $\mathbf w$ is parallel to $\mathbf x_2$, $\mathbf w = 2\mathbf x_2/\|\mathbf x_2\|^2$. The margin $2/\|\mathbf w\| = \|\mathbf x_2\| = 2.828$ is the distance between the two points.
Example 2 · nlpm-g-svm-due-punti · level facile · notes
Hard-margin SVM: $\min \tfrac12\|\mathbf w\|^2$ subject to $y_i(\mathbf w'\mathbf x_i + b) \ge 1$, with $\mathbf w \in \mathbb R^2$ and $b$ free. Two observations: $\mathbf x_1 = (0; 0)$ with label $y_1 = -1$ and $\mathbf x_2 = (1; 4)$ with label $y_2 = +1$. What are the optimal $\tilde{\mathbf w}$ and the margin $2/\|\tilde{\mathbf w}\|$?
  1. $\mathbf w = (0.118; 0.471)$, margin $2.062$
  2. $\mathbf w = (1; 4)$, margin $0.485$
  3. $\mathbf w = (0.118; 0.471)$, margin $4.123$
  4. $\mathbf w = (0.059; 0.235)$, margin $8.246$
Explanation. Both constraints are active: $b = -1$ and $\mathbf w'\mathbf x_2 + b = 1$; the minimum-norm $\mathbf w$ is parallel to $\mathbf x_2$, $\mathbf w = 2\mathbf x_2/\|\mathbf x_2\|^2$. The margin $2/\|\mathbf w\| = \|\mathbf x_2\| = 4.123$ is the distance between the two points.
Example 1 · nlpm-g-svm-soft · level media · notes
Soft-margin SVM: objective $\tfrac12\|\mathbf w\|^2 + C\sum_i \xi_i$, where for given $\mathbf w, b$ the optimal slacks are $\xi_i = \max\{0,\ 1 - y_i(\mathbf w'\mathbf x_i + b)\}$. Candidate classifier $\mathbf w = (0; -2)$, $b = 0$, with $C = 1$; observations $\mathbf x_1 = (1; -2)$, $y_1 = +1$; $\mathbf x_2 = (-1; 2)$, $y_2 = -1$; $\mathbf x_3 = (-1; -2)$, $y_3 = -1$; $\mathbf x_4 = (0; 1)$, $y_4 = +1$. What are $\sum_i \xi_i$ and the objective value?
  1. $\sum_i \xi_i = 6$, objective $8$
  2. $\sum_i \xi_i = 8$, objective $12$
  3. $\sum_i \xi_i = 8$, objective $10$
  4. $\sum_i \xi_i = 2$, objective $4$
Explanation. Compute $y_i(\mathbf w'\mathbf x_i + b)$ for each observation: the points with value $\ge 1$ are beyond the margin and pay nothing, the others pay $1 - y_i(\mathbf w'\mathbf x_i + b)$. The slacks sum to $8$ and the objective is $\tfrac12\cdot 4 + 1\cdot 8 = 10$. Dropping the $\max$ lets well-classified points subtract.
Example 2 · nlpm-g-svm-soft · level media · notes
Soft-margin SVM: objective $\tfrac12\|\mathbf w\|^2 + C\sum_i \xi_i$, where for given $\mathbf w, b$ the optimal slacks are $\xi_i = \max\{0,\ 1 - y_i(\mathbf w'\mathbf x_i + b)\}$. Candidate classifier $\mathbf w = (-1; 0)$, $b = 2$, with $C = 2$; observations $\mathbf x_1 = (-2; 1)$, $y_1 = -1$; $\mathbf x_2 = (-2; -2)$, $y_2 = +1$; $\mathbf x_3 = (2; 1)$, $y_3 = -1$; $\mathbf x_4 = (2; -1)$, $y_4 = -1$. What are $\sum_i \xi_i$ and the objective value?
  1. $\sum_i \xi_i = 7$, objective $14.5$
  2. $\sum_i \xi_i = 4$, objective $8.5$
  3. $\sum_i \xi_i = 7$, objective $15$
  4. $\sum_i \xi_i = 5$, objective $10.5$
Explanation. Compute $y_i(\mathbf w'\mathbf x_i + b)$ for each observation: the points with value $\ge 1$ are beyond the margin and pay nothing, the others pay $1 - y_i(\mathbf w'\mathbf x_i + b)$. The slacks sum to $7$ and the objective is $\tfrac12\cdot 1 + 2\cdot 7 = 14.5$. Dropping the $\max$ lets well-classified points subtract.
Example 1 · nlpm-g-svm-margine · level facile · notes
SVM for binary classification: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. A trained SVM has $\mathbf w = (1; 1)$ and $b = 5$; its margin lines are $\mathbf w'\mathbf x + b = \pm 1$. What are the margin (the distance between the two margin lines) and the distance of the point $\mathbf x_0 = (3; -4)$ from the hyperplane?
  1. margin $1.414$, distance $2.828$
  2. margin $1.414$, distance $4$
  3. margin $0.707$, distance $2.828$
  4. margin $1$, distance $2.828$
Explanation. $\|\mathbf w\| = \sqrt{2} = 1.414$: the margin is $2/\|\mathbf w\| = 1.414$; the distance of $\mathbf x_0$ is $|\mathbf w'\mathbf x_0 + b|/\|\mathbf w\| = 4/1.414 = 2.828$. Forgetting to divide by $\|\mathbf w\|$ is the typical mistake.
Example 2 · nlpm-g-svm-margine · level facile · notes
SVM for binary classification: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. A trained SVM has $\mathbf w = (-2; 4)$ and $b = -3$; its margin lines are $\mathbf w'\mathbf x + b = \pm 1$. What are the margin (the distance between the two margin lines) and the distance of the point $\mathbf x_0 = (-4; -1)$ from the hyperplane?
  1. margin $0.447$, distance $0.224$
  2. margin $0.224$, distance $0.224$
  3. margin $0.447$, distance $1$
  4. margin $0.1$, distance $0.224$
Explanation. $\|\mathbf w\| = \sqrt{20} = 4.472$: the margin is $2/\|\mathbf w\| = 0.447$; the distance of $\mathbf x_0$ is $|\mathbf w'\mathbf x_0 + b|/\|\mathbf w\| = 1/4.472 = 0.224$. Forgetting to divide by $\|\mathbf w\|$ is the typical mistake.
Example 1 · nlpm-g-svm-duale-w · level facile · notes
SVM for binary classification: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. In the dual of the soft margin ($\max\ \sum_i\alpha_i - \tfrac12\sum_i\sum_j\alpha_i\alpha_jy_iy_j\mathbf x_i'\mathbf x_j$, $\sum_i\alpha_iy_i = 0$, $0 \le \alpha_i \le C$) only three points have $\tilde\alpha_i > 0$: $\mathbf x_1 = (1; 1)$, $y_1 = +1$, $\tilde\alpha_1 = 1.5$; $\mathbf x_2 = (3; 3)$, $y_2 = +1$, $\tilde\alpha_2 = 1.5$; $\mathbf x_3 = (-3; 3)$, $y_3 = -1$, $\tilde\alpha_3 = 3$. What is the optimal $\tilde{\mathbf w}$ of the primal?
  1. $\tilde{\mathbf w} = (-15; 3)$
  2. $\tilde{\mathbf w} = (-3; 15)$
  3. $\tilde{\mathbf w} = (15; -3)$
  4. $\tilde{\mathbf w} = (6; 6)$
Explanation. Primal–dual relation: $\tilde{\mathbf w} = \sum_i\tilde\alpha_iy_i\mathbf x_i$, a sum over the support vectors only, with the sign of the labels: $1.5\,\mathbf x_1 + 1.5\,\mathbf x_2 - 3\,\mathbf x_3 = (15; -3)$. Forgetting the labels $y_i$ is the typical mistake.
Example 2 · nlpm-g-svm-duale-w · level facile · notes
SVM for binary classification: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. In the dual of the soft margin ($\max\ \sum_i\alpha_i - \tfrac12\sum_i\sum_j\alpha_i\alpha_jy_iy_j\mathbf x_i'\mathbf x_j$, $\sum_i\alpha_iy_i = 0$, $0 \le \alpha_i \le C$) only three points have $\tilde\alpha_i > 0$: $\mathbf x_1 = (4; 3)$, $y_1 = +1$, $\tilde\alpha_1 = 2$; $\mathbf x_2 = (2; 3)$, $y_2 = +1$, $\tilde\alpha_2 = 2$; $\mathbf x_3 = (3; -2)$, $y_3 = -1$, $\tilde\alpha_3 = 4$. What is the optimal $\tilde{\mathbf w}$ of the primal?
  1. $\tilde{\mathbf w} = (24; 4)$
  2. $\tilde{\mathbf w} = (0; 20)$
  3. $\tilde{\mathbf w} = (12; 12)$
  4. $\tilde{\mathbf w} = (0; -20)$
Explanation. Primal–dual relation: $\tilde{\mathbf w} = \sum_i\tilde\alpha_iy_i\mathbf x_i$, a sum over the support vectors only, with the sign of the labels: $2\,\mathbf x_1 + 2\,\mathbf x_2 - 4\,\mathbf x_3 = (0; 20)$. Forgetting the labels $y_i$ is the typical mistake.
Example 1 · nlpm-g-svm-rbf-valore · level facile · notes
SVM for binary classification: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. With the RBF (Gaussian) kernel $K(\mathbf x, \mathbf z) = e^{-\gamma\|\mathbf x - \mathbf z\|^2}$ and $\gamma = 0.5$, what is $K(\mathbf x, \mathbf z)$ for $\mathbf x = (4; 2)$ and $\mathbf z = (3; 1)$?
  1. $K = 0.018$
  2. $K = 0.607$
  3. $K = 0.368$
  4. $K = 0.493$
Explanation. $\|\mathbf x - \mathbf z\|^2 = 2$ (the squared distance, not the distance), so $K = e^{-0.5\cdot 2} = 0.368$. Points far apart give $K$ close to 0, coincident points $K = 1$; a larger $\gamma$ makes the kernel more local.
Example 2 · nlpm-g-svm-rbf-valore · level facile · notes
SVM for binary classification: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. With the RBF (Gaussian) kernel $K(\mathbf x, \mathbf z) = e^{-\gamma\|\mathbf x - \mathbf z\|^2}$ and $\gamma = 0.5$, what is $K(\mathbf x, \mathbf z)$ for $\mathbf x = (4; 3)$ and $\mathbf z = (3; 4)$?
  1. $K = 0.368$
  2. $K = 0.493$
  3. $K = 0.607$
  4. $K = 0.018$
Explanation. $\|\mathbf x - \mathbf z\|^2 = 2$ (the squared distance, not the distance), so $K = e^{-0.5\cdot 2} = 0.368$. Points far apart give $K$ close to 0, coincident points $K = 1$; a larger $\gamma$ makes the kernel more local.
Example 1 · nlpm-g-svr-tubo · level facile · notes
Support Vector Regression: errors within a tube $|y_i - \hat y_i| \le \varepsilon$ cost nothing, those outside pay $|y_i - \hat y_i| - \varepsilon$ (the slacks $\xi_i$, $\xi_i^*$). The estimated line is $\hat y = -8x + 210$, with $\varepsilon = 7$; the observations $(x_i; y_i)$ are (2; 205), (9; 124), (10; 141), (11; 113), (13; 99). How many points fall outside the tube, and what is their total penalty $\sum_i(\xi_i + \xi_i^*)$?
  1. $4$ points outside, penalty $45$
  2. $1$ points outside, penalty $17$
  3. $1$ points outside, penalty $45$
  4. $4$ points outside, penalty $17$
Explanation. Residuals $y_i - \hat y_i$: $11$, $-14$, $11$, $-9$, $-7$. Those with $|r_i| > 7$ are 4; each pays only the part beyond the tube, $|r_i| - 7$, for a total of $17$. Paying the whole residual gives $45$.
Example 2 · nlpm-g-svr-tubo · level facile · notes
Support Vector Regression: errors within a tube $|y_i - \hat y_i| \le \varepsilon$ cost nothing, those outside pay $|y_i - \hat y_i| - \varepsilon$ (the slacks $\xi_i$, $\xi_i^*$). The estimated line is $\hat y = -6x + 240$, with $\varepsilon = 4$; the observations $(x_i; y_i)$ are (1; 241), (7; 202), (10; 183), (13; 168), (14; 161). How many points fall outside the tube, and what is their total penalty $\sum_i(\xi_i + \xi_i^*)$?
  1. $2$ points outside, penalty $18$
  2. $3$ points outside, penalty $18$
  3. $2$ points outside, penalty $6$
  4. $3$ points outside, penalty $6$
Explanation. Residuals $y_i - \hat y_i$: $7$, $4$, $3$, $6$, $5$. Those with $|r_i| > 4$ are 3; each pays only the part beyond the tube, $|r_i| - 4$, for a total of $6$. Paying the whole residual gives $18$.
Example 1 · nlpm-g-svm-duale-b · level media · notes
SVM for binary classification: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. A soft-margin SVM (dual multipliers $0 \le \alpha_i \le C$) gives $\tilde{\mathbf w} = (0; 1)$. The point $\mathbf x_k = (2; 3)$ with label $y_k = -1$ has $0 < \tilde\alpha_k < C$. What are the intercept $\tilde b$ and the score $f(\mathbf x_0) = \tilde{\mathbf w}'\mathbf x_0 + \tilde b$ of $\mathbf x_0 = (2; 1)$?
  1. $\tilde b = -3$, $f(\mathbf x_0) = -2$
  2. $\tilde b = -4$, $f(\mathbf x_0) = -3$
  3. $\tilde b = 4$, $f(\mathbf x_0) = 5$
  4. $\tilde b = -2$, $f(\mathbf x_0) = -1$
Explanation. $0 < \tilde\alpha_k < C$ means $\mathbf x_k$ lies exactly on its margin line: $y_k(\tilde{\mathbf w}'\mathbf x_k + b) = 1$, so $\tilde b = y_k - \tilde{\mathbf w}'\mathbf x_k = -4$ (since $1/y_k = y_k$). Then $f(\mathbf x_0) = -3$: $\mathbf x_0$ is assigned to class $-1$.
Example 2 · nlpm-g-svm-duale-b · level media · notes
SVM for binary classification: observations $\mathbf x_i$ with labels $y_i \in \{-1, +1\}$, hyperplane $\mathbf w'\mathbf x + b = 0$. A soft-margin SVM (dual multipliers $0 \le \alpha_i \le C$) gives $\tilde{\mathbf w} = (-1; 2)$. The point $\mathbf x_k = (-1; -3)$ with label $y_k = -1$ has $0 < \tilde\alpha_k < C$. What are the intercept $\tilde b$ and the score $f(\mathbf x_0) = \tilde{\mathbf w}'\mathbf x_0 + \tilde b$ of $\mathbf x_0 = (3; 2)$?
  1. $\tilde b = 4$, $f(\mathbf x_0) = 5$
  2. $\tilde b = 5$, $f(\mathbf x_0) = 6$
  3. $\tilde b = -4$, $f(\mathbf x_0) = -3$
  4. $\tilde b = 6$, $f(\mathbf x_0) = 7$
Explanation. $0 < \tilde\alpha_k < C$ means $\mathbf x_k$ lies exactly on its margin line: $y_k(\tilde{\mathbf w}'\mathbf x_k + b) = 1$, so $\tilde b = y_k - \tilde{\mathbf w}'\mathbf x_k = 4$ (since $1/y_k = y_k$). Then $f(\mathbf x_0) = 5$: $\mathbf x_0$ is assigned to class $+1$.

13. Least-squares regression (1)

Example 1 · nlpm-g-ls-media · level facile · notes
Least squares without features: $\min \sum_i r_i^2$ subject to $b + r_i = y_i$, with $b$ and $r_i$ free, on the five observations $y = (145, 130, 130, 151, 81)$. What are the optimal intercept $\tilde b$ and the multiplier $\tilde\pi$ of the constraint of the largest observation ($y = 151$)?
  1. $\tilde b = 130$, $\tilde\pi = 42$
  2. $\tilde b = 127.4$, $\tilde\pi = 23.6$
  3. $\tilde b = 127.4$, $\tilde\pi = 47.2$
  4. $\tilde b = 130$, $\tilde\pi = 47.2$
Explanation. Stationarity in $b$ gives $\sum_i r_i = 0$: $\tilde b$ is the mean, $127.4$. Stationarity in $r_i$ gives $\pi_i = 2 r_i$: for $y = 151$ the residual is $23.6$ and $\tilde\pi = 47.2$. The median $130$ would be the optimum of absolute deviations.
Example 2 · nlpm-g-ls-media · level facile · notes
Least squares without features: $\min \sum_i r_i^2$ subject to $b + r_i = y_i$, with $b$ and $r_i$ free, on the five observations $y = (110, 148, 105, 87, 112)$. What are the optimal intercept $\tilde b$ and the multiplier $\tilde\pi$ of the constraint of the largest observation ($y = 148$)?
  1. $\tilde b = 112.4$, $\tilde\pi = 71.2$
  2. $\tilde b = 110$, $\tilde\pi = 76$
  3. $\tilde b = 112.4$, $\tilde\pi = 35.6$
  4. $\tilde b = 110$, $\tilde\pi = 71.2$
Explanation. Stationarity in $b$ gives $\sum_i r_i = 0$: $\tilde b$ is the mean, $112.4$. Stationarity in $r_i$ gives $\pi_i = 2 r_i$: for $y = 148$ the residual is $35.6$ and $\tilde\pi = 71.2$. The median $110$ would be the optimum of absolute deviations.