In the notation used throughout the lab notes, how is the value of the variable $x_j$ in an *optimal* solution of a model written?
With a bar, $\bar x_j$
With a tilde, $\tilde x_j$
With an asterisk, $x_j^*$
With a hat, $\hat x_j$
Explanation. In the notes the bar marks the values of a feasible solution and the tilde those of an optimal one ($\tilde x_j$, $\tilde z$); the asterisk is not used for the solutions of the models.
In the notation of the lab notes, which symbols denote, in this order, the dual variable of constraint $i$, the reduced cost of variable $x_j$ and the slack of constraint $i$ (in a feasible solution)?
$\bar\pi_i$, $\bar c_j$, $\bar s_i$
$\bar y_i$, $\bar r_j$, $\bar s_i$
$\bar\lambda_i$, $\bar\pi_j$, $\bar u_i$
$\bar y_i$, $\bar c_j$, $\bar\xi_i$
Explanation. Dual variables are always $\pi_i$ (never $y$), reduced costs $\bar c_j$ and slacks $\bar s_i$, with the bar for a feasible solution and the tilde for an optimal one.
Every application chapter of the lab notes follows the same eight-step outline. In which step is a minimal instance solved by hand, before turning on the solver?
Guided construction of the model (step 2)
Case study with reproducible CSV data (step 4)
Worked numerical example (step 3)
Sensitivity analysis (step 7)
Explanation. The outline is: motivation, guided construction, worked example by hand, case study, Python/Gurobi code, results, sensitivity, exercises.
The lab 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?
What is the optimal value of the model?
Which solver finds the optimum fastest?
Which decision do we recommend, and how robust is it?
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.
In the lab a solved model is not only read but *interrogated*. Which of these is an example of interrogating a production plan?
How much is one more hour of capacity worth?
How many simplex iterations did Gurobi need?
Which Python version ran the script?
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.
Every application chapter of the notes follows an eight-step outline. In the step “Results”, what happens to the output of the solver?
It is used to build a second, larger model
It is translated into managerial language
It is copied unchanged into the report
It is compared with the output of another solver
Explanation. The steps are: motivation, guided construction, worked example by hand, case study, Python/Gurobi code, results (the output in managerial language), sensitivity, exercises.
All the numbers of the case studies in the notes are produced by the Python scripts of the course. If you change the data of a case study, what must be done?
Nothing: the numbers in the notes do not depend on the data
Edit the numbers in the notes by hand
Re-run the scripts, which regenerate data, tables and figures
Switch to the academic licence of Gurobi
Explanation. The scripts regenerate data, results and figures: changed data mean regenerated numbers, never hand-edited ones.
The lab uses mathematical programming as a *decision* tool. According to the notes, where does the value of a model lie?
In the precision of the optimal value it computes
In the speed of the solver that solves it
In the quality of the recommendation it makes possible
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.
After solving a lab model we *interrogate* it with three kinds of questions: marginal value, robustness, compromise. Which question is about **robustness**?
Does the solution hold if the data change by 5%?
How much is one more hour of capacity worth?
Which compromise would we advise the decision maker?
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.
In the lab notes the objects of a model (products, channels, assets, scenarios) are numbered. How are the index sets written?
Enumerated explicitly, e.g. $i \in \{1, 2, \dots, n\}$
As abstract sets with no numbering, e.g. $i \in I$
Only with the counter $n$, never with a set
As sets of names (strings) read from the data
Explanation. Indices run over explicitly enumerated sets, so the text already uses the notation of the built model; the only non-enumerated sets are those of a graph $G = (N, A)$.
Every model of the lab notes is written with the same layout: variables introduced first, numbered objective and constraint families, a description family by family. What closes each formulation?
The objective function, written last
The list of the data with their units
The sign constraints, which define the variables
The value of the optimal solution, if known
Explanation. By convention the nonnegativity constraints close the model, since they define the variables; after the model a list describes objective and constraints, with the number of constraints of each family.
The lab uses only continuous variables; one of the three reasons is *coverage*: many real decisions are naturally continuous. Which list contains only decisions of this kind?
Opening a plant, choosing one site out of five, number of trucks
Shift assignments, routes of a vehicle, yes/no investments
Number of servers, number of batches, on/off of a machine
Explanation. Quantities, flows, shares, prices, powers and coordinates are the examples of the notes; opening, choosing, counting or switching on/off are yes/no or integer decisions.
Every application chapter of the lab notes follows the same eight steps. What does the step «Case study» contain?
A minimal instance solved by hand, step by step
A realistic instance with data in CSV files
The complete Python code, commented
Exercises from verification to small extensions
Explanation. The case study is a realistic instance whose data are in CSV files; the minimal instance is the hand-worked example (step 3), the code is the implementation (step 5).
In the course LP Modelling all the models are LPs. Why is every local optimum of an LP also global?
Because an LP is a convex problem
Because an LP always has a unique optimum
Because the variables of an LP are integer
Because the region of an LP is always bounded
Explanation. An LP is always convex: linear objective and polyhedral feasible region. Hence every local optimum is global; the optimum need not be unique and the region may be unbounded.
Which module of the series is the prerequisite of the course LP Modelling?
Combinatorial Optimization
Heuristic Algorithms
Linear Programming
Dynamic Programming
Explanation. The prerequisite is the module Linear Programming, in particular duality and sensitivity analysis, which the course uses in every chapter.
In the map of the models of the LP Modelling notes, which application is a scenario-based stochastic LP?
Multi-period production and inventory
Data Envelopment Analysis
Electric vehicle charging
Newsvendor and variants
Explanation. The newsvendor decides the quantity before knowing the demand: in the scenario formulation it is a stochastic LP. The other three are deterministic LPs.
In the map of the models of the LP Modelling notes, which central concept goes with arbitrage and pricing?
The duality that prices
Tail risk
Relative efficiency
Deciding before knowing
Explanation. In the arbitrage chapter the duals of the LP are the risk-neutral probabilities that price every security: the duality that prices. The other concepts belong to CVaR, DEA and the newsvendor.
In the map of the models of the LP Modelling notes, which application has «relative efficiency» as its central concept?
Multi-period production and inventory
VaR and CVaR
Data Envelopment Analysis
Robust and quantile regression
Explanation. DEA compares units (branches) that use inputs to produce outputs and measures the efficiency of each one with respect to the others: relative efficiency.
The LP Modelling notes use continuous variables only. Which tool would be lost or weakened with binary variables?
Duality with shadow prices
Writing the data as CSV
Using Python and Gurobi
Printing the figures
Explanation. The teaching motivation: with continuous variables duality, shadow prices and reduced costs hold, and they turn a numerical solution into an economic explanation.
The essential path of the course LP Modelling consists of four lab sessions. What is the topic of the second one?
Electric vehicle charging
Data Envelopment Analysis
Arbitrage and pricing
Robust and quantile regression
Explanation. The four sessions: (1) production and inventory, (2) DEA and the envelopment form, (3) scenario-based decisions (newsvendor or CVaR), (4) a project of your choice.
In the four-session essential path of the course LP Modelling, what is covered in the third session?
DEA and the envelopment form
Production and inventory with shadow prices
Scenario decisions: newsvendor or CVaR
A project of your choice
Explanation. The third session is devoted to scenario-based decisions, with the newsvendor or the CVaR; DEA and production are the second and the first, the project the fourth.
According to the LP Modelling notes, what is the right question at the end of every lab session?
Which decision do we recommend and how robust is it?
How long does the solver take to find the optimum?
How many variables and constraints does the model have?
Which programming language is the fastest?
Explanation. The value of a model lies in the quality of the recommendation: the optimum is not enough, we need a decision to recommend and its robustness.
According to the *coverage* reason of the LP Modelling notes, which decisions are continuous by nature?
Opening or closing a plant
Power levels, flows and portfolio weights
Assigning a shift to every employee
The visiting order of a tour of cities
Explanation. Many real decisions are continuous quantities: quantities, flows, portfolio weights, power levels, weights. Opening a plant, assigning shifts or ordering visits require integer variables instead.
In the four-session essential path of the course LP Modelling, what is the topic of the first session?
Production and inventory, with shadow prices
DEA and its envelopment form
The newsvendor in the scenario formulation
Arbitrage and the pricing of securities
Explanation. The first session is on production and inventory: a multi-period LP, the duals of capacity and the check of a shadow price by perturbation.
In the LP Modelling notes, which set does a count such as the number $n$ of products belong to?
$\mathbb{Q}_{>0}$
$\mathbb{Z}_{\ge 1}$
$\mathbb{R}$
$\{0, 1\}$
Explanation. Counts are positive integers, $n \in \mathbb{Z}_{\ge 1}$; numerical data are rational instead ($\mathbb{Q}_{\ge 0}$ or $\mathbb{Q}_{>0}$).
Duality rules of LP. In a maximization primal, the equality constraint $\sum_{j} a_{ij} x_j = b_i$ generates in the dual a variable $\pi_i$ that is:
non-negative, $\pi_i \ge 0$
non-positive, $\pi_i \le 0$
free, $\pi_i \gtreqless 0$
fixed at $\pi_i = 0$
Explanation. By the duality rules, equality constraints of the primal give free dual variables (and free primal variables give dual equality constraints).
Primal $\max \sum_j c_jx_j$ subject to $\sum_j a_{ij}x_j \le b_i$ ($i = 1, \dots, m$), with dual variables $\pi_i \ge 0$. Which dual constraint does a variable $x_j \ge 0$ generate?
$\sum_{i} a_{ij}\pi_i \ge c_j$
$\sum_{i} a_{ij}\pi_i \le c_j$
$\sum_{i} a_{ij}\pi_i = c_j$
$\sum_{i} a_{ij}\pi_i \ge b_i$
Explanation. The dual constraint of $x_j$ has as coefficients the column of $x_j$ and as right-hand side $c_j$; a non-negative variable of a maximization gives a $\ge$ constraint in the (minimization) dual.
In a **minimization** LP with optimal value $\tilde z$, the shadow price of constraint $i$ is $\tilde\pi_i = \partial\tilde z/\partial b_i$. What is its sign for an active requirement $\sum_j a_{ij}x_j \ge b_i$?
$\tilde\pi_i \le 0$
$\tilde\pi_i \ge 0$
Any sign, depending on the data
Always $\tilde\pi_i = 0$
Explanation. Increasing $b_i$ shrinks the feasible region, and a narrower region cannot lower the minimum: $\tilde\pi_i \ge 0$, the marginal cost of the requirement.
At the optimum of an LP, constraint $i$ has slack $\bar s_i > 0$ (it is not active). What is its shadow price $\tilde\pi_i$ (rate of change of the optimal value with $b_i$)?
$\tilde\pi_i = \bar s_i$
$\tilde\pi_i = -\bar s_i$
It depends on the sign of $b_i$
$\tilde\pi_i = 0$
Explanation. By complementary slackness $\tilde\pi_i\,\bar s_i = 0$: a resource left over is worth nothing at the margin.
LP $\max \sum_j c_jx_j$ subject to $\sum_j a_{ij}x_j \le b_i$, $x \ge 0$, and dual values $\bar\pi_i$. How is the reduced cost $\bar c_j$ of the variable $x_j$ defined?
$\bar c_j = c_j - \sum_{i} a_{ij}\,\bar\pi_i$
$\bar c_j = \sum_{i} a_{ij}\,\bar\pi_i - b_i$
$\bar c_j = c_j - \sum_{i} a_{ij}\,\bar x_j$
$\bar c_j = c_j - b_i\,\bar\pi_i$
Explanation. The reduced cost is the slack of the dual constraint of $x_j$: the coefficient $c_j$ net of the value, at the dual prices, of the resources consumed by one unit of $x_j$.
At the optimum of an LP the variable $x_j$ is at zero, $\tilde x_j = 0$, and its reduced cost is also zero, $\bar c_j = 0$. What can be concluded?
$x_j$ is positive in every other optimal solution
The LP is infeasible or unbounded
Nothing certain: under degeneracy this can happen
Its objective coefficient $c_j$ is zero
Explanation. Only the implication $\bar c_j \ne 0 \Rightarrow \tilde x_j$ on a bound holds, not the converse: a null reduced cost does not say that the variable is used (degeneracy, alternative optima).
The LP $\max\,30x_1 + 50x_2$ (two constraints) has optimal value $\tilde z = 1900$. Constraint 1 has right-hand side $b_1 = 90$, shadow price $\tilde\pi_1 = 14$ and validity range $[40, 240]$ (the values of $b_1$ for which $\tilde\pi_1$ stays the same). What is the optimal value if $b_1 = 100$?
$1914$
$2040$
$1900$
$3300$
Explanation. $100$ lies inside the validity range, so the shadow price is exact: $1900 + (100 - 90) \cdot 14 = 2040$.
Primal (P) $\max \sum_j c_jx_j$ subject to $\sum_j a_{ij}x_j \le b_i$, $x \ge 0$; dual (D) $\min \sum_i b_i\pi_i$ subject to $\sum_i a_{ij}\pi_i \ge c_j$, $\pi \ge 0$. Which statement is the weak duality theorem?
For all feasible $\bar x$ of (P) and $\bar\pi$ of (D): $\sum_{j} c_j\bar x_j \le \sum_{i} b_i\bar\pi_i$
For all feasible $\bar x$ of (P) and $\bar\pi$ of (D): $\sum_{j} c_j\bar x_j \ge \sum_{i} b_i\bar\pi_i$
For all feasible $\bar x$ of (P) and $\bar\pi$ of (D): $\sum_{j} c_j\bar x_j = \sum_{i} b_i\bar\pi_i$
If (P) has a feasible solution, then (D) also has a feasible solution
Explanation. Every feasible solution of the dual gives an upper bound on the value of the maximization primal. Equality holds only for optimal pairs (strong duality).
Let (P) be a maximization LP and (D) its minimization dual. Which statement is the strong duality theorem?
If (P) and (D) are both feasible, every pair of feasible solutions has the same value
If (P) has an optimal solution, it is unique, and so is the optimal solution of (D)
(P) has an optimal solution if and only if (D) has one, and then the optimal values coincide
If both have optimal solutions, the optimal value of (D) is strictly larger than that of (P)
Explanation. Strong duality: an optimum of one problem exists exactly when an optimum of the other exists, and the gap closes. Existence does not mean uniqueness.
Primal $\max\{\sum_j c_jx_j : \sum_j a_{ij}x_j \le b_i,\ x \ge 0\}$; for feasible $\bar x$ and dual-feasible $\bar\pi$ let $\bar s_i = b_i - \sum_j a_{ij}\bar x_j$ (slacks) and $\bar c_j = c_j - \sum_i a_{ij}\bar\pi_i$ (reduced costs). The pair is optimal if and only if:
$\bar\pi_i + \bar s_i = 0$ for every $i$ and $\bar x_j + \bar c_j = 0$ for every $j$
$\bar s_i = 0$ for every $i$ and $\bar c_j = 0$ for every $j$
$\bar s_i > 0 \Leftrightarrow \bar\pi_i = 0$ for every $i$ and $\bar x_j > 0 \Leftrightarrow \bar c_j = 0$ for every $j$
$\bar\pi_i\,\bar s_i = 0$ for every $i$ and $\bar x_j\,\bar c_j = 0$ for every $j$
Explanation. These are the complementary slackness conditions. They give implications (slack constraint $\Rightarrow$ null dual), not equivalences: degeneracy is allowed, so the third option is too strong.
To prove weak duality for (P) $\max\{\sum_j c_jx_j : \sum_j a_{ij}x_j \le b_i,\ x \ge 0\}$ and its dual (D), with $\bar x$ feasible for (P) and $\bar\pi$ for (D), one uses the chain $\sum_j c_j\bar x_j \le \sum_j\sum_i a_{ij}\bar\pi_i\bar x_j \le \sum_i b_i\bar\pi_i$. Which facts are needed?
Complementary slackness at $(\bar x, \bar\pi)$ and strong duality
Optimality of $\bar x$ for (P) and uniqueness of $\bar\pi$
Existence of an optimal solution of both (P) and (D)
Explanation. Only feasibility of the two solutions is used: dual feasibility multiplied by $\bar x \ge 0$, then primal feasibility multiplied by $\bar\pi \ge 0$. No optimality or strong duality is involved.
In a **minimization** LP with optimal value $\tilde z$, the shadow price $\tilde\pi_i = \partial\tilde z/\partial b_i$ of a capacity constraint $\sum_j a_{ij}x_j \le b_i$ satisfies $\tilde\pi_i \le 0$. Which facts give this sign?
The constraint is active at the optimum and its slack is zero
Raising $b_i$ enlarges the region, and a larger region never raises the minimum
Strong duality and the non-negativity of all the variables
The reduced costs of the basic variables are zero at the optimum
Explanation. The sign of $\tilde\pi_i$ always follows from two questions: does raising $b_i$ enlarge or shrink the feasible region? A wider region never worsens the optimum.
Every chapter of the lab ends with the same six-step sensitivity protocol. What does step 3, devoted to shadow prices and reduced costs, prescribe?
Build three scenarios (pessimistic, central, optimistic) and compare the plans
Vary a weight in the objective and trace a cost-service frontier
Check each dual against a re-optimization after a small perturbation, and read the reduced costs
Flag the abrupt changes of the optimal mix as the data vary
Explanation. Step 3 verifies the duals by perturbation and reads the reduced cost of every variable at zero; scenarios are step 4, trade-offs step 5, stability step 6.
Duality rules for LPs. What is the dual of $\max\ 30x_1 + 50x_2$ subject to $x_1 + 3x_2 \le 90$, $2x_1 + x_2 \le 80$, $x_1, x_2 \ge 0$ (one dual variable $\pi_i$ per constraint)?
Explanation. Two $\le$ constraints in a maximum give $\pi_1, \pi_2 \ge 0$; each variable $x_j \ge 0$ gives a $\ge c_j$ constraint whose coefficients are the *columns* of the primal; the right-hand sides $(90, 80)$ become the costs of a minimum. Using the rows is the typical mistake.
Duality rules for LPs, read for a **minimization** primal (the table is read from right to left). Which sign has the dual variable $\pi_i$ of a constraint $\sum_j a_{ij}x_j \le b_i$?
$\pi_i \ge 0$
$\pi_i$ free
$\pi_i \le 0$
It depends on the sign of $b_i$
Explanation. In a minimum a $\ge$ constraint gives $\pi_i \ge 0$, an equality a free $\pi_i$, a $\le$ constraint $\pi_i \le 0$ (as in the «all cases» LP of the notes, where $\tilde\pi_3 = -1$).
Let (P) be a maximization LP and (D) its minimization dual. (P) is feasible and **unbounded** (its objective grows without limit). What does weak duality imply for (D)?
(D) is infeasible
(D) is unbounded too
(D) has an optimal value $+\infty$ attained at a vertex
Nothing: weak duality concerns only optimal solutions
Explanation. Weak duality says that every feasible $\bar\pi$ of (D) gives an upper bound $\sum_i b_i\bar\pi_i$ on every primal value: if the primal values are unbounded, no such bound exists, so (D) has no feasible solution.
The strong duality theorem says: (P) has an optimal solution if and only if (D) has one, and then the optimal values coincide. Its hypothesis is that (P) **has an optimum**. If instead (P) is infeasible, what can be said of (D)?
(D) has an optimum, with value 0
(D) is always unbounded, never infeasible
(D) is always infeasible as well
(D) is infeasible or unbounded
Explanation. Without an optimum of (P) the theorem says only that (D) has no optimum either: (D) can be unbounded or itself infeasible (there are pairs of LPs that are both infeasible).
Complementary slackness for an LP: $\bar\pi_i\bar s_i = 0$ (dual value times slack of constraint $i$) and $\bar x_j\bar c_j = 0$ (variable times reduced cost). At the optimum, which implication **always** holds?
$\bar\pi_i = 0$ $\Rightarrow$ the constraint is slack
Variable at zero ($\bar x_j = 0$) $\Rightarrow$ $\bar c_j \ne 0$
Active constraint ($\bar s_i = 0$) $\Rightarrow$ $\bar\pi_i \ne 0$
Explanation. The conditions are implications, not equivalences: a slack constraint has zero dual and a nonzero variable has zero reduced cost. Because of degeneracy an active constraint can have a zero dual, and a variable at zero a zero reduced cost.
For an LP, $\bar x$ and $\bar\pi$ satisfy $\bar\pi_i\bar s_i = 0$ for every constraint $i$ and $\bar x_j\bar c_j = 0$ for every variable $j$ ($\bar s_i$ slacks, $\bar c_j$ reduced costs). What else is needed to conclude that both are optimal?
That $\bar x$ is feasible for (P) and $\bar\pi$ for (D)
That every constraint of the primal is active
Explanation. The theorem is about a pair of **feasible** solutions: feasibility plus complementary slackness gives equal objective values, hence optimality by weak duality. An infeasible pair can satisfy the products and be far from optimal.
(P) is a maximization LP and (D) its dual. A feasible $\bar x$ of (P) and a feasible $\bar\pi$ of (D) have the **same** objective value, $\sum_j c_j\bar x_j = \sum_i b_i\bar\pi_i$. What follows?
Nothing, unless strong duality is checked first
Both are optimal, by weak duality
Only $\bar x$ is optimal; $\bar\pi$ may not be
The two problems have unique optimal solutions
Explanation. By weak duality every primal value is $\le \sum_i b_i\bar\pi_i$, which $\bar x$ attains: $\bar x$ is optimal, and symmetrically $\bar\pi$. Equal values certify optimality; uniqueness is not implied.
LP sensitivity analysis: what does the validity interval $[c_j^{\min}, c_j^{\max}]$ of the objective coefficient $c_j$ (Gurobi attributes `SAObjLow`–`SAObjUp`) mean?
Varying only $c_j$ in it, the optimal value does not change
Varying only $c_j$ in it, the shadow prices do not change
Varying only $c_j$ in it, the optimal solution does not change
Varying only $c_j$ in it, $x_j$ stays strictly positive
Explanation. It is the largest interval in which, changing only $c_j$, the optimal solution stays the same; the optimal value does change (by $\tilde x_j$ per unit of $c_j$). For a variable at zero one endpoint is the threshold at which it becomes worth using.
LP $\max\ 30x_1 + 50x_2$ ($x_1 + 3x_2 \le 90$, $2x_1 + x_2 \le 80$) with a third variable $x_3$ ($c_3 = 20$, consumptions $1$ and $1$): at the optimum $x_3 = 0$, reduced cost $\bar c_3 = -2$, threshold $c_3^{\max} = 22$. With $c_3 = 23$ the new optimum is $(0, 5, 75)$. What does this show?
The reduced cost was computed wrongly
The reduced cost says *when* $x_3$ enters, not *how* the solution changes
Above the threshold $x_3$ enters with one unit only
Above the threshold the old solution stays optimal
Explanation. Past $c_3^{\max} = 22$ the variable becomes worth using, but the new solution must be recomputed: here it changes completely, from $(30, 20, 0)$ to $(0, 5, 75)$ with value $1975$.
Every lab session ends with the same six-step sensitivity protocol. What does step 2, «one-at-a-time», prescribe?
Change all parameters together by $\pm 5\%$
Vary one key parameter on a grid and plot value and decisions
Solve the model once per scenario of a pessimistic–optimistic set
Remove one constraint at a time and solve again
Explanation. One-at-a-time: one key parameter moves on a grid, the others stay fixed, and the optimal value and decisions are plotted. Scenarios are step 4, stability step 6.
Six-step sensitivity protocol of the lab. In which step are frontiers such as cost–service, risk–return or cost–emissions traced, by varying a weight or a threshold?
Step 1, base scenario
Step 3, shadow prices and reduced costs
Step 4, scenarios
Step 5, trade-off
Explanation. Step 5 (trade-off) varies a weight or a threshold to trace a frontier; step 4 builds at least three coherent scenarios (pessimistic, central, optimistic).
LP $\max\ 30x_1 + 50x_2$ subject to $x_1 + 3x_2 \le 90$, $2x_1 + x_2 \le 80$, $x \ge 0$, and its dual $\min\ 90\pi_1 + 80\pi_2$ subject to $\pi_1 + 2\pi_2 \ge 30$, $3\pi_1 + \pi_2 \ge 50$, $\pi \ge 0$. $\bar x = (30, 20)$ and $\bar\pi = (14, 8)$ are feasible and both objectives equal $1900$. What does this certify, and by which theorem?
Only that $\bar x$ is feasible
That the dual is unbounded
Both optimal: strong duality
That the optimum of (P) is unique
Explanation. $90\cdot 14 + 80\cdot 8 = 1260 + 640 = 1900 = 30\cdot 30 + 50\cdot 20$: a feasible primal–dual pair with equal values is optimal (weak duality makes equality a certificate; strong duality guarantees that such a pair exists).
Strong duality for LPs: (P) has an optimal solution if and only if (D) has one, and then the optimal values coincide. What does it **not** say?
That the optimal solutions are unique
That the optimal values are equal
That an optimum of (D) exists when (P) has one
That the duality gap closes at the optimum
Explanation. Existence is not uniqueness: there can be several optimal solutions (e.g. with degeneracy or parallel objective), but all share the same optimal value.
Pair (P) $\max\{\sum_j c_jx_j : \sum_j a_{ij}x_j \le b_i,\ x \ge 0\}$ and dual (D); slacks $\bar s_i$ and reduced costs $\bar c_j$. Two feasible solutions $\bar x$ and $\bar\pi$ are optimal if and only if:
$\bar\pi_i + \bar s_i = 0$ and $\bar x_j + \bar c_j = 0$ for every $i$, $j$
$\bar\pi_i\bar s_i = 0$ and $\bar x_j\bar c_j = 0$ for every $i$, $j$
$\bar s_i = 0$ and $\bar c_j = 0$ for every $i$, $j$
Explanation. These are the complementary slackness conditions: a constraint with positive slack has a zero dual and a positive variable has a zero reduced cost.
Maximization LP with optimal value $\tilde z$ and shadow price $\tilde\pi_i$ of constraint $i$, valid in the range $[b_i^{\min}, b_i^{\max}]$. How does $\tilde z$ change when $b_i$ moves within the range?
Linearly, with slope $\tilde\pi_i$
It stays constant, equal to $\tilde z$
Quadratically in $b_i$
Linearly, with slope $c_i$
Explanation. Within the validity range the optimal basis does not change and $\tilde z$ is linear in $b_i$ with slope $\tilde\pi_i = \partial\tilde z/\partial b_i$.
Maximization primal and its dual; at the optimum the dual $\tilde\pi_i$ of constraint $i$ is strictly positive. What does complementary slackness say about constraint $i$?
It is active: $\bar s_i = 0$
It has positive slack
It can be removed
The dual is unbounded
Explanation. From $\tilde\pi_i \bar s_i = 0$ and $\tilde\pi_i > 0$ it follows $\bar s_i = 0$: the constraint is active at the optimum.
(P) is a maximization LP and (D) its dual. What does weak duality say about the value of a feasible solution of (D)?
It is at most the optimal value of (P)
It equals the optimal value of (P)
It is at least the optimal value of (P)
It has no link with (P)
Explanation. Every feasible solution of the minimization dual gives an upper bound: $\sum_j c_j \bar x_j \le \sum_i b_i \bar\pi_i$ for every feasible pair.
Maximization LP: the variable $x_j$ is $0$ at the optimum, with reduced cost $\bar c_j = -2$. By how much must its coefficient $c_j$ grow for activating it to pay off?
By at least $1$
By at least $2$
By at least $4$
By any positive amount
Explanation. The reduced cost is the distance from convenience: with $\bar c_j = -2$ the coefficient must rise by at least $2$ (the threshold $c_j^{\max}$).
3. The solver: building, solving, interpreting (28)
In gurobipy, `m` is a `Model`. What does `m.addVar(name='b')` create, with no other argument?
A free continuous variable
A continuous variable with `lb=0` and `ub=+inf`
A binary variable
A continuous variable in $[0, 1]$
Explanation. The default is continuous with lower bound $0$: a free variable (regression intercept, CVaR threshold) needs `lb=-GRB.INFINITY`. Forgetting it is the most frequent mistake in the lab.
After solving an LP with gurobipy, which attributes of a constraint give its shadow price and the validity range of its right-hand side?
`X` and `SAObjLow`/`SAObjUp`
`RC` and `SARHSLow`/`SARHSUp`
`Pi` and `SARHSLow`/`SARHSUp`
`Slack` and `SAObjLow`/`SAObjUp`
Explanation. `Pi` on the constraint is $\tilde\pi_i$ and `SARHSLow`–`SARHSUp` is the range $[b_i^{\min}, b_i^{\max}]$; `X`, `RC` and `SAObjLow`/`SAObjUp` belong to the variables.
In gurobipy the constraint `constr` is written `quicksum(x[v,t] for v in V) + base[t] <= C`, where `base[t]` is a constant (the base load of hour `t`) and `C` is the meter capacity. To set the capacity to `nuovaC` in a sensitivity analysis one writes:
`constr.RHS = nuovaC`
`constr.RHS = nuovaC - base[t]`
`constr.RHS = nuovaC + base[t]`
`constr.Pi = nuovaC`
Explanation. Gurobi moves the constant to the right-hand side: the stored RHS is `C - base[t]`. Writing `RHS = nuovaC` would relax the constraint by `base[t]` (the bug of the EV case study).
A gurobipy model meant to maximize profit, with non-negative variables, returns optimum $0$ with all variables at zero. What is the most likely cause?
The objective is missing or has the wrong sense (e.g. `GRB.MINIMIZE`)
The model is infeasible and Gurobi returns the origin
The size limit of the pip licence has been exceeded
A variable was declared free with `lb=-GRB.INFINITY`
Explanation. With non-negative variables, minimizing a profit gives $x = 0$: check `setObjective(..., GRB.MAXIMIZE)`. An infeasible model returns no solution at all.
In gurobipy, after `x = m.addVars(I, T, name='x')` (a `tupledict` indexed by pairs `(i, t)`), how is the sum of `x[i,t]` over all `t`, for a fixed `i`, written?
`x.sum('*', i)`
`sum(x)`
`x.sum(i, '*')`
`gp.quicksum(x[i])`
Explanation. In a `tupledict` the wildcard `'*'` runs over one index: `x.sum(i, '*')` sums over the second index; `gp.quicksum(x[i, t] for t in T)` is the alternative.
After solving an LP with gurobipy, which attribute of a constraint tells whether it is active (binding) at the optimum?
`c.Pi`, which is non-zero exactly when the constraint is active
`c.Slack`, which is $0$ when the constraint is active
`c.SARHSUp`, which equals the right-hand side when it is active
`c.RC`, which is positive when the constraint is active
Explanation. An active constraint has zero slack. A null `Pi` does not imply a slack constraint (degeneracy), and `RC` belongs to variables, not constraints.
Every gurobipy script of the lab follows the same skeleton: data, model, solution, results, sensitivity. Which instruction comes right after `m.optimize()` in the “solution” block?
`assert m.Status == GRB.OPTIMAL`, to stop on an unexpected status
`m.setObjective(...)`, to fix the objective
`m.addConstrs(...)`, to add the missing constraints
`m.computeIIS()`, to be run in every script
Explanation. The skeleton checks the status before reading any value; objective and constraints belong to the model block, `computeIIS()` only to the diagnosis of an infeasible model.
The standard gurobipy skeleton of the lab has five blocks: data, model, solution, results, sensitivity. What does the sensitivity block do?
It reads the CSV files and defines the parameters
It creates variables, constraints and objective
It loops over a key parameter, re-optimizes and saves figures
It prints `.X`, `.Pi` and `.RC` in a readable report
Explanation. Data come first, then the model, the solution (with the status check), the report of `.X`, `.Pi`, `.RC`, and finally the loop over a parameter.
A gurobipy model minimizes a total cost and, after `m.optimize()`, its status is `GRB.UNBOUNDED`. What is the most likely cause?
A missing constraint or bound lets the cost decrease without limit
Total demand exceeds total capacity and no shortage variable exists
The coefficients span too many orders of magnitude (bad scaling)
The time limit `TimeLimit` stopped the solver before the optimum
Explanation. Unbounded means the objective improves indefinitely: almost always a constraint or a bound is missing. Demand above capacity gives `INFEASIBLE`, a time limit gives `TIME_LIMIT`.
Before solving, the Gurobi log prints the line `Optimize a model with 24 rows, 36 columns and 72 nonzeros`. What are the 24 rows and the 36 columns?
24 variables and 36 constraints
24 iterations and 36 seconds
24 constraints and 36 variables
24 data rows and 36 data columns of the CSV
Explanation. Rows are constraints, columns are variables, nonzeros the non-null coefficients of the matrix: the first check is that the model has the expected size.
How is the full (free) academic Gurobi licence obtained, according to the lab notes?
It is already included in `pip install gurobipy`
By buying it from the Gurobi website with any email
By setting `m.Params.License = 'academic'`
University email on the Gurobi portal, then `grbgetkey`
Explanation. One registers on portal.gurobi.com with the institutional email, requests a Named-User Academic License and runs the `grbgetkey` command given by the portal, from the university network or VPN.
A gurobipy script stops with the error `Model too large for size-limited license`. What is the remedy?
Activate the full academic licence
Set `m.Params.OutputFlag = 0` to save memory
Split the model into two smaller models solved separately
Declare all variables with `lb=-GRB.INFINITY`
Explanation. The pip licence stops at 2000 variables and 2000 constraints; the full academic licence removes the limit. Splitting the model would change the problem.
In gurobipy the lab writes `v1 = m.addConstr(x1 + 3*x2 <= 90, name='vincolo1')`, keeping the returned object in `v1`. Why?
Otherwise the constraint is not added to the model
To be able to delete it before `m.optimize()`
To read later its attributes, such as the dual `v1.Pi`
Because `addConstr` requires an assignment
Explanation. `addConstr` adds the constraint in any case; keeping the object is what allows reading `Pi`, `Slack`, `SARHSLow/Up` after the solve, or changing its `RHS` in a sensitivity loop.
Step 5 of building a gurobipy model in the lab is `m.write('lp_2x2.lp')`. What is it for?
It saves the optimal solution to a file
It writes the model in readable form, for checking
It is required before calling `m.optimize()`
It exports the log of the solver to a file
Explanation. It is a debugging step (optional): the `.lp` file shows objective and constraints as Gurobi received them, the quickest way to catch a sign or index error.
A gurobipy script sets `m.Params.TimeLimit = 60` before `m.optimize()`. What happens if the solver has not finished after 60 seconds?
The solve restarts with looser tolerances
The best solution found is reported with status `OPTIMAL`
Python raises an exception and the model is lost
It stops, with status `TIME_LIMIT` (code 9)
Explanation. The limit is in seconds; when it is reached `m.Status` is `TIME_LIMIT` (9), not `OPTIMAL`: this is why the status is always checked before reading any number.
In gurobipy, after `m.optimize()`, `m.Status` is an integer code. Which code corresponds to `GRB.OPTIMAL`?
0
1
2
3
Explanation. The table of the notes: `OPTIMAL` = 2, `INFEASIBLE` = 3, `UNBOUNDED` = 5, `TIME_LIMIT` = 9. In code one compares with the named constant, `m.Status == GRB.OPTIMAL`.
After solving an LP with gurobipy, which attributes of a **variable** give the validity interval of its objective coefficient (the range in which the optimal solution does not change)?
`SAObjLow` and `SAObjUp`
`SARHSLow` and `SARHSUp`
`LB` and `UB` of the variable
`RC` and `Slack`
Explanation. `SAObjLow`–`SAObjUp` is $[c_j^{\min}, c_j^{\max}]$; `SARHSLow`–`SARHSUp` is the interval of a constraint's right-hand side; `LB`/`UB` are the bounds of the variable.
The interpretation checklist of the lab has seven points, from «is the status `OPTIMAL`?» onwards. What is the last one?
Print all the variables with six decimals
Save the model and the solution to an `.lp` file
Solve again with a different solver
Write a three-line managerial recommendation
Explanation. The checklist ends with the recommendation: status, order of magnitude, active constraints, shadow prices, reduced costs, stability under 5% perturbations, then three lines for the decision maker.
In the interpretation checklist of the lab, what should be read for each variable that is at zero in the optimal solution of an LP?
Its `SARHSLow`/`SARHSUp` validity interval
Its reduced cost `RC`
Its `Slack`, which must be positive
Nothing: a variable at zero tells nothing
Explanation. The reduced cost of a variable at zero is the improvement of $c_j$ needed for it to enter; `Slack` and `SARHS` are attributes of constraints, not of variables.
gurobipy output of the LP $\max\ 30x_1 + 50x_2$: `vincolo1: Slack = 0, Pi = 14.0, SARHS = [40, 240]`, `vincolo2: Slack = 0, Pi = 8.0, SARHS = [30, 180]`. Only one right-hand side can be raised by a few units, at the same cost per unit. Which one, and why?
$b_2$: its validity interval $[30, 180]$ is narrower
Either one: both constraints are active at the optimum
$b_1$: one unit is worth $14$ against $8$
Neither: active constraints cannot be relaxed
Explanation. Shadow prices compare resources: one unit of $b_1$ raises the optimum by $14$, one of $b_2$ by $8$, valid while $b_1$ stays in $[40, 240]$.
gurobipy output of a **minimization** LP: the constraint `vincolo3`, $x_1 - 2x_2 \le -20$, has `Slack = 0`, `Pi = -1.0`, `SARHS = [-200, inf]`. How is it read?
Raising $b_3$ by 1 lowers the optimal cost by 1
Raising $b_3$ by 1 raises the optimal cost by 1
The constraint is not active, so it can be removed
A negative `Pi` signals an error in the model
Explanation. $\texttt{Pi} = \partial\tilde z/\partial b_3 = -1$: a $\le$ constraint in a minimum has $\texttt{Pi} \le 0$, and loosening it saves $1$ per unit (check: $b_3 = -19$ gives $\tilde z = 619$ instead of $620$).
gurobipy output of a **minimization** LP: the variable $x_3 \le 0$ (declared with `ub=0`) has `X = 0`, `RC = -3.0`, `SAObj = [-inf, -6.0]`; its objective coefficient is $c_3 = -9$. How is it read?
$x_3$ is basic and could move away from zero for free
At its upper bound; it enters only if $c_3 \ge -6$
$x_3$ is at its upper bound and lowering $c_3$ makes it enter
The negative `RC` means the solution is not optimal
Explanation. Zero is the upper bound of a variable $\le 0$; forcing $x_3 = -1$ would worsen the cost by $3$, and the variable becomes worth using only when $c_3$ reaches the endpoint `SAObjUp` $= -6$.
In a minimum-cost flow LP solved with gurobipy, an arc is saturated (its flow equals its capacity $u$, a variable at its upper bound) and has `RC` $= -4$. How is it read?
The arc is too expensive and should carry less flow
The solution is degenerate and `RC` has no meaning
Raising its cost by 4 would make it worth using
One more unit of capacity on that arc would save 4
Explanation. For a variable at its upper bound `RC` is the shadow price of the bound: in a minimum, a saturated arc with $\texttt{RC} < 0$ saves $|\texttt{RC}|$ per extra unit of capacity.
A gurobipy production LP returns `INFEASIBLE`. `m.computeIIS()` writes a conflict made of the capacity constraints of months 1–4 and the balances of the same months. What is the most sensible diagnosis?
A sign error in the objective
Early demand exceeds early capacity
A variable declared free by mistake
The model is badly scaled overall
Explanation. An irreducible inconsistent set (IIS) is a minimal set of constraints that cannot hold together: here capacity and balances of the first four months, i.e. their demand cannot be served in time. Remedies: more capacity, or lost demand with a penalty.
`python3 -m pip install gurobipy` installs Gurobi with a licence included in the package. What are its limits?
200 variables and 200 constraints
2000 variables and 2000 constraints
No limit for LPs
20000 variables, unlimited constraints
Explanation. The licence of the pip package goes up to 2000 variables and 2000 constraints: all the models of the course fit; beyond that the free academic licence is needed.
In an LP, a shadow price $\tilde\pi_i$ is used to evaluate a change of the right-hand side $b_i$ far beyond `SARHSUp` (the upper end of its validity range). Why is it a mistake?
Outside the range shadow prices are always zero
`SARHSUp` is the optimal value, not a bound on $b_i$
The shadow price always changes sign at `SARHSUp`
$\tilde\pi_i$ is exact only within its range: beyond, re-solve
Explanation. Interpreting a shadow price outside `SARHSLow`–`SARHSUp` is in the checklist of the most frequent mistakes: the optimal value is piecewise linear in $b_i$.
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?
Six, to be as precise as possible
Few: six decimals of an estimate wobbling at the second mislead
None: estimates should not be reported
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.
In a **minimization** LP solved with gurobipy, what sign does the attribute `Pi` (shadow price $\partial\tilde z/\partial b_i$) of an active constraint $\sum_j a_{ij}x_j \le b_i$ have? Getting it wrong is in the lab checklist of mistakes.
$\texttt{Pi} \le 0$: more capacity can only lower the cost
$\texttt{Pi} \ge 0$: capacity always has a positive price
$\texttt{Pi} = 0$: active constraints have no price
Any sign, depending on the solver's conventions
Explanation. Raising $b_i$ enlarges the feasible region and a larger region never raises the minimum, so $\texttt{Pi} \le 0$; in a maximization the same constraint has $\texttt{Pi} \ge 0$.
All the results of the lab are reproducible from the Python scripts of the course. What does the script that runs them all (`run_all.py` in the English edition, `esegui_tutti.py` in the Italian one) do?
It installs Gurobi and activates the licence
It regenerates data, results and figures
It compiles the slides only
It uploads the results to the course website
Explanation. One command regenerates everything the notes show; installing the dependencies is a separate `pip install`.
One entry of the lab checklist of mistakes is “optimizing a single objective when the problem has two”. Which lab example illustrates it?
Reading `.X` before checking `m.Status`
Choosing $C$ and $\gamma$ on the test set
Using a shadow price outside its validity range
The pure minimax peak of the EV fleet, which ignores the cost
Explanation. Minimizing only the peak returns an arbitrary solution among those of minimum peak (27.79 € instead of 22.15 € for the same peak): combine the two objectives.
The lab materials are organized in folders. Where are the data of all the case studies?
In `dati/`, as CSV files
Inside the Python scripts, as constants
In `soluzioni/`, together with the solutions
In `slides/`, as tables
Explanation. `dati/` holds all case-study data in CSV; `python/` has one script per chapter, `soluzioni/` the exercise solutions for teachers, `slides/` the slides of the four lab sessions.
In the course LP Modelling, which chapters can replace sessions 3–4 in an edition oriented towards uncertainty and estimation?
Production, EV charging and DEA
Newsvendor, CVaR, arbitrage, regression
The theory background and the solver
The introduction only
Explanation. The chapters from the newsvendor to robust and quantile regression can replace sessions 3–4, or become in-depth material for individual projects.
Among the topics proposed for the project of your choice (session 4) of the course LP Modelling, which one appears?
Electric vehicle charging
The travelling salesman
Graph colouring
Scheduling on several machines
Explanation. The project proposes EV charging, arbitrage or robust and quantile regression, with a managerial presentation: all linear models of the course.
Checklist of mistakes: in gurobipy one writes the constraint `quicksum(x) + base <= C`, where `base` is a constant. Which right-hand side does Gurobi store?
$C$, the capacity written on the right
$C - \text{base}$, the capacity minus the constant
$C + \text{base}$, the capacity plus the constant
$\text{base}$, the constant alone
Explanation. Gurobi moves the constants to the right: the right-hand side is $C - \text{base}$. To change the capacity to $C'$ one therefore writes `v.RHS = C' - base`, not `v.RHS = C'`.
According to the checklist of mistakes of the course LP Modelling, which variables need `lb=-GRB.INFINITY` in gurobipy?
The end-of-month inventories $s_{it}$ in production
The powers $x_{vt}$ assigned to the vehicles
The weights $\lambda_j$ of the envelopment form
The regression intercept $b$ and the CVaR threshold $\eta$
Explanation. In gurobipy the default lower bound is $0$. The intercept $b$ and the threshold $\eta$ may be negative: they are free. Inventories, powers and weights are instead non-negative.
The checklist of mistakes of the course LP Modelling warns against choosing the parameters ($\tau$, $\lambda$, the budget) by looking at:
the data used to make the decision
the number of constraints of the model
the Gurobi documentation
the running time of the solver
Explanation. If the parameters are chosen on the same data (or scenarios) used to decide, the assessment is optimistic: separate validation data are needed.
What does the `notebooks/` folder of the course LP Modelling contain?
One Colab notebook per chapter
The solutions reserved to instructors
The LaTeX sources of the notes
The slides in editable form
Explanation. Every chapter with a model has its notebook, generated from the script: it opens in Colab and runs in the browser with nothing to install.
The course LP Modelling installs `gurobipy`, `matplotlib`, `pandas` and `scipy`. What is `scipy` for?
Solving the LPs instead of Gurobi
Drawing the figures of the notes
Only the statistical functions
Reading the CSV data files
Explanation. All the models are solved with Gurobi; `scipy` is needed only for the statistical functions (for instance the normal quantiles in the newsvendor).
In the course LP Modelling, which script regenerates data, tables and figures in one go (in the English version)?
`python/make_notebooks.py`
`python/run_all.py`
`python/stile.py`
`python/lab04_production.py`
Explanation. `run_all.py` runs all the chapter scripts and then regenerates the notebooks; `stile.py` only contains the palette and the saving functions.
After `m.optimize()` in gurobipy, what does the checklist of mistakes recommend before reading `.X` or `.Pi`?
Check that `m.Status` is `GRB.OPTIMAL`
Call `m.update()` a second time
Set `m.Params.OutputFlag = 1`
Save the model to an `.lp` file
Explanation. If the model is infeasible, unbounded or interrupted, `.X` and `.Pi` do not exist or are meaningless: the status must always be checked first.
The checklist of mistakes of the course LP Modelling mentions updating the right-hand side of a constraint with constants on the left. In which chapter did it happen?
Multi-period production and inventory
Data Envelopment Analysis
Electric vehicle charging
Arbitrage and pricing
Explanation. In EV charging the grid constraint contains the base load $b_t$: Gurobi moves it into the right-hand side, and the first analysis of the meter capacity updated the RHS the wrong way.
In a **maximization** LP solved with gurobipy, what is the sign of the attribute `Pi` of a resource constraint $\le$?
$\texttt{Pi} \le 0$
$\texttt{Pi} \ge 0$
$\texttt{Pi} = 0$ always
Any sign
Explanation. In a maximization more resource enlarges the region and the optimum cannot get worse: the shadow price of a $\le$ constraint is non-negative. In minimization problems, instead, a $\le$ constraint has $\texttt{Pi} \le 0$.
In session 4 of the course LP Modelling (project of your choice), what is prepared besides the model and its results?
A new version of the lecture notes
An implementation in a second solver
A proof of strong duality
A managerial presentation of the results
Explanation. The project of your choice (EV charging, arbitrage or regression) ends with a managerial presentation: the recommendation counts as much as the optimum.
How many application chapters, that is with a model and a case study, does the course LP Modelling have?
3
11
7
14
Explanation. Seven application chapters (production, EV charging, DEA, newsvendor, VaR and CVaR, arbitrage, regression) plus three chapters of tools and the organization.
To run the models of the course LP Modelling with nothing to install, what does one use?
The chapter notebook opened in Colab
A Gurobi licence installed locally
A virtual machine of the department
The PDF of the notes with the code
Explanation. Every chapter has its notebook: it opens in Colab from the badge at the top of the page, installs the solver by itself and runs in the browser.
In a **minimization** LP solved with gurobipy, what is the sign of the attribute `Pi` of a demand constraint $\ge$?
$\texttt{Pi} \ge 0$
$\texttt{Pi} \le 0$
$\texttt{Pi} = 0$ always
Any sign
Explanation. Increasing the demand shrinks the region and in a minimization the optimal cost cannot decrease: the shadow price of a $\ge$ constraint is non-negative.
The shadow price of the capacity of a month is $-3.81$ €/hour in the range $[330, 431]$ hours. The capacity goes from $420$ to $600$ hours. What does the checklist recommend?
Predict the cost with $-3.81 \cdot 180$
Re-optimize: we left the range
Double the shadow price
Consider the model infeasible
Explanation. The shadow price holds only within its validity range; $600$ is beyond $431$, so the linear prediction does not hold and one re-optimizes.
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). What is the role of the balance constraints $s_{i,t-1} + x_{it} = d_{it} + s_{it}$?
They bound the machine hours used in each month $t$
They make the objective convex, hence the LP solvable
They link consecutive months and force demand to be served
They force the inventory $s_{it}$ to zero in every month
Explanation. The balance is the intertemporal link: what comes in (previous inventory plus production) equals what goes out (demand plus next inventory).
The production-inventory LP with $n$ products and $m$ months has balance constraints $s_{i,t-1} + x_{it} = d_{it} + s_{it}$ (for every product $i$ and month $t$) and machine-capacity constraints $\sum_i a_i x_{it} \le b_t$. How many constraints does it have, besides non-negativity?
$n\,m + m$
$2\,n\,m$
$n + m$
$n\,m$
Explanation. $n\,m$ inventory balances (one per product and month) and $m$ capacity constraints (one per month, shared by all products).
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). $h_i$ is the monthly holding cost and $a_i$ the machine hours per unit of product $i$. In the case study the shadow prices of the monthly capacity constraints differ by exactly $h_3/a_3 = 0.762$ € per hour between consecutive months. Why?
Because $0.762$ €/hour is the production cost of product 3
Because the solver rounds the duals to the last product's data
Because each hour costs the same in every month of the horizon
Because one more hour lets $1/a_3$ units of product 3 be made a month later
Explanation. Making $1/a_3$ units of product 3 one month later saves one month of holding, $h_3/a_3$ per hour: the economic argument and the solver give the same number.
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). What happens if the balance constraints $s_{i,t-1} + x_{it} = d_{it} + s_{it}$ are removed, keeping capacity and non-negativity?
The model becomes infeasible, since capacity alone cannot be met
The optimum produces nothing: no constraint forces demand to be served
The model becomes unbounded, since the cost can decrease without limit
Nothing changes: the capacity constraints already link the months
Explanation. Without the balance the minimum cost is reached by producing nothing. With the balances, if total demand exceeds cumulated capacity, the model is infeasible.
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). Capacity is tight in the peak months, so some production must be anticipated. Holding costs $h_i$ (€/unit/month) and machine hours $a_i$ (per unit) differ by product. Which product is it cheapest to produce in advance and stock?
The one with the smallest $h_i/a_i$, the holding cost per machine hour anticipated
The one with the smallest $h_i$, whatever its machine hours $a_i$
The one with the smallest $a_i$, which uses the least capacity
All products in proportion to their demand in the peak months
Explanation. Anticipating one machine hour by one month costs $h_i/a_i$. In the case study product 3 ($h_3/a_3 = 0.762$, the smallest) is produced in advance, up to 107 units in stock.
Consider a minimization LP and its optimal value $\tilde z(b_i)$ as a function of a single right-hand side $b_i$, on the values where the LP is feasible. Which statement is correct?
$\tilde z(b_i)$ is concave and piecewise linear
$\tilde z(b_i)$ is convex and piecewise linear, with slope $\tilde\pi_i$
$\tilde z(b_i)$ is linear on its whole domain
$\tilde z(b_i)$ is differentiable on its whole domain
Explanation. The slope is the shadow price, which changes at the endpoints of the validity ranges: this is why the capacity value curve of the production case study is convex and decreasing, with kinks.
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). Production costs $c_{it}$ and holding costs $h_{it}$ are the data of the objective. Which facts prove that at the optimum the inventory of the last month $m$ is zero, $\tilde s_{im} = 0$?
Only that the capacity constraints are active in month $m$
Strong duality between the LP and its dual
That demand is the same in every month
$h_{im} > 0$ and $c_{it} > 0$: producing the leftover less keeps all balances and lowers the cost
Explanation. A positive terminal inventory is money wasted: removing it (producing less in the last month in which it was produced) keeps every balance feasible and strictly lowers the cost.
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). In the case study (3 products, 6 months) the problem becomes infeasible when the monthly capacities $b_t$ are cut below $97\%$ of their values. Why?
Because the holding costs become negative
Because the objective becomes non-convex
Because cumulated capacity can no longer cover cumulated demand
Because Gurobi needs at least $97\%$ of capacity
Explanation. With balances that force demand to be served, the production of months $1..t$ must cover the demand of months $1..t$ (net of initial stocks): below that capacity no plan exists.
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). One product, two months: demand $d = (60, 100)$, capacity $80$ units per month, production cost $10$ €/unit, holding cost $1$ €/unit/month, no initial inventory. What is the optimal cost?
$1620$ €
$1600$ €
$1640$ €
$1700$ €
Explanation. Month 2 can make only 80 of its 100 units, so 20 are made in month 1 and held: $x = (80, 80)$, $s_1 = 20$, cost $10 \cdot 160 + 1 \cdot 20 = 1620$ €.
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). In the case study the capacity constraint of month 6 has shadow price $-3.810$ €/hour. Adding one hour in month 6 and re-solving, the cost goes from $32889.33$ to $32885.52$ €. What does this check show?
The shadow price is confirmed: the change, $-3.81$, matches it
The shadow price is wrong, since the cost decreased
The extra hour is outside the validity range
Capacity in month 6 is not binding
Explanation. This is step 3 of the protocol: the re-optimization reproduces the marginal prediction of the dual, $\Delta\tilde z = \tilde\pi_6 \cdot 1$.
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). Case study: 3 products, 6 months, demand peaking in months 4–5, the same unit costs in every month. Product 3 is produced in $89.5$ units in month 1 but only $29.0$ in month 5. Why?
Its demand is much higher in month 1 than in month 5
Pre-build: it is made early to free capacity in the peak months
Its production cost is lower in month 1 than in month 5
A numerical error: an optimal plan never builds inventory
Explanation. With equal costs, inventory only costs money; the solver anticipates product 3 (the one with the smallest holding cost per machine hour) to free machine hours in the peak months, and the stock returns to zero in month 6.
According to the lab notes, what is the core difficulty of multi-period production planning with shared resources?
The demand of the future months is unknown
Today's decision changes tomorrow's constraints
The products need integer quantities
The production costs are nonlinear
Explanation. Producing early or not changes the inventory available later, hence what the later months must produce within their capacity: the balance constraints tie the months together.
Where does the multi-period production-inventory problem of the lab appear in practice?
Only in the scheduling of a single machine
Only in the choice of the location of a plant
Only in the pricing of seasonal products
In master production schedules and monthly contracts
Explanation. Whenever production is planned over several periods with shared resources: master production schedules (MPS), aggregate planning, supply contracts with monthly profiles.
Why is the production-inventory LP the ideal starting point of the lab, according to the notes?
Its numbers all have an economic reading
It is the only lab model without duals
It has a closed-form solution
It needs no data from the company
Explanation. Production quantities, inventories, shadow prices of capacity and their ranges all translate directly into money and decisions, which is the habit the lab wants to build.
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, $c_{it}$ and $h_{it}$ = unit production and holding costs, $a_i$ = machine hours per unit, $b_t$ = hours available): balances $s_{i,t-1} + x_{it} = d_{it} + s_{it}$, capacities $\sum_ia_ix_{it} \le b_t$. One product, two months: demand $(60, 100)$, capacity $80$ units per month ($a = 1$), no initial stock. Why is the solution «forced»?
Because the holding cost is zero
Because the demand of month 1 exceeds its capacity
Total demand equals total capacity
Because the LP has a single variable
Explanation. Total demand $160$ = total capacity $160$: the only feasible plan is $x_1 = x_2 = 80$ with $s_1 = 20$, so both capacity constraints are active.
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, $c_{it}$ and $h_{it}$ = unit production and holding costs, $a_i$ = machine hours per unit, $b_t$ = hours available): balances $s_{i,t-1} + x_{it} = d_{it} + s_{it}$, capacities $\sum_ia_ix_{it} \le b_t$. One product, two months: demand $(60, 100)$, capacity $80$ per month, $c = 10$, $h = 1$; optimal plan $x = (80, 80)$, $s_1 = 20$. With one more unit of capacity in month 2 the cost drops by 1 €. What is the shadow price of the month-2 capacity, and why?
$-1$: one unit less waits in stock
$-10$: one unit less is produced
$+1$: extra capacity costs money
$0$: the constraint is not active
Explanation. With $b_2 = 81$: $x_2 = 81$, $s_1 = 19$, $x_1 = 79$; the total production is the same, but one unit no longer waits a month in stock, saving $h = 1$. In a minimum a $\le$ capacity has dual $\le 0$.
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, $c_{it}$ and $h_{it}$ = unit production and holding costs, $a_i$ = machine hours per unit, $b_t$ = hours available): balances $s_{i,t-1} + x_{it} = d_{it} + s_{it}$, capacities $\sum_ia_ix_{it} \le b_t$. One product, two months, demand $(60, 100)$, capacity $80$ per month: both capacity constraints are active, yet one more unit of capacity in month 1 changes nothing (dual $0$). How is this possible?
It is a numerical error of the solver
Because month 1 has a higher cost
Because the holding cost is paid in month 2
Degeneracy: active, yet zero dual
Explanation. Month 1 already produces what is needed (60 for itself, 20 for month 2); extra capacity there is useless. Complementary slackness gives only «slack ⇒ zero dual», not the converse.
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, $c_{it}$ and $h_{it}$ = unit production and holding costs, $a_i$ = machine hours per unit, $b_t$ = hours available): balances $s_{i,t-1} + x_{it} = d_{it} + s_{it}$, capacities $\sum_ia_ix_{it} \le b_t$. Case study: 3 products, 6 months; $(c_i, h_i, a_i, s_{i0})$ = $(12, 0.8, 0.9, 30)$, $(18, 1.2, 1.4, 20)$, $(25, 1.6, 2.1, 10)$; hours $b_t$ = 420, 420, 460, 460, 460, 420; demand peaking in months 4–5. Which product has the lowest holding cost per machine hour, $h_i/a_i$?
Product 1, $0.889$
Product 2, $0.857$
Product 3, $0.762$
All equal
Explanation. $0.8/0.9 = 0.889$, $1.2/1.4 = 0.857$, $1.6/2.1 = 0.762$: holding product 3 is the cheapest way to «store» machine hours, which is why it is produced in advance.
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, $c_{it}$ and $h_{it}$ = unit production and holding costs, $a_i$ = machine hours per unit, $b_t$ = hours available): balances $s_{i,t-1} + x_{it} = d_{it} + s_{it}$, capacities $\sum_ia_ix_{it} \le b_t$. Case study: 3 products, 6 months; $(c_i, h_i, a_i, s_{i0})$ = $(12, 0.8, 0.9, 30)$, $(18, 1.2, 1.4, 20)$, $(25, 1.6, 2.1, 10)$; hours $b_t$ = 420, 420, 460, 460, 460, 420; demand peaking in months 4–5. In month 5 the demands are $210$, $150$, $95$. How many machine hours would month 5 need to produce its own demand, against $b_5 = 460$?
$455$, within the capacity
$598.5$, beyond capacity
$460$, exactly the capacity
$520$, just beyond capacity
Explanation. $0.9\cdot 210 + 1.4\cdot 150 + 2.1\cdot 95 = 189 + 210 + 199.5 = 598.5 > 460$: the peak cannot be served month by month, so inventory built in the earlier months is needed.
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, $c_{it}$ and $h_{it}$ = unit production and holding costs, $a_i$ = machine hours per unit, $b_t$ = hours available): balances $s_{i,t-1} + x_{it} = d_{it} + s_{it}$, capacities $\sum_ia_ix_{it} \le b_t$. Case study: 3 products, 6 months; $(c_i, h_i, a_i, s_{i0})$ = $(12, 0.8, 0.9, 30)$, $(18, 1.2, 1.4, 20)$, $(25, 1.6, 2.1, 10)$; hours $b_t$ = 420, 420, 460, 460, 460, 420; demand peaking in months 4–5. How does the initial stock $s_{i0}$ enter the model?
As a datum in the balance of month 1
As a decision variable of month 0
As a lower bound on the final stock
It is ignored by the LP
Explanation. For $t = 1$ the balance reads $s_{i0} + x_{i1} = d_{i1} + s_{i1}$ with $s_{i0}$ known: it is data, not a variable (30, 20 and 10 units in the case study).
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, $c_{it}$ and $h_{it}$ = unit production and holding costs, $a_i$ = machine hours per unit, $b_t$ = hours available): balances $s_{i,t-1} + x_{it} = d_{it} + s_{it}$, capacities $\sum_ia_ix_{it} \le b_t$. Case study: 3 products, 6 months; $(c_i, h_i, a_i, s_{i0})$ = $(12, 0.8, 0.9, 30)$, $(18, 1.2, 1.4, 20)$, $(25, 1.6, 2.1, 10)$; hours $b_t$ = 420, 420, 460, 460, 460, 420; demand peaking in months 4–5. Where are the data of the case study kept, and why does it matter?
Inside the notes only, as tables
In the log printed by the solver
In a database that must be queried by hand
In CSV files read by the script
Explanation. Demand and capacity are in the CSV files of the `dati/` folder; the script reads them, so changing a datum and rerunning regenerates all the numbers of the chapter.
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, $c_{it}$ and $h_{it}$ = unit production and holding costs, $a_i$ = machine hours per unit, $b_t$ = hours available): balances $s_{i,t-1} + x_{it} = d_{it} + s_{it}$, capacities $\sum_ia_ix_{it} \le b_t$. The gurobipy balance is written `(s0[i] if t == 1 else s[i, t-1]) + x[i, t] == domanda[i, t] + s[i, t]`. Why the conditional expression?
To skip month 1 in the whole model
Stock entering month 1 is the datum `s0[i]`
To make the constraint an inequality
Because `s[i, 0]` is a free variable
Explanation. There is no variable $s_{i0}$: in month 1 the incoming stock is the initial stock (a constant), in the following months it is the variable of the previous month.
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, $c_{it}$ and $h_{it}$ = unit production and holding costs, $a_i$ = machine hours per unit, $b_t$ = hours available): balances $s_{i,t-1} + x_{it} = d_{it} + s_{it}$, capacities $\sum_ia_ix_{it} \le b_t$. In the script the capacity constraints are created as `v_cap = m.addConstrs(...)`, keeping the returned object. What is it used for?
To delete the constraints in month 6
To print the model to a file
Nothing: it is required by the syntax
To read the duals `Pi` and their ranges
Explanation. The shadow prices of the capacities and their validity ranges (`Pi`, `SARHSLow`, `SARHSUp`) are read from these objects in the sensitivity analysis.
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, $c_{it}$ and $h_{it}$ = unit production and holding costs, $a_i$ = machine hours per unit, $b_t$ = hours available): balances $s_{i,t-1} + x_{it} = d_{it} + s_{it}$, capacities $\sum_ia_ix_{it} \le b_t$. In the script `x = m.addVars(prodotti, mesi, name='x')` with no bounds. What kind of variables are created?
Continuous, nonnegative, one per pair
Binary variables, one per product
Integer variables, one per month
Free, one per (product, month) pair
Explanation. `addVars` over two index sets creates one variable per pair; the default bounds are $[0, +\infty)$ and the type is continuous, exactly what $x_{it} \ge 0$ requires.
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, $c_{it}$ and $h_{it}$ = unit production and holding costs, $a_i$ = machine hours per unit, $b_t$ = hours available): balances $s_{i,t-1} + x_{it} = d_{it} + s_{it}$, capacities $\sum_ia_ix_{it} \le b_t$. The balances are written with `==` in the script. What does the equality impose?
That production equals demand in every month
That the inventories stay constant
That all demand is served on time
That the capacity is fully used
Explanation. In every month incoming stock plus production equals demand plus outgoing stock: nothing is lost and no backlog is allowed. Allowing lost demand would need an extra variable with a penalty.
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, $c_{it}$ and $h_{it}$ = unit production and holding costs, $a_i$ = machine hours per unit, $b_t$ = hours available): balances $s_{i,t-1} + x_{it} = d_{it} + s_{it}$, capacities $\sum_ia_ix_{it} \le b_t$. Case study: 3 products, 6 months; $(c_i, h_i, a_i, s_{i0})$ = $(12, 0.8, 0.9, 30)$, $(18, 1.2, 1.4, 20)$, $(25, 1.6, 2.1, 10)$; hours $b_t$ = 420, 420, 460, 460, 460, 420; demand peaking in months 4–5. In the optimal plan product 1 is produced in $80$ units in month 1, although its demand is $110$. Why?
Capacity of month 1 is saturated
The initial stock of 30 covers the rest
Product 1 is cheaper in later months
Part of its demand is lost
Explanation. $s_{10} = 30$: the balance $30 + 80 = 110 + 0$ holds with no inventory left; month 1 uses only 330 of its 420 hours.
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, $c_{it}$ and $h_{it}$ = unit production and holding costs, $a_i$ = machine hours per unit, $b_t$ = hours available): balances $s_{i,t-1} + x_{it} = d_{it} + s_{it}$, capacities $\sum_ia_ix_{it} \le b_t$. Case study: 3 products, 6 months; $(c_i, h_i, a_i, s_{i0})$ = $(12, 0.8, 0.9, 30)$, $(18, 1.2, 1.4, 20)$, $(25, 1.6, 2.1, 10)$; hours $b_t$ = 420, 420, 460, 460, 460, 420; demand peaking in months 4–5. In the optimal plan (cost $32{,}889.33$ €) every inventory is zero at the end of month 6. Why?
An explicit constraint forces it
The solver rounds the last month
The demand of month 6 is zero
A final stock would only cost money
Explanation. Nothing values the stock after the horizon, so any unit left at the end would add holding and production cost without serving demand: the model does not leave any.
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, $c_{it}$ and $h_{it}$ = unit production and holding costs, $a_i$ = machine hours per unit, $b_t$ = hours available): balances $s_{i,t-1} + x_{it} = d_{it} + s_{it}$, capacities $\sum_ia_ix_{it} \le b_t$. Case study: 3 products, 6 months; $(c_i, h_i, a_i, s_{i0})$ = $(12, 0.8, 0.9, 30)$, $(18, 1.2, 1.4, 20)$, $(25, 1.6, 2.1, 10)$; hours $b_t$ = 420, 420, 460, 460, 460, 420; demand peaking in months 4–5. In the optimal plan products 1 and 2 are produced on demand, while product 3 accumulates inventory in months 1–3 (up to $106.9$ units at the end of month 3). What strategy has the solver found?
Pre-build of product 3
Level production of every product
Lost sales in the peak months
Overtime in the peak months
Explanation. Product 3 has the lowest $h_i/a_i$: producing it early frees hours in the peak months 4–5 at the smallest holding cost per hour; its inventory then falls back to zero.
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, $c_{it}$ and $h_{it}$ = unit production and holding costs, $a_i$ = machine hours per unit, $b_t$ = hours available): balances $s_{i,t-1} + x_{it} = d_{it} + s_{it}$, capacities $\sum_ia_ix_{it} \le b_t$. Case study: 3 products, 6 months; $(c_i, h_i, a_i, s_{i0})$ = $(12, 0.8, 0.9, 30)$, $(18, 1.2, 1.4, 20)$, $(25, 1.6, 2.1, 10)$; hours $b_t$ = 420, 420, 460, 460, 460, 420; demand peaking in months 4–5. Month 1 uses $330$ of its $420$ hours; the solver reports `Pi` $= 0$ with validity range $[330, +\infty)$. How is it read?
Month 1 is the bottleneck of the plan
Extra hours in month 1 are worth $0.762$ €
Slack constraint: extra hours are worthless
The model is degenerate in month 1
Explanation. A slack constraint has zero shadow price; the price stays zero as long as $b_1 \ge 330$, the hours actually used. Below 330 the constraint would start to bind.
Production LP with one product, initial stock 0, demands $d_t$, capacities $b_t$ (units per month), balances $s_{t-1} + x_t = d_t + s_t$, $0 \le x_t \le b_t$, $s_t \ge 0$. Which condition on the data is necessary and sufficient for feasibility?
Total capacity at least total demand
$b_t \ge d_t$ in every month
Capacity of the last month at least its demand
Cumulated capacity $\ge$ cumulated demand, every $t$
Explanation. Stock can only carry production forward: demand up to month $t$ must be produced in months $1, \dots, t$. Comparing only the totals is not enough (a late surplus cannot serve an early peak); $b_t \ge d_t$ is sufficient but not necessary.
EV charging LP: power $x_{vt}$ to vehicle $v$ in hour $t$ (1 h), energy price $\pi_t$, availability datum $a_{vt} \in \{0,1\}$, charger power $\bar p_v$, required energy $e_v$, efficiency $\eta$, base load $b_t$, meter limit $k$; minimize $\sum_{v,t}\pi_tx_{vt}$. Why does the model need no binary variables?
Availability $a_{vt}$ is an observed datum and the decision (how much power) is continuous
Gurobi cannot handle binary variables in models of this size
All the vehicles are plugged in during every hour of the night
The energy prices $\pi_t$ are the same in every hour
Explanation. The constraint $x_{vt} \le a_{vt}\,\bar p_v$ sets the power to zero in the hours of absence: no on/off decision is needed.
EV charging LP: power $x_{vt}$ to vehicle $v$ in hour $t$ (1 h), energy price $\pi_t$, availability datum $a_{vt} \in \{0,1\}$, charger power $\bar p_v$, required energy $e_v$, efficiency $\eta$, base load $b_t$, meter limit $k$; minimize $\sum_{v,t}\pi_tx_{vt}$. The energy constraint of vehicle $v$ is $\eta\sum_t x_{vt} \ge e_v$. Why does it hold with equality at the optimum?
Because $\eta < 1$ forces extra energy to be drawn
Because the meter constraint is always saturated
Because prices are positive: extra energy only adds cost
Because the charging windows are disjoint
Explanation. Charging more than necessary is allowed but never worthwhile: with $\pi_t > 0$ any extra kWh only increases the cost, so the requirement is met exactly.
EV charging LP: power $x_{vt}$ to vehicle $v$ in hour $t$ (1 h), energy price $\pi_t$, availability datum $a_{vt} \in \{0,1\}$, charger power $\bar p_v$, required energy $e_v$, efficiency $\eta$, base load $b_t$, meter limit $k$; minimize $\sum_{v,t}\pi_tx_{vt}$. In the case study the shadow price of the energy constraint of one vehicle is $0.0947 = 0.09/\eta$ €/kWh. What does it represent?
The average energy price of the night
The price of the vehicle's marginal hour, divided by $\eta$
The energy price of the evening peak
The hourly cost of the meter capacity $k$
Explanation. The marginal kWh is bought in the cheapest hour still free in the vehicle's window; one more kWh in the battery needs $1/\eta$ kWh from the grid at that hour's price.
EV charging LP: power $x_{vt}$ to vehicle $v$ in hour $t$ (1 h), energy price $\pi_t$, availability datum $a_{vt} \in \{0,1\}$, charger power $\bar p_v$, required energy $e_v$, efficiency $\eta$, base load $b_t$, meter limit $k$; minimize $\sum_{v,t}\pi_tx_{vt}$. How is the peak-shaving variant (minimize the highest hourly draw from the grid) formulated?
Adding a binary variable for each peak hour
Minimizing $\sum_v\sum_t x_{vt}^2$
Fixing the power of every vehicle to $e_v/(\eta\, m)$
Minimizing $z$ subject to $\sum_v x_{vt} + b_t \le z$ for every hour $t$
Explanation. The auxiliary variable $z$ is the peak draw; the multi-objective variant minimizes cost $+\,\rho\, z$.
EV charging LP: power $x_{vt}$ to vehicle $v$ in hour $t$ (1 h), energy price $\pi_t$, availability datum $a_{vt} \in \{0,1\}$, charger power $\bar p_v$, required energy $e_v$, efficiency $\eta$, base load $b_t$, meter limit $k$; minimize $\sum_{v,t}\pi_tx_{vt}$. Peak shaving minimizes the peak draw $z$. In the case study the pure minimax (peak 68 kW) spends $27.79$ €, while minimizing cost $+\,0.2\,z$ reaches the same peak for $22.15$ €. What is the lesson?
With two objectives, optimizing one alone wastes the other
The pure minimax is always the best choice for the meter
Peak shaving is never convenient for the operator
The energy cost does not depend on the peak
Explanation. The pure minimax is degenerate in the cost: among the solutions with minimum peak it returns an arbitrary one. The weighted objective picks the cheapest.
EV charging LP: power $x_{vt}$ to vehicle $v$ in hour $t$ (1 h), energy price $\pi_t$, availability datum $a_{vt} \in \{0,1\}$, charger power $\bar p_v$, required energy $e_v$, efficiency $\eta$, base load $b_t$, meter limit $k$; minimize $\sum_{v,t}\pi_tx_{vt}$. A sensitivity analysis on the meter limit $k$ gives the same cost for every value of $k$, even very small ones. What should be suspected first?
That the model is infeasible for small $k$
That the energy prices $\pi_t$ are wrong
Our own code, e.g. `RHS = nuovaC` on a constraint storing `C - base[t]`
A bug in Gurobi
Explanation. It really happened while preparing the case study: when a sensitivity analysis changes nothing, suspect the code before the model.
EV charging LP: power $x_{vt}$ to vehicle $v$ in hour $t$ (1 h), energy price $\pi_t$, availability datum $a_{vt} \in \{0,1\}$, charger power $\bar p_v$, required energy $e_v$, efficiency $\eta$, base load $b_t$, meter limit $k$; minimize $\sum_{v,t}\pi_tx_{vt}$. Which constraints couple the vehicles to one another?
The energy constraints $\eta\sum_t x_{vt} \ge e_v$
The meter constraints $\sum_v x_{vt} + b_t \le k$, one per hour
The charger limits $x_{vt} \le a_{vt}\bar p_v$
The non-negativity constraints $x_{vt} \ge 0$
Explanation. Without the meter limit every vehicle could be optimized separately; the hourly meter constraints make them compete for the power.
EV charging LP: power $x_{vt}$ to vehicle $v$ in hour $t$ (1 h), energy price $\pi_t$, availability datum $a_{vt} \in \{0,1\}$, charger power $\bar p_v$, required energy $e_v$, efficiency $\eta$, base load $b_t$, meter limit $k$; minimize $\sum_{v,t}\pi_tx_{vt}$. Under which conditions is the shadow price of the energy constraint of vehicle $v$ equal to $\pi_t/\eta$ for one of its hours $t$?
When all the hours of the night have the same price $\pi_t$
When vehicle $v$ is plugged in during one single hour
When the meter constraint is active in every hour $t$
When in hour $t$ it is plugged in and no power limit is saturated
Explanation. The marginal kWh can then be bought exactly in hour $t$; if that hour were saturated, the dual would also include the value of the binding limit.
EV charging, one vehicle, two hours: it needs $e = 10$ kWh ($\eta = 1$), prices $\pi_1 = 0.12$ and $\pi_2 = 0.20$ €/kWh, charger power $\bar p = 8$ kW, so it charges 8 kWh in hour 1 and 2 in hour 2 (hours of 1 h, so kW and kWh coincide). How much would one more kW of charger power in hour 1 save?
$0.20$ €, the price of hour 2
$0.12$ €, the price of hour 1
$0.08$ €, the price difference $\pi_2 - \pi_1$
Nothing, since the requirement is already met
Explanation. One more kW in hour 1 moves one kWh from the expensive to the cheap hour: saving $0.20 - 0.12 = 0.08$ €. That is the (absolute) value of the dual of the power limit.
EV charging LP: power $x_{vt}$ to vehicle $v$ in hour $t$ (1 h), energy price $\pi_t$, availability datum $a_{vt} \in \{0,1\}$, charger power $\bar p_v$, required energy $e_v$, efficiency $\eta$, base load $b_t$, meter limit $k$; minimize $\sum_{v,t}\pi_tx_{vt}$. In the case study ($\eta = 0.95$) the shadow prices of the energy constraints are $0.0842$ €/kWh for vans V2, V3, V6 and $0.0947$ for V1, V4, V5. Why do they differ?
Their windows differ: the cheapest free hour costs $0.08$ for some, $0.09$ for others
Because the vans have different batteries $e_v$
Because the meter is saturated only for V1, V4, V5
Because $\eta$ differs between the two groups
Explanation. $0.0842 = 0.08/\eta$ and $0.0947 = 0.09/\eta$: vans whose windows cover the hours at $0.08$ buy their marginal kWh there; the others arrive late or leave early.
EV charging LP: power $x_{vt}$ to vehicle $v$ in hour $t$ (1 h), energy price $\pi_t$, availability datum $a_{vt} \in \{0,1\}$, charger power $\bar p_v$, required energy $e_v$, efficiency $\eta$, base load $b_t$, meter limit $k$; minimize $\sum_{v,t}\pi_tx_{vt}$. In the case study the nightly cost is $20.36$ € with meter limit $k = 120$ kW, $21.09$ € with $k = 80$, and the model is infeasible with $k = 60$ or $65$ kW. Why infeasible?
Because the energy prices become negative
Because the vehicles cannot get their energy within their windows
Because the solver needs $k \ge 70$
Because the peak-shaving variable becomes negative
Explanation. Too low a meter limit leaves too little power in the hours when the vans are plugged in: the energy requirements cannot all be met.
EV charging LP: power $x_{vt}$ to vehicle $v$ in hour $t$ (1 h), energy price $\pi_t$, availability datum $a_{vt} \in \{0,1\}$, charger power $\bar p_v$, required energy $e_v$, efficiency $\eta$, base load $b_t$, meter limit $k$; minimize $\sum_{v,t}\pi_tx_{vt}$. Minimizing cost $+\,\rho z$ ($z$ = peak draw) for growing $\rho$, the case study finds: $\rho = 0$: cost $20.36$ €, peak $103.4$ kW; $\rho = 0.1$: $21.39$ €, $74.9$ kW; $\rho = 0.2$: $22.15$ €, $68.0$ kW. What does this show?
Cutting the peak is very expensive
Peak and cost do not interact
The pure cost minimum already has the minimum peak
Large peak cuts cost little: $-28\%$ for about one euro
Explanation. The trade-off frontier is steep at first: cutting the peak from 103 to 75 kW costs about one euro per night, getting to 68 kW less than two.
EV charging LP: power $x_{vt}$ to vehicle $v$ in hour $t$ (1 h), energy price $\pi_t$, availability datum $a_{vt} \in \{0,1\}$, charger power $\bar p_v$, required energy $e_v$, efficiency $\eta$, base load $b_t$, meter limit $k$; minimize $\sum_{v,t}\pi_tx_{vt}$. Which condition on the data is necessary for the LP to be feasible, whatever the meter limit?
$e_v \le \bar p_v$ for every vehicle $v$: one hour of charging is enough
$\sum_t \pi_t \ge e_v$ for every vehicle $v$
$\eta\,\bar p_v \sum_t a_{vt} \ge e_v$ for every vehicle $v$
$k \ge b_t$ in the most expensive hour only
Explanation. Vehicle $v$ can receive at most $\eta\,\bar p_v$ kWh in each hour in which it is plugged in: if $\eta\,\bar p_v\sum_t a_{vt} < e_v$ its energy constraint cannot hold. The meter can make the model infeasible even when this holds.
A company fleet of electric vans charges at night when energy is cheap. What risk does the smart-charging chapter of the lab point out?
Vans may not be available in the morning
If all charge together, the peak load explodes
Energy prices are fixed by contract
Chargers cannot modulate power
Explanation. Charging everything in the cheap hours concentrates the demand: power costs grow and the meter limit can be exceeded; the model spreads the power over vehicles and hours.
The smart-charging problem «seems» to need on/off variables but is a pure LP. Why?
Because Gurobi cannot handle binaries
Because vehicles never stop charging
Because prices are constant
The true decision is continuous
Explanation. The model decides the power given to each vehicle in each hour, a continuous quantity between 0 and the charger power: no on/off variable is needed.
EV charging LP: power $x_{vt}$ to vehicle $v$ in hour $t$ (1 h), energy price $\pi_t$, availability $a_{vt} \in \{0, 1\}$, charger power $\bar p_v$, required energy $e_v$, efficiency $\eta$, base load $b_t$, meter limit $k$; minimize $\sum_{v,t}\pi_tx_{vt}$ with $\eta\sum_tx_{vt} \ge e_v$, $x_{vt} \le \bar p_va_{vt}$, $\sum_vx_{vt} + b_t \le k$. One vehicle, two hours: $e = 10$ kWh, $\eta = 1$, prices $0.10$ and $0.20$ €/kWh, charger power $\bar p = 8$ kW. What are the cost and the shadow price of the energy requirement?
Cost $1.00$ €, shadow price $0.10$
Cost $2.00$ €, shadow price $0.20$
Cost $1.20$ €, shadow price $0.20$
Cost $1.20$ €, shadow price $0.10$
Explanation. 8 kWh in the cheap hour, 2 in the expensive one: $0.8 + 0.4 = 1.20$ €. The 11th kWh would go to the expensive hour, so the dual is $0.20$ €/kWh.
EV charging LP: power $x_{vt}$ to vehicle $v$ in hour $t$ (1 h), energy price $\pi_t$, availability $a_{vt} \in \{0, 1\}$, charger power $\bar p_v$, required energy $e_v$, efficiency $\eta$, base load $b_t$, meter limit $k$; minimize $\sum_{v,t}\pi_tx_{vt}$ with $\eta\sum_tx_{vt} \ge e_v$, $x_{vt} \le \bar p_va_{vt}$, $\sum_vx_{vt} + b_t \le k$. One vehicle, two hours, $e = 10$ kWh, prices $0.10$ and $0.20$ €/kWh, $\bar p = 8$ kW: what is one more kW of charger power worth in hour 1?
$0.10$ €: one kWh moves to hour 1
$0.20$ €: the price of hour 2
$0$: the power limit is not active here
$0.30$ €: the sum of the two prices
Explanation. With $\bar p = 9$ one more kWh is charged at $0.10$ instead of $0.20$: the saving is the price difference, $0.10$ € per kW.
EV charging LP: power $x_{vt}$ to vehicle $v$ in hour $t$ (1 h), energy price $\pi_t$, availability $a_{vt} \in \{0, 1\}$, charger power $\bar p_v$, required energy $e_v$, efficiency $\eta$, base load $b_t$, meter limit $k$; minimize $\sum_{v,t}\pi_tx_{vt}$ with $\eta\sum_tx_{vt} \ge e_v$, $x_{vt} \le \bar p_va_{vt}$, $\sum_vx_{vt} + b_t \le k$. One vehicle, two hours, $e = 10$ kWh, prices $0.10$ and $0.20$ €/kWh, but now $\bar p = 12$ kW. What are the cost and the duals?
Cost $1.20$ €, both duals unchanged here
Cost $1.00$ €, energy dual $0.20$
Cost $2.00$ €, power dual $0.10$
Cost $1.00$ €, duals $0.10$ and $0$
Explanation. All 10 kWh fit in the cheap hour: cost $1.00$ €; the marginal kWh still goes to hour 1 (dual $0.10$) and the power limit is slack (dual $0$).
EV charging LP: power $x_{vt}$ to vehicle $v$ in hour $t$ (1 h), energy price $\pi_t$, availability $a_{vt} \in \{0, 1\}$, charger power $\bar p_v$, required energy $e_v$, efficiency $\eta$, base load $b_t$, meter limit $k$; minimize $\sum_{v,t}\pi_tx_{vt}$ with $\eta\sum_tx_{vt} \ge e_v$, $x_{vt} \le \bar p_va_{vt}$, $\sum_vx_{vt} + b_t \le k$. In the gurobipy code the availability is not a constraint: `x[v, t].UB = P[v] * disp[v, t]`. What happens when vehicle $v$ is not plugged in at hour $t$?
The model becomes infeasible
Its upper bound is 0
It charges at full power anyway
The variable becomes free in sign
Explanation. With `disp[v, t] = 0` the bound $x_{vt} \le \bar p_va_{vt}$ becomes $x_{vt} \le 0$: availability windows are handled through variable bounds.
EV charging LP: power $x_{vt}$ to vehicle $v$ in hour $t$ (1 h), energy price $\pi_t$, availability $a_{vt} \in \{0, 1\}$, charger power $\bar p_v$, required energy $e_v$, efficiency $\eta$, base load $b_t$, meter limit $k$; minimize $\sum_{v,t}\pi_tx_{vt}$ with $\eta\sum_tx_{vt} \ge e_v$, $x_{vt} \le \bar p_va_{vt}$, $\sum_vx_{vt} + b_t \le k$. Case study: six vans with different night windows, stylized hourly prices with an evening peak, base load of the building, meter $k = 120$ kW, $\eta = 0.95$. Why does the energy constraint read $\eta\sum_tx_{vt} \ge e_v$?
Because $\eta$ converts kWh into euros
Because the meter takes $\eta$ of the power
Because the price includes taxes
Only a share $\eta$ reaches the battery
Explanation. With $\eta = 0.95$ a vehicle must draw $e_v/0.95$ kWh from the grid; that is why its dual is the hour price divided by $\eta$.
EV charging LP: power $x_{vt}$ to vehicle $v$ in hour $t$ (1 h), energy price $\pi_t$, availability $a_{vt} \in \{0, 1\}$, charger power $\bar p_v$, required energy $e_v$, efficiency $\eta$, base load $b_t$, meter limit $k$; minimize $\sum_{v,t}\pi_tx_{vt}$ with $\eta\sum_tx_{vt} \ge e_v$, $x_{vt} \le \bar p_va_{vt}$, $\sum_vx_{vt} + b_t \le k$. In the gurobipy code the energy and meter constraints are kept as `v_ene = m.addConstrs(...)` and `v_rete = m.addConstrs(...)`. Why?
To read duals and change RHS
To delete them after the solve
Because Gurobi requires named constraints
To print them in the solver log
Explanation. The duals of `v_ene` are the prices of the marginal hours; `v_rete` is the meter constraint whose `RHS` is changed in the sensitivity analysis (minus the base load!).
EV charging LP: power $x_{vt}$ to vehicle $v$ in hour $t$ (1 h), energy price $\pi_t$, availability $a_{vt} \in \{0, 1\}$, charger power $\bar p_v$, required energy $e_v$, efficiency $\eta$, base load $b_t$, meter limit $k$; minimize $\sum_{v,t}\pi_tx_{vt}$ with $\eta\sum_tx_{vt} \ge e_v$, $x_{vt} \le \bar p_va_{vt}$, $\sum_vx_{vt} + b_t \le k$. Case study: which constraints are written as variable bounds and which as explicit constraints?
All of them as variable bounds
All of them as explicit constraints
Power as bounds; energy, meter as constraints
Energy as a bound; the rest as constraints
Explanation. $x_{vt} \le \bar p_va_{vt}$ concerns a single variable, so it is a bound; energy (one per vehicle) and meter (one per hour) involve sums of variables.
EV charging LP: power $x_{vt}$ to vehicle $v$ in hour $t$ (1 h), energy price $\pi_t$, availability $a_{vt} \in \{0, 1\}$, charger power $\bar p_v$, required energy $e_v$, efficiency $\eta$, base load $b_t$, meter limit $k$; minimize $\sum_{v,t}\pi_tx_{vt}$ with $\eta\sum_tx_{vt} \ge e_v$, $x_{vt} \le \bar p_va_{vt}$, $\sum_vx_{vt} + b_t \le k$. Case results: minimum cost $20.36$ €/night with a peak draw of $103.4$ kW (limit 120); the smallest possible peak is $68.0$ kW. What does the cost-minimizing plan do?
It spreads the charging evenly over the night
It charges in the cheap hours
It charges only during the evening peak
It keeps the draw at 68 kW
Explanation. Minimizing only the energy cost pushes every vehicle into the cheap hours, so the total draw peaks at 103 kW; peak shaving spreads it and stays at 68 kW.
EV charging LP (minimize energy cost, meter limit $\sum_vx_{vt} + b_t \le k$): night cost $21.93$ € at $k = 70$ kW, $21.09$ at $80$, $20.63$ at $90$, $20.36$ at $120$; infeasible at $60$–$65$. Why do the savings per extra kW shrink as $k$ grows?
An LP's value is convex in a RHS
Energy prices fall during the night
The batteries get full at high $k$
It is numerical noise
Explanation. For a minimum, $\tilde z(k)$ is convex and, for a $\le$ constraint, non-increasing: its slope (the shadow price of the meter) rises toward zero as $k$ grows and the meter stops binding.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. With weights $u_r, v_i \ge 0$, the efficiency ratio of DMU $j$ is $\sum_r u_ry_{rj}/\sum_i v_ix_{ij}$. How is the relative efficiency of DMU $o$ defined?
As the ratio between its total output and the average output of all DMUs
As its efficiency ratio computed with weights fixed by management
As the maximum of its ratio over weights giving no DMU a ratio above $1$
As the minimum of its ratio over all non-negative weights
Explanation. Each DMU chooses the weights that show it in the best light: if even then it stays below $1$, the inefficiency does not depend on an arbitrary choice of prices.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. The fractional CCR model maximizes the ratio $\sum_r u_ry_{ro}/\sum_i v_ix_{io}$ subject to ratio $\le 1$ for every DMU. What allows the Charnes–Cooper transformation to turn it into an LP?
Scaling all weights by $t > 0$ changes no ratio, so one may impose $\sum_i v_ix_{io} = 1$
All the ratios are smaller than $1$, so the denominators can be dropped
The optimal weights are integers, so the ratios can be enumerated
The outputs are the same for all DMUs, so only the inputs matter
Explanation. With the denominator of the objective normalized to $1$ the objective is the numerator, and each ratio constraint multiplied by its positive denominator becomes linear.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Input-oriented CCR envelopment form: $\min\theta$ subject to $\sum_j\lambda_jx_{ij} \le \theta x_{io}$, $\sum_j\lambda_jy_{rj} \ge y_{ro}$, $\lambda_j \ge 0$, $\theta$ free. What is the reference set (the peers) of DMU $o$?
All the DMUs with efficiency $\tilde\theta = 1$
The DMUs $j$ with $\tilde\lambda_j > 0$ in the optimal solution
All the DMUs with larger outputs than $o$
The DMUs that use the same inputs as $o$
Explanation. The peers are the efficient DMUs combined into the virtual DMU of $o$: the units $o$ should learn from.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Input-oriented CCR envelopment form: $\min\theta$ subject to $\sum_j\lambda_jx_{ij} \le \theta x_{io}$, $\sum_j\lambda_jy_{rj} \ge y_{ro}$, $\lambda_j \ge 0$, $\theta$ free. In the case study the CCR optimum of branch 6 has $\sum_j \tilde\lambda_j = 1.924$ (and is unique). What does it suggest about its scale?
Too small (increasing returns): consider merging it
Efficient at every scale: nothing to change
Wrong data: the sum must be at most $1$
Too large (decreasing returns): consider splitting it
Explanation. $\sum_j\tilde\lambda_j > 1$ signals decreasing returns, $< 1$ increasing returns; branch 6 is in fact efficient in the BCC model, so its CCR inefficiency is due to size.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Input-oriented CCR envelopment form: $\min\theta$ subject to $\sum_j\lambda_jx_{ij} \le \theta x_{io}$, $\sum_j\lambda_jy_{rj} \ge y_{ro}$, $\lambda_j \ge 0$, $\theta$ free. A second phase maximizes the input and output slacks with $\theta$ fixed at $\tilde\theta$. When is DMU $o$ weakly but not strongly efficient?
When $\tilde\theta < 1$
When $\tilde\theta = 1$ and all the slacks are zero
When $\tilde\theta = 1$ but some optimal slack of the second phase is positive
When it is not a peer of any other DMU
Explanation. It cannot contract all inputs in the same proportion, but it can reduce at least one input (or expand an output): another combination of DMUs does the same with less.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Input-oriented CCR envelopment form: $\min\theta$ subject to $\sum_j\lambda_jx_{ij} \le \theta x_{io}$, $\sum_j\lambda_jy_{rj} \ge y_{ro}$, $\lambda_j \ge 0$, $\theta$ free. What sign do the shadow prices of the output constraints $\sum_j\lambda_jy_{rj} \ge y_{ro}$ have, and what are they?
$\ge 0$; they are the optimal output weights $\tilde u_r$ of the multiplier form
$\le 0$; they are the output slacks of the second phase
Any sign; they are the optimal intensities $\tilde\lambda_j$
$\ge 0$; they are the optimal input weights $\tilde v_i$
Explanation. Raising the right-hand side of a $\ge$ constraint shrinks the region, so the minimum $\tilde\theta$ cannot decrease; by duality these duals are the weights $\tilde u_r$.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. In the case study of 12 bank branches, branch 7 is a peer (reference unit) of five inefficient branches. What does the lab recommend before acting on the targets?
Nothing: the targets computed by the LP are exact
Check the data of the most cited peers and repeat the analysis without them
Remove all the inefficient branches from the analysis
Switch to the BCC model, which has no peers
Explanation. DEA is relative: a single DMU on the frontier can change the verdict on many others, and a recording error would make it “too good”.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. The BCC model adds $\sum_j\lambda_j = 1$ to the input-oriented CCR envelopment form. Which relation between the two efficiencies of the same DMU always holds?
Explanation. Hence the scale efficiency $\tilde\theta^{\rm CCR}/\tilde\theta^{\rm BCC}$ lies in $(0, 1]$. The extra constraint shrinks the feasible region of a minimization, so $\tilde\theta$ cannot decrease; the difference between the two measures is due to size.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Input-oriented CCR envelopment form: $\min\theta$ subject to $\sum_j\lambda_jx_{ij} \le \theta x_{io}$, $\sum_j\lambda_jy_{rj} \ge y_{ro}$, $\lambda_j \ge 0$, $\theta$ free. Let $\tilde h_o$ be the optimal value of the CCR multiplier form (the relative efficiency of $o$). Which statement links it to the optimal $\tilde\theta$ of the envelopment form?
Explanation. The envelopment form is the dual of the multiplier form: by strong duality the optimal values coincide, so the optimal radial contraction of the inputs is the relative efficiency.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. The BCC model is the input-oriented CCR envelopment form plus the constraint $\sum_j\lambda_j = 1$. Which facts prove $\tilde\theta^{\rm BCC} \ge \tilde\theta^{\rm CCR}$?
Strong duality between the BCC and the CCR models, which have the same dual
The extra constraint shrinks the region, and a minimum over a smaller set is never lower
Variable returns to scale always make every DMU look worse than constant returns
The slacks of the second phase are non-negative in both models
Explanation. Same objective and the same constraints plus one: the feasible set of BCC is contained in that of CCR.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. CCR multiplier form: $\max\sum_r u_ry_{ro}$ subject to $\sum_i v_ix_{io} = 1$ and $\sum_r u_ry_{rj} - \sum_i v_ix_{ij} \le 0$ for every $j$, $u, v \ge 0$. In its dual (the envelopment form), why is $\theta$ free and each $\lambda_j \ge 0$?
$\theta$ is an efficiency, which can have any sign; the $\lambda_j$ are weights, hence $\ge 0$
The outputs $y_{rj}$ are positive, so both the dual variables must be $\ge 0$ except $\theta$
The normalization is an equality (free dual); the ratio constraints are $\le$ in a max ($\ge 0$)
The inputs $x_{ij}$ are positive, so the duals of the ratio constraints are $\ge 0$
Explanation. These are the duality conversion rules: equality $\to$ free variable, $\le$ constraint in a maximization $\to$ variable $\ge 0$.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Why does DEA let each DMU choose its own weights $u_r, v_i$, instead of comparing outputs and inputs at fixed prices?
No common prices exist: an inefficiency must survive the most favourable weights
Fixed weights would make the LP infeasible for the most efficient DMUs
The weights must be integers, and fixed prices are rarely integers
Fixed prices would make every DMU efficient, so no ranking would remain
Explanation. If a DMU stays below $1$ even with the weights most favourable to it, its inefficiency does not depend on an arbitrary choice of prices.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. In the CCR multiplier form, which quantities are the decision variables of the LP solved for DMU $o$?
The inputs $x_{ij}$ and outputs $y_{rj}$ of all DMUs
The efficiencies of all the DMUs
The intensities $\lambda_j$ of the virtual DMU
The output weights $u_r$ and input weights $v_i$
Explanation. In DEA $x$ and $y$ are data; the multiplier form chooses the weights, while the intensities $\lambda_j$ are the variables of the dual (envelopment) form.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. One input, one output. DMU 1 uses $x = 2$ to produce $y = 2$; DMU 5 uses $x = 2$ to produce $y = 1$. DMU 5 has BCC efficiency $\tilde\theta = 1$ (its input cannot be contracted radially). Is it strongly efficient?
Yes: $\tilde\theta = 1$ means strongly efficient
No: it is weakly efficient, with output slack $1$
No: its efficiency is $0.5$
Yes, because it uses the smallest input
Explanation. DMU 1 does more with the same input: the second phase finds output slack $\tilde s^+ = 1$. With $\tilde\theta = 1$ but a positive slack, DMU 5 is only weakly efficient.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Case study of 12 bank branches: branch 1 has CCR efficiency $0.806$, BCC efficiency $0.900$ and, in the CCR optimum, $\sum_j\tilde\lambda_j = 0.671$. What is the diagnosis?
Too small (increasing returns) and also inefficient once scale is removed
Too large: it should be split
Efficient: the CCR score is an artefact
Efficient in the BCC model, so only a scale problem
Explanation. $\sum\tilde\lambda_j < 1$ signals increasing returns (too small); BCC $0.90 < 1$ means a technical inefficiency remains even comparing with branches of its size.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Case study: CCR-efficient branches are 2, 7, 9, 10; BCC-efficient branches are 2, 3, 6, 7, 8, 9, 10, 12. What do branches 3, 6, 8, 12 have in common?
They are inefficient in every model
They are peers of all the other branches
Their CCR inefficiency is due only to scale
They have data errors
Explanation. BCC efficiency $1$ with CCR below $1$ means scale efficiency $\tilde\theta^{\rm CCR}/\tilde\theta^{\rm BCC} < 1$: they work well for their size (here all too large, $\sum\tilde\lambda_j > 1$).
A bank compares its twelve branches with Data Envelopment Analysis (DEA). Why is a simple comparison of spending not enough?
Because branches have the same size
Because the data are confidential
Because DEA needs only one output
Outputs have no common price
Explanation. Loans and deposits have no agreed relative value, and a large branch is not inefficient just because it spends more: DEA compares each branch with the best observed practices.
How does DEA compute the efficiency index of the units it compares?
By solving one LP for each unit
By one regression on all units
By ranking units by output
By a single LP for all units together
Explanation. Each unit gets its own LP (same constraints, different objective and normalization); the index compares it with the best observed practices.
Besides an efficiency index, what does the DEA chapter of the lab learn to read in the dual (envelopment) form?
The prices of the outputs on the market
Reference units and targets
The number of employees to hire next year
The demand of each unit
Explanation. The envelopment form names the peers ($\tilde\lambda_j > 0$) and, through $\tilde\theta$ and the slacks, how much each input should shrink; BCC also separates technical and scale inefficiency.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. What is a DMU in DEA?
A decision variable of the LP
A data matrix of the model
A unit compared with similar units
The best unit of the sample
Explanation. Decision Making Unit: branches, hospitals, schools... each uses the same kinds of inputs to produce the same kinds of outputs, so they can be compared.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Relative efficiency is the weighted ratio $\sum_ru_ry_{ro}/\sum_iv_ix_{io}$ with weights chosen by the DMU itself. What value means «efficient»?
$1$, the maximum allowed
$0$, the minimum allowed
Any value above $1$
The mean of all the ratios
Explanation. The weights must keep every DMU's ratio at most $1$; a DMU is efficient when, with its most favourable weights, it reaches $1$.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. The CCR fractional model maximizes $\sum_ru_ry_{ro}/\sum_iv_ix_{io}$ with every ratio $\le 1$. Why can it be turned into an LP (Charnes–Cooper)?
Because the ratios are always equal to 1
Scaling all weights changes no ratio
Because the inputs are positive integers
Because the outputs are fixed
Explanation. Ratios are invariant to a common scaling of the weights, so one can impose $\sum_iv_ix_{io} = 1$: the objective becomes the numerator and each ratio constraint, multiplied by its positive denominator, becomes linear.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Input-oriented CCR envelopment form: $\min\theta$ subject to $\sum_j\lambda_jx_{ij} \le \theta x_{io}$, $\sum_j\lambda_jy_{rj} \ge y_{ro}$, $\lambda_j \ge 0$. Why is $\tilde\theta \le 1$ always?
Because the outputs are positive
Because every $\lambda_j \le 1$ by construction
The DMU alone is feasible
Because of the normalization of the inputs
Explanation. The DMU itself, taken alone, is a feasible virtual unit with $\theta = 1$; minimizing can only do as well or better, so $\tilde\theta \le 1$.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Input-oriented CCR envelopment form: $\min\theta$ subject to $\sum_j\lambda_jx_{ij} \le \theta x_{io}$, $\sum_j\lambda_jy_{rj} \ge y_{ro}$, $\lambda_j \ge 0$. In the CCR envelopment form, $\sum_j\tilde\lambda_j < 1$ suggests increasing returns (the DMU is too small) and $> 1$ decreasing returns. Under which condition is this reading valid?
When the optimum is unique
Always, whatever the optimal solution
Only when $\tilde\theta = 1$
Only with a single output
Explanation. With several optimal $\lambda$'s their sum can differ from one solution to another, and the direction of the scale inefficiency would be ambiguous.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Input-oriented CCR envelopment form: $\min\theta$ subject to $\sum_j\lambda_jx_{ij} \le \theta x_{io}$, $\sum_j\lambda_jy_{rj} \ge y_{ro}$, $\lambda_j \ge 0$. After the radial contraction, a second phase computes the slacks $s_i^-$, $s_r^+$ at fixed $\tilde\theta$. What are the targets of DMU $o$?
$\hat x_{io} = x_{io}$, $\hat y_{ro} = y_{ro}$
$\hat x_{io} = x_{io} - s_i^-$, outputs unchanged
Only $\hat x_{io} = \tilde\theta x_{io}$, outputs unchanged
$\tilde\theta x_{io} - s_i^-$ and $y_{ro} + s_r^+$
Explanation. First the radial contraction by $\tilde\theta$, then the residual slack of each input is removed and each output slack added.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Input-oriented CCR envelopment form: $\min\theta$ subject to $\sum_j\lambda_jx_{ij} \le \theta x_{io}$, $\sum_j\lambda_jy_{rj} \ge y_{ro}$, $\lambda_j \ge 0$. When is a DMU **strongly** efficient?
When $\tilde\theta = 1$, whatever the slacks
$\tilde\theta = 1$ and no slack
When it is a peer of another DMU of the sample
When its slacks are positive
Explanation. With $\tilde\theta = 1$ but a positive slack the DMU is only weakly efficient: it cannot shrink all inputs proportionally, but another unit does the same with less of some input.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Five DMUs with one input and one output: $x = (2, 4, 6, 5, 2)$, $y = (2, 6, 7, 3, 1)$. What is the CCR efficiency of DMU 1, with one input and one output?
$0.67$
$1.00$
$0.40$
$0.50$
Explanation. With one input and one output the CCR efficiency is $y/x$ divided by the best ratio, $6/4 = 1.5$ (DMU 2): $(2/2)/1.5 = 0.667$.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Five DMUs with one input and one output: $x = (2, 4, 6, 5, 2)$, $y = (2, 6, 7, 3, 1)$. In the CCR envelopment form for DMU 1, the only peer is DMU 2. What is $\tilde\lambda_2$?
$1$
$2/3$
$1/3$
$1/2$
Explanation. The virtual unit $\lambda_2(4, 6)$ must produce DMU 1's output: $6\lambda_2 = 2$, so $\lambda_2 = 1/3$, and it uses $4/3 = 0.667\cdot 2$ of input, i.e. $\tilde\theta = 0.667$.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Five DMUs with one input and one output: $x = (2, 4, 6, 5, 2)$, $y = (2, 6, 7, 3, 1)$. BCC efficiencies: $(1;\ 1;\ 1;\ 0.5;\ 1)$; CCR: $(0.667;\ 1;\ 0.778;\ 0.4;\ 0.333)$. What is the scale efficiency $\mathrm{SE} = \tilde\theta^{\rm CCR}/\tilde\theta^{\rm BCC}$ of DMU 4?
$0.5$
$0.4$
$1.25$
$0.8$
Explanation. $0.4/0.5 = 0.8$: part of DMU 4's inefficiency is technical (BCC $0.5$), part is due to scale.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Five DMUs with one input and one output: $x = (2, 4, 6, 5, 2)$, $y = (2, 6, 7, 3, 1)$. DMU 5 ($x = 2$, $y = 1$) has $\tilde\theta^{\rm BCC} = 1$ but a second-phase output slack $\tilde s^+ = 1$. Why?
It is the most efficient DMU
DMU 1 does better with it
Its input could be cut in half
It is only a numerical error
Explanation. No convex combination uses less than 2 units of input, so $\tilde\theta = 1$; but DMU 1 does better with the same input: DMU 5 is only weakly efficient.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Bank case: 12 branches, inputs staff (FTE) and operating costs, outputs loans and deposits. How are the data of the twelve branches obtained in the case study?
From a real bank's balance sheet
From a survey of the managers
Generated by the script with a fixed seed
Typed in by hand from the notes
Explanation. They are synthetic but realistic: a production function with decreasing returns to scale plus a random inefficiency per branch, generated with a fixed seed and saved in a CSV file.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Bank case: 12 branches, inputs staff (FTE) and operating costs, outputs loans and deposits. How many inputs, outputs and DMUs does the case study have?
$m = 2$, $p = 2$, $n = 12$
$m = 1$, $p = 1$, $n = 12$
$m = 2$, $p = 1$, $n = 5$
$m = 12$, $p = 2$, $n = 2$
Explanation. Staff (FTE) and operating costs as inputs, loans and deposits as outputs, twelve branches: each envelopment LP has at most 16 variables and 13 constraints.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Bank case: 12 branches, inputs staff (FTE) and operating costs, outputs loans and deposits. Why are the data of the bank case generated with decreasing returns to scale?
To make every branch efficient
To make the LPs smaller
Because CCR requires it
So that CCR and BCC differ
Explanation. With non-constant returns, large branches look inefficient under CCR but may be efficient under BCC: the case shows the gap between technical and scale efficiency.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Bank case: 12 branches, inputs staff (FTE) and operating costs, outputs loans and deposits. Branch 7 is the smallest (9 FTE, 640 k€ of costs) and is a peer of five inefficient branches. What does «peer» mean?
A branch with the same efficiency
A unit with $\tilde\lambda_j > 0$ in the virtual unit
A branch of the same size
The branch with the lowest costs
Explanation. The peers are the efficient units that make up the virtual unit of DMU $o$ in the envelopment form: they are its benchmarks.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Input-oriented CCR envelopment form: $\min\theta$ subject to $\sum_j\lambda_jx_{ij} \le \theta x_{io}$, $\sum_j\lambda_jy_{rj} \ge y_{ro}$, $\lambda_j \ge 0$. In the gurobipy function `inviluppo` the variable `theta` is created with `lb=-GRB.INFINITY`. Why?
Because $\theta$ must be negative
Because Gurobi needs a free objective
$\theta$ is free in the model
To allow $\theta > 1$
Explanation. In the envelopment form $\theta$ is a free variable; the constraints and $\lambda_o = 1$ give $0 < \tilde\theta \le 1$ anyway. Forgetting `lb` would just impose a harmless $\theta \ge 0$ here, but the model declares what it states.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Input-oriented CCR envelopment form: $\min\theta$ subject to $\sum_j\lambda_jx_{ij} \le \theta x_{io}$, $\sum_j\lambda_jy_{rj} \ge y_{ro}$, $\lambda_j \ge 0$. The function `inviluppo(X, Y, o, vrs=False)` adds `lam.sum() == 1` when `vrs=True`. Which model does it then solve?
BCC, with variable returns to scale
CCR, with constant returns
The multiplier form
The second phase of the slacks
Explanation. The convexity constraint $\sum_j\lambda_j = 1$ makes the virtual unit a convex combination of observed units: the BCC model.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Input-oriented CCR envelopment form: $\min\theta$ subject to $\sum_j\lambda_jx_{ij} \le \theta x_{io}$, $\sum_j\lambda_jy_{rj} \ge y_{ro}$, $\lambda_j \ge 0$. For each branch the script solves both the envelopment form and the multiplier form, with an `assert` that the two optimal values coincide. What does this check?
That the data are positive
That every branch is efficient
That the solver is fast enough
Strong duality between the two forms
Explanation. The two forms are a primal–dual pair: equal optimal values (and the shadow price of the normalization equal to $\tilde\theta$) verify strong duality numerically.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Input-oriented CCR envelopment form: $\min\theta$ subject to $\sum_j\lambda_jx_{ij} \le \theta x_{io}$, $\sum_j\lambda_jy_{rj} \ge y_{ro}$, $\lambda_j \ge 0$. In the script one envelopment LP per DMU is built and solved. What changes from one DMU $o$ to the next?
The whole set of constraints
Only the terms of DMU $o$
The number of variables
The sense of the objective
Explanation. The constraint matrix of the observed units is the same; only the terms with $x_{io}$ and $y_{ro}$ change, so one function called with different `o` builds all twelve LPs.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Bank case: 12 branches, inputs staff (FTE) and operating costs, outputs loans and deposits. Branch 6: CCR $0.76$, BCC $1.00$, sum of the $\tilde\lambda_j$ $= 1.924$ (only peer: branch 7). What do the notes recommend?
Cut its staff by 24%
Close the branch down
Consider splitting it in two
Nothing: it is efficient
Explanation. BCC efficiency 1 means no technical inefficiency; the CCR gap is all scale, and a sum of $\lambda$'s above 1 signals decreasing returns: the branch is too big.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Bank case: 12 branches, inputs staff (FTE) and operating costs, outputs loans and deposits. Branch 1: CCR $0.8055$, BCC $0.90$, sum of $\tilde\lambda_j = 0.671$; after the second phase its cost target is $463.2$ k€ against $720$ actual. What is its situation?
Too small and inefficient
Too large, but technically efficient
Efficient in both models
Inefficient only in the outputs
Explanation. A sum of $\lambda$'s below 1 means increasing returns (too small), and BCC $< 1$ means technical inefficiency too; a residual cost slack of $116.8$ k€ remains after the radial contraction.
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Input-oriented CCR envelopment form: $\min\theta$ subject to $\sum_j\lambda_jx_{ij} \le \theta x_{io}$, $\sum_j\lambda_jy_{rj} \ge y_{ro}$, $\lambda_j \ge 0$. Branch 6 ($\tilde\theta = 0.76$): the shadow price of the deposits constraint is $0.0104$, equal to the optimal weight $\tilde u_2$ of the multiplier form. Why are these prices nonnegative?
Because outputs are positive numbers
Because $\theta \le 1$
Because the LP is degenerate
A $\ge$ in a minimum cannot lower $\tilde\theta$
Explanation. Raising the required output shrinks the feasible region, and in a minimum the optimum cannot improve: $\tilde\theta$ rises by $0.0104$ per million of deposits (checked by perturbation).
DEA: $n$ units (DMUs) $j$ use inputs $x_{ij}$ to produce outputs $y_{rj}$; DMU $o$ is evaluated. Input-oriented CCR envelopment form: $\min\theta$ subject to $\sum_j\lambda_jx_{ij} \le \theta x_{io}$, $\sum_j\lambda_jy_{rj} \ge y_{ro}$, $\lambda_j \ge 0$. Removing branch 7 (peer of five branches) and recomputing CCR, five branches change efficiency and branches 3 and 8 become efficient. What do the notes recommend?
Remove branch 7 permanently
Check the most cited peers' data
Ignore the result: DEA is stable
Use only the BCC model from now on
Explanation. DEA measures efficiency relative to the observed units: one frontier unit can change many judgements, so a recording error there would make it «too good».
Newsvendor: a product is bought at cost $c$, sold at price $p$, and unsold units are salvaged at $v < c$. What are the underage cost $c_u$ (per unit of unmet demand) and the overage cost $c_o$ (per unsold unit)?
$c_u = p$, $c_o = c$
$c_u = p - c$, $c_o = c - v$
$c_u = c - v$, $c_o = p - c$
$c_u = p - v$, $c_o = c$
Explanation. Underage = lost margin $p - c$; overage = cost of an unsold unit net of its salvage value, $c - v$.
Newsvendor: order quantity $q$ before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. If running short costs much more than running long ($c_u \gg c_o$), the optimal quantity $\tilde q$ is:
the mean demand $\mathbb E[D]$
a low quantile of the demand
zero
a high quantile of the demand
Explanation. $\alpha = c_u/(c_u + c_o)$ is close to $1$ and $\tilde q = F^{-1}(\alpha)$. With perishable goods (high $c_o$) one orders little.
Newsvendor: order quantity $q$ before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. Scenario LP: demand $d_s$ with probability $\pi_s$; the overage is a variable $o_s$ with $o_s \ge q - d_s$, $o_s \ge 0$ and term $\pi_sc_oo_s$ in the minimized cost. Why does $o_s = (q - d_s)^+$ hold at the optimum without binary variables?
Its positive cost pushes $o_s$ down to the larger of its two lower bounds
Because $q$ is larger than every demand $d_s$ at the optimum
Because Gurobi linearizes the $\max$ automatically
Because the scenarios are equally likely
Explanation. This positive-part trick returns unchanged in the CVaR (the excesses $\xi_s$) and in quantile regression.
Newsvendor: order quantity $q$ before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. What does the value of the stochastic solution (VSS) measure?
The expected value of a perfect demand forecast
The expected cost of the optimal order $\tilde q$
Expected cost of ordering $\mathbb E[D]$ minus expected cost of $\tilde q$
The variance of the cost at the optimal order
Explanation. VSS is the gain from modelling the uncertainty instead of plugging in the mean: in the case study $11.17$ € per cycle, $11\%$ of the cost.
Newsvendor: order quantity $q$ before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. In the case study, at $\tilde q = 110$ the probability of no stock-out, $\mathbb P(D \le \tilde q)$, is $69\%$, while the fill rate (expected share of demand served) is $96\%$. What does this show?
That the newsvendor model is wrong
That cycle service level and fill rate are different measures
That the fill rate is always the smaller of the two
That $\tilde q$ should equal the mean demand
Explanation. The two are often confused in contracts: promising $95\%$ probability of full coverage costs $45.59$ € per cycle more, promising a $95\%$ fill rate is almost free.
Newsvendor: order quantity $q$ before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. Three equally likely demand scenarios $D \in \{80, 100, 120\}$, $c_u = 9$, $c_o = 4$. What is the optimal quantity?
$100$, the mean demand
$80$, the smallest scenario
$110$, between the two largest
$120$, the largest scenario
Explanation. $\alpha = 9/13 = 0.6923$ and $F(100) = 2/3 < \alpha$: the smallest $q$ with $F(q) \ge \alpha$ is $120$. Check: $C(120) = 80$ against $C(100) = 86.7$.
Newsvendor: order quantity $q$ before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. $F$ is continuous. Which statement is the quantile rule for the optimal quantity $\tilde q$?
Newsvendor: order quantity $q$ before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. Which argument and assumptions give the quantile rule $F(\tilde q) = c_u/(c_u + c_o)$?
Explanation. It pays to order one more unit while $c_u(1 - F(q)) \ge c_oF(q)$; continuity of $F$ makes the equality attainable. No normality is needed; with discrete demand one takes the smallest $q$ with $F(q) \ge \alpha$.
Newsvendor: order quantity $q$ before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. Scenario LP with demands $d_s$ of probability $\pi_s$ and overage variables $o_s \ge q - d_s$, $o_s \ge 0$. What is needed for $o_s = (q - d_s)^+$ to hold at the optimum?
That every scenario has demand larger than $q$
That the coefficient $\pi_s\,c_o$ of $o_s$ in the minimized objective be positive
That $o_s$ be declared as a free variable
That the problem be a maximization
Explanation. If $\pi_sc_o > 0$, any $o_s$ above $\max\{q - d_s, 0\}$ could be lowered, reducing the cost. With a zero or negative coefficient the trick fails.
Newsvendor: order quantity $q$ before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. Bakery case study: $p = 15$, $c = 6$, salvage $v = 2$ €, demand normal with mean $100$ and standard deviation $20$. The optimal order is $\tilde q = 110.05$. Why above the mean?
Because the normal distribution is skewed to the right
Because the salvage value is positive
Because $\alpha = c_u/(c_u + c_o) = 9/13 > 1/2$
Because $c_o > c_u$
Explanation. $c_u = p - c = 9$, $c_o = c - v = 4$: running short costs more, so the critical ratio exceeds one half and $\tilde q = F^{-1}(0.6923)$ lies above the median $100$.
Newsvendor: order quantity $q$ before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. Demand is normal with mean $m$ and standard deviation $\sigma$, so $\tilde q = m + z\,\sigma$ with $z = \Phi^{-1}(\alpha)$ ($\Phi$ = standard normal distribution function, $\alpha = c_u/(c_u + c_o)$). When is the safety stock $z\sigma$ positive?
When $c_u > c_o$, i.e. $\alpha > 1/2$
When $c_o > c_u$, i.e. $\alpha < 1/2$
Always, since $\sigma > 0$
Only when the salvage value is zero
Explanation. $\Phi^{-1}(\alpha) > 0$ exactly when $\alpha > 1/2$; with expensive overage ($c_o > c_u$) one orders below the mean.
Newsvendor: order quantity $q$ before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. A risk-averse bakery minimizes $(1-\lambda)\,\mathbb E[\text{cost}] + \lambda\,\mathrm{CVaR}_{0.90}(\text{cost})$. In the case study, as $\lambda$ goes from $0$ to $1$, how does the order change?
It falls from $108.6$ to $101.2$: risk aversion means ordering less
It stays at $108.6$: the CVaR does not depend on $q$
It drops to zero: not ordering removes every risk
It rises from $108.6$ to $116.2$: the worst scenarios are shortages
Explanation. Here the costly tail comes from stock-outs ($c_u > c_o$), so protection means ordering more: $6.5$ € more on average cut the mean cost of the worst $10\%$ by $21.4$ €.
Multi-product newsvendor: three cakes ordered in quantities $q_i$, minimum expected cost of overage and underage, with a shared production budget $\sum_i c_iq_i \le 1200$ €. At the optimum the budget is fully spent and its shadow price is $-0.553$. How is it read?
Each euro of budget costs $0.553$ € of interest
One more euro of budget lowers the expected cost by about $0.553$ €
The budget should be cut by $55.3\%$
The cakes are $55.3\%$ correlated
Explanation. In a minimization a $\le$ budget has a non-positive dual: relaxing it by one euro lowers the optimal expected cost by $0.553$ €.
Multi-product newsvendor with a shared budget $\sum_i c_iq_i \le B$ that is active at the optimum. Compared with the single-product optimal quantities (each product on its own), the quantities with the budget are:
higher, to use the whole budget
identical, since the products are independent
zero for all but the most profitable product
lower: the budget multiplier acts like an extra unit cost
Explanation. With multiplier $\lambda$ the optimality condition of each product includes the term $\lambda c_i$, as if the purchase cost were higher: every quantity shrinks (in the case study from $111.1$ to $99.3$ for the first cake).
The newsvendor model describes a very common decision. Which one?
Choosing a price after observing the demand
Splitting a budget among channels with known returns
Routing flows on a network with known demands
Choosing a quantity before observing the demand
Explanation. Order too much and units are left unsold; too little and sales are lost: fashion, fresh food, drugs, hotel capacity, spare parts. It is the entry point to stochastic optimization: decide first, discover later.
According to the lab notes, what is the «clear-cut result» that makes the newsvendor didactically strong?
The optimal quantity is not the mean demand
The optimal quantity is always the mean demand
Ordering the largest possible demand is always optimal
Uncertainty can be replaced by its expected value
Explanation. The optimum is a quantile of demand fixed by the ratio of the two costs, generally different from the mean; replacing the uncertainty with its mean has a measurable cost (the VSS).
Which tools for «deciding first and discovering later» does the newsvendor chapter of the lab introduce?
Integer variables and branch-and-bound
Kernels and support vectors
Scenarios, VSS and risk measures
Shadow prices of capacity constraints only
Explanation. The chapter turns the stochastic problem into a scenario LP, measures the value of modelling uncertainty (VSS) and adds service levels and risk aversion (mean–CVaR).
Newsvendor: order quantity $q$ chosen before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. For which product would you expect a low critical ratio $c_u/(c_u + c_o)$, hence a small order?
A spare part whose shortage stops a production line
A perishable item with low margin and costly leftovers
A drug that must never be missing in a hospital
A best-selling item with a high margin
Explanation. If unsold units are expensive ($c_o$ large) and the lost margin small ($c_u$ small), the ratio is low and one orders a low quantile of demand; costly shortages push the order up.
Newsvendor: order quantity $q$ chosen before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. The rule $F(\tilde q) = c_u/(c_u + c_o)$ assumes $F$ continuous. With a **discrete** demand, which $q$ is optimal?
The mean of the discrete demand
The $q$ with $F(q)$ closest to $c_u/(c_u + c_o)$
The smallest $q$ with $F(q) \ge c_u/(c_u + c_o)$
The largest $q$ with $F(q) \le c_u/(c_u + c_o)$
Explanation. With jumps in $F$ the equation may have no solution; the marginal argument (the next unit pays while $F(q) < c_u/(c_u + c_o)$) gives the smallest $q$ with $F(q) \ge c_u/(c_u + c_o)$, as in the three-scenario example of the notes.
Newsvendor: order quantity $q$ chosen before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. Three equiprobable scenarios $D \in \{80, 100, 120\}$, $c_u = 9$, $c_o = 4$. What is the expected cost of ordering the mean, $q = 100$?
$80.0$
$86.7$
$180.0$
$100.0$
Explanation. $C(100) = \tfrac13[4\cdot 20 + 0 + 9\cdot 20] = 260/3 \approx 86.7$, more than $C(120) = 80$ at the optimum: ordering the mean costs $6.7$ more.
Newsvendor: order quantity $q$ chosen before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. Three equiprobable scenarios $D \in \{80, 100, 120\}$ with $c_u = 9$, $c_o = 4$, so $\alpha^* = 9/13 \approx 0.692$. Why is $q = 100$ not optimal according to the discrete quantile rule?
Because $100$ is the mean, never optimal
Because $F(100) = 1/3$ is far below $\alpha^*$
Because $F(100) = 1 > \alpha^*$
Because $F(100) = 2/3 \approx 0.667 < \alpha^*$
Explanation. The rule takes the smallest $q$ with $F(q) \ge 0.692$: $F(80) = 1/3$, $F(100) = 2/3 < 0.692$, $F(120) = 1$, so $\tilde q = 120$, consistent with the direct cost comparison.
Newsvendor: order quantity $q$ chosen before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. Three equiprobable scenarios $D \in \{80, 100, 120\}$, $c_u = 9$, $c_o = 4$: the optimum is $q = 120$, the largest scenario, although the mean is 100. What is the managerial reading?
Being short costs over twice being long
The demand data are wrong
Leftovers have no cost here
The mean is always too cautious a choice
Explanation. With $c_u = 9$ against $c_o = 4$ every missing unit hurts more than twice an unsold one, so one covers the high scenario; uncertainty is managed, not ignored.
Newsvendor: order quantity $q$ chosen before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. Bakery: $c_u = 9$, $c_o = 4$, demand normal with mean $100$ and standard deviation $20$; $\tilde q = 110.05$. The expected cost is $91.43$ € at $\tilde q$ and $103.72$ € at $q = 100$. What does the comparison show?
That the normal model is inadequate here
That ordering the mean costs about $12$ € more per cycle
That the two quantities are equivalent
That the optimum should be below the mean
Explanation. Ordering the 69th percentile instead of the mean saves $103.72 - 91.43 \approx 12.3$ € per cycle: the gain of using the quantile rule.
Newsvendor: order quantity $q$ chosen before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. Bakery case: the optimal $q$ is estimated from $k$ sampled demand scenarios, 30 replications for each $k$. What happens with few scenarios?
The estimate is biased toward the mean
The estimate is exact but slow to compute
The LP becomes infeasible
The decision is unstable
Explanation. Scenarios are themselves a sample, and the decision inherits their variance: below about 100 scenarios the optimal $q$ moves by $\pm 3$ units between replications.
Scenario LP of the newsvendor: demands $d_s$ with probabilities $\pi_s$ ($s = 1, \dots, k$); variables $q \ge 0$, overage $o_s \ge q - d_s$ and underage $u_s \ge d_s - q$, with $o_s, u_s \ge 0$; minimize $\sum_s\pi_s(c_oo_s + c_uu_s)$. With $k = 600$ equiprobable scenarios the LP gives $q = 108.61$ and the empirical $69.23\%$ quantile of the scenarios is $108.60$. Why do they coincide?
A theorem: the LP gives an empirical quantile
By chance: with other data they would differ
Because the scenarios were drawn from a normal distribution
Because the LP rounds $q$ to the nearest scenario
Explanation. The scenario LP minimizes the expected cost under the empirical distribution, and the quantile rule applies to it: the optimum is an empirical quantile at the critical ratio (here $9/13$).
Scenario LP of the newsvendor: demands $d_s$ with probabilities $\pi_s$ ($s = 1, \dots, k$); variables $q \ge 0$, overage $o_s \ge q - d_s$ and underage $u_s \ge d_s - q$, with $o_s, u_s \ge 0$; minimize $\sum_s\pi_s(c_oo_s + c_uu_s)$. How many variables and constraints (besides nonnegativity) does the LP have with $k$ scenarios?
$k$ variables and $k$ constraints
$2k$ variables and $k + 1$ constraints
$2k + 1$ variables and $2k$ constraints
$k + 1$ variables and $2k$ constraints
Explanation. Variables: $q$ plus $o_s$ and $u_s$ for each scenario; constraints: one overage and one underage definition per scenario. The only true decision is $q$.
Newsvendor: order quantity $q$ chosen before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. Bakery case ($\tilde q = 110$): a cycle service level of $95\%$ ($\mathbb P(D \le q) = 0.95$) requires $q = 132.9$ and costs $+45.59$ € per cycle. What does a $95\%$ **fill rate** (share of demand served on average) cost?
Almost nothing: at $\tilde q$ the fill rate is already $96\%$
The same $45.59$ €: the two measures coincide
More, because the fill rate is stricter
It cannot be computed with this model
Explanation. At $\tilde q$ the probability of no stock-out is only $69\%$ but the fill rate is already $96\%$: promising a 95% fill rate is almost free, promising 95% probability of full coverage is expensive. Read the service-level agreement carefully.
Newsvendor: order quantity $q$ chosen before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. Bakery case: cycle service levels $90\%$, $95\%$, $99\%$ require $q = 125.6$, $132.9$, $146.5$ and cost $+23.4$, $+45.6$, $+95.6$ € per cycle over the economic optimum. How does the cost grow?
Linearly in the service level
It decreases after $95\%$
Faster and faster near 100%
It does not depend on the service level
Explanation. Each extra point of service needs a higher quantile of demand, in the thin right tail: the extra cost almost doubles from 90% to 95% and again to 99%.
Newsvendor: order quantity $q$ chosen before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. At the optimal order $\tilde q$ of the quantile rule, what is the probability of **not** running out of stock, $\mathbb P(D \le \tilde q)$?
$1/2$, since $\tilde q$ is the median
$c_o/(c_u + c_o)$
$1$: the optimum never runs out
$c_u/(c_u + c_o)$
Explanation. By definition $F(\tilde q) = c_u/(c_u + c_o)$: the cycle service level of the economic optimum is the critical ratio ($69\%$ in the bakery). Demanding more costs extra.
Newsvendor: order quantity $q$ chosen before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. A risk-averse bakery minimizes $(1-\lambda)\mathbb E[\text{cost}] + \lambda\,\mathrm{CVaR}_{0.90}(\text{cost})$. With $\lambda = 0$: mean cost $88.33$, CVaR $245.93$; with $\lambda = 0.25$: $90.37$ and $229.29$; with $\lambda = 1$: $94.87$ and $224.56$. What do the numbers show?
Protection grows linearly with $\lambda$
Most of it comes already at $\lambda = 0.25$
The CVaR does not depend on $\lambda$
With $\lambda = 1$ the mean cost decreases
Explanation. From $\lambda = 0$ to $0.25$ the CVaR drops by $16.6$ € for $2$ € of mean cost; going on to $\lambda = 1$ gains less than $5$ € more: the frontier is steep at first and flat afterwards.
Newsvendor: order quantity $q$ chosen before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. Why does the newsvendor chapter add a CVaR term to the expected cost?
Because the expected cost is not convex
Because the scenario LP has no solution otherwise
To estimate the demand distribution
The mean hides rare disasters
Explanation. The expected cost weighs all scenarios equally; the CVaR looks at the mean of the worst $10\%$, so the decision maker can trade a little mean cost for protection against bad tails.
Newsvendor: order quantity $q$ chosen before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. In the mean–CVaR newsvendor of the lab, the risk-averse order goes from $108.6$ ($\lambda = 0$) to $116.2$ ($\lambda = 1$). Why does risk aversion raise the order here?
Because leftovers become cheaper
Because the mean demand grows with $\lambda$
The worst scenarios are stock-outs
Because the CVaR ignores the underage cost
Explanation. With $c_u = 9 > c_o = 4$ the most expensive scenarios are those with high demand and lost sales; protecting against them means ordering more.
Newsvendor: order quantity $q$ chosen before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. Three cakes with demands correlated at $\rho = 0.7$ (holidays go well or badly for all of them). What does the strong positive correlation imply for the risk of the joint plan?
No diversification: they fail together
It removes the risk, by compensation
It makes the budget constraint inactive
Nothing: correlation does not matter for the newsvendor
Explanation. With high correlation the bad scenarios hit all products at once; treating them as independent would underestimate the risk of the plan.
Newsvendor: order quantity $q$ chosen before observing the random demand $D$ (distribution function $F$); unit underage cost $c_u$ (demand left unmet) and overage cost $c_o$ (unit left unsold); minimize $c_o\mathbb E[(q - D)^+] + c_u\mathbb E[(D - q)^+]$. Three cakes, shared budget of $1200$ €: panettone $111.1 \to 99.3$, pandoro $91.5 \to 75.4$, torrone $65.9 \to 56.8$ (without $\to$ with budget). How are the quantities cut?
All by the same percentage
All by the same number of units
Not proportionally, product by product
Only the most expensive product is cut
Explanation. Cuts are $11\%$, $18\%$ and $14\%$: the budget multiplier acts as an extra cost per euro spent, which weighs differently on each product according to its costs.
Six equally likely losses $\{2, 4, 5, 7, 12, 20\}$, $\alpha = 0.80$. $\mathrm{VaR}_\alpha$ is the smallest loss $\eta$ with $\mathbb P(L \le \eta) \ge \alpha$, and $\mathrm{CVaR}_\alpha = \mathrm{VaR}_\alpha + \frac{1}{1-\alpha}\mathbb E[(L - \mathrm{VaR}_\alpha)^+]$. What are VaR and CVaR?
VaR $= 12$, CVaR $= 16$
VaR $= 20$, CVaR $= 20$
VaR $= 12$, CVaR $= 18.67$
VaR $= 7$, CVaR $= 12$
Explanation. $F$ reaches $0.80$ at the fifth loss: VaR $= 12$. CVaR $= 12 + \frac{1}{0.2}\cdot\frac16(20 - 12) = 18.67$: part of the tail mass sits on the point 12. The plain mean of $\{12, 20\}$, $16$, is the typical mistake.
Rockafellar–Uryasev LP for a loss with scenarios $s$ of probability $\pi_s$ and loss $\ell_s(\mathbf x)$: $\min\ \eta + \frac{1}{1-\alpha}\sum_s\pi_s\xi_s$ subject to $\xi_s \ge \ell_s(\mathbf x) - \eta$, $\xi_s \ge 0$, $\mathbf x \in X$. How must the threshold variable $\eta$ be declared in gurobipy?
With the default bounds of `addVar`
As a binary variable
With `ub=0`
Free: `m.addVar(lb=-GRB.INFINITY)`
Explanation. $\eta \gtreqless 0$ in the model; the default `lb=0` would impose $\eta \ge 0$, a frequent mistake in the lab.
Rockafellar–Uryasev LP for a loss with scenarios $s$ of probability $\pi_s$ and loss $\ell_s(\mathbf x)$: $\min\ \eta + \frac{1}{1-\alpha}\sum_s\pi_s\xi_s$ subject to $\xi_s \ge \ell_s(\mathbf x) - \eta$, $\xi_s \ge 0$, $\mathbf x \in X$. With $\alpha = 0.99$ and only $k = 220$ equally likely scenarios, why is the estimated CVaR unreliable?
Because the LP becomes non-convex for $\alpha$ close to $1$
Because the tail contains only 2–3 scenarios
Because the VaR is then always unique
Because the CVaR is not defined for $\alpha > 0.95$
Explanation. The tail of mass $0.01$ holds $2.2$ scenarios: the estimate is almost noise. Rule of thumb: at least a few dozen scenarios beyond the quantile.
Two-stage supply chain with CVaR: capacities $x_a$ are booked with suppliers $a$ before the demand scenario $s$ is known; then purchases $f_{as}$ and shortages $u_s$ are decided in each scenario. Which variables are first-stage?
The purchases $f_{as}$ in each scenario
The shortages $u_s$ in each scenario
The booked capacities $x_a$, the same in all scenarios
The CVaR excesses $\xi_s$
Explanation. First-stage decisions are taken before observing the scenario and cannot depend on it; purchases and shortages are recourse decisions.
Two-stage supply chain: in scenario $s$ the demand $d_s$ is covered by purchases $f_{1s} + f_{2s}$ and a shortage variable $u_s \ge 0$, with $f_{1s} + f_{2s} + u_s \ge d_s$; each unit of $u_s$ costs a penalty $g$. Why is the model never infeasible?
Uncovered demand becomes shortage, paid with the penalty $g$
Because the booked capacities are unlimited
Because the demand is deterministic
Because the risk weight is zero
Explanation. The model “buys” infeasibility at the price of the penalty: the demand constraint can always be satisfied with $u_s$ large enough.
Rockafellar–Uryasev LP for a loss with scenarios $s$ of probability $\pi_s$ and loss $\ell_s(\mathbf x)$: $\min\ \eta + \frac{1}{1-\alpha}\sum_s\pi_s\xi_s$ subject to $\xi_s \ge \ell_s(\mathbf x) - \eta$, $\xi_s \ge 0$, $\mathbf x \in X$. Which statement is correct?
At the optimum $\eta$ is the expected loss and the value is the VaR
At the optimum $\eta$ is a VaR and the optimal value is the CVaR
Binary variables are needed to select the tail scenarios
The optimal value is the maximum loss over the scenarios
Explanation. Minimizing over $\eta$ balances threshold and excesses: the balance point is the $\alpha$-quantile. With discrete distributions the VaR may not be unique ($\tilde\eta$ is a VaR).
VaR$_\alpha$ is the $\alpha$-quantile of a loss, CVaR$_\alpha$ the average loss in the worst tail of mass $1 - \alpha$. Which comparison is correct?
VaR is convex in the decisions and CVaR is not
Both always reward diversification
VaR has a scenario-based LP formulation, CVaR does not
CVaR is convex and subadditive; VaR in general is neither
Explanation. CVaR is the coherent measure of the pair: convex, subadditive (it rewards diversification) and optimizable with an LP; VaR may violate subadditivity.
Rockafellar–Uryasev LP for a loss with scenarios $s$ of probability $\pi_s$ and loss $\ell_s(\mathbf x)$: $\min\ \eta + \frac{1}{1-\alpha}\sum_s\pi_s\xi_s$ subject to $\xi_s \ge \ell_s(\mathbf x) - \eta$, $\xi_s \ge 0$, $\mathbf x \in X$. Under which assumptions is the whole model an LP?
Equally likely scenarios and $\alpha = 0.9$
Normally distributed scenario losses
$X$ is a polyhedron and each loss $\ell_s(\mathbf x)$ is linear in $\mathbf x$
At most 2000 scenarios
Explanation. With polyhedral $X$ and linear losses all constraints and the objective are linear; the threshold $\eta$ is free and the excesses non-negative. 2000 is only the Colab licence limit.
Rockafellar–Uryasev LP for a loss with scenarios $s$ of probability $\pi_s$ and loss $\ell_s(\mathbf x)$: $\min\ \eta + \frac{1}{1-\alpha}\sum_s\pi_s\xi_s$ subject to $\xi_s \ge \ell_s(\mathbf x) - \eta$, $\xi_s \ge 0$, $\mathbf x \in X$. Why does $\xi_s = (\ell_s - \eta)^+$ hold at the optimum, for every scenario with $\pi_s > 0$?
$\xi_s$ has cost $\pi_s/(1-\alpha) > 0$ and lower bounds $\ell_s - \eta$ and $0$
Because the threshold $\eta$ is a free variable
Because $\alpha < 1$ makes the problem bounded
Because the losses $\ell_s$ are positive
Explanation. Same positive-part trick as in the newsvendor: the objective pushes each $\xi_s$ down to the larger of its two lower bounds.
Mean-CVaR portfolio: the loss of scenario $s$ is $\ell_s(\mathbf x) = -\sum_i r_{is}x_i$, where $r_{is}$ is the return of asset $i$ in scenario $s$ and $x_i$ its share. Why can the whole model be solved as an LP?
$r_{is}$ are data, so each loss is linear in $\mathbf x$, and the shares form a polyhedron
The returns are normally distributed, so the CVaR has a closed linear form
The scenarios are equally likely, so the CVaR is a plain average of losses
The losses are always positive, so the positive parts can be dropped
Explanation. Linear losses and polyhedral constraints ($\sum_ix_i = 1$, return threshold, $x \ge 0$) keep the Rockafellar–Uryasev formulation linear, whatever the distribution of the returns (here fat tails).
Rockafellar–Uryasev LP for a loss with scenarios $s$ of probability $\pi_s$ and loss $\ell_s(\mathbf x)$: $\min\ \eta + \frac{1}{1-\alpha}\sum_s\pi_s\xi_s$ subject to $\xi_s \ge \ell_s(\mathbf x) - \eta$, $\xi_s \ge 0$, $\mathbf x \in X$. How can a stress test be built into this scenario model?
By raising $\alpha$ until the LP becomes infeasible
By declaring $\eta$ non-negative
By removing the scenarios with the largest losses
By adding extreme scenarios or raising their probabilities $\pi_s$
Explanation. The probabilities $\pi_s$ are data: reweighting scenarios or adding extreme ones shows how the optimal decision and the CVaR react to harsher tails.
Many lab models optimize a mean value. Why do VaR and CVaR look at the **tail** of the loss distribution instead?
Because the mean cannot be computed with scenarios
The mean can hide rare large losses
Because the tail is always normal
Because the tail makes the model integer
Explanation. A mean can look reassuring while a few scenarios carry very large losses; VaR gives a high threshold of loss, CVaR the average loss beyond it.
VaR and CVaR of a loss at level $\alpha$: which question does each answer?
VaR: the mean loss; CVaR: the largest loss
VaR: the probability of a loss; CVaR: its variance
Both: the loss in the single worst scenario
VaR: a threshold; CVaR: the mean beyond it
Explanation. VaR is the $\alpha$-quantile of the loss (a threshold exceeded with probability at most $1 - \alpha$); CVaR is the average loss in the worst tail of mass $1 - \alpha$, so it also says how bad things get.
Who uses VaR and CVaR as a standard language, according to the lab notes?
Only academic statisticians
Only weather forecasters
Banks, insurers, supply chain managers
Only portfolio managers with normal returns
Explanation. After the financial crises «how much do we lose in the worst scenarios?» became a regulatory question too; the same measures are used for logistics plans, as in the two-stage supply chain of the chapter.
Six equiprobable losses $\{2, 4, 5, 7, 12, 20\}$, $\alpha = 0.80$: mean $8.33$, $\mathrm{VaR}_{0.80} = 12$, $\mathrm{CVaR}_{0.80} = 18.67$. Why is the CVaR not simply $20$, the mean of the scenarios strictly above the VaR?
Because the CVaR must equal the VaR plus the mean
Because of a rounding error
Because part of the tail mass sits on $12$
Because the losses are not equiprobable
Explanation. The scenario at 20 weighs $1/6 \approx 0.167$, less than $0.20$: the remaining $0.033$ of the tail sits on the quantile 12. Hence $\mathrm{CVaR} = 12 + \frac{1}{0.20}\cdot\frac16(20 - 12) = 18.67$.
Rockafellar–Uryasev LP for a loss with scenarios $s$ of probability $\pi_s$ and loss $\ell_s(\mathbf x)$, level $\alpha \in (0, 1)$: $\min\ \eta + \frac{1}{1-\alpha}\sum_s\pi_s\xi_s$ subject to $\xi_s \ge \ell_s(\mathbf x) - \eta$, $\xi_s \ge 0$, $\mathbf x \in X$, $\eta$ free. Six equiprobable losses $\{2, 4, 5, 7, 12, 20\}$ (no decision $\mathbf x$), $\alpha = 0.80$: the LP returns $\eta^* = 12$. What are the excesses $\xi_s$ and the optimal value?
$\xi = (0, 0, 0, 0, 0, 20)$, value $28.67$
$\xi = (0, 0, 0, 0, 0, 8)$, value $18.67$
$\xi = (0, 0, 0, 0, 0, 8)$, value $13.33$
$\xi = (10, 8, 7, 5, 0, 8)$, value $50.5$
Explanation. $\xi_s = (\ell_s - 12)^+$: only the loss 20 exceeds the threshold, by 8. Value $12 + \frac{1}{0.2}\cdot\frac16\cdot 8 = 18.67$: one LP gives VaR and CVaR, with the mass «straddling» the quantile treated correctly.
Two-stage supply chain with CVaR: supplier 1 is cheap but fragile (in $12\%$ of the scenarios its availability drops to $30\%$), supplier 2 expensive but reliable. As the risk weight $\lambda$ goes from 0 to 1, what happens to the booked capacities?
They do not change: only the recourse changes
Capacity moves toward supplier 1
Both shrink to cut the booking cost
Capacity moves toward the reliable supplier 2
Explanation. From $\lambda = 0$ to $1$ supplier 1 goes from $161.5$ to $68.5$ and supplier 2 from $134.2$ to $236.9$: protection against the failure scenarios is bought with reliable capacity.
Two-stage supply chain with CVaR of the lab: from $\lambda = 0$ to $\lambda = 1$ the mean cost goes from $1724$ to $1906$ € and the $\mathrm{CVaR}_{0.90}$ from $2902$ to $2139$ €; already with $\lambda = 0.5$: $1803$ and $2217$. How do the notes call the extra mean cost paid for the protection?
The value of the stochastic solution
The cost of resilience
The price of anarchy
The shadow price of the capacity
Explanation. About $+79$ € of mean cost buy $-685$ € of CVaR (at $\lambda = 0.5$): the cost of resilience, the number needed in a discussion about dual sourcing or reshoring.
Rockafellar–Uryasev LP for a loss with scenarios $s$ of probability $\pi_s$ and loss $\ell_s(\mathbf x)$, level $\alpha \in (0, 1)$: $\min\ \eta + \frac{1}{1-\alpha}\sum_s\pi_s\xi_s$ subject to $\xi_s \ge \ell_s(\mathbf x) - \eta$, $\xi_s \ge 0$, $\mathbf x \in X$, $\eta$ free. With discrete scenarios the LP returns some optimal $\eta^*$. What can be said of it?
It is always the mean loss
It is always unique and equal to the largest loss
It is a VaR, not necessarily unique
It has no meaning, only the objective does
Explanation. At the optimum $\eta^*$ is an $\alpha$-quantile of the loss; with discrete distributions the set of minimizers in $\eta$ can be an interval, so $\eta^*$ is *a* VaR. The optimal value, the CVaR, is unique.
Rockafellar–Uryasev LP for a loss with scenarios $s$ of probability $\pi_s$ and loss $\ell_s(\mathbf x)$, level $\alpha \in (0, 1)$: $\min\ \eta + \frac{1}{1-\alpha}\sum_s\pi_s\xi_s$ subject to $\xi_s \ge \ell_s(\mathbf x) - \eta$, $\xi_s \ge 0$, $\mathbf x \in X$, $\eta$ free. Sensitivity analysis of the lab: what is the expected effect of raising the confidence level $\alpha$?
Fewer scenarios in the tail: noisier estimate
A smaller CVaR
No effect at all on the stability of the estimate
The LP becomes infeasible for large $\alpha$
Explanation. A higher $\alpha$ looks at a thinner tail: with a fixed number of scenarios fewer of them lie beyond the quantile and the estimate is noisier; the CVaR itself can only grow.
Mean-CVaR portfolio of the course (eight sector stocks, 220 monthly scenarios): which minimum expected return and which level $\alpha$ does the case study use?
$8\%$ per year and $\alpha = 0.90$
$5\%$ per year and $\alpha = 0.95$
$8\%$ per year and $\alpha = 0.99$
$10\%$ per year and $\alpha = 0.90$
Explanation. One minimizes the $\mathrm{CVaR}_{0.90}$ of the monthly loss with an expected return of at least $8\%$ per year.
Mean-CVaR portfolio of the course, $\alpha = 0.90$, expected return at least $8\%$: the mean monthly loss is $-0.67\%$ and the VaR$_{90}$ is $3.27\%$. What is the CVaR$_{90}$?
$3.27\%$
$-0.67\%$
$4.89\%$
$2.60\%$
Explanation. The CVaR$_{90}$ is the mean loss in the worst 10\% of the months, hence not below the VaR: $4.89\%$.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. The LP turns out to be unbounded. What does it mean?
No arbitrage exists in this market
A type A arbitrage exists: cash today with no risk, scalable at will
The price data are inconsistent and the LP is infeasible
Only a type B arbitrage exists
Explanation. A strategy of negative cost and non-negative payoffs exists; the constraints are homogeneous, so it can be scaled. Adding $\sum_i s^0_ix_i \ge -1$ gives optimum $-1$ and a concrete strategy.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. What is a type B arbitrage?
A strategy that collects cash today and never pays tomorrow
A strategy with negative cost and negative payoffs
A strategy costing nothing today, never losing, gaining in some state
A portfolio made only of risk-free securities
Explanation. In the LP: optimum $0$, with some state constraint slack in every optimal solution.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. The dual has a variable $p_j \ge 0$ per state and constraints $\sum_j s^1_{ij}p_j = s^0_i$; from security 0, $\sum_j R\,p_j = 1$. What are the numbers $q_j = R\,p_j$?
Risk-neutral probabilities: prices are discounted expected payoffs under $q$
The real-world probabilities of the states
The optimal positions of the portfolio
The payoffs of the risk-free security
Explanation. They are non-negative and sum to $1$, and $s^0_i = \frac1R\sum_j q_j\,s^1_{ij}$ for every security.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. In an incomplete market (more states than securities, here only securities 0 and 1 quoted), how is a new security priced without creating arbitrage?
With a unique price, as in a complete market
At its expected payoff under the real-world probabilities
It cannot be priced at all
With an interval: min and max discounted payoff over consistent measures
Explanation. In the case study the call with strike 12 has interval $[1.4615, 2.0308]$; any price outside it allows an arbitrage.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. With three states and consistent prices, the dual returns the risk-neutral measure $q = (0.296;\ 0.704;\ 0)$. What does $q_3 = 0$ signal?
An error in the price data
Degeneracy: state 3 is not priced, a type B arbitrage on it remains
That state 3 cannot occur
A type A arbitrage
Explanation. The fundamental theorem requires $q_j > 0$ for every state to exclude type B arbitrage as well.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. Why is the optimal value of this LP always $\le 0$?
The null portfolio is feasible and costs $0$
Because all the prices $s^0_i$ are positive
Because the risk-free return $R$ is at least $1$
Because the positions $x_i$ are free
Explanation. A minimum cannot exceed the value of a feasible solution; a negative value is an immediate cash inflow.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. A risk-neutral measure is a vector $q \ge 0$ with $\sum_j q_j = 1$ and $s^0_i = \frac1R\sum_j q_js^1_{ij}$ for all $i$. Which statement is the fundamental theorem of asset pricing?
No arbitrage if and only if a risk-neutral measure with $q_j \ge 0$ exists
No arbitrage if and only if the risk-neutral measure is unique
No arbitrage of type A or B if and only if one exists with $q_j > 0$ for all $j$
No arbitrage if and only if prices are expected payoffs under real probabilities
Explanation. Strict positivity is needed to exclude type B arbitrage; uniqueness characterizes complete markets, not the absence of arbitrage.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. Conversely, assume a risk-neutral measure $q > 0$ exists, with $s^0_i = \frac1R\sum_j q_js^1_{ij}$. Which computation shows that there is no arbitrage?
The primal LP is unbounded, so its value is $-\infty$ and no strategy is profitable
Payoffs $\ge 0$ give cost $\frac1R\sum_j q_j\bigl(\sum_i s^1_{ij}x_i\bigr) \ge 0$, $> 0$ if one payoff is positive
The risk-free security costs $1$ and pays $R$, so every portfolio has cost equal to its payoff
The dual objective is zero, and by weak duality every portfolio has cost exactly $0$
Explanation. Substituting the pricing relation in the cost: with $q > 0$ no strategy can collect cash (type A) or gain for free (type B).
Three states, risk-free security 0 (costs 1, pays $R = 1.04$), risky securities 1 and 2 priced $6$ and $20$, paying $(10, 15, 13)$ and $(30, 15, 25)$. Consider the portfolio $x = (-27, 1, 1)$ (borrow 27, buy one of each). What are its cost today and its payoffs?
Cost $+1$, payoffs $(11.92;\ 1.92;\ 9.92)$: not an arbitrage
Cost $-1$, payoffs $(13;\ 3;\ 11)$: type B arbitrage
Cost $0$, payoffs $(11.92;\ 1.92;\ 9.92)$: type B arbitrage
Cost $-1$, payoffs $(11.92;\ 1.92;\ 9.92)$: type A arbitrage
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. Normalized version: add $\sum_i s^0_ix_i \ge -1$. In the case study, the prices of security 2 that create no arbitrage form the interval $[18.69, 21.54]$. What is the optimal value of the normalized LP if security 2 is quoted at $25$?
$-1$: outside the interval an arbitrage exists
$0$: no arbitrage at any price
$-25$: the gain equals the price
The LP becomes infeasible
Explanation. Inside the interval the value is $0$ (consistent prices); outside it drops to $-1$, the normalized amount collected by an arbitrage strategy.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. Why are the positions $x_i$ free variables in this LP?
Because prices can be negative
Because the number of states is finite
Because the dual requires equality constraints
Because each security can be bought ($x_i > 0$) or sold short ($x_i < 0$)
Explanation. Free positions model buying and short selling; by the duality rules each free variable gives an equality in the dual, the pricing relation $\sum_j s^1_{ij}p_j = s^0_i$.
What is an **arbitrage**, in the lab chapter on arbitrage and pricing?
A risky strategy with a high expected return
A strategy that copies the market index
Money from nothing, with no risk of loss
A loan at the risk-free rate
Explanation. It either cashes in today with no risk of losing tomorrow, or costs nothing today and can only gain tomorrow; in a well-functioning market such opportunities cannot last.
Why is «no arbitrage» the working hypothesis of all price finance?
Anyone would exploit it until prices adjust
Because arbitrage is illegal
Because markets have no risk-free security
Because prices are fixed by regulators
Explanation. An arbitrage can be scaled at will, so it would be exploited until prices become consistent: trading desks look for inconsistencies, risk managers validate listed prices, new securities are priced consistently.
According to the lab notes, what is the didactic «surprise» of the arbitrage chapter?
Arbitrage requires stochastic simulation
Prices can only be found by trial and error
Arbitrage needs integer variables
Arbitrage detection is an LP
Explanation. Shadow prices, complementary slackness and strong duality of the background chapter turn into risk-neutral probabilities and the fundamental theorem of pricing: the cleanest primal–dual pair of the notes.
Which professionals use the «no arbitrage» check, according to the lab notes?
Only central banks and regulators
Traders, risk managers, pricers
Only auditors at the end of the year
Only retail investors
Explanation. Desks look for inconsistencies among quoted instruments, risk managers validate listed prices, and a new security (e.g. an option) must be priced consistently with the existing ones.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R = 1 + r$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. With an arbitrage of type A the LP is unbounded. How do the notes obtain a finite certificate, a concrete strategy?
By bounding each position, $|x_i| \le 1$
By adding the normalization $\sum_i s^0_ix_i \ge -1$
By making the positions nonnegative
By removing the risk-free security
Explanation. The constraints are homogeneous, so the strategy can be scaled at will; requiring that today's income be at most 1 makes the optimum $-1$ and the solution a concrete strategy.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R = 1 + r$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. The dual has a variable $p_j \ge 0$ per state, constraints $\sum_j s^1_{ij}p_j = s^0_i$ and objective $\max\sum_j 0\cdot p_j$. What follows from the zero objective?
The dual is always unbounded
The dual has a unique solution
The primal is always infeasible
Every feasible solution is optimal
Explanation. All right-hand sides of the primal are zero, so the dual objective is identically zero: any $p \ge 0$ that prices the securities is an optimal dual solution, and its existence is what matters.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R = 1 + r$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. Three-state market of the lab ($R = 1.04$): payoffs of security 1 $(10, 15, 13)$, of security 2 $(30, 15, 25)$. Prices today $s^0_1 = 6$, $s^0_2 = 20$; the strategy $x = (-27, 1, 1)$ costs $-1$ today and pays $(11.92;\ 1.92;\ 9.92)$. What happens to the LP without normalization?
It has optimum $-1$, the income
It is infeasible
It is unbounded
It has optimum $0$: no arbitrage
Explanation. The constraints are homogeneous: multiplying the strategy by any $t > 0$ cashes in $t$ today with nonnegative payoffs, so the cost has no lower bound (arbitrage of type A).
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R = 1 + r$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. Three-state market of the lab ($R = 1.04$): payoffs of security 1 $(10, 15, 13)$, of security 2 $(30, 15, 25)$. Prices today $s^0_1 = 6$, $s^0_2 = 20$. To check by hand that $x = (-27, 1, 1)$ is an arbitrage, what is computed?
Cost today and payoff in each state
Its expected return under the real probabilities
Its variance across the three states
Only its cost today
Explanation. Type A arbitrage: negative cost today and nonnegative payoff in every state, here $-27\cdot 1.04 + 10 + 30 = 11.92$, $1.92$ and $9.92$; no probabilities are involved.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R = 1 + r$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. Three-state market of the lab ($R = 1.04$): payoffs of security 1 $(10, 15, 13)$, of security 2 $(30, 15, 25)$. The case study analyses two price configurations: $(s^0_1, s^0_2) = (6, 20)$ and $(13, 18.6923)$. What is found?
Both price configurations are consistent
Both configurations contain an arbitrage
$(6, 20)$ is consistent, $(13, 18.6923)$ has an arbitrage
$(6, 20)$: type A; $(13, 18.6923)$: consistent
Explanation. With $(6, 20)$ the LP is unbounded (with normalization optimum $-1$); with $(13, 18.6923)$ the optimum is 0 and the duals give a pricing measure that reproduces all prices.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R = 1 + r$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. In the gurobipy code of the case study the positions are created with `m.addVars(n1, lb=-GRB.INFINITY)`. What would go wrong with the default bounds?
Nothing: the default bounds are already free
Short selling would be forbidden
The model would become nonlinear
The duals would no longer be available
Explanation. The default lower bound is 0: the positions could not be negative, so strategies that sell short (such as borrowing at the risk-free rate) would be excluded and many arbitrages not detected.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R = 1 + r$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. The case-study script adds the normalization $\sum_i s^0_ix_i \ge -1$ only when requested (`normalizza`). What is reported for prices $(6, 20)$ without it?
Status `UNBOUNDED`
Status `INFEASIBLE`: no strategy
Optimum $0$: no arbitrage
Optimum $-1$, as when normalized
Explanation. Without normalization the LP with an arbitrage of type A has no finite optimum: the status is `UNBOUNDED`; with it, optimum $-1$ and payoffs $(0;\ 0;\ 0.20) \ge 0$.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R = 1 + r$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. In the case-study code the state constraints are kept in `v_stato = m.addConstrs(...)`. Why?
To delete them after the solve
Because `addConstrs` requires it
To read their duals `Pi`
To print them in the solver log
Explanation. The duals of the state constraints are the pricing measure $p_j$; multiplied by $R$ they give the risk-neutral probabilities.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R = 1 + r$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. Three-state market of the lab ($R = 1.04$): payoffs of security 1 $(10, 15, 13)$, of security 2 $(30, 15, 25)$. Consistent prices $(1;\ 13;\ 18.6923)$: the duals of the state constraints are $p^* = (0.2846;\ 0.6769;\ 0)$. What is the risk-neutral measure $q$?
$q = p^* = (0.2846;\ 0.6769;\ 0)$
$q = (1/3;\ 1/3;\ 1/3)$
$q = p^*/R = (0.274;\ 0.651;\ 0)$
$q = R\,p^* = (0.296;\ 0.704;\ 0)$
Explanation. The dual constraint of the risk-free security gives $\sum_jp_j = 1/R$, so $q_j = R\,p_j$ are probabilities: $1.04\cdot 0.2846 = 0.296$ and $1.04\cdot 0.6769 = 0.704$.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R = 1 + r$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. Three-state market of the lab ($R = 1.04$): payoffs of security 1 $(10, 15, 13)$, of security 2 $(30, 15, 25)$. With $q = (0.296;\ 0.704;\ 0)$, how is the price of security 2 today checked?
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R = 1 + r$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. Three-state market of the lab ($R = 1.04$): payoffs of security 1 $(10, 15, 13)$, of security 2 $(30, 15, 25)$. Consistent prices $(1;\ 13;\ 18.6923)$, optimum of the arbitrage LP $= 0$. What does it mean?
The prices are consistent: no arbitrage
Payoffs strictly positive in every state: arbitrage
The LP is infeasible
A negative payoff in state 3
Explanation. With optimum 0 no strategy has negative cost and nonnegative payoffs: the prices are consistent, and the duals of the active state constraints price the securities.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R = 1 + r$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. Three-state market of the lab ($R = 1.04$): payoffs of security 1 $(10, 15, 13)$, of security 2 $(30, 15, 25)$. Only securities 0 and 1 are quoted (prices 1 and 13). How do the notes compute the interval of prices of security 2 that create no arbitrage?
By solving the arbitrage LP with random prices
By averaging the payoffs of security 2
Min and max of its value over consistent $p$
With one LP that maximizes the price
Explanation. Over the pricing measures $p \ge 0$ that reproduce the quoted prices, minimizing and maximizing the value of security 2 gives $[18.69;\ 21.54]$.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R = 1 + r$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. A call on security 1 with strike 12 pays $(0, 3, 1)$ in the three states. With securities 0, 1, 2 quoted its price is unique, $2.0308$; with only 0 and 1 it is an interval, $[1.4615;\ 2.0308]$. Which hypothesis makes the price unique?
A positive risk-free rate
A complete market
A payoff of the call that is never zero
Real probabilities known in advance
Explanation. With three independent securities in three states the dual system $\sum_js^1_{ij}p_j = s^0_i$ has a unique solution and every new security has one price; with fewer securities (incomplete market) the consistent measures are infinite and the price is an interval.
One-period market: security $i$ costs $s^0_i$ today and pays $s^1_{ij}$ tomorrow in state $j$; security 0 is risk-free (costs 1, pays $R = 1 + r$). Arbitrage LP: $\min\sum_i s^0_ix_i$ subject to $\sum_i s^1_{ij}x_i \ge 0$ for every state $j$, positions $x_i$ free. Three-state market of the lab ($R = 1.04$): payoffs of security 1 $(10, 15, 13)$, of security 2 $(30, 15, 25)$. Prices today $s^0_1 = 6$, $s^0_2 = 20$. One buys one unit of each risky security (spending 26) and borrows $B$ at the risk-free rate ($x_0 = -B$). What is the largest $B$ for which the payoffs stay $\ge 0$ in every state?
$B = 30$
$B = 38.46$
$B = 27$
$B = 28.85$
Explanation. Payoff in state $j$: $s^1_{1j} + s^1_{2j} - 1.04B \ge 0$, i.e. $B \le \min(40, 30, 38)/1.04 = 30/1.04 = 28.85$; the worst state binds. Today one cashes in up to $28.85 - 26 = 2.85$ with no risk.
Quantile regression LP: observations $y_i$ with features $x_{ij}$, coefficients $w_j$ and intercept $b$ free, deviations above $u_i \ge 0$ and below $v_i \ge 0$ with $\sum_j w_jx_{ij} + b + u_i - v_i = y_i$; minimize $\sum_i[\tau u_i + (1 - \tau)v_i]$, $0 < \tau < 1$. Let $\tilde\pi_i$ be the optimal dual of the equality constraint of observation $i$. In which interval does it lie?
$[0, 1]$
$[-1, 1]$
$[-(1 - \tau),\ \tau]$
$[-\tau,\ 1 - \tau]$
Explanation. From the dual constraints of $u_i$ and $v_i$: $\tilde\pi_i = \tau$ above the estimate, $-(1 - \tau)$ below, an interior value on the interpolated points.
Quantile regression LP: observations $y_i$ with features $x_{ij}$, coefficients $w_j$ and intercept $b$ free, deviations above $u_i \ge 0$ and below $v_i \ge 0$ with $\sum_j w_jx_{ij} + b + u_i - v_i = y_i$; minimize $\sum_i[\tau u_i + (1 - \tau)v_i]$, $0 < \tau < 1$. With $p$ features, what are the support points of the optimal estimate?
The observations with the largest deviations
The outliers, such as the strike days
All the observations below the estimate
The interpolated observations (usually $p + 1$), with interior duals
Explanation. Moving any other observation, as long as it stays on its side of the estimate, changes nothing.
Quantile regression LP: observations $y_i$ with features $x_{ij}$, coefficients $w_j$ and intercept $b$ free, deviations above $u_i \ge 0$ and below $v_i \ge 0$ with $\sum_j w_jx_{ij} + b + u_i - v_i = y_i$; minimize $\sum_i[\tau u_i + (1 - \tau)v_i]$, $0 < \tau < 1$. Feature selection adds a budget $\sum_j z_j \le t$ with $z_j \ge |w_j|$. Why must the features be standardized first?
To make the LP feasible for every budget $t$
Otherwise the budget adds coefficients in different units
To make all the coefficients $w_j$ positive
Because Gurobi requires standardized data
Explanation. Without standardization the selection would depend on the units of measurement; after it each coefficient reads as pieces per standard deviation of the feature.
Quantile regression LP: observations $y_i$ with features $x_{ij}$, coefficients $w_j$ and intercept $b$ free, deviations above $u_i \ge 0$ and below $v_i \ge 0$ with $\sum_j w_jx_{ij} + b + u_i - v_i = y_i$; minimize $\sum_i[\tau u_i + (1 - \tau)v_i]$, $0 < \tau < 1$. With the budget $\sum_j |w_j| \le t$ on standardized coefficients, the shadow price of the budget goes from $-19.95$ to $-4.20$ pieces per unit as $t$ grows. How is it read?
As the price of complexity: first units buy signal, the last ones noise
As the coefficient of temperature in the fitted model
As the number of selected features
As the error made on the strike days
Explanation. The first units of budget buy temperature, which explains almost everything; the budget to choose is the one beyond which the shadow price becomes negligible.
A bakery orders the critical-fractile quantile of demand (newsvendor rule). For a hot weekend day the quantile of the whole history says $148$ pieces, the quantile regression conditioned on the day says $132$. What is the gain?
None: the two numbers are equivalent
A lower selling price for the bakery
About 16 fewer unsold pieces, with the same costs and rule
A higher critical fractile
Explanation. The quantile rule still holds, applied to the demand conditional on the day, using information already in hand; the gap between median and critical fractile is the safety stock.
Quantile regression LP: observations $y_i$ with features $x_{ij}$, coefficients $w_j$ and intercept $b$ free, deviations above $u_i \ge 0$ and below $v_i \ge 0$ with $\sum_j w_jx_{ij} + b + u_i - v_i = y_i$; minimize $\sum_i[\tau u_i + (1 - \tau)v_i]$, $0 < \tau < 1$. The dual constraint of the free intercept $b$ is $\sum_i\tilde\pi_i = 0$. What does it express?
That the deviations sum to zero
The quantile property: about a fraction $\tau$ of the data below the estimate
That the estimate passes through the mean of the data
That all the duals are zero
Explanation. With $\tilde\pi_i = \tau$ above, $-(1 - \tau)$ below and interior values on the $p + 1$ support points: $\tau n_+ - (1 - \tau)n_- + \sum_{\text{interp.}}\tilde\pi_i = 0$; with $\tau = 1/2$ half above and half below.
Quantile regression LP: observations $y_i$ with features $x_{ij}$, coefficients $w_j$ and intercept $b$ free, deviations above $u_i \ge 0$ and below $v_i \ge 0$ with $\sum_j w_jx_{ij} + b + u_i - v_i = y_i$; minimize $\sum_i[\tau u_i + (1 - \tau)v_i]$, $0 < \tau < 1$. Why is at least one of $\tilde u_i$, $\tilde v_i$ zero at the optimum?
Because $u_i$ and $v_i$ are binary variables
Because the intercept $b$ is free
Because the features are standardized
$\tau, 1 - \tau > 0$: lowering both by the same amount keeps the constraint, lowers the cost
Explanation. Same positive-part reasoning as in the newsvendor: the split of the deviation into $u_i - v_i$ is tight at the optimum.
Quantile regression for a bakery: for a hot weekend day the median model ($\tau = 0.5$) predicts $126.3$ pieces and the model at the critical fractile $\tau = 9/13$ predicts $132.1$. What is the safety stock, and how is it obtained?
$5.8$ pieces: the quantile prediction minus the median one
$132.1$ pieces: the whole quantile prediction
$16$ pieces: the gap with the unconditional quantile
$0$: no distribution was assumed
Explanation. The safety stock is computed directly as the gap between the two conditional estimates, with no assumption on the distribution of demand.
Quantile regression LP: observations $y_i$ with features $x_{ij}$, coefficients $w_j$ and intercept $b$ free, deviations above $u_i \ge 0$ and below $v_i \ge 0$ with $\sum_j w_jx_{ij} + b + u_i - v_i = y_i$; minimize $\sum_i[\tau u_i + (1 - \tau)v_i]$, $0 < \tau < 1$. With no features ($p = 0$) only the intercept $b$ is left. What does the LP return as $\tilde b$?
The mean of the observations
An empirical $\tau$-quantile of the observations
The median, whatever $\tau$
The largest observation
Explanation. Raising $b$ pays while the share of observations below it is at most $\tau$: the model *is* the quantile rule; with features it gives a conditional quantile.
The lab chapter on robust and quantile regression starts from the parameters used by the other models (demand curves, costs, scenarios). What is its point?
Those parameters are given and need no discussion
Estimating them is itself an optimization problem
They are always estimated by least squares
They can be estimated only with a machine-learning library
Explanation. Someone must estimate the numbers that feed the models, and the estimate is an optimization problem: with absolute deviations it stays an LP, solved with Gurobi as everything else.
In the lab, a demand forecast is estimated by minimizing the sum of absolute deviations instead of squared ones. Which two advantages do the notes give?
A closed-form solution and a unique optimum
Smaller errors on every observation and faster solves
No need for data and no need for a solver
It stays an LP and anomalous days weigh less
Explanation. Absolute deviations keep the problem linear (two nonnegative parts per deviation) and pay each deviation once, so a few anomalous days cannot pull the line; weighting the two parts asymmetrically aims at a quantile.
Quantile regression LP: observations $y_i$ ($i = 1, \dots, n$) with features $x_{ij}$ ($j = 1, \dots, p$), free coefficients $w_j$ and intercept $b$, deviations above $u_i \ge 0$ and below $v_i \ge 0$ with $\sum_j w_jx_{ij} + b + u_i - v_i = y_i$; minimize $\sum_i[\tau u_i + (1 - \tau)v_i]$, $0 < \tau < 1$. How many variables and equality constraints does the LP have?
$p$ variables and $n + 1$ constraints
$n + p$ variables and $2n$ constraints
$2n + p + 1$ variables and $n$ constraints
$2n$ variables and $p + 1$ constraints
Explanation. Free variables: the $p$ coefficients and the intercept; nonnegative: $u_i$ and $v_i$ for each observation; one equality constraint per observation defines its deviation.
Quantile regression LP: observations $y_i$ ($i = 1, \dots, n$) with features $x_{ij}$ ($j = 1, \dots, p$), free coefficients $w_j$ and intercept $b$, deviations above $u_i \ge 0$ and below $v_i \ge 0$ with $\sum_j w_jx_{ij} + b + u_i - v_i = y_i$; minimize $\sum_i[\tau u_i + (1 - \tau)v_i]$, $0 < \tau < 1$. No features ($p = 0$): seven days of sales $88, 96, 104, 112, 120, 132, 148$ and $\tau = 9/13$ (bakery with $c_u = 9$, $c_o = 4$). What are the optimal intercept $\tilde b$ and the optimal value?
$\tilde b = 120$, value $680/13 \approx 52.31$
$\tilde b = 112$, value $768/13 \approx 59.08$
$\tilde b = 132$, value $704/13 \approx 54.15$
$\tilde b = 114.29$ (the mean), value $\approx 57.14$
Explanation. Raising $b$ saves $\tau$ on each observation above and costs $1 - \tau$ on each one below: it pays while the share below is at most $\tau$. $\tilde b = 120$ (4 below, 2 above, $4/7 \le \tau \le 5/7$); value $\tfrac4{13}(32 + 24 + 16 + 8) + \tfrac9{13}(12 + 28) = 680/13$.
Bakery history, least-absolute-deviations model with three features on all 60 days: normal days have deviations of at most $23.2$ loaves, the five strike days at least $67.5$. How do the notes use this?
As a diagnostic for anomalous days
As a reason to switch to least squares
To drop the temperature from the model
To set $\tau$ equal to the share of anomalous days
Explanation. The deviation itself is a diagnostic tool: a threshold at 40 loaves flags exactly the five strike days, without knowing anything about the strikes.
Quantile regression LP: observations $y_i$ ($i = 1, \dots, n$) with features $x_{ij}$ ($j = 1, \dots, p$), free coefficients $w_j$ and intercept $b$, deviations above $u_i \ge 0$ and below $v_i \ge 0$ with $\sum_j w_jx_{ij} + b + u_i - v_i = y_i$; minimize $\sum_i[\tau u_i + (1 - \tau)v_i]$, $0 < \tau < 1$. No features ($p = 0$), seven observations $88, 96, 104, 112, 120, 132, 148$, $\tau = 9/13$: the optimum is $\tilde b = 120$, with 4 observations below and 2 above. The duals are $\tau$ for the observations above, $-(1 - \tau)$ for those below, and they sum to zero. What is the dual $\tilde\pi$ of the interpolated observation $120$?
$9/13$
$-4/13$
$-2/13$
$2/13$
Explanation. From $\sum_i\tilde\pi_i = 0$: $2\cdot\tfrac9{13} - 4\cdot\tfrac4{13} + \tilde\pi = 0$, so $\tilde\pi = -2/13$, strictly inside $[-4/13, 9/13]$ as for every interpolated point.
Quantile regression LP: observations $y_i$ ($i = 1, \dots, n$) with features $x_{ij}$ ($j = 1, \dots, p$), free coefficients $w_j$ and intercept $b$, deviations above $u_i \ge 0$ and below $v_i \ge 0$ with $\sum_j w_jx_{ij} + b + u_i - v_i = y_i$; minimize $\sum_i[\tau u_i + (1 - \tau)v_i]$, $0 < \tau < 1$. Let $\tilde\pi_i$ be the optimal dual of the constraint of observation $i$. Optimality on the free coefficient $w_j$ gives $\sum_i\tilde\pi_ix_{ij} = 0$. What does it express?
Feature $j$ must be standardized
Deviation signs are unrelated to feature $j$
Coefficient $w_j$ is zero at the optimum
Exactly half of the observations are above the estimate
Explanation. A free variable gives an equality dual constraint. Since $\tilde\pi_i$ is $\tau$ or $-(1 - \tau)$ according to the side of the deviation, the condition says that the deviations' signs, weighted by $x_{ij}$, balance out: the analogue, feature by feature, of the quantile property given by the intercept.
Quantile regression LP: observations $y_i$ ($i = 1, \dots, n$) with features $x_{ij}$ ($j = 1, \dots, p$), free coefficients $w_j$ and intercept $b$, deviations above $u_i \ge 0$ and below $v_i \ge 0$ with $\sum_j w_jx_{ij} + b + u_i - v_i = y_i$; minimize $\sum_i[\tau u_i + (1 - \tau)v_i]$, $0 < \tau < 1$. Bakery, 55 normal days, three features: the table of the estimates for $\tau = 0.10, 0.50, 9/13, 0.90$ ends with the column «share below the estimate»: $0.073$, $0.455$, $0.673$, $0.873$. What does that column check?
The quantile property of the estimates
The share of days with positive temperature
The out-of-sample error of each model
The share of features with nonzero coefficient
Explanation. Up to the $p + 1$ support points, the estimate leaves a share $\tau$ of the observations below it: the values are close to the four $\tau$'s, slightly smaller because the interpolated points are not counted.
Quantile regression LP: observations $y_i$ ($i = 1, \dots, n$) with features $x_{ij}$ ($j = 1, \dots, p$), free coefficients $w_j$ and intercept $b$, deviations above $u_i \ge 0$ and below $v_i \ge 0$ with $\sum_j w_jx_{ij} + b + u_i - v_i = y_i$; minimize $\sum_i[\tau u_i + (1 - \tau)v_i]$, $0 < \tau < 1$. A bakery sells at $p = 15$ €, buys at $c = 6$ € and recovers $v = 2$ € per unsold item, so $c_u = 9$ and $c_o = 4$. Which $\tau$ gives, through quantile regression, the quantity to produce each day?
$\tau = 1/2$, the median
$\tau = 4/13 = c_o/(c_u + c_o)$
$\tau = 9/13 = c_u/(c_u + c_o)$
$\tau = 9/4 = c_u/c_o$
Explanation. The newsvendor orders the quantile $c_u/(c_u + c_o) = 9/13 \approx 0.69$ of demand; quantile regression with that $\tau$ gives it conditionally on the day. $4/13$ swaps the two costs.
Quantile regression LP: observations $y_i$ ($i = 1, \dots, n$) with features $x_{ij}$ ($j = 1, \dots, p$), free coefficients $w_j$ and intercept $b$, deviations above $u_i \ge 0$ and below $v_i \ge 0$ with $\sum_j w_jx_{ij} + b + u_i - v_i = y_i$; minimize $\sum_i[\tau u_i + (1 - \tau)v_i]$, $0 < \tau < 1$. Bakery estimates: the weekend coefficient is $+37.05$ loaves for $\tau = 0.10$ and $+27.98$ for $\tau = 0.90$. How is this read?
A numerical error: coefficients must not depend on $\tau$
Effects can differ across quantiles of demand
The weekend matters only for $\tau = 0.10$
The model should use only $\tau = 1/2$
Explanation. Each $\tau$ estimates a different conditional quantile, and a feature may shift the low part of the distribution more than the high part: quantile regression describes the whole conditional distribution, not just its center.
Quantile regression LP: observations $y_i$ ($i = 1, \dots, n$) with features $x_{ij}$ ($j = 1, \dots, p$), free coefficients $w_j$ and intercept $b$, deviations above $u_i \ge 0$ and below $v_i \ge 0$ with $\sum_j w_jx_{ij} + b + u_i - v_i = y_i$; minimize $\sum_i[\tau u_i + (1 - \tau)v_i]$, $0 < \tau < 1$. Feature selection adds variables $z_j \ge 0$, constraints $-z_j \le w_j \le z_j$ and the budget $\sum_jz_j \le t$. Why does $\tilde z_j = |\tilde w_j|$ hold at the optimum?
Because $z_j$ appears in the objective with a positive cost
Because the constraints force $z_j = w_j$
Because the features are standardized
Because extra $z_j$ only wastes budget
Explanation. The two constraints say $z_j \ge |w_j|$; any $z_j$ above $|w_j|$ wastes budget that could relax another coefficient, so at the optimum it can be taken equal to $|w_j|$ and the model stays an LP.
Quantile regression LP: observations $y_i$ ($i = 1, \dots, n$) with features $x_{ij}$ ($j = 1, \dots, p$), free coefficients $w_j$ and intercept $b$, deviations above $u_i \ge 0$ and below $v_i \ge 0$ with $\sum_j w_jx_{ij} + b + u_i - v_i = y_i$; minimize $\sum_i[\tau u_i + (1 - \tau)v_i]$, $0 < \tau < 1$. Bakery, budget $\sum_j|w_j| \le t$ on standardized coefficients, three true features and four irrelevant ones. As $t$ grows, temperature enters at $t = 3$, price at $t = 24$, weekend at $t = 30$. What does the order of entry tell?
The order of importance of the features
The order in which the data were collected
Which features are measured in the largest units
Nothing: it is arbitrary for an LP
Explanation. With a scarce budget the LP spends it where it reduces the error most: the true features enter in order of importance, while the irrelevant ones stay near zero until the budget becomes clearly excessive.
Quantile regression LP: observations $y_i$ ($i = 1, \dots, n$) with features $x_{ij}$ ($j = 1, \dots, p$), free coefficients $w_j$ and intercept $b$, deviations above $u_i \ge 0$ and below $v_i \ge 0$ with $\sum_j w_jx_{ij} + b + u_i - v_i = y_i$; minimize $\sum_i[\tau u_i + (1 - \tau)v_i]$, $0 < \tau < 1$. With a budget $t$ on the standardized coefficients, how do the notes choose $t$?
The $t$ that minimizes the error on the historical data
The largest $t$ the solver accepts
The $t$ beyond which its shadow price is negligible
Always $t$ equal to the number of features
Explanation. The historical error always decreases with $t$ (more freedom chases noise); the shadow price, the price of complexity, says when an extra unit of budget stops buying signal.
Quantile regression LP: observations $y_i$ ($i = 1, \dots, n$) with features $x_{ij}$ ($j = 1, \dots, p$), free coefficients $w_j$ and intercept $b$, deviations above $u_i \ge 0$ and below $v_i \ge 0$ with $\sum_j w_jx_{ij} + b + u_i - v_i = y_i$; minimize $\sum_i[\tau u_i + (1 - \tau)v_i]$, $0 < \tau < 1$. With the budget constraint $\sum_jz_j \le t$ ($z_j \ge |w_j|$), the optimal mean absolute deviation as a function of $t$ is decreasing and convex. Which result explains the convexity?
The features are standardized
Convexity of an LP's value in a right-hand side
The quantile property of the intercept
Strong duality makes every value function linear
Explanation. For a minimization LP, $\tilde z(t)$ is the maximum of the dual objective over a fixed dual feasible set, linear in $t$: a maximum of linear functions is convex. The slope is the shadow price, which rises from $-19.95$ to $-4.20$.
Bakery with 60 days of history, 5 of them strike days. The least absolute deviations line (LP, $\tau = 1/2$) with temperature alone is estimated on the 60 days and then on the 55 normal days only. By how much do the two intercepts differ?
$11.24$ pieces
$7.43$ pieces
$0.72$ pieces
$3.81$ pieces
Explanation. On the 60 days $b = 209.77$, on the 55 normal days $b = 210.49$: a mere $0.72$ pieces. The LP pays every deviation once and the strikes barely move the line.
Bakery: the least absolute deviations line (LP, $\tau = 1/2$) estimated with temperature alone on 60 days, 5 of them strike days, is $209.77 - 3.63\,t$. What is its mean absolute deviation on the 55 normal days?
$13.08$ pieces
$23.2$ pieces
$67.5$ pieces
$3.63$ pieces
Explanation. The script gives $13.08$ pieces: the line stays where the normal data are. $23.2$ and $67.5$ are the extreme deviations of the three-feature model; $3.63$ is the slope.
Why, in the course LP Modelling, is the demand of the bakery estimated by minimising the sum of the *absolute* deviations?
So that the variables of the model are integer
The model stays an LP and withstands anomalous days
So that the estimate always equals the mean
So that fewer days of history are needed
Explanation. Absolute deviations are linearized with two non-negative variables: the model is an LP, and every deviation weighs in proportion to its size, so a few anomalous days do not drag the estimate.
Bakery, least absolute deviations line ($\tau = 1/2$) with temperature alone ($p = 1$) on the 60 days. How many observations does the line interpolate (the support points)?
$1$
$29$
$60$
$2$
Explanation. The support points are $p + 1 = 2$, as many as the free variables ($w$ and $b$): 29 observations lie above the line, 29 below, 2 on the line.
Bakery, least absolute deviations LP ($\tau = 1/2$) with temperature alone on the 60 days: 29 observations above the line, 29 below, 2 on the line. How many duals $\tilde\pi_i$ equal $+0.5$?
$2$
$29$
$58$
$30$
Explanation. An observation above the estimate has $\tilde u_i > 0$ and hence $\tilde\pi_i = \tau = 0.5$: these are the 29 above the line. The 29 below have $-0.5$, the 2 support points an intermediate value.
Quantile regression of the bakery on the 55 normal days, typical day (28 degrees, price $3.00$, weekend): the predicted median is $126.3$ pieces and the predicted $9/13$ quantile is $132.1$. Which safety stock is produced?
$126.3$ pieces
$148.0$ pieces
$5.8$ pieces
$16.0$ pieces
Explanation. The safety stock is the difference between the critical-fractile quantile and the median: $132.1 - 126.3 = 5.8$ pieces. $148$ is the quantile with no features.
Bakery, feature selection with a budget on the standardized coefficients: in which order do the features enter as the budget grows?
Temperature, price, weekend
Weekend, price, temperature
Price, temperature, rain
Temperature, followers, price
Explanation. They enter in order of importance: temperature (budget 3), price (24), weekend (30). The irrelevant features stay below 2 pieces until the budget is excessive.
In the regression of the course LP Modelling, what is the point of aiming at a *quantile* of demand instead of its centre?
Giving the number the newsvendor needs
Reducing the number of observations
Removing the intercept from the model
Making the variables integer
Explanation. By weighting deviations above and below asymmetrically the estimate aims at the critical-fractile quantile: the quantity the newsvendor should produce.
Feature selection with a budget on the coefficients: what does the auxiliary variable $z_j$, with $-z_j \le w_j \le z_j$, represent?
The sign of the coefficient $w_j$
The deviation of observation $j$
The absolute value of the coefficient $w_j$
The dual of the budget constraint
Explanation. The two constraints force $z_j \ge |w_j|$ and, with the budget $\sum_j z_j \le t$, at the optimum $z_j = |w_j|$: a constraint on the sum of absolute values written in linear form.
Why, in feature selection, are the features standardized before imposing the budget on the coefficients?
To make the variables of the model integer
To remove the intercept from the estimate
To reduce the number of days of history
The budget adds coefficients in different units
Explanation. A budget on the sum of the $|w_j|$ makes sense only if the coefficients are comparable: after standardizing, each one measures pieces per standard deviation.
Bakery, least absolute deviations model with three features on the 60 days: demand $= 276.46 - 3.97\,t - 23.12\,p + 28.51\,w$ ($w = 1$ at weekends). By how much does the predicted demand grow at weekends?
$28.51$ pieces
$23.12$ pieces
$3.97$ pieces
$276.46$ pieces
Explanation. The coefficient of $w$ is $28.51$: for the same temperature and price, at weekends the estimate rises by $28.51$ pieces.
What does the chapter on robust and quantile regression estimate for the newsvendor?
The mean of the daily demand
The variance of the daily demand
The conditional quantile of the demand
The optimal selling price of bread
Explanation. By weighting deviations asymmetrically, the regression estimates the quantile of demand conditional on the conditions of the day.
Generated questions (38)
Each generator builds a new instance, with different numbers, at every start: a few examples here.
2. Background: linear programming and sensitivity analysis (6)
Example 1 · lpm-g-lp-duali-cs · level facile · notes
Consider the LP $\max\; 43x_1 + 73x_2$ subject to $x_1 + 4x_2 \le 47$, $3x_1 + 3x_2 \le 96$, $x_1, x_2 \ge 0$; its dual has one variable $\pi_i \ge 0$ per constraint $i$ (the shadow price of the constraint). The optimal solution is $(\tilde x_1, \tilde x_2) = (27, 5)$, with both constraints active. What are the optimal dual values $(\tilde\pi_1, \tilde\pi_2)$?
$(\tilde\pi_1; \tilde\pi_2) = (18.11; 6.22)$
$(\tilde\pi_1; \tilde\pi_2) = (11; 10)$
$(\tilde\pi_1; \tilde\pi_2) = (10; 11)$
$(\tilde\pi_1; \tilde\pi_2) = (10.75; 10.43)$
Explanation. Both variables are positive, so by complementary slackness both dual constraints are active: $1\pi_1 + 3\pi_2 = 43$ and $4\pi_1 + 3\pi_2 = 73$ (the coefficients are the columns of the primal), hence $\tilde\pi = (10; 11)$. Solving with the rows instead of the columns is the typical mistake.
Example 2 · lpm-g-lp-duali-cs · level facile · notes
Consider the LP $\max\; 32x_1 + 49x_2$ subject to $2x_1 + x_2 \le 72$, $2x_1 + 4x_2 \le 138$, $x_1, x_2 \ge 0$; its dual has one variable $\pi_i \ge 0$ per constraint $i$ (the shadow price of the constraint). The optimal solution is $(\tilde x_1, \tilde x_2) = (25, 22)$, with both constraints active. What are the optimal dual values $(\tilde\pi_1, \tilde\pi_2)$?
$(\tilde\pi_1; \tilde\pi_2) = (5; 11)$
$(\tilde\pi_1; \tilde\pi_2) = (13.17; 5.67)$
$(\tilde\pi_1; \tilde\pi_2) = (11; 5)$
$(\tilde\pi_1; \tilde\pi_2) = (8; 9.8)$
Explanation. Both variables are positive, so by complementary slackness both dual constraints are active: $2\pi_1 + 2\pi_2 = 32$ and $1\pi_1 + 4\pi_2 = 49$ (the coefficients are the columns of the primal), hence $\tilde\pi = (5; 11)$. Solving with the rows instead of the columns is the typical mistake.
Example 1 · lpm-g-lp-costo-ridotto · level facile · notes
Consider the LP $\max\; 43x_1 + 73x_2$ subject to $x_1 + 4x_2 \le 47$, $3x_1 + 3x_2 \le 96$, $x_1, x_2 \ge 0$; its dual has one variable $\pi_i \ge 0$ per constraint $i$ (the shadow price of the constraint). At the optimum the duals are $(\tilde\pi_1, \tilde\pi_2) = (10, 11)$. We add a variable $x_3 \ge 0$ with objective coefficient $c_3 = 49$ and consumptions $a_{13} = 4$, $a_{23} = 1$. What are its reduced cost $\bar c_3$ ($c_3$ minus the value of the resources it consumes at the shadow prices) and the threshold $c_3^{\max}$, the smallest $c_3$ at which $x_3$ becomes worth using?
$\bar c_3 = 2$, threshold $c_3^{\max} = 51$
$\bar c_3 = -5$, threshold $c_3^{\max} = 54$
$\bar c_3 = 9$, threshold $c_3^{\max} = 40$
$\bar c_3 = -2$, threshold $c_3^{\max} = 51$
Explanation. The resources absorbed by one unit of $x_3$ are worth $4\cdot 10 + 1\cdot 11 = 51$ at the shadow prices, so $\bar c_3 = 49 - 51 = -2$: $x_3$ stays at zero and becomes worth activating only if $c_3$ rises to at least $51$.
Example 2 · lpm-g-lp-costo-ridotto · level facile · notes
Consider the LP $\max\; 32x_1 + 49x_2$ subject to $2x_1 + x_2 \le 72$, $2x_1 + 4x_2 \le 138$, $x_1, x_2 \ge 0$; its dual has one variable $\pi_i \ge 0$ per constraint $i$ (the shadow price of the constraint). At the optimum the duals are $(\tilde\pi_1, \tilde\pi_2) = (5, 11)$. We add a variable $x_3 \ge 0$ with objective coefficient $c_3 = 60$ and consumptions $a_{13} = 4$, $a_{23} = 4$. What are its reduced cost $\bar c_3$ ($c_3$ minus the value of the resources it consumes at the shadow prices) and the threshold $c_3^{\max}$, the smallest $c_3$ at which $x_3$ becomes worth using?
$\bar c_3 = 4$, threshold $c_3^{\max} = 64$
$\bar c_3 = -4$, threshold $c_3^{\max} = 64$
$\bar c_3 = 40$, threshold $c_3^{\max} = 20$
$\bar c_3 = -4$, threshold $c_3^{\max} = 60$
Explanation. The resources absorbed by one unit of $x_3$ are worth $4\cdot 5 + 4\cdot 11 = 64$ at the shadow prices, so $\bar c_3 = 60 - 64 = -4$: $x_3$ stays at zero and becomes worth activating only if $c_3$ rises to at least $64$.
Example 1 · lpm-g-lp-intervallo-b · level media · notes
Consider the LP $\max\; 43x_1 + 73x_2$ subject to $x_1 + 4x_2 \le 47$, $3x_1 + 3x_2 \le 96$, $x_1, x_2 \ge 0$; its dual has one variable $\pi_i \ge 0$ per constraint $i$ (the shadow price of the constraint). At the optimum both constraints are active and $\tilde x = (27, 5)$, with $\tilde x_1, \tilde x_2 > 0$. Keeping $b_2 = 96$ fixed, for which values of $b_1$ does this basis stay optimal (the validity range of the shadow price $\tilde\pi_1$)?
$b_1 \in [24; 96]$
$b_1 \in [35.25; 141]$
$b_1 \in [32; 128]$
$b_1 \in [32; 47]$
Explanation. With both constraints active, $x(b_1)$ solves $A x = (b_1, 96)$: $x_1 = (3b_1 - 384)/(-9)$ and $x_2 = (96 - 3b_1)/(-9)$. The basis stays optimal (the duals do not change) as long as both are $\ge 0$, that is for $b_1 \in [32, 128]$; Gurobi returns it as `SARHSLow`–`SARHSUp`.
Example 2 · lpm-g-lp-intervallo-b · level media · notes
Consider the LP $\max\; 32x_1 + 49x_2$ subject to $2x_1 + x_2 \le 72$, $2x_1 + 4x_2 \le 138$, $x_1, x_2 \ge 0$; its dual has one variable $\pi_i \ge 0$ per constraint $i$ (the shadow price of the constraint). At the optimum both constraints are active and $\tilde x = (25, 22)$, with $\tilde x_1, \tilde x_2 > 0$. Keeping $b_2 = 138$ fixed, for which values of $b_1$ does this basis stay optimal (the validity range of the shadow price $\tilde\pi_1$)?
$b_1 \in [34.5; 138]$
$b_1 \in [69; 276]$
$b_1 \in [72; 288]$
$b_1 \in [34.5; 72]$
Explanation. With both constraints active, $x(b_1)$ solves $A x = (b_1, 138)$: $x_1 = (4b_1 - 138)/6$ and $x_2 = (276 - 2b_1)/6$. The basis stays optimal (the duals do not change) as long as both are $\ge 0$, that is for $b_1 \in [34.5, 138]$; Gurobi returns it as `SARHSLow`–`SARHSUp`.
Example 1 · lpm-g-lp-dualita-debole · level facile · notes
Consider the LP $\max\; 43x_1 + 73x_2$ subject to $x_1 + 4x_2 \le 47$, $3x_1 + 3x_2 \le 96$, $x_1, x_2 \ge 0$; its dual has one variable $\pi_i \ge 0$ per constraint $i$ (the shadow price of the constraint). The point $\bar x = (23, 4)$ is feasible for the primal and $\bar\pi = (11, 11)$ is feasible for the dual $\min\ 47\pi_1 + 96\pi_2$ (dual constraints $\pi_1 + 3\pi_2 \ge 43$, $4\pi_1 + 3\pi_2 \ge 73$). By weak duality, which interval certainly contains the optimal value $\tilde z$ of the primal?
$\tilde z \in [989; 1281]$
$\tilde z \in [1573; 1865]$
$\tilde z \in [1281; 1427]$
$\tilde z \in [1281; 1573]$
Explanation. Every feasible primal point gives a lower bound for a maximum, $43\cdot 23 + 73\cdot 4 = 1281$, and every feasible dual point an upper bound, $47\cdot 11 + 96\cdot 11 = 1573$. So $1281 \le \tilde z \le 1573$ (here $\tilde z = 1526$). Swapping the roles of the two bounds is the typical mistake.
Example 2 · lpm-g-lp-dualita-debole · level facile · notes
Consider the LP $\max\; 32x_1 + 49x_2$ subject to $2x_1 + x_2 \le 72$, $2x_1 + 4x_2 \le 138$, $x_1, x_2 \ge 0$; its dual has one variable $\pi_i \ge 0$ per constraint $i$ (the shadow price of the constraint). The point $\bar x = (21, 18)$ is feasible for the primal and $\bar\pi = (7, 14)$ is feasible for the dual $\min\ 72\pi_1 + 138\pi_2$ (dual constraints $2\pi_1 + 2\pi_2 \ge 32$, $\pi_1 + 4\pi_2 \ge 49$). By weak duality, which interval certainly contains the optimal value $\tilde z$ of the primal?
$\tilde z \in [672; 1554]$
$\tilde z \in [2436; 3318]$
$\tilde z \in [1554; 2436]$
$\tilde z \in [1554; 1995]$
Explanation. Every feasible primal point gives a lower bound for a maximum, $32\cdot 21 + 49\cdot 18 = 1554$, and every feasible dual point an upper bound, $72\cdot 7 + 138\cdot 14 = 2436$. So $1554 \le \tilde z \le 2436$ (here $\tilde z = 1878$). Swapping the roles of the two bounds is the typical mistake.
Example 1 · lpm-g-lp-perturbazione · level facile · notes
Consider the LP $\max\; 43x_1 + 73x_2$ subject to $x_1 + 4x_2 \le 47$, $3x_1 + 3x_2 \le 96$, $x_1, x_2 \ge 0$; its dual has one variable $\pi_i \ge 0$ per constraint $i$ (the shadow price of the constraint). At the optimum $\tilde z = 1526$, the shadow price of constraint 1 is $\tilde\pi_1 = 10$ (and $\tilde\pi_2 = 11$), and the validity range of $b_1$ (where $\tilde\pi_1$ stays exact) is $[32; 128]$. What is the new optimal value if $b_1$ changes from $47$ to $57$, all else equal?
$\tilde z = 1426$
$\tilde z = 1536$
$\tilde z = 1636$
$\tilde z = 1626$
Explanation. The new value $57$ is inside the validity range, so the shadow price is exact: $\tilde z + \tilde\pi_1\,\Delta b_1 = 1526 + 10\cdot(10) = 1626$.
Example 2 · lpm-g-lp-perturbazione · level facile · notes
Consider the LP $\max\; 32x_1 + 49x_2$ subject to $2x_1 + x_2 \le 72$, $2x_1 + 4x_2 \le 138$, $x_1, x_2 \ge 0$; its dual has one variable $\pi_i \ge 0$ per constraint $i$ (the shadow price of the constraint). At the optimum $\tilde z = 1878$, the shadow price of constraint 1 is $\tilde\pi_1 = 5$ (and $\tilde\pi_2 = 11$), and the validity range of $b_1$ (where $\tilde\pi_1$ stays exact) is $[34.5; 138]$. What is the new optimal value if $b_1$ changes from $72$ to $83$, all else equal?
$\tilde z = 1933$
$\tilde z = 1883$
$\tilde z = 1823$
$\tilde z = 1999$
Explanation. The new value $83$ is inside the validity range, so the shadow price is exact: $\tilde z + \tilde\pi_1\,\Delta b_1 = 1878 + 5\cdot(11) = 1933$.
Example 1 · lpm-g-lp-tutti-casi · level complessa · notes
Consider the LP $\min\ -4x_1 + 12x_2 - 12x_3$, subject to (1) $x_1 + x_2 \ge 39$, (2) $x_1 + x_2 - x_3 = 64$, (3) $3x_1 - x_2 \le 92$, $x_1 \ge 0$, $x_2$ free, $x_3 \le 0$. Its optimal solution is $\tilde x = (39, 25, 0)$. Let $\tilde\pi_i = \partial\tilde z/\partial b_i$ be the dual value of constraint $i$ (in a minimum: $\pi_i \ge 0$ for $\ge$, free for $=$, $\le 0$ for $\le$). Using complementary slackness, what are the optimal dual values?
Explanation. Constraint (1) is slack ($64 > 39$), so $\tilde\pi_1 = 0$. $x_1 > 0$ and $x_2 \ne 0$ make their dual constraints active (columns of the primal): $\pi_2 + 3\pi_3 = -4$ and $\pi_2 - \pi_3 = 12$, so $\tilde\pi_2 = 8$, $\tilde\pi_3 = -4 \le 0$ as required. The dual constraint of $x_3$ need not be active: $x_3$ sits at its bound $0$ with reduced cost $-12 + 8 = -4$. Check: $\sum_i b_i\tilde\pi_i = 144 = \tilde z$.
Example 2 · lpm-g-lp-tutti-casi · level complessa · notes
Consider the LP $\min\ 4x_1 + 16x_2 - 12x_3$, subject to (1) $x_1 + x_2 \ge 51$, (2) $x_1 + x_2 - x_3 = 64$, (3) $x_1 - 2x_2 \le -41$, $x_1 \ge 0$, $x_2$ free, $x_3 \le 0$. Its optimal solution is $\tilde x = (29, 35, 0)$. Let $\tilde\pi_i = \partial\tilde z/\partial b_i$ be the dual value of constraint $i$ (in a minimum: $\pi_i \ge 0$ for $\ge$, free for $=$, $\le 0$ for $\le$). Using complementary slackness, what are the optimal dual values?
Explanation. Constraint (1) is slack ($64 > 51$), so $\tilde\pi_1 = 0$. $x_1 > 0$ and $x_2 \ne 0$ make their dual constraints active (columns of the primal): $\pi_2 + \pi_3 = 4$ and $\pi_2 - 2\pi_3 = 16$, so $\tilde\pi_2 = 8$, $\tilde\pi_3 = -4 \le 0$ as required. The dual constraint of $x_3$ need not be active: $x_3$ sits at its bound $0$ with reduced cost $-12 + 8 = -4$. Check: $\sum_i b_i\tilde\pi_i = 676 = \tilde z$.
3. The solver: building, solving, interpreting (4)
Example 1 · lpm-g-sv-dimensioni · level facile · notes
A gurobipy production-inventory LP has $n = 4$ products and $m = 8$ months: variables $x_{it} \ge 0$ (units produced) and $s_{it} \ge 0$ (inventory at the end of the month) for every product $i$ and month $t$; one balance constraint $s_{i,t-1} + x_{it} = d_{it} + s_{it}$ per product and month (initial inventory $s_{i0}$ is a datum); one machine-hours constraint $\sum_i a_ix_{it} \le b_t$ per month. What does the line `Optimize a model with ... rows, ... columns` of the Gurobi log report?
$64$ rows, $40$ columns
$40$ rows, $64$ columns
$32$ rows, $64$ columns
$40$ rows, $32$ columns
Explanation. Rows are constraints: $nm = 32$ balances plus $m = 8$ capacities, $40$ in all; columns are variables: $2nm = 64$. Checking these sizes is the first reading of the log.
Example 2 · lpm-g-sv-dimensioni · level facile · notes
A gurobipy production-inventory LP has $n = 3$ products and $m = 11$ months: variables $x_{it} \ge 0$ (units produced) and $s_{it} \ge 0$ (inventory at the end of the month) for every product $i$ and month $t$; one balance constraint $s_{i,t-1} + x_{it} = d_{it} + s_{it}$ per product and month (initial inventory $s_{i0}$ is a datum); one machine-hours constraint $\sum_i a_ix_{it} \le b_t$ per month. What does the line `Optimize a model with ... rows, ... columns` of the Gurobi log report?
$44$ rows, $33$ columns
$33$ rows, $66$ columns
$44$ rows, $66$ columns
$66$ rows, $44$ columns
Explanation. Rows are constraints: $nm = 33$ balances plus $m = 11$ capacities, $44$ in all; columns are variables: $2nm = 66$. Checking these sizes is the first reading of the log.
Example 1 · lpm-g-sv-rc-soglia · level facile · notes
gurobipy, minimization LP: $\min\ 16x_1 + 17x_2$ subject to $2x_1 + 2x_2 \ge 110$, $x_1, x_2 \ge 0$. At the optimum $x_2 = 0$. What are its reduced cost (attribute `x2.RC`, $c_2$ minus the value of the resources it uses at the shadow prices) and the cost threshold `SAObjLow` below which $x_2$ becomes worth using?
`RC` $= 1$, threshold $16$
`RC` $= 1$, threshold $18$
`RC` $= -1$, threshold $16$
`RC` $= 9$, threshold $8$
Explanation. Only $x_1$ is used, so the shadow price of the constraint is $c_1/a_1 = 8$; $x_2$ uses $2$ units, worth $16$: `RC` $= 17 - 16 = 1 \ge 0$ (a variable at its lower bound in a minimum). It becomes worth using when its cost falls to $16$.
Example 2 · lpm-g-sv-rc-soglia · level facile · notes
gurobipy, minimization LP: $\min\ 8x_1 + 16x_2$ subject to $2x_1 + 3x_2 \ge 30$, $x_1, x_2 \ge 0$. At the optimum $x_2 = 0$. What are its reduced cost (attribute `x2.RC`, $c_2$ minus the value of the resources it uses at the shadow prices) and the cost threshold `SAObjLow` below which $x_2$ becomes worth using?
`RC` $= 4$, threshold $12$
`RC` $= -4$, threshold $12$
`RC` $= 4$, threshold $20$
`RC` $= 12$, threshold $4$
Explanation. Only $x_1$ is used, so the shadow price of the constraint is $c_1/a_1 = 4$; $x_2$ uses $3$ units, worth $12$: `RC` $= 16 - 12 = 4 \ge 0$ (a variable at its lower bound in a minimum). It becomes worth using when its cost falls to $12$.
Example 1 · lpm-g-sv-pi-capacita · level facile · notes
gurobipy, minimization LP: $\min\ 5x_1 + 11x_2$ subject to demand $x_1 + x_2 \ge 130$ and capacity of the cheap source $x_1 \le 70$, $x \ge 0$. Output: optimal cost $1010$; demand constraint `Pi` $= 11$; capacity constraint `Pi` $= -6$, `SARHS` $= [0, 130]$. What is the optimal cost if the capacity becomes $71$?
$\tilde z = 1004$
$\tilde z = 1015$
$\tilde z = 1016$
$\tilde z = 1021$
Explanation. `Pi` $= \partial\tilde z/\partial b$: a $\le$ capacity in a minimum has `Pi` $\le 0$, each unit saves $6$ (the cheap source replaces the expensive one). The new value is inside `SARHS`, so $1010 + (-6)\cdot(1) = 1004$.
Example 2 · lpm-g-sv-pi-capacita · level facile · notes
gurobipy, minimization LP: $\min\ 4x_1 + 12x_2$ subject to demand $x_1 + x_2 \ge 50$ and capacity of the cheap source $x_1 \le 40$, $x \ge 0$. Output: optimal cost $280$; demand constraint `Pi` $= 12$; capacity constraint `Pi` $= -8$, `SARHS` $= [0, 50]$. What is the optimal cost if the capacity becomes $44$?
$\tilde z = 248$
$\tilde z = 328$
$\tilde z = 312$
$\tilde z = 296$
Explanation. `Pi` $= \partial\tilde z/\partial b$: a $\le$ capacity in a minimum has `Pi` $\le 0$, each unit saves $8$ (the cheap source replaces the expensive one). The new value is inside `SARHS`, so $280 + (-8)\cdot(4) = 248$.
Example 1 · lpm-g-sv-rhs-costante · level facile · notes
In gurobipy the meter constraint of an EV-charging model is written `constr = m.addConstr(quicksum(x[v,t] for v in V) + base[t] <= C)`, with the constant `base[t] = 39` (base load, kW) and `C = 109` (meter limit). What value does Gurobi store in `constr.RHS`, and which value must be assigned to `constr.RHS` to study a meter limit of $134$ kW?
`constr.RHS` $= 148$, to set $173$
`constr.RHS` $= 109$, to set $134$
`constr.RHS` $= 70$, to set $134$
`constr.RHS` $= 70$, to set $95$
Explanation. Gurobi moves the constant to the right-hand side: `RHS` $= 109 - 39 = 70$. Writing `constr.RHS = 134` would impose $\sum_v x_{vt} \le 134$, another constraint; the correct assignment is $134 - 39 = 95$.
Example 2 · lpm-g-sv-rhs-costante · level facile · notes
In gurobipy the meter constraint of an EV-charging model is written `constr = m.addConstr(quicksum(x[v,t] for v in V) + base[t] <= C)`, with the constant `base[t] = 29` (base load, kW) and `C = 119` (meter limit). What value does Gurobi store in `constr.RHS`, and which value must be assigned to `constr.RHS` to study a meter limit of $109$ kW?
`constr.RHS` $= 90$, to set $80$
`constr.RHS` $= 148$, to set $138$
`constr.RHS` $= 90$, to set $109$
`constr.RHS` $= 119$, to set $109$
Explanation. Gurobi moves the constant to the right-hand side: `RHS` $= 119 - 29 = 90$. Writing `constr.RHS = 109` would impose $\sum_v x_{vt} \le 109$, another constraint; the correct assignment is $109 - 29 = 80$.
4. Multi-period production and inventory (3)
Example 1 · lpm-g-prod-2mesi-costo · level facile · notes
Production-inventory LP, one product, two months: $x_t$ = units produced and $s_t$ = inventory at the end of month $t$, balance $s_{t-1} + x_t = d_t + s_t$ ($s_0 = 0$), capacity $x_t \le b_t$; minimize $\sum_t (c\,x_t + h\,s_t)$. Data: demand $d_1 = 55$, $d_2 = 100$; $b_1 = b_2 = 80$ units; $c = 14$ €/unit, holding cost $h = 1$ €/unit/month. What is the optimal cost of the plan?
2190 €
2270 €
2170 €
2210 €
Explanation. Month 2 produces at most $80$, so $\tilde s_1 = d_2 - b_2 = 20$ units are produced in month 1 and held for one month: $14\cdot 155 + 1\cdot 20 = 2190$ €.
Example 2 · lpm-g-prod-2mesi-costo · level facile · notes
Production-inventory LP, one product, two months: $x_t$ = units produced and $s_t$ = inventory at the end of month $t$, balance $s_{t-1} + x_t = d_t + s_t$ ($s_0 = 0$), capacity $x_t \le b_t$; minimize $\sum_t (c\,x_t + h\,s_t)$. Data: demand $d_1 = 25$, $d_2 = 100$; $b_1 = b_2 = 70$ units; $c = 6$ €/unit, holding cost $h = 2$ €/unit/month. What is the optimal cost of the plan?
810 €
750 €
950 €
870 €
Explanation. Month 2 produces at most $70$, so $\tilde s_1 = d_2 - b_2 = 30$ units are produced in month 1 and held for one month: $6\cdot 125 + 2\cdot 30 = 810$ €.
Example 1 · lpm-g-prod-2mesi-duali · level facile · notes
Production-inventory LP, one product, two months: $x_t$ = units produced and $s_t$ = inventory at the end of month $t$, balance $s_{t-1} + x_t = d_t + s_t$ ($s_0 = 0$), capacity $x_t \le b_t$; minimize $\sum_t (c\,x_t + h\,s_t)$. Data: demand $d_1 = 50$, $d_2 = 100$; $b_1 = b_2 = 80$ units; $c = 14$ €/unit, holding cost $h = 1$ €/unit/month. What are the shadow prices $\tilde\pi_t = \partial\tilde z/\partial b_t$ of the two capacity constraints ($\tilde z$ = optimal cost; Gurobi's sign convention)?
$\tilde\pi_1 = 0$, $\tilde\pi_2 = -1$
$\tilde\pi_1 = -1$, $\tilde\pi_2 = 0$
$\tilde\pi_1 = 0$, $\tilde\pi_2 = 1$
$\tilde\pi_1 = 0$, $\tilde\pi_2 = -14$
Explanation. One more unit of capacity in month 2 lets one unit be produced a month later, saving the holding cost: $\tilde\pi_2 = -h = -1$ (a $\le$ constraint in a minimization has $\tilde\pi \le 0$). Month 1 produces $70 < 80$: its constraint is slack and $\tilde\pi_1 = 0$.
Example 2 · lpm-g-prod-2mesi-duali · level facile · notes
Production-inventory LP, one product, two months: $x_t$ = units produced and $s_t$ = inventory at the end of month $t$, balance $s_{t-1} + x_t = d_t + s_t$ ($s_0 = 0$), capacity $x_t \le b_t$; minimize $\sum_t (c\,x_t + h\,s_t)$. Data: demand $d_1 = 25$, $d_2 = 100$; $b_1 = b_2 = 70$ units; $c = 6$ €/unit, holding cost $h = 2$ €/unit/month. What are the shadow prices $\tilde\pi_t = \partial\tilde z/\partial b_t$ of the two capacity constraints ($\tilde z$ = optimal cost; Gurobi's sign convention)?
$\tilde\pi_1 = 0$, $\tilde\pi_2 = -2$
$\tilde\pi_1 = 0$, $\tilde\pi_2 = 2$
$\tilde\pi_1 = -2$, $\tilde\pi_2 = 0$
$\tilde\pi_1 = 0$, $\tilde\pi_2 = -6$
Explanation. One more unit of capacity in month 2 lets one unit be produced a month later, saving the holding cost: $\tilde\pi_2 = -h = -2$ (a $\le$ constraint in a minimization has $\tilde\pi \le 0$). Month 1 produces $55 < 70$: its constraint is slack and $\tilde\pi_1 = 0$.
Example 1 · lpm-g-prod-3mesi · level complessa · notes
Production-inventory LP, one product, three months: $x_t$ = units produced and $s_t$ = inventory at the end of month $t$, balance $s_{t-1} + x_t = d_t + s_t$ ($s_0 = 0$), capacity $x_t \le b_t$; minimize $z = \sum_t (c\,x_t + h\,s_t)$. Data: $(d_1, d_2, d_3) = (60, 55, 120)$, $(b_1, b_2, b_3) = (80, 80, 90)$, $c = 9$ €/unit, $h = 2$ €/unit/month. What are the optimal cost $\tilde z$ and the optimal inventories $\tilde s_1, \tilde s_2$?
Explanation. With the same $c$ every month it pays to produce as late as possible. Month 3 lacks $120 - 90 = 30$ units: $\tilde s_2 = 30$. Month 2 must cover $55 + 30 = 85 > 80$, so $\tilde s_1 = 5$. Cost $9\cdot 235 + 2\cdot(5 + 30) = 2185$ €.
Example 2 · lpm-g-prod-3mesi · level complessa · notes
Production-inventory LP, one product, three months: $x_t$ = units produced and $s_t$ = inventory at the end of month $t$, balance $s_{t-1} + x_t = d_t + s_t$ ($s_0 = 0$), capacity $x_t \le b_t$; minimize $z = \sum_t (c\,x_t + h\,s_t)$. Data: $(d_1, d_2, d_3) = (50, 100, 70)$, $(b_1, b_2, b_3) = (70, 100, 60)$, $c = 11$ €/unit, $h = 2$ €/unit/month. What are the optimal cost $\tilde z$ and the optimal inventories $\tilde s_1, \tilde s_2$?
Explanation. With the same $c$ every month it pays to produce as late as possible. Month 3 lacks $70 - 60 = 10$ units: $\tilde s_2 = 10$. Month 2 must cover $100 + 10 = 110 > 100$, so $\tilde s_1 = 10$. Cost $11\cdot 220 + 2\cdot(10 + 10) = 2460$ €.
5. Smart charging of electric vehicles (2)
Example 1 · lpm-g-ev-un-veicolo · level facile · notes
EV charging LP, one vehicle, two one-hour slots: $x_t$ = energy charged in hour $t$ (kWh), $0 \le x_t \le \bar p = 11$ (charger power, kW), requirement $x_1 + x_2 \ge e = 20$ kWh (efficiency $\eta = 1$); minimize $\pi_1x_1 + \pi_2x_2$ with $\pi_1 = 0.15$, $\pi_2 = 0.25$ €/kWh. What are the minimum cost and the shadow price of the requirement (cost of one more kWh)?
cost 3.9 €, shadow price 0.1 €/kWh
cost 3.9 €, shadow price 0.15 €/kWh
cost 3 €, shadow price 0.15 €/kWh
cost 3.9 €, shadow price 0.25 €/kWh
Explanation. The cheap hour is used at full power ($11$ kWh), the remaining $9$ kWh go into hour 2: $3.9$ €. One more kWh would end up in the expensive hour: the dual is the price of the marginal hour, $0.25$.
Example 2 · lpm-g-ev-un-veicolo · level facile · notes
EV charging LP, one vehicle, two one-hour slots: $x_t$ = energy charged in hour $t$ (kWh), $0 \le x_t \le \bar p = 6$ (charger power, kW), requirement $x_1 + x_2 \ge e = 7$ kWh (efficiency $\eta = 1$); minimize $\pi_1x_1 + \pi_2x_2$ with $\pi_1 = 0.12$, $\pi_2 = 0.3$ €/kWh. What are the minimum cost and the shadow price of the requirement (cost of one more kWh)?
cost 1.02 €, shadow price 0.3 €/kWh
cost 1.02 €, shadow price 0.18 €/kWh
cost 0.84 €, shadow price 0.12 €/kWh
cost 1.02 €, shadow price 0.12 €/kWh
Explanation. The cheap hour is used at full power ($6$ kWh), the remaining $1$ kWh go into hour 2: $1.02$ €. One more kWh would end up in the expensive hour: the dual is the price of the marginal hour, $0.3$.
Example 1 · lpm-g-ev-tre-ore · level media · notes
EV charging LP, one vehicle plugged in for three one-hour slots: $x_t$ = energy drawn from the grid in hour $t$ (kWh), $0 \le x_t \le \bar p = 9$; requirement $\eta\,(x_1 + x_2 + x_3) \ge e = 18$ kWh, with efficiency $\eta = 0.9$; minimize $\sum_t \pi_t x_t$ with $(\pi_1, \pi_2, \pi_3) = (0.18, 0.25, 0.08)$ €/kWh. What are the minimum cost and the shadow price of the requirement (cost of one more kWh in the battery)?
cost 2.34 €, shadow price 0.18 €/kWh
cost 2.84 €, shadow price 0.25 €/kWh
cost 2.84 €, shadow price 0.278 €/kWh
cost 2.84 €, shadow price 0.089 €/kWh
Explanation. The grid must supply $e/\eta = 20$ kWh, bought in the cheapest hours at full power $\bar p$: cost $2.84$ €. One more kWh in the battery needs $1/\eta$ kWh in the marginal hour (price $0.25$): shadow price $0.25/0.9 = 0.278$ €/kWh. Forgetting $\eta$ buys only $e$ kWh.
Example 2 · lpm-g-ev-tre-ore · level media · notes
EV charging LP, one vehicle plugged in for three one-hour slots: $x_t$ = energy drawn from the grid in hour $t$ (kWh), $0 \le x_t \le \bar p = 9$; requirement $\eta\,(x_1 + x_2 + x_3) \ge e = 21.6$ kWh, with efficiency $\eta = 0.9$; minimize $\sum_t \pi_t x_t$ with $(\pi_1, \pi_2, \pi_3) = (0.25, 0.2, 0.3)$ €/kWh. What are the minimum cost and the shadow price of the requirement (cost of one more kWh in the battery)?
cost 5.13 €, shadow price 0.3 €/kWh
cost 5.85 €, shadow price 0.3 €/kWh
cost 5.85 €, shadow price 0.333 €/kWh
cost 5.85 €, shadow price 0.222 €/kWh
Explanation. The grid must supply $e/\eta = 24$ kWh, bought in the cheapest hours at full power $\bar p$: cost $5.85$ €. One more kWh in the battery needs $1/\eta$ kWh in the marginal hour (price $0.3$): shadow price $0.3/0.9 = 0.333$ €/kWh. Forgetting $\eta$ buys only $e$ kWh.
6. Data Envelopment Analysis (3)
Example 1 · lpm-g-dea-ccr-1x1 · level facile · notes
DEA with five DMUs (decision-making units), one input $x$ and one output $y$. DMU $j$: 1 $(x_{11}, y_{11}) = (8, 7)$; 2 $(x_{12}, y_{12}) = (10, 11)$; 3 $(x_{13}, y_{13}) = (3, 10)$; 4 $(x_{14}, y_{14}) = (8, 8)$; 5 $(x_{15}, y_{15}) = (11, 1)$. The CCR efficiency of DMU $o$ is $h_o = \max\, u\,y_o/(v\,x_o)$ over the weights $u, v \ge 0$ that give every DMU $j$ a ratio $u\,y_j/(v\,x_j) \le 1$. What is the CCR efficiency $\tilde h_{5}$ of DMU 5?
$\tilde h_{5} = 0.083$
$\tilde h_{5} = 0.091$
$\tilde h_{5} = 0.273$
$\tilde h_{5} = 0.027$
Explanation. With one input and one output the weights cancel: the efficiency is $y_o/x_o$ divided by the best ratio, $10/3$ of DMU 3: $(1/11)/(10/3) = 0.027$.
Example 2 · lpm-g-dea-ccr-1x1 · level facile · notes
DEA with five DMUs (decision-making units), one input $x$ and one output $y$. DMU $j$: 1 $(x_{11}, y_{11}) = (6, 11)$; 2 $(x_{12}, y_{12}) = (5, 2)$; 3 $(x_{13}, y_{13}) = (6, 11)$; 4 $(x_{14}, y_{14}) = (10, 8)$; 5 $(x_{15}, y_{15}) = (12, 10)$. The CCR efficiency of DMU $o$ is $h_o = \max\, u\,y_o/(v\,x_o)$ over the weights $u, v \ge 0$ that give every DMU $j$ a ratio $u\,y_j/(v\,x_j) \le 1$. What is the CCR efficiency $\tilde h_{4}$ of DMU 4?
$\tilde h_{4} = 0.727$
$\tilde h_{4} = 0.436$
$\tilde h_{4} = 0.5$
$\tilde h_{4} = 0.8$
Explanation. With one input and one output the weights cancel: the efficiency is $y_o/x_o$ divided by the best ratio, $11/6$ of DMU 1: $(8/10)/(11/6) = 0.436$.
Example 1 · lpm-g-dea-bcc-1x1 · level media · notes
DEA with five DMUs (decision-making units), one input $x$ and one output $y$. DMU $j$: 1 $(x_{11}, y_{11}) = (4, 4)$; 2 $(x_{12}, y_{12}) = (2, 2)$; 3 $(x_{13}, y_{13}) = (5, 7)$; 4 $(x_{14}, y_{14}) = (3, 6)$; 5 $(x_{15}, y_{15}) = (7, 9)$. The input-oriented BCC efficiency $\tilde\theta^{\rm BCC}$ of DMU $o$ is the smallest $\theta$ such that a convex combination of the DMUs ($\lambda_j \ge 0$, $\sum_j\lambda_j = 1$) produces at least $y_o$ with at most $\theta x_o$; the scale efficiency is $\mathrm{SE} = \tilde\theta^{\rm CCR}/\tilde\theta^{\rm BCC}$. DMU 1 has $\tilde\theta^{\rm CCR} = 0.5$. What are its $\tilde\theta^{\rm BCC}$ and $\mathrm{SE}$?
Explanation. The BCC virtual DMU is a convex combination ($\sum_j \lambda_j = 1$) producing at least $y_o = 4$ with the least input: combining two DMUs on either side of $y_o$ gives $\tilde\theta^{\rm BCC} = 0.625$, better than the best single DMU ($0.75$). Then $\mathrm{SE} = \tilde\theta^{\rm CCR}/\tilde\theta^{\rm BCC} = 0.8$.
Example 2 · lpm-g-dea-bcc-1x1 · level media · notes
DEA with five DMUs (decision-making units), one input $x$ and one output $y$. DMU $j$: 1 $(x_{11}, y_{11}) = (6, 11)$; 2 $(x_{12}, y_{12}) = (5, 2)$; 3 $(x_{13}, y_{13}) = (6, 11)$; 4 $(x_{14}, y_{14}) = (10, 8)$; 5 $(x_{15}, y_{15}) = (12, 10)$. The input-oriented BCC efficiency $\tilde\theta^{\rm BCC}$ of DMU $o$ is the smallest $\theta$ such that a convex combination of the DMUs ($\lambda_j \ge 0$, $\sum_j\lambda_j = 1$) produces at least $y_o$ with at most $\theta x_o$; the scale efficiency is $\mathrm{SE} = \tilde\theta^{\rm CCR}/\tilde\theta^{\rm BCC}$. DMU 4 has $\tilde\theta^{\rm CCR} = 0.436$. What are its $\tilde\theta^{\rm BCC}$ and $\mathrm{SE}$?
Explanation. The BCC virtual DMU is a convex combination ($\sum_j \lambda_j = 1$) producing at least $y_o = 8$ with the least input: combining two DMUs on either side of $y_o$ gives $\tilde\theta^{\rm BCC} = 0.567$, better than the best single DMU ($0.6$). Then $\mathrm{SE} = \tilde\theta^{\rm CCR}/\tilde\theta^{\rm BCC} = 0.77$.
Example 1 · lpm-g-dea-ccr-2input · level complessa · notes
DEA with five DMUs (decision-making units), two inputs and one output, data $(x_{1j}, x_{2j}; y_{1j})$: 1: $(24, 4; 2)$, 2: $(18, 16; 2)$, 3: $(4, 16; 2)$, 4: $(30, 36; 3)$, 5: $(30, 30; 3)$. Input-oriented CCR envelopment model for DMU $o$: $\min\theta$ subject to $\sum_j\lambda_jx_{ij} \le \theta x_{io}$ ($i = 1, 2$), $\sum_j\lambda_jy_{1j} \ge y_{1o}$, $\lambda_j \ge 0$. For $o = 4$, what are the efficiency $\tilde\theta$ and the radial input targets $(\tilde\theta x_{1o}; \tilde\theta x_{2o})$?
$\tilde\theta = 0.167$, target $(5; 6)$
$\tilde\theta = 0.341$, target $(10.22; 12.27)$
$\tilde\theta = 0.511$, target $(15.33; 18.4)$
$\tilde\theta = 0.667$, target $(20; 24)$
Explanation. With constant returns divide the inputs by the output: the points $(x_{1j}/y_{1j}, x_{2j}/y_{2j})$ are compared with the same output. The envelopment form looks for the smallest $\theta$ such that a combination of DMUs uses at most $\theta$ times both inputs of DMU 4: here the optimum combines two DMUs, $\tilde\theta = 0.511$ (the best single DMU gives only $0.667$).
Example 2 · lpm-g-dea-ccr-2input · level complessa · notes
DEA with five DMUs (decision-making units), two inputs and one output, data $(x_{1j}, x_{2j}; y_{1j})$: 1: $(5, 8; 1)$, 2: $(22, 22; 2)$, 3: $(7, 11; 1)$, 4: $(20, 18; 2)$, 5: $(10, 5; 1)$. Input-oriented CCR envelopment model for DMU $o$: $\min\theta$ subject to $\sum_j\lambda_jx_{ij} \le \theta x_{io}$ ($i = 1, 2$), $\sum_j\lambda_jy_{1j} \ge y_{1o}$, $\lambda_j \ge 0$. For $o = 2$, what are the efficiency $\tilde\theta$ and the radial input targets $(\tilde\theta x_{1o}; \tilde\theta x_{2o})$?
$\tilde\theta = 0.313$, target $(6.88; 6.88)$
$\tilde\theta = 0.727$, target $(16; 16)$
$\tilde\theta = 0.625$, target $(13.75; 13.75)$
$\tilde\theta = 0.455$, target $(10; 10)$
Explanation. With constant returns divide the inputs by the output: the points $(x_{1j}/y_{1j}, x_{2j}/y_{2j})$ are compared with the same output. The envelopment form looks for the smallest $\theta$ such that a combination of DMUs uses at most $\theta$ times both inputs of DMU 2: here the optimum combines two DMUs, $\tilde\theta = 0.625$ (the best single DMU gives only $0.727$).
7. The Newsvendor and its variants (5)
Example 1 · lpm-g-nv-uniforme · level facile · notes
Newsvendor: a quantity $q$ is ordered before the demand is known; each unit costs $c = 12$ €, sells at $p = 21$ € and, if unsold, is salvaged at $v = 9$ €. Demand is uniform on $[140, 164]$ and $q$ maximizes the expected profit. What are the critical ratio $\alpha^* = \mathbb P(D \le q^*)$ and the optimal quantity $q^*$?
$\alpha^* = 0.75$, $q^* = 158$
$\alpha^* = 0.5$, $q^* = 152$
$\alpha^* = 0.25$, $q^* = 146$
$\alpha^* = 0.6364$, $q^* = 155.3$
Explanation. $c_u = p - c = 9$, $c_o = c - v = 3$, $\alpha^* = c_u/(c_u + c_o) = 9/12$; for the uniform distribution $F^{-1}(\alpha) = 140 + 24\,\alpha$, so $q^* = 158$, not the mean.
Example 2 · lpm-g-nv-uniforme · level facile · notes
Newsvendor: a quantity $q$ is ordered before the demand is known; each unit costs $c = 14$ €, sells at $p = 18$ € and, if unsold, is salvaged at $v = 4$ €. Demand is uniform on $[60, 116]$ and $q$ maximizes the expected profit. What are the critical ratio $\alpha^* = \mathbb P(D \le q^*)$ and the optimal quantity $q^*$?
$\alpha^* = 0.2857$, $q^* = 76$
$\alpha^* = 0.7143$, $q^* = 100$
$\alpha^* = 0.5$, $q^* = 88$
$\alpha^* = 0.5625$, $q^* = 91.5$
Explanation. $c_u = p - c = 4$, $c_o = c - v = 10$, $\alpha^* = c_u/(c_u + c_o) = 4/14$; for the uniform distribution $F^{-1}(\alpha) = 60 + 56\,\alpha$, so $q^* = 76$, not the mean.
Example 1 · lpm-g-nv-discreto · level media · notes
Newsvendor: a quantity $q$ is ordered before the demand $D$ is known, to minimize the expected cost $\mathbb E[c_o(q - D)^+ + c_u(D - q)^+]$, with underage cost $c_u = 4$ per unit of unmet demand and overage cost $c_o = 12$ per unsold unit. Demand scenarios (probability in brackets): $70$ (0.3), $110$ (0.1), $120$ (0.3), $130$ (0.3). What are the optimal quantity $q^*$ and its expected cost?
$q^* = 130$, expected cost 276
$q^* = 70$, expected cost 148
$q^* = 110$, expected cost 180
$q^* = 120$, expected cost 204
Explanation. $\alpha^* = 4/16 = 0.25$: the optimum is the smallest $q$ with $F(q) \ge \alpha^*$, that is $q^* = 70$, with expected cost $\sum_s \pi_s (c_o (q - d_s)^+ + c_u (d_s - q)^+) = 148$.
Example 2 · lpm-g-nv-discreto · level media · notes
Newsvendor: a quantity $q$ is ordered before the demand $D$ is known, to minimize the expected cost $\mathbb E[c_o(q - D)^+ + c_u(D - q)^+]$, with underage cost $c_u = 11$ per unit of unmet demand and overage cost $c_o = 4$ per unsold unit. Demand scenarios (probability in brackets): $60$ (0.4), $100$ (0.3), $110$ (0.1), $130$ (0.1), $140$ (0.1). What are the optimal quantity $q^*$ and its expected cost?
$q^* = 110$, expected cost 147
$q^* = 100$, expected cost 152
$q^* = 60$, expected cost 352
$q^* = 130$, expected cost 167
Explanation. $\alpha^* = 11/15 = 0.7333$: the optimum is the smallest $q$ with $F(q) \ge \alpha^*$, that is $q^* = 110$, with expected cost $\sum_s \pi_s (c_o (q - d_s)^+ + c_u (d_s - q)^+) = 147$.
Example 1 · lpm-g-nv-vss · level complessa · notes
Newsvendor: a quantity $q$ is ordered before the demand $D$ is known, to minimize the expected cost $\mathbb E[c_o(q - D)^+ + c_u(D - q)^+]$, with underage cost $c_u = 7$ per unit of unmet demand and overage cost $c_o = 11$ per unsold unit. Demand scenarios (probability in brackets): $130$ (0.4), $140$ (0.2), $160$ (0.2), $190$ (0.1), $200$ (0.1). Compute the optimal quantity $q^*$, its expected cost and the value of the stochastic solution VSS (expected cost of ordering the mean demand minus the cost of $q^*$).
$q^* = 130$, cost 147, VSS $= 147$
$q^* = 140$, cost 149, VSS $= 41.8$
$q^* = 130$, cost 147, VSS $= 190.8$
$q^* = 130$, cost 147, VSS $= 43.8$
Explanation. $\alpha^* = 0.3889$ gives $q^* = 130$ with cost $147$. The mean demand is $151$, whose expected cost is $190.8$: VSS $= 190.8 - 147 = 43.8$.
Example 2 · lpm-g-nv-vss · level complessa · notes
Newsvendor: a quantity $q$ is ordered before the demand $D$ is known, to minimize the expected cost $\mathbb E[c_o(q - D)^+ + c_u(D - q)^+]$, with underage cost $c_u = 11$ per unit of unmet demand and overage cost $c_o = 4$ per unsold unit. Demand scenarios (probability in brackets): $60$ (0.4), $100$ (0.3), $110$ (0.1), $130$ (0.1), $140$ (0.1). Compute the optimal quantity $q^*$, its expected cost and the value of the stochastic solution VSS (expected cost of ordering the mean demand minus the cost of $q^*$).
$q^* = 110$, cost 147, VSS $= 45$
$q^* = 110$, cost 147, VSS $= 192$
$q^* = 100$, cost 152, VSS $= 40$
$q^* = 110$, cost 147, VSS $= 147$
Explanation. $\alpha^* = 0.7333$ gives $q^* = 110$ with cost $147$. The mean demand is $92$, whose expected cost is $192$: VSS $= 192 - 147 = 45$.
Example 1 · lpm-g-nv-normale · level facile · notes
Newsvendor: a product is bought at $c = 8$ €, sold at $p = 20$ € and each unsold unit is recovered at $v = 4$ €; demand is normal with mean $190$ and standard deviation $10$. The optimal order satisfies $F(\tilde q) = c_u/(c_u + c_o)$ with $c_u = p - c$ and $c_o = c - v$, so $\tilde q = \mu + z\sigma$ with $z = \Phi^{-1}(c_u/(c_u + c_o))$ (standard normal quantiles: $\Phi^{-1}(0.6) = 0.253$, $\Phi^{-1}(0.7) = 0.524$, $\Phi^{-1}(0.75) = 0.674$, $\Phi^{-1}(0.8) = 0.842$, $\Phi^{-1}(0.9) = 1.282$). What is $\tilde q$?
$\tilde q = 196.7$
$\tilde q = 198.4$
$\tilde q = 183.3$
$\tilde q = 190$
Explanation. $c_u = 12$, $c_o = 4$, critical ratio $12/16 = 0.75$, $z = 0.674$: $\tilde q = 190 + 0.674\cdot 10 = 196.7$, above the mean because shortages cost more than leftovers. Swapping $c_u$ and $c_o$ gives $\mu - z\sigma$.
Example 2 · lpm-g-nv-normale · level facile · notes
Newsvendor: a product is bought at $c = 8$ €, sold at $p = 22$ € and each unsold unit is recovered at $v = 2$ €; demand is normal with mean $90$ and standard deviation $20$. The optimal order satisfies $F(\tilde q) = c_u/(c_u + c_o)$ with $c_u = p - c$ and $c_o = c - v$, so $\tilde q = \mu + z\sigma$ with $z = \Phi^{-1}(c_u/(c_u + c_o))$ (standard normal quantiles: $\Phi^{-1}(0.6) = 0.253$, $\Phi^{-1}(0.7) = 0.524$, $\Phi^{-1}(0.75) = 0.674$, $\Phi^{-1}(0.8) = 0.842$, $\Phi^{-1}(0.9) = 1.282$). What is $\tilde q$?
$\tilde q = 100.5$
$\tilde q = 79.5$
$\tilde q = 103.5$
$\tilde q = 90$
Explanation. $c_u = 14$, $c_o = 6$, critical ratio $14/20 = 0.7$, $z = 0.524$: $\tilde q = 90 + 0.524\cdot 20 = 100.5$, above the mean because shortages cost more than leftovers. Swapping $c_u$ and $c_o$ gives $\mu - z\sigma$.
Example 1 · lpm-g-nv-servizio-uniforme · level media · notes
Newsvendor with uniform demand on $[90, 180]$, $c_u = 6$, $c_o = 9$. The expected cost of an order $q$ in $[90, 180]$ is $C(q) = \frac{c_o(q - 90)^2 + c_u(180 - q)^2}{2\cdot 90}$, minimized at $\tilde q = 90 + \frac{c_u}{c_u + c_o}\cdot 90$. A contract imposes a cycle service level $\mathbb P(D \le q) = 0.9$. What are the required order $q_\beta$ and its extra expected cost $C(q_\beta) - C(\tilde q)$?
$q_\beta = 171$, extra cost $33.75$
$q_\beta = 99$, extra cost $168.75$
$q_\beta = 171$, extra cost $168.75$
$q_\beta = 171$, extra cost $330.75$
Explanation. $q_\beta = 90 + 0.9\cdot 90 = 171$; $\tilde q = 126$; $C(q_\beta) = 330.75$ and $C(\tilde q) = 162$, so the service level costs $168.75$ more per cycle than the economic optimum, whose service level is only $0.4$.
Example 2 · lpm-g-nv-servizio-uniforme · level media · notes
Newsvendor with uniform demand on $[70, 180]$, $c_u = 4$, $c_o = 2$. The expected cost of an order $q$ in $[70, 180]$ is $C(q) = \frac{c_o(q - 70)^2 + c_u(180 - q)^2}{2\cdot 110}$, minimized at $\tilde q = 70 + \frac{c_u}{c_u + c_o}\cdot 110$. A contract imposes a cycle service level $\mathbb P(D \le q) = 0.9$. What are the required order $q_\beta$ and its extra expected cost $C(q_\beta) - C(\tilde q)$?
$q_\beta = 169$, extra cost $17.97$
$q_\beta = 169$, extra cost $69.3$
$q_\beta = 81$, extra cost $17.97$
$q_\beta = 169$, extra cost $91.3$
Explanation. $q_\beta = 70 + 0.9\cdot 110 = 169$; $\tilde q = 143.33$; $C(q_\beta) = 91.3$ and $C(\tilde q) = 73.33$, so the service level costs $17.97$ more per cycle than the economic optimum, whose service level is only $0.67$.
8. VaR and CVaR (4)
Example 1 · lpm-g-cvar-coda-intera · level facile · notes
Risk measures of a loss $L$ with $k = 10$ equally likely scenarios: $24, 32, 35, 5, 33, 25, 36, 1, 8, 11$. $\mathrm{VaR}_\alpha$ is the smallest loss $\ell$ with $\mathbb P(L \le \ell) \ge \alpha$; $\mathrm{CVaR}_\alpha$ is the mean loss in the worst tail of probability $1 - \alpha$. With $\alpha = 0.7$, what are $\mathrm{VaR}_\alpha$ and $\mathrm{CVaR}_\alpha$?
VaR $= 33$, CVaR $= 34.67$
VaR $= 32$, CVaR $= 34$
VaR $= 32$, CVaR $= 36$
VaR $= 32$, CVaR $= 34.67$
Explanation. Sorting the losses, the distribution function reaches $0.7$ at position 7 in increasing order: VaR $= 32$. The tail of mass $1 - \alpha$ contains exactly the 3 worst losses, whose mean is the CVaR, $34.67$.
Example 2 · lpm-g-cvar-coda-intera · level facile · notes
Risk measures of a loss $L$ with $k = 8$ equally likely scenarios: $34, 13, 4, 16, 35, 32, 27, 38$. $\mathrm{VaR}_\alpha$ is the smallest loss $\ell$ with $\mathbb P(L \le \ell) \ge \alpha$; $\mathrm{CVaR}_\alpha$ is the mean loss in the worst tail of probability $1 - \alpha$. With $\alpha = 0.75$, what are $\mathrm{VaR}_\alpha$ and $\mathrm{CVaR}_\alpha$?
VaR $= 34$, CVaR $= 36.5$
VaR $= 34$, CVaR $= 35.67$
VaR $= 35$, CVaR $= 36.5$
VaR $= 34$, CVaR $= 38$
Explanation. Sorting the losses, the distribution function reaches $0.75$ at position 6 in increasing order: VaR $= 34$. The tail of mass $1 - \alpha$ contains exactly the 2 worst losses, whose mean is the CVaR, $36.5$.
Example 1 · lpm-g-cvar-a-cavallo · level media · notes
Risk measures of a loss $L$ with six equally likely scenarios: $24, 32, 35, 5, 33, 25$. $\mathrm{VaR}_\alpha$ is the smallest loss $\ell$ with $\mathbb P(L \le \ell) \ge \alpha$, and $\mathrm{CVaR}_\alpha = \mathrm{VaR}_\alpha + \mathbb E[(L - \mathrm{VaR}_\alpha)^+]/(1 - \alpha)$. With $\alpha = 0.75$ (the tail of probability $1 - \alpha$ is not a whole number of scenarios), what are $\mathrm{VaR}_\alpha$ and $\mathrm{CVaR}_\alpha$?
VaR $= 33$, CVaR $= 34$
VaR $= 33$, CVaR $= 34.33$
VaR $= 35$, CVaR $= 34.33$
VaR $= 33$, CVaR $= 35$
Explanation. VaR $= 33$, the first loss at which the distribution function reaches $\alpha$. Then $\mathrm{CVaR} = \mathrm{VaR} + \frac{1}{1-\alpha}\sum_s \pi_s (\ell_s - \mathrm{VaR})^+ = 34.33$: the part of the tail mass that sits on the VaR point is counted at the VaR value.
Example 2 · lpm-g-cvar-a-cavallo · level media · notes
Risk measures of a loss $L$ with six equally likely scenarios: $34, 13, 4, 16, 35, 32$. $\mathrm{VaR}_\alpha$ is the smallest loss $\ell$ with $\mathbb P(L \le \ell) \ge \alpha$, and $\mathrm{CVaR}_\alpha = \mathrm{VaR}_\alpha + \mathbb E[(L - \mathrm{VaR}_\alpha)^+]/(1 - \alpha)$. With $\alpha = 0.75$ (the tail of probability $1 - \alpha$ is not a whole number of scenarios), what are $\mathrm{VaR}_\alpha$ and $\mathrm{CVaR}_\alpha$?
VaR $= 34$, CVaR $= 34.67$
VaR $= 34$, CVaR $= 34.5$
VaR $= 35$, CVaR $= 34.67$
VaR $= 34$, CVaR $= 35$
Explanation. VaR $= 34$, the first loss at which the distribution function reaches $\alpha$. Then $\mathrm{CVaR} = \mathrm{VaR} + \frac{1}{1-\alpha}\sum_s \pi_s (\ell_s - \mathrm{VaR})^+ = 34.67$: the part of the tail mass that sits on the VaR point is counted at the VaR value.
Example 1 · lpm-g-cvar-pesato · level complessa · notes
Risk measures of a loss $L$ with scenarios (probability in brackets): $26$ (0.3), $20$ (0.3), $9$ (0.3), $3$ (0.05), $27$ (0.05). $\mathrm{VaR}_\alpha$ is the smallest loss $\ell$ with $\mathbb P(L \le \ell) \ge \alpha$; $\mathrm{CVaR}_\alpha$ is the optimal value of the Rockafellar–Uryasev LP $\min_\eta\, \eta + \mathbb E[(L - \eta)^+]/(1 - \alpha)$. With $\alpha = 0.9$, what are $\mathrm{VaR}_\alpha$ and $\mathrm{CVaR}_\alpha$?
VaR $= 26$, CVaR $= 26.14$
VaR $= 26$, CVaR $= 27$
VaR $= 27$, CVaR $= 27$
VaR $= 26$, CVaR $= 26.5$
Explanation. Sorting the losses and accumulating the probabilities, $F$ reaches $0.9$ at $\ell = 26$: VaR $= 26$. Then $\mathrm{CVaR} = 26 + \frac{1}{0.1}\sum_s \pi_s(\ell_s - 26)^+ = 26.5$. The conditional mean beyond the VaR ignores the tail mass sitting on the VaR point.
Example 2 · lpm-g-cvar-pesato · level complessa · notes
Risk measures of a loss $L$ with scenarios (probability in brackets): $34$ (0.35), $13$ (0.3), $4$ (0.25), $16$ (0.05), $35$ (0.05). $\mathrm{VaR}_\alpha$ is the smallest loss $\ell$ with $\mathbb P(L \le \ell) \ge \alpha$; $\mathrm{CVaR}_\alpha$ is the optimal value of the Rockafellar–Uryasev LP $\min_\eta\, \eta + \mathbb E[(L - \eta)^+]/(1 - \alpha)$. With $\alpha = 0.85$, what are $\mathrm{VaR}_\alpha$ and $\mathrm{CVaR}_\alpha$?
VaR $= 34$, CVaR $= 34.33$
VaR $= 35$, CVaR $= 35$
VaR $= 34$, CVaR $= 34.13$
VaR $= 34$, CVaR $= 35$
Explanation. Sorting the losses and accumulating the probabilities, $F$ reaches $0.85$ at $\ell = 34$: VaR $= 34$. Then $\mathrm{CVaR} = 34 + \frac{1}{0.15}\sum_s \pi_s(\ell_s - 34)^+ = 34.33$. The conditional mean beyond the VaR ignores the tail mass sitting on the VaR point.
Example 1 · lpm-g-cvar-eccessi · level facile · notes
Rockafellar–Uryasev formulation of the CVaR: for a threshold $\eta$, the excesses are $\xi_s = (\ell_s - \eta)^+$ and the function to minimize over $\eta$ is $F(\eta) = \eta + \frac{1}{1-\alpha}\sum_s\pi_s\xi_s$. Five equiprobable scenarios ($\pi_s = 0.2$) with losses $\ell = (18; 18; 24; 26; 4)$, $\alpha = 0.8$. For $\eta = 18$ (not necessarily optimal), what are $\sum_s\xi_s$ and $F(\eta)$?
$\sum_s\xi_s = 14$, value $20.8$
$\sum_s\xi_s = 14$, value $32$
$\sum_s\xi_s = 14$, value $21.5$
$\sum_s\xi_s = 0$, value $18$
Explanation. Only the losses above $18$ count: $\xi = (0; 0; 6; 8; 0)$, sum $14$. Then $F(18) = 18 + \frac{1}{0.2}\cdot 0.2\cdot 14 = 32$. Negative differences are cut at zero; forgetting the factor $1/(1-\alpha)$ is the other typical mistake.
Example 2 · lpm-g-cvar-eccessi · level facile · notes
Rockafellar–Uryasev formulation of the CVaR: for a threshold $\eta$, the excesses are $\xi_s = (\ell_s - \eta)^+$ and the function to minimize over $\eta$ is $F(\eta) = \eta + \frac{1}{1-\alpha}\sum_s\pi_s\xi_s$. Five equiprobable scenarios ($\pi_s = 0.2$) with losses $\ell = (12; 26; 10; 3; 12)$, $\alpha = 0.8$. For $\eta = 21$ (not necessarily optimal), what are $\sum_s\xi_s$ and $F(\eta)$?
$\sum_s\xi_s = 5$, value $26$
$\sum_s\xi_s = 5$, value $22$
$\sum_s\xi_s = 5$, value $22.25$
$\sum_s\xi_s = -42$, value $-21$
Explanation. Only the losses above $21$ count: $\xi = (0; 5; 0; 0; 0)$, sum $5$. Then $F(21) = 21 + \frac{1}{0.2}\cdot 0.2\cdot 5 = 26$. Negative differences are cut at zero; forgetting the factor $1/(1-\alpha)$ is the other typical mistake.
9. Arbitrage and pricing (5)
Example 1 · lpm-g-arb-neutrali · level facile · notes
One-period market with two states of the world: a risk-free security costs $1$ today and pays $R = 1.1$ in both states; a risky security costs $s^0_1 = 33$ today and pays $58$ in state 1 and $31$ in state 2. Risk-neutral probabilities are $q_1, q_2 \ge 0$ with $q_1 + q_2 = 1$ under which every price equals the expected payoff divided by $R$. What are $q_1$ and $q_2$?
$(q_1; q_2) = (0.6259; 0.3741)$
$(q_1; q_2) = (0.0741; 0.9259)$
$(q_1; q_2) = (0.8037; 0.1963)$
$(q_1; q_2) = (0.1963; 0.8037)$
Explanation. The price is the discounted expected payoff: $s^0_1 = (q_1 \cdot 58 + q_2 \cdot 31)/R$ with $q_1 + q_2 = 1$, so $q_1 = (R s^0_1 - 31)/(58 - 31) = 0.1963$. Forgetting $R$ is the typical mistake.
Example 2 · lpm-g-arb-neutrali · level facile · notes
One-period market with two states of the world: a risk-free security costs $1$ today and pays $R = 1.05$ in both states; a risky security costs $s^0_1 = 44$ today and pays $50$ in state 1 and $29$ in state 2. Risk-neutral probabilities are $q_1, q_2 \ge 0$ with $q_1 + q_2 = 1$ under which every price equals the expected payoff divided by $R$. What are $q_1$ and $q_2$?
$(q_1; q_2) = (0.819; 0.181)$
$(q_1; q_2) = (0.924; 0.076)$
$(q_1; q_2) = (0.181; 0.819)$
$(q_1; q_2) = (0.7143; 0.2857)$
Explanation. The price is the discounted expected payoff: $s^0_1 = (q_1 \cdot 50 + q_2 \cdot 29)/R$ with $q_1 + q_2 = 1$, so $q_1 = (R s^0_1 - 29)/(50 - 29) = 0.819$. Forgetting $R$ is the typical mistake.
One-period market with two states of the world: a risk-free security costs $1$ today and pays $R = 1.1$ in both states; a risky security costs $s^0_1 = 33$ today and pays $58$ in state 1 and $31$ in state 2. Risk-neutral probabilities are $q_1, q_2 \ge 0$ with $q_1 + q_2 = 1$ under which every price equals the expected payoff divided by $R$. A call option with strike $34$ pays tomorrow $\max(s^1_{1j} - 34, 0)$ in state $j$, where $s^1_{1j}$ is the payoff of the risky security. In this complete market, what is the arbitrage-free price of the call today?
4.28
1.62
4.71
10.91
Explanation. The risk-neutral probabilities are $q_1 = (R s^0_1 - 31)/(58 - 31) = 0.1963$, $q_2 = 1 - q_1$. The call pays $(24, 0)$, so its price is $q_1 \cdot 24/R = 4.28$: discounted expected value under $q$.
One-period market with two states of the world: a risk-free security costs $1$ today and pays $R = 1.05$ in both states; a risky security costs $s^0_1 = 44$ today and pays $50$ in state 1 and $29$ in state 2. Risk-neutral probabilities are $q_1, q_2 \ge 0$ with $q_1 + q_2 = 1$ under which every price equals the expected payoff divided by $R$. A call option with strike $37$ pays tomorrow $\max(s^1_{1j} - 37, 0)$ in state $j$, where $s^1_{1j}$ is the payoff of the risky security. In this complete market, what is the arbitrage-free price of the call today?
10.14
10.65
8.84
6.19
Explanation. The risk-neutral probabilities are $q_1 = (R s^0_1 - 29)/(50 - 29) = 0.819$, $q_2 = 1 - q_1$. The call pays $(13, 0)$, so its price is $q_1 \cdot 13/R = 10.14$: discounted expected value under $q$.
Example 1 · lpm-g-arb-intervallo · level complessa · notes
One-period market with three states: a risk-free security costs $1$ and pays $R = 1.1$ in every state; a risky security costs $s^0_1 = 14$ and pays $(a_1; a_2; a_3) = (5; 36; 11)$ in the three states. A new security pays $(c_1; c_2; c_3) = (5; 1; 2)$. Its price is consistent (creates no arbitrage) if it equals $\frac1R\sum_j q_j\, c_j$ for risk-neutral probabilities $q_j \ge 0$, $\sum_j q_j = 1$, that also price the two existing securities. What is the interval of consistent prices (its endpoints)?
$[1.82; 3.66]$
$[1.71; 3.49]$
$[1.66; 3.33]$
$[0.91; 4.55]$
Explanation. The consistent measures satisfy $\sum_j q_j = 1$ and $\sum_j q_j a_j = R\,s^0_1 = 15.4$: a segment whose endpoints put mass on two states only, one with payoff below and one above $15.4$. Minimizing and maximizing $\frac1R\sum_j q_jc_j$ (two LPs) over it gives $[1.66, 3.33]$. Forgetting the factor $R$ (in the constraint or in the discount) shifts the interval.
Example 2 · lpm-g-arb-intervallo · level complessa · notes
One-period market with three states: a risk-free security costs $1$ and pays $R = 1.05$ in every state; a risky security costs $s^0_1 = 24$ and pays $(a_1; a_2; a_3) = (35; 16; 8)$ in the three states. A new security pays $(c_1; c_2; c_3) = (8; 18; 16)$. Its price is consistent (creates no arbitrage) if it equals $\frac1R\sum_j q_j\, c_j$ for risk-neutral probabilities $q_j \ge 0$, $\sum_j q_j = 1$, that also price the two existing securities. What is the interval of consistent prices (its endpoints)?
$[10.38; 12.53]$
$[10.9; 13.16]$
$[7.62; 17.14]$
$[10.72; 13.13]$
Explanation. The consistent measures satisfy $\sum_j q_j = 1$ and $\sum_j q_j a_j = R\,s^0_1 = 25.2$: a segment whose endpoints put mass on two states only, one with payoff below and one above $25.2$. Minimizing and maximizing $\frac1R\sum_j q_jc_j$ (two LPs) over it gives $[10.38, 12.53]$. Forgetting the factor $R$ (in the constraint or in the discount) shifts the interval.
Example 1 · lpm-g-arb-portafoglio · level facile · notes
One-period market with three states: security 0 is risk-free (costs 1 today, pays $R = 1.05$ in every state); security 1 costs $15$ and pays $(10; 10; 6)$; security 2 costs $25$ and pays $(16; 26; 32)$. The portfolio $x = (-28; -1; -1)$ holds $x_i$ units of security $i$ (negative = short). What are its cost today, $\sum_is^0_ix_i$, and its smallest payoff tomorrow over the three states?
cost $-68$, smallest payoff $-67.4$
cost $-68$, smallest payoff $-66$
cost $-69.4$, smallest payoff $-67.4$
cost $-68$, smallest payoff $-55.4$
Explanation. Cost: $-28\cdot 1 + -1\cdot 15 + -1\cdot 25 = -68$. Payoffs: $-28\cdot 1.05 + -1s^1_{1j} + -1s^1_{2j}$ = $-55.4$, $-65.4$, $-67.4$, smallest $-67.4$. A negative cost with every payoff $\ge 0$ would be an arbitrage of type A. The risk-free position pays $R$ per unit, not 1.
Example 2 · lpm-g-arb-portafoglio · level facile · notes
One-period market with three states: security 0 is risk-free (costs 1 today, pays $R = 1.04$ in every state); security 1 costs $15$ and pays $(18; 9; 6)$; security 2 costs $38$ and pays $(22; 36; 34)$. The portfolio $x = (-36; 2; 1)$ holds $x_i$ units of security $i$ (negative = short). What are its cost today, $\sum_is^0_ix_i$, and its smallest payoff tomorrow over the three states?
cost $32$, smallest payoff $20.56$
cost $32$, smallest payoff $10$
cost $32$, smallest payoff $8.56$
cost $30.56$, smallest payoff $8.56$
Explanation. Cost: $-36\cdot 1 + 2\cdot 15 + 1\cdot 38 = 32$. Payoffs: $-36\cdot 1.04 + 2s^1_{1j} + 1s^1_{2j}$ = $20.56$, $16.56$, $8.56$, smallest $8.56$. A negative cost with every payoff $\ge 0$ would be an arbitrage of type A. The risk-free position pays $R$ per unit, not 1.
Example 1 · lpm-g-arb-prezzo-atteso · level facile · notes
One-period market with three states and risk-free gross return $R = 1.02$. The duals of the arbitrage LP give the risk-neutral probabilities $q = (0.2; 0.1; 0.7)$, and every price today is the discounted expected payoff under $q$: $s^0_i = \frac1R\sum_jq_js^1_{ij}$. A new security pays $(10; 16; 4)$ in the three states. What is its arbitrage-free price today?
$s^0 = 6.27$
$s^0 = 6.53$
$s^0 = 9.8$
$s^0 = 6.4$
Explanation. Expected payoff under $q$: $6.4$; discounted: $6.4/1.02 = 6.27$. Forgetting to discount, or using equal probabilities instead of $q$, are the typical mistakes.
Example 2 · lpm-g-arb-prezzo-atteso · level facile · notes
One-period market with three states and risk-free gross return $R = 1.02$. The duals of the arbitrage LP give the risk-neutral probabilities $q = (0.3; 0.5; 0.2)$, and every price today is the discounted expected payoff under $q$: $s^0_i = \frac1R\sum_jq_js^1_{ij}$. A new security pays $(2; 12; 26)$ in the three states. What is its arbitrage-free price today?
$s^0 = 11.57$
$s^0 = 12.04$
$s^0 = 11.8$
$s^0 = 13.07$
Explanation. Expected payoff under $q$: $11.8$; discounted: $11.8/1.02 = 11.57$. Forgetting to discount, or using equal probabilities instead of $q$, are the typical mistakes.
10. Robust and quantile regression (6)
Example 1 · lpm-g-reg-perdita · level facile · notes
Quantile regression with no features: an intercept $b$ is fitted to $y = (120; 135; 141; 87; 137)$ by minimizing $\sum_i [\tau u_i + (1 - \tau) v_i]$, where $u_i = (y_i - b)^+$ and $v_i = (b - y_i)^+$ are the deviations above and below $b$. With $\tau = 0.8$, what is the objective value for $b = 121$?
$85$
$38$
$47$
$68$
Explanation. The deviations above ($u_i$, observations larger than $b$) sum to $50$ and are paid $\tau$; those below ($v_i$) sum to $35$ and are paid $1 - \tau$: $0.8\cdot 50 + 0.2\cdot 35 = 47$.
Example 2 · lpm-g-reg-perdita · level facile · notes
Quantile regression with no features: an intercept $b$ is fitted to $y = (107; 139; 102; 86; 108)$ by minimizing $\sum_i [\tau u_i + (1 - \tau) v_i]$, where $u_i = (y_i - b)^+$ and $v_i = (b - y_i)^+$ are the deviations above and below $b$. With $\tau = 0.9$, what is the objective value for $b = 130$?
$19.8$
$106.2$
$113.4$
$126$
Explanation. The deviations above ($u_i$, observations larger than $b$) sum to $9$ and are paid $\tau$; those below ($v_i$) sum to $117$ and are paid $1 - \tau$: $0.9\cdot 9 + 0.1\cdot 117 = 19.8$.
Example 1 · lpm-g-reg-quantile · level media · notes
Quantile regression with no features: an intercept $b$ is fitted to the $n = 7$ observations $y = (126; 143; 149; 88; 145; 130; 151)$ by minimizing $z(b) = \sum_i [\tau (y_i - b)^+ + (1 - \tau)(b - y_i)^+]$, with $\tau = 0.25$. What are the optimal intercept $\tilde b$ and the optimal value $\tilde z$?
$\tilde b = 143$, $\tilde z = 67.75$
$\tilde b = 130$, $\tilde z = 51.5$
$\tilde b = 126$, $\tilde z = 50.5$
$\tilde b = 88$, $\tilde z = 79$
Explanation. Without features the LP returns the empirical $\tau$-quantile: raising $b$ pays while the share of observations below it is at most $\tau$. Since $\tau n = 1.75$, $\tilde b$ is the observation in position 2 in increasing order, $126$, with $\tilde z = 50.5$.
Example 2 · lpm-g-reg-quantile · level media · notes
Quantile regression with no features: an intercept $b$ is fitted to the $n = 6$ observations $y = (148; 105; 87; 112; 149; 144)$ by minimizing $z(b) = \sum_i [\tau (y_i - b)^+ + (1 - \tau)(b - y_i)^+]$, with $\tau = 0.75$. What are the optimal intercept $\tilde b$ and the optimal value $\tilde z$?
$\tilde b = 148$, $\tilde z = 36.75$
$\tilde b = 112$, $\tilde z = 86.75$
$\tilde b = 149$, $\tilde z = 37.25$
$\tilde b = 144$, $\tilde z = 38.75$
Explanation. Without features the LP returns the empirical $\tau$-quantile: raising $b$ pays while the share of observations below it is at most $\tau$. Since $\tau n = 4.5$, $\tilde b$ is the observation in position 5 in increasing order, $148$, with $\tilde z = 36.75$.
Example 1 · lpm-g-reg-duale-interpolato · level media · notes
Quantile regression LP with no features: $\min\sum_i[\tau u_i + (1 - \tau)v_i]$ subject to $b + u_i - v_i = y_i$, $u_i, v_i \ge 0$, $b$ free; $\tilde\pi_i$ is the optimal dual of the constraint of observation $i$ (it equals $\tau$ for observations above $\tilde b$, $-(1 - \tau)$ for those below, and $\sum_i\tilde\pi_i = 0$). Data: $y = (94; 101; 84; 87; 106)$, $\tau = 7/10$. What are $\tilde b$ and the dual $\tilde\pi$ of the interpolated observation ($y_i = \tilde b$)?
$\tilde b = 101$, $\tilde\pi = -0.2$
$\tilde b = 94$, $\tilde\pi = 0.7$
$\tilde b = 101$, $\tilde\pi = 0.2$
$\tilde b = 106$, $\tilde\pi = 0.2$
Explanation. $\tilde b$ is the empirical $\tau$-quantile: with $(k - 1)/n < \tau < k/n$ for $k = 4$ it is the 4th smallest value, $101$, with $3$ observations below and $1$ above. From $\sum_i\tilde\pi_i = 0$: $\tilde\pi = (1 - \tau)\cdot 3 - \tau\cdot 1 = 0.2$, inside $[-(1 - \tau), \tau]$.
Example 2 · lpm-g-reg-duale-interpolato · level media · notes
Quantile regression LP with no features: $\min\sum_i[\tau u_i + (1 - \tau)v_i]$ subject to $b + u_i - v_i = y_i$, $u_i, v_i \ge 0$, $b$ free; $\tilde\pi_i$ is the optimal dual of the constraint of observation $i$ (it equals $\tau$ for observations above $\tilde b$, $-(1 - \tau)$ for those below, and $\sum_i\tilde\pi_i = 0$). Data: $y = (105; 87; 112; 149; 144; 133; 154)$, $\tau = 11/14$. What are $\tilde b$ and the dual $\tilde\pi$ of the interpolated observation ($y_i = \tilde b$)?
$\tilde b = 149$, $\tilde\pi = 0.286$
$\tilde b = 154$, $\tilde\pi = 0.286$
$\tilde b = 149$, $\tilde\pi = -0.286$
$\tilde b = 144$, $\tilde\pi = 0.786$
Explanation. $\tilde b$ is the empirical $\tau$-quantile: with $(k - 1)/n < \tau < k/n$ for $k = 6$ it is the 6th smallest value, $149$, with $5$ observations below and $1$ above. From $\sum_i\tilde\pi_i = 0$: $\tilde\pi = (1 - \tau)\cdot 5 - \tau\cdot 1 = 0.286$, inside $[-(1 - \tau), \tau]$.
Example 1 · lpm-g-reg-lad-3punti · level complessa · notes
Quantile regression LP with one feature ($p = 1$): $\min\sum_i[\tau u_i + (1 - \tau)v_i]$ subject to $wx_i + b + u_i - v_i = y_i$, $u_i, v_i \ge 0$ ($u_i$: observation above the line, $v_i$: below), $w, b$ free, with $\tau = 0.5$ and three observations $(x_i; y_i)$: (1; 34), (4; 47), (5; 12). An optimal line interpolates $p + 1 = 2$ observations. What are the optimal slope $\tilde w$, intercept $\tilde b$ and optimal value?
slope $4.33$, intercept $29.67$, value $19.67$
slope $-5.5$, intercept $39.5$, value $29.5$
slope $-35$, intercept $187$, value $59$
slope $-5.5$, intercept $39.5$, value $14.75$
Explanation. Three candidate lines, one per pair of points; each leaves one residual $r$ on the third point, which costs $\tau r$ if the point is above ($r > 0$) and $(1 - \tau)|r|$ if below. Values: $19.67$, $14.75$, $59$. The cheapest is the line with slope $-5.5$ and intercept $39.5$.
Example 2 · lpm-g-reg-lad-3punti · level complessa · notes
Quantile regression LP with one feature ($p = 1$): $\min\sum_i[\tau u_i + (1 - \tau)v_i]$ subject to $wx_i + b + u_i - v_i = y_i$, $u_i, v_i \ge 0$ ($u_i$: observation above the line, $v_i$: below), $w, b$ free, with $\tau = 0.5$ and three observations $(x_i; y_i)$: (1; 56), (3; 46), (8; 38). An optimal line interpolates $p + 1 = 2$ observations. What are the optimal slope $\tilde w$, intercept $\tilde b$ and optimal value?
slope $-5$, intercept $61$, value $8.5$
slope $-2.57$, intercept $58.57$, value $2.43$
slope $-2.57$, intercept $58.57$, value $4.86$
slope $-1.6$, intercept $50.8$, value $3.4$
Explanation. Three candidate lines, one per pair of points; each leaves one residual $r$ on the third point, which costs $\tau r$ if the point is above ($r > 0$) and $(1 - \tau)|r|$ if below. Values: $8.5$, $2.43$, $3.4$. The cheapest is the line with slope $-2.57$ and intercept $58.57$.
Example 1 · lpm-g-reg-obiettivo-retta · level facile · notes
Quantile regression LP with one feature: $\min\sum_i[\tau u_i + (1 - \tau)v_i]$ with $wx_i + b + u_i - v_i = y_i$, $u_i, v_i \ge 0$ ($u_i$: observation above the line, $v_i$: below). For the candidate line $w = 1$, $b = 110$ (not necessarily optimal), $\tau = 0.9$ and the observations $(x_i; y_i)$ (4; 117), (5; 125), (14; 112), (18; 138), what are $\sum_iu_i$, $\sum_iv_i$ and the objective value?
$\sum u_i = 23$, $\sum v_i = 12$, value $13.1$
$\sum u_i = 12$, $\sum v_i = 23$, value $21.9$
$\sum u_i = 23$, $\sum v_i = 12$, value $35$
$\sum u_i = 23$, $\sum v_i = 12$, value $21.9$
Explanation. Residuals $y_i - (wx_i + b)$: $3$, $10$, $-12$, $10$; positive parts sum to $23$ (the $u_i$), negative parts to $12$ (the $v_i$). Value $0.9\cdot 23 + 0.1\cdot 12 = 21.9$; swapping the weights of the two sides is the typical mistake.
Example 2 · lpm-g-reg-obiettivo-retta · level facile · notes
Quantile regression LP with one feature: $\min\sum_i[\tau u_i + (1 - \tau)v_i]$ with $wx_i + b + u_i - v_i = y_i$, $u_i, v_i \ge 0$ ($u_i$: observation above the line, $v_i$: below). For the candidate line $w = 4$, $b = 130$ (not necessarily optimal), $\tau = 0.25$ and the observations $(x_i; y_i)$ (4; 139), (9; 170), (13; 183), (19; 195), what are $\sum_iu_i$, $\sum_iv_i$ and the objective value?
$\sum u_i = 5$, $\sum v_i = 18$, value $8.25$
$\sum u_i = 18$, $\sum v_i = 5$, value $14.75$
$\sum u_i = 5$, $\sum v_i = 18$, value $23$
$\sum u_i = 5$, $\sum v_i = 18$, value $14.75$
Explanation. Residuals $y_i - (wx_i + b)$: $-7$, $4$, $1$, $-11$; positive parts sum to $5$ (the $u_i$), negative parts to $18$ (the $v_i$). Value $0.25\cdot 5 + 0.75\cdot 18 = 14.75$; swapping the weights of the two sides is the typical mistake.
Example 1 · lpm-g-reg-scorta · level facile · notes
A bakery forecasts daily demand from temperature $t$ (°C), price $p$ (€) and weekend indicator $e \in \{0, 1\}$ with quantile regression. Median model ($\tau = 0.5$): $274 - 3.5\,t - 26\,p + 32\,e$; model at the critical fractile $\tau = 9/13$ (the newsvendor quantile): $285 - 3.7\,t - 26\,p + 36\,e$. For a day with $t = 23$, $p = 3$, $e = 1$, how much should be produced, and what is the safety stock?
produce $147.5$, safety stock $10.4$
produce $157.9$, safety stock $157.9$
produce $168.3$, safety stock $10.4$
produce $157.9$, safety stock $10.4$
Explanation. One produces the forecast at the critical fractile, $157.9$; the median forecast is $147.5$, and their difference, $10.4$, is the safety stock, obtained with no assumption on the distribution of demand.
Example 2 · lpm-g-reg-scorta · level facile · notes
A bakery forecasts daily demand from temperature $t$ (°C), price $p$ (€) and weekend indicator $e \in \{0, 1\}$ with quantile regression. Median model ($\tau = 0.5$): $266 - 3.9\,t - 25\,p + 30\,e$; model at the critical fractile $\tau = 9/13$ (the newsvendor quantile): $276 - 4.1\,t - 27\,p + 30\,e$. For a day with $t = 13$, $p = 2.5$, $e = 0$, how much should be produced, and what is the safety stock?
produce $152.8$, safety stock $2.4$
produce $155.2$, safety stock $155.2$
produce $155.2$, safety stock $2.4$
produce $157.6$, safety stock $2.4$
Explanation. One produces the forecast at the critical fractile, $155.2$; the median forecast is $152.8$, and their difference, $2.4$, is the safety stock, obtained with no assumption on the distribution of demand.