← Back to the site

Question bank

466 fixed questions · 14 generated questions

Fixed questions (466)

1. Heuristic algorithms: definitions (54)

eh-f-001 · level teorema · notes
For an optimization problem with optimal value $z(I)$, let $\mathscr{A}(I)$ be the value found by a heuristic and $gap(I)$ the relative gap between $\mathscr{A}(I)$ and the best known dual bound. Which statement is correct?
  1. The relative error of $\mathscr{A}$ on $I$ always equals $gap(I)$
  2. The relative error of $\mathscr{A}$ on $I$ is at most $gap(I)$
  3. $gap(I)$ is a lower bound on the performance ratio of $\mathscr{A}$
  4. The relative error of $\mathscr{A}$ on $I$ is at least $gap(I)$
Explanation. The gap is measured against a dual bound, which is not better than $z(I)$: it is never smaller than the relative error, and it coincides with it only when the dual bound equals $z(I)$.
eh-f-002 · level ipotesi · notes
For a minimization problem with positive values, let $\mathscr{A}(I)$ be the value of a heuristic, $z(I)$ the optimal value and $\mathrm{LB}(I)$ a bound. Which facts are needed to prove that the relative error $\frac{\mathscr{A}(I)-z(I)}{z(I)}$ does not exceed $gap(I)=\frac{\mathscr{A}(I)-\mathrm{LB}(I)}{\mathrm{LB}(I)}$?
  1. $\mathrm{LB}(I)\le z(I)$, hence $\frac{\mathscr{A}(I)}{z(I)}\le\frac{\mathscr{A}(I)}{\mathrm{LB}(I)}$
  2. $z(I)\le\mathrm{LB}(I)$, hence $\frac{\mathscr{A}(I)}{\mathrm{LB}(I)}\le\frac{\mathscr{A}(I)}{z(I)}$
  3. $\mathscr{A}(I)\le 2\,z(I)$, because $\mathscr{A}$ is a $2$-approximation
  4. $\mathscr{A}(I)=z(I)$, because the neighborhood used by $\mathscr{A}$ is exact
Explanation. It is enough that $\mathrm{LB}(I)$ is a dual bound: dividing $\mathscr{A}(I)$ by a smaller number gives a larger ratio, and $1$ is subtracted from both sides.
eh-f-003 · level facile · notes
A heuristic for a maximization problem finds $\mathscr{A}(I)=16$ and the dual bound $\mathrm{UB}(I)=17$ is known. The relative gap is the difference between the two bounds divided by the lower bound. What is its value?
  1. $5.88\%$
  2. $1$
  3. $94.1\%$
  4. $6.25\%$
Explanation. The gap always divides by the lower bound, here the heuristic value: $\frac{\mathrm{UB}(I)-\mathscr{A}(I)}{\mathscr{A}(I)}=\frac{1}{16}=6.25\%$. Dividing by $17$ is the typical mistake on the denominator.
eh-f-004 · level facile · notes
In local search, a neighborhood $N$ maps every feasible solution $S$ to a set $N(S)$ of neighboring solutions. When is the neighborhood $N$ called exact?
  1. When every solution in $N(S)$ has a better value than $S$
  2. When every global optimum is a local optimum with respect to $N$
  3. When every local optimum with respect to $N$ is a global optimum
  4. When local search with $N$ stops after a finite number of moves
Explanation. A neighbourhood is exact if it has no local optima that are not global; the small neighbourhoods used in practice usually are not.
eh-f-005 · level facile · notes
A heuristic algorithm $\mathscr{A}$ computes, for every instance $I$, a feasible solution of value $\mathscr{A}(I)$, without guaranteeing that it is optimal ($z(I)$ = optimal value). For a maximization problem, which relation always holds?
  1. $\mathscr{A}(I)\ge z(I)/2$
  2. $\mathscr{A}(I)\le z(I)$
  3. $\mathscr{A}(I)\ge z(I)$
  4. $\mathscr{A}(I)=z(I)$ on small instances
Explanation. A feasible solution cannot exceed the maximum. $\mathscr{A}(I)\ge z(I)$ holds for minimization problems; a factor $\frac12$ would be an approximation guarantee, which a generic heuristic does not have.
eh-f-006 · level facile · notes
Approximation algorithms are a special case of heuristic algorithms. What do they have in addition to most heuristics used in practice?
  1. A proven guarantee on the ratio between $\mathscr{A}(I)$ and $z(I)$
  2. The optimal solution on all small instances
  3. The use of random choices to escape local optima
  4. A running time polynomial in the size of the instance
Explanation. A generic heuristic is usually polynomial too; the difference is the guarantee on the ratio, valid for all instances. The quality of the other heuristics is assessed on the instances to be solved.
eh-f-007 · level facile · notes
Instance of $P\,||\,C_{\max}$ (jobs on $m$ identical machines, minimize the makespan, i.e. the maximum load): $m=3$ and times $t=(5,5,4,4,3,3,3)$. Which lower bound on the makespan follows, and which solution attains it?
  1. $10$, attained by $\{1,5,6\},\{2,3\},\{4,7\}$
  2. $5=\max_jt_j$, attained by $\{1,5\},\{2,6\},\{3,4,7\}$
  3. $9=\lceil27/3\rceil$, attained by $\{1,2\},\{3,4\},\{5,6,7\}$
  4. $9=\lceil27/3\rceil$, attained by $\{1,3\},\{2,4\},\{5,6,7\}$
Explanation. The lower bound is $\max\{\max_jt_j,\lceil\sum_jt_j/m\rceil\}=\max\{5,9\}=9$, and the loads $(9,9,9)$ attain it: $z(I)=9$. $\{1,2\}$ has load $10$.
eh-f-008 · level facile · notes
The notes on heuristic algorithms use four reference instances (knapsack, bin packing, TSP, $P\,||\,C_{\max}$) whose optimal value $z(I)$ is known. What is knowing it good for?
  1. To replace the dual bound in computing the gap
  2. To choose the hardest instances for every heuristic
  3. To measure exactly the error of every heuristic solution
  4. To make the heuristics exact on those instances
Explanation. With $z(I)$ known one computes the relative error, not only the gap. In practice $z(I)$ is unknown and a dual bound is needed.
eh-f-009 · level facile · notes
Heuristic algorithms are classified into constructive heuristics, local search, metaheuristics and ILP-based heuristics. What characterizes a constructive heuristic?
  1. It accepts worse solutions to leave a local optimum
  2. It extends a partial solution and never revises a choice
  3. It starts from a complete solution and improves it by small changes
  4. It uses a MIP solver to explore large sets of solutions
Explanation. The other three options describe, in order, local search, ILP-based heuristics and metaheuristics.
eh-f-010 · level facile · notes
What do the heuristics based on integer linear programming (ILP), one of the four classes of heuristic algorithms, use?
  1. A MIP formulation, its relaxation and a MIP solver
  2. A population of solutions that recombine
  3. Only elementary moves on a complete solution
  4. Only an ordering of the elements by a criterion
Explanation. They use the model to guide the search or to explore large sets of solutions, and can start from the solution of another heuristic.
eh-f-011 · level facile · notes
For the four problems of the notes on heuristics, solutions are represented by: a binary vector $x$ (knapsack), a vector $bin$ (bin packing), a permutation $\sigma$ (TSP), a vector $mach$ ($P\,||\,C_{\max}$). Which representations always describe feasible solutions?
  1. All four representations
  2. The knapsack vector $x$ and the bin packing vector $bin$
  3. Only the knapsack vector $x$
  4. The TSP permutation and the vector $mach$
Explanation. Every permutation is a tour and every assignment of the jobs is a schedule. A vector $x$ can exceed the capacity and a vector $bin$ can overfill a bin.
eh-f-012 · level facile · notes
In bin packing with $n$ items a solution is represented by the vector $bin$, where $bin_j$ is the bin of item $j$. How large is the search space at most, and is every vector a feasible solution?
  1. $n!$; yes, every vector is feasible
  2. At most $n^n$; yes, every vector is a feasible partition
  3. At most $n^n$; no, a bin can exceed the capacity
  4. $2^n$; yes, every vector is feasible
Explanation. Every item has at most $n$ possible bins: $n^n$ vectors. A vector is always a partition, but does not always respect the capacity.
eh-f-013 · level facile · notes
Knapsack with $c=9$, profits $p=(10,7,6,4)$, weights $w=(5,4,3,3)$ and solution $x=(1,0,1,0)$ (items $1,3$, profit $16$). The flip neighborhood adds or removes an item; the swap neighborhood removes a chosen item and adds an unchosen one. Is $x$ a local optimum?
  1. No for both neighborhoods
  2. Yes for flip, no for swap
  3. No for flip, yes for swap
  4. Yes for both neighborhoods
Explanation. Flip: adding $2$ or $4$ exceeds $9$, removing an item worsens. Swap: removing $3$ and adding $2$ gives weight $9$ and profit $17$. Being a local optimum depends on the neighborhood.
eh-f-014 · level facile · notes
A neighborhood is exact if every local optimum of it is a global optimum. Which of the following neighborhoods is exact?
  1. Edge in and edge out, for the minimum spanning tree
  2. The flip (adding or removing an item), for the knapsack
  3. Moving one item, for bin packing
  4. The $2$-opt (replacing two edges), for the TSP
Explanation. Exact neighborhoods exist for polynomial problems (minimum spanning tree, adjacent vertices of the simplex). For NP-hard problems small neighborhoods are not exact.
eh-f-015 · level facile · notes
The solution values, seen as a function on the search space, form the landscape explored by a heuristic. For a minimization problem, what are the local optima and the global optimum?
  1. The borders of the search space; the global one is the farthest
  2. The peaks of the hills; the global one is the highest peak
  3. The passes between two valleys; the global one is the lowest
  4. The valley bottoms; the global one is the bottom of the deepest valley
Explanation. For a minimum a local optimum has no better, i.e. lower, neighbors: it is a valley bottom.
eh-f-016 · level facile · notes
Between intensification (searching better where good solutions already are) and diversification (moving to regions not yet explored), where does pure local search stand?
  1. It balances the two thanks to worsening moves
  2. It does neither: it chooses at random
  3. Pure intensification: it stops at the first local optimum
  4. It is pure diversification: it explores all valleys
Explanation. Local search goes down the current valley as long as a neighbor improves; leaving the valley is the task of metaheuristics.
eh-f-017 · level facile · notes
A heuristic algorithm can be evaluated by worst-case analysis or by experimental analysis. What does experimental analysis give?
  1. A better dual bound for computing the gap
  2. The typical behavior on benchmark instances
  3. A guarantee valid for all instances of the problem
  4. The optimal value of every benchmark instance
Explanation. It measures gaps and times on a sufficiently large and varied set of instances. The worst case gives guarantees for all instances, often far from typical behavior.
eh-f-018 · level facile · notes
According to the notes on heuristic algorithms, when can a heuristic algorithm be called good?
  1. If it often finds, in the available time, solutions with a small gap
  2. If it finds the optimal solution on at least one instance
  3. If it is the fastest among the available algorithms
  4. If it has a worst-case performance guarantee
Explanation. What matters is the behavior on the instances it is meant for: quality and time together, on many instances and, if randomized, on several seeds.
eh-f-019 · level facile · notes
For an optimization problem with optimal value $z(I)$ on instance $I$, what distinguishes a heuristic algorithm from an exact one?
  1. It may return infeasible solutions, as long as their value is good
  2. It always returns an optimal solution, but without proving it
  3. It returns a dual bound instead of a solution
  4. It returns a feasible solution, usually quickly, without guaranteeing that it is optimal
Explanation. A heuristic trades quality for time: it quickly computes a feasible solution whose value is hopefully close to $z(I)$, but in general it does not know how far it is.
eh-f-020 · level facile · notes
Why are heuristic algorithms used for NP-hard problems such as knapsack, bin packing, the TSP and $P\,||\,C_{\max}$, even though exact algorithms exist?
  1. Because heuristics always find the optimum on large instances
  2. Because heuristics also give a dual bound for free
  3. Exact algorithms may take exponential time, while a good solution is often needed quickly
  4. Because exact algorithms do not exist for these problems
Explanation. For NP-hard problems no polynomial exact algorithm is known; a heuristic quickly gives a feasible solution, i.e., a primal bound, to be used alone or as a starting point.
eh-f-021 · level facile · notes
In the notes on heuristics, every knapsack instance (KP: weights $w_j$, capacity $c$) satisfies $w_j\le c$ for every item and $\sum_j w_j>c$. Why is the case $\sum_j w_j\le c$ excluded?
  1. Because the split item would be the first one
  2. It is trivial: all items fit, and taking them all is optimal
  3. Because the instance has no feasible solution
  4. Because the LP relaxation would become unbounded
Explanation. If all items fit together, with positive profits the optimal solution takes them all, and no heuristic is needed. $w_j\le c$ instead excludes items that never fit.
eh-f-022 · level facile · notes
In the notes on heuristics, every $P\,||\,C_{\max}$ instance ($n$ jobs, $m$ identical machines) satisfies $n>m$. What would happen with $n\le m$?
  1. One job per machine would be optimal, with makespan $\max_j t_j$
  2. The optimal makespan would be $\sum_j t_j/m$
  3. Dynamic programming would be needed to solve it
  4. The problem would have no feasible solution
Explanation. With at least as many machines as jobs, every job goes on a different machine and the makespan is the longest job, which is also a lower bound: the instance is trivial.
eh-f-023 · level facile · notes
For a minimization problem, a heuristic finds a solution of value $\mathscr{A}(I)=25$ and a dual bound is $\mathrm{LB}(I)=20$, so $20\le z(I)\le 25$. The relative gap is $\frac{\mathscr{A}(I)-\mathrm{LB}(I)}{\mathrm{LB}(I)}$. What is it, and what does it guarantee?
  1. $5$: the solution is exactly $5$ away from the optimum
  2. $20\%$: the relative error of the solution is exactly $20\%$
  3. $25\%$: the relative error of the solution is at least $25\%$
  4. $25\%$: the relative error of the solution is at most $25\%$
Explanation. $(25-20)/20=25\%$. Since $\mathrm{LB}(I)\le z(I)$, the relative error $\frac{\mathscr{A}(I)-z(I)}{z(I)}$ does not exceed the gap; the optimal value stays unknown between $20$ and $25$.
eh-f-024 · level facile · notes
Heuristic algorithms are divided into four classes: constructive heuristics, local search, metaheuristics and heuristics based on integer linear programming (MIP). Which statement about the classes is correct?
  1. Constructive heuristics improve a complete solution, local search builds it
  2. MIP heuristics never use solutions found by other heuristics
  3. They are not alternatives: a local search usually starts from a constructive solution, and a metaheuristic contains local searches
  4. They are alternatives: an algorithm belongs to one class and uses none of the others
Explanation. The classes combine: build, improve with a local search, escape local optima with a metaheuristic; a MIP heuristic may start from a known solution and improve it.
eh-f-025 · level facile · notes
To which class of heuristic algorithms does a method belong that, starting from a complete solution, repeatedly replaces it with a better neighbouring solution as long as one exists?
  1. Heuristic based on integer linear programming
  2. Local search
  3. Constructive heuristic
  4. Metaheuristic
Explanation. A local search improves a complete solution with moves in a neighbourhood and stops at a local optimum; a constructive heuristic starts from the empty solution instead, and a metaheuristic also accepts worsening moves to escape local optima.
eh-f-026 · level facile · notes
For the 0-1 knapsack with $n$ items a solution is represented by a binary vector of length $n$. The search space also contains vectors exceeding the capacity. What must a heuristic do with these objects?
  1. Restrict itself to feasible vectors, or accept infeasible ones and penalize them
  2. Return them as a solution, if their profit is larger
  3. Make them feasible by increasing the capacity
  4. Ignore them: an infeasible vector can never be generated
Explanation. When the representation also describes infeasible objects, the heuristic either avoids them or accepts them with a penalty in the objective, for example on the excess weight.
eh-f-027 · level facile · notes
For $P\,||\,C_{\max}$ a solution is represented by the vector giving the machine of every job. How many vectors does the search space contain with $n=6$ jobs and $m=3$ machines?
  1. $18$
  2. $216$
  3. $90$
  4. $729$
Explanation. Every job chooses one of the $3$ machines: $3^6=729$. Many vectors describe the same schedule, since machines are identical; $6^3=216$ swaps the roles of $n$ and $m$.
eh-f-028 · level facile · notes
In a minimization problem with objective function $f$, a solution $S$ is a local optimum with respect to the neighbourhood $N$ if $f(S)\le f(S')$ for every $S'\in N(S)$. Which statement is correct?
  1. A global optimum may fail to be a local optimum, if the neighbourhood is large
  2. A local optimum does not exist if the neighbourhood is not exact
  3. A global optimum is a local optimum for every neighbourhood; a local optimum may not be global
  4. A local optimum is a global optimum for every neighbourhood
Explanation. No solution is better than a global optimum, so neither are its neighbours. The converse holds only for exact neighbourhoods.
eh-f-029 · level facile · notes
In heuristics one speaks of intensification and diversification of the exploration of the search space. What do they mean?
  1. They are synonyms: both mean using random numbers
  2. Intensifying is searching better near the good solutions found; diversifying is moving to unexplored regions
  3. Intensifying is increasing the number of iterations; diversifying is using more processors
  4. Intensifying is accepting worsening moves; diversifying is accepting only improving moves
Explanation. Intensification goes down to the bottom of the current valley; diversification leaves it, possibly through worse solutions, to reach another one.
eh-f-030 · level facile · notes
What happens to a heuristic with too much intensification, and to one with too much diversification?
  1. The first is trapped in the first valley; the second wanders without fully exploring any valley
  2. Both find the global optimum, but the first faster
  3. The first becomes an exact algorithm; the second an optimal random search
  4. The first wanders aimlessly; the second is trapped in the first valley
Explanation. Local search is pure intensification and stops at the first local optimum; every metaheuristic is a way of balancing the two tendencies.
eh-f-031 · level facile · notes
How is a heuristic that makes random choices (for example with a pseudo-random number generator) evaluated correctly?
  1. It cannot be evaluated: random results are not comparable
  2. It is run once, with the seed giving the best result
  3. Its best result is compared with the worst result of the other heuristics
  4. Every instance is solved several times with different seeds, and the mean and spread of the results are reported
Explanation. The results depend on the random numbers: a single seed says nothing. Heuristics are compared on the same instances and with the same running time.
eh-f-032 · level facile · notes
On a TSP instance, the same constructive rule applied from different starting cities gives tours of length between $18$ and $25$. What does this teach about the evaluation of heuristics?
  1. It is enough to report the best value, $18$, as the quality of the heuristic
  2. The optimal length is the average, $21.5$
  3. A single instance or run proves nothing: many instances and comparisons at equal time are needed
  4. The rule is wrong, because a heuristic must always give the same value
Explanation. The result of a heuristic varies with the instances and with the initial choices; experimental analysis measures gaps and times on many instances, worst-case analysis gives guarantees valid always.
eh-f-033 · level teorema · notes
For the TSP, let $a_i$ and $b_i$ be the two smallest distances from city $i$ to the others. The bound $z(I)\ge\lceil\frac12\sum_i(a_i+b_i)\rceil$ is proved as follows: in every tour every city is the endpoint of two edges at least $a_i$ and $b_i$ long. Why does the factor $\frac12$ appear?
  1. To account for asymmetric distances
  2. Summing over the cities every edge of the tour is counted twice, once per endpoint
  3. Because only one of the two smallest distances is used
  4. Because the tour has $n/2$ edges
Explanation. $2L(\sigma)=\sum_i$(lengths of the two edges at $i$)$\ge\sum_i(a_i+b_i)$; rounding up is valid because the distances are integer.
eh-f-034 · level facile · notes
A TSP instance with $4$ cities has distances $d_{12}=2$, $d_{13}=4$, $d_{14}=3$, $d_{23}=3$, $d_{24}=5$, $d_{34}=2$. With $a_i,b_i$ the two smallest distances from city $i$, what is the bound $\lceil\frac12\sum_i(a_i+b_i)\rceil$?
  1. $10$
  2. $19$
  3. $11$
  4. $9$
Explanation. City $1$: $2+3$; city $2$: $2+3$; city $3$: $2+3$; city $4$: $2+3$. Sum $20$, half $10$. The tour $1,2,3,4$ is worth $2+3+2+3=10$, so the bound is exact here.
eh-f-370 · level teorema · notes
A neighbourhood $N$ is exact: every local optimum with respect to $N$ is a global optimum. A local search with neighbourhood $N$ stops at the solution $S$. What can be concluded?
  1. $S$ is an optimal solution
  2. $S$ is optimal only with best improvement
  3. $S$ has zero gap only with a dual bound
  4. Nothing: exactness concerns the size of $N$
Explanation. The local search stops at a local optimum with respect to $N$ and, by definition of exact neighbourhood, every local optimum is global. The rule used to choose the neighbour does not matter.
eh-f-371 · level teorema · notes
Minimization problem with positive values: a heuristic finds $\mathscr{A}(I)=12$ and a dual bound is $\mathrm{LB}(I)=10$. What does the proposition on the gap guarantee for the relative error $\frac{\mathscr{A}(I)-z(I)}{z(I)}$?
  1. It is at most $16.7\%$
  2. It is exactly $20\%$
  3. It is at least $20\%$
  4. It is at most $20\%$
Explanation. $gap(I)=\frac{12-10}{10}=20\%$ and the relative error is at most the gap, since $10\le z(I)\le 12$. $16.7\%$ divides by the larger bound; the error is $20\%$ only if $z(I)=10$.
eh-f-372 · level teorema · notes
TSP with $5$ cities and integer distances: the sums $a_i+b_i$ of the two smallest distances from each city are $6,7,7,8,9$. What does the two-smallest-distances bound give?
  1. $z(I)\ge 18$
  2. $z(I)\le 19$
  3. $z(I)\ge 19$
  4. $z(I)\ge 37$
Explanation. $z(I)\ge\lceil\frac12(6+7+7+8+9)\rceil=\lceil 18.5\rceil=19$: every city has two tour edges, and every edge is counted by two cities. It is a lower bound, not an upper bound.
eh-f-373 · level teorema · notes
Which statement holds for every neighbourhood $N$ of an optimization problem?
  1. A local optimum for $N$ has no neighbours
  2. Every optimal solution is a local optimum for $N$
  3. Every local optimum for $N$ is an optimal solution
  4. Two local optima for $N$ have the same value
Explanation. No solution is better than a global optimum, hence neither are its neighbours: it is a local optimum for every neighbourhood. The converse holds only for exact neighbourhoods.
eh-f-374 · level teorema · notes
Maximization problem: a heuristic finds $\mathscr{A}(I)=40$ and a dual bound is $\mathrm{UB}(I)=50$. What is the gap, and what does it guarantee?
  1. $25\%$: the relative error of $40$ is at most $25\%$
  2. $20\%$: the relative error is at least $20\%$
  3. $25\%$: hence $z(I)=50$
  4. $20\%$: the gap is divided by $\mathrm{UB}(I)$
Explanation. The gap divides by the smaller bound, here the heuristic value: $\frac{50-40}{40}=25\%$, and the relative error is at most the gap. The optimal value lies between $40$ and $50$, it is not necessarily $50$.
eh-f-375 · level ipotesi · notes
The proposition «the relative error of $\mathscr{A}$ on $I$ is at most $gap(I)$», with $gap(I)=\frac{\mathrm{UB}-\mathrm{LB}}{\mathrm{LB}}$, which assumption on the values does it need?
  1. The heuristic is a local search with an exact neighbourhood
  2. The problem is a maximization problem
  3. All the data of the instance are integers
  4. The smaller bound $\mathrm{LB}(I)$ is positive
Explanation. The gap divides by the smaller bound: $\mathrm{LB}(I)>0$ is needed (positive values). It holds for every heuristic, for minimization and maximization problems, with any data.
eh-f-376 · level ipotesi · notes
In the TSP bound $z(I)\ge\lceil\frac12\sum_i(a_i+b_i)\rceil$, why can the value be rounded up?
  1. The number of cities is even
  2. The tour always starts at city $1$
  3. The distances are integers, and so is $z(I)$
  4. The distances satisfy the triangle inequality
Explanation. With integer distances every tour has integer length, and an integer not smaller than $18.5$ is at least $19$. The triangle inequality is not needed, and the starting city does not matter.
eh-f-377 · level ipotesi · notes
What does the definition of heuristic algorithm for an optimization problem $\mathscr{P}$ require?
  1. A running time linear in the input size
  2. A feasible solution for every instance
  3. An optimal solution at least on small instances
  4. A guarantee on the ratio with the optimum
Explanation. A heuristic computes a feasible solution of every instance, without guaranteeing that it is optimal. A worst-case guarantee is typical of approximation algorithms.
eh-f-378 · level ipotesi · notes
A neighbourhood associates with every feasible solution $S$ a set $N(S)$ of neighbours. What is required of the neighbours?
  1. They are feasible solutions
  2. They are better than $S$
  3. They differ from $S$ in one variable
  4. They are local optima
Explanation. $N(S)\subseteq\mathscr{F}(I)$: the neighbours are feasible solutions. They need not be better, and the move that produces them depends on the chosen neighbourhood.
eh-f-379 · level ipotesi · notes
Maximization problem with objective function $f$. When is $S$ a local optimum with respect to the neighbourhood $N$?
  1. If $f(S)>f(S')$ for all $S'\in N(S)$
  2. If $f(S)\ge f(S')$ for some $S'\in N(S)$
  3. If $f(S)\le f(S')$ for all $S'\in N(S)$
  4. If $f(S)\ge f(S')$ for all $S'\in N(S)$
Explanation. No neighbour is better: $f(S)\ge f(S')$ for all neighbours. The inequality need not be strict (neighbours of equal value are allowed); $\le$ is the condition for minimization problems.
eh-f-380 · level ipotesi · notes
Minimization problem: the heuristic value $\mathscr{A}(I)$ equals a dual bound $\mathrm{LB}(I)$. What can be concluded, and on what is it based?
  1. Nothing: the gap is zero but the error is not
  2. $\mathscr{A}(I)=z(I)$ only with integer data
  3. $\mathscr{A}(I)$ is optimal, since $\mathrm{LB}(I)\le z(I)$
  4. $\mathscr{A}(I)$ is optimal only if the heuristic is exact
Explanation. $\mathrm{LB}(I)\le z(I)\le\mathscr{A}(I)=\mathrm{LB}(I)$: the solution is optimal, certified by the dual bound. No other assumption on the heuristic or on the data is needed.
eh-f-416 · level ipotesi · notes
For a problem with finitely many feasible solutions, which neighbourhood is exact whatever the instance?
  1. The 2-opt neighbourhood of the TSP
  2. The move neighbourhood of $P\,||\,C_{\max}$
  3. The one where every solution neighbours all others
  4. The flip neighbourhood of the 0/1 knapsack
Explanation. With $N(S)=\mathscr{F}(I)$ a local optimum has no better solution: it is global. Flip, 2-opt and move have local optima that are not global (examples of this chapter and of local search).
eh-f-417 · level teorema · notes
TSP: a tour of length $25$, a dual bound $\mathrm{LB}(I)=17$ and the optimal value $z(I)=18$. What are the gap and the relative error $\frac{\mathscr{A}(I)-z(I)}{z(I)}$?
  1. Gap and error both $\approx47.1\%$
  2. Gap $\approx47.1\%$, error $\approx38.9\%$
  3. Gap $\approx32\%$, error $\approx28\%$
  4. Gap $\approx38.9\%$, error $\approx47.1\%$
Explanation. $gap=\frac{25-17}{17}\approx47.1\%$ and error $=\frac{25-18}{18}\approx38.9\%$: the error is at most the gap. $32\%$ and $28\%$ divide by $25$, the larger value.
eh-f-427 · level facile · notes
Which class of heuristics builds a single solution, one element at a time, never revising a choice?
  1. Local search from a solution
  2. Metaheuristics, from a local optimum
  3. MIP-based heuristics
  4. Constructive heuristics
Explanation. It is the definition of constructive heuristics. Local search modifies a complete solution, metaheuristics guide local search, MIP heuristics use a model and a solver.
eh-f-428 · level facile · notes
What is the search space of a heuristic?
  1. The set of neighbours of a solution
  2. The running time allowed to the heuristic
  3. The objects the representation describes
  4. The set of the optimal solutions
Explanation. The representation is the data structure of the solutions; the search space is the set of all the objects it can describe, which may also contain infeasible objects.
eh-f-429 · level facile · notes
The 0/1 knapsack with $n$ items is represented by a binary vector $\vet x\in\{0,1\}^n$. How many objects does the search space contain?
  1. $\binom{n}{2}$
  2. $2^n$
  3. $n!$
  4. $n^2$
Explanation. Each item is in or out: $2^n$ vectors, feasible or not. $n!$ counts the permutations, the natural representation of the TSP.
eh-f-430 · level facile · notes
What is meant by intensification in a heuristic algorithm?
  1. Searching near the good solutions found
  2. Moving to regions of the space not explored yet
  3. Computing a stronger dual bound
  4. Increasing the number of test instances
Explanation. Intensifying is moving down toward the bottom of the current valley; diversification leads to new regions. Local search is pure intensification.
eh-f-431 · level facile · notes
A heuristic diversifies too much and intensifies too little. What happens?
  1. It stays trapped in the first valley
  2. It always finds the global optimum
  3. It stops at once at a local optimum
  4. It wanders, never reaching a valley bottom
Explanation. Too much diversification makes the search wander without ever reaching the bottom of a valley; too much intensification traps it in the first one. Every metaheuristic balances the two.
eh-f-432 · level facile · notes
How is the quality of a heuristic measured on an instance whose optimal value is unknown?
  1. By the number of iterations performed
  2. By the running time alone
  3. By the gap with respect to the best dual bound
  4. By the relative error with respect to the optimum
Explanation. Without the optimal value the relative error cannot be computed: the gap with respect to the best available dual bound is used, which is an upper bound on the error.
eh-f-433 · level facile · notes
Why must the experimental analysis of a heuristic use a large and varied set of instances?
  1. To obtain a worst-case guarantee
  2. To avoid conclusions that hold only on a few instances
  3. Because on small instances it does not terminate
  4. Because the gap is defined only on many instances
Explanation. A heuristic may behave well on some instances and badly on others: few instances give conclusions that are not general. Worst-case guarantees come from theoretical analysis, not from experiments.

2. Constructive heuristics (104)

eh-f-035 · level teorema · notes
In scheduling $P\,||\,C_{\max}$ ($m$ identical machines, optimal makespan $z(I)$), $LIST$ assigns the jobs in the order of a list to the least loaded machine, and $LPT$ does the same with the list sorted by non-increasing duration. Which guarantees hold?
  1. $LIST(I)\le\left(2-\frac1m\right)z(I)$ and $LPT(I)\le\left(\frac43-\frac1{3m}\right)z(I)$
  2. $LIST(I)\le\left(2-\frac1m\right)z(I)$ and $LPT(I)\le\left(\frac54-\frac1{4m}\right)z(I)$
  3. $LIST(I)\le\frac32\,z(I)$ and $LPT(I)\le\frac{17}{10}\,z(I)$
  4. $LIST(I)\le\left(\frac43-\frac1{3m}\right)z(I)$ and $LPT(I)\le\left(2-\frac1m\right)z(I)$
Explanation. Graham: any list guarantees $2-\frac1m$; sorting it by non-increasing time lowers the guarantee to $\frac43-\frac1{3m}$.
eh-f-036 · level teorema · notes
The greedy coloring $GC$ scans the vertices of $G$ in the order of a list and gives each the smallest color not used by its already colored neighbors; $\Delta(G)$ is the maximum degree and $\chi(G)$ the chromatic number. Which statement is correct?
  1. $GC(I)\le\Delta(G)+1$ for every list, and on bipartite graphs it always gives $2$ colors
  2. $GC(I)\le\Delta(G)$ for every connected graph and every vertex list
  3. $GC(I)\le\chi(G)+1$ for every list, hence $GC$ is off by at most one color
  4. $GC(I)\le\Delta(G)+1$ for every list, but on bipartite graphs a list can give $n/2$ colors
Explanation. A vertex has at most $\Delta(G)$ already colored neighbours, so it finds a color among the first $\Delta(G)+1$. The crown graphs have $\chi=2$ but, with an unfavourable list, $GC=n/2$.
eh-f-037 · level facile · notes
In bin packing, First Fit (FF) puts every item, in the given order, into the first bin where it fits; First Fit Decreasing (FFD) does the same after sorting the items by non-increasing weight. Which statement is correct?
  1. FFD always uses the optimal number of bins
  2. FF and FFD always use the same number of bins
  3. There are instances on which FFD uses more bins than FF
  4. FFD always uses at most as many bins as FF
Explanation. Sorting the items helps on average and in the worst case, but not instance by instance: the notes show an instance on which FFD uses one bin more than FF.
eh-f-038 · level facile · notes
In an insertion heuristic for the symmetric TSP (distances $d_{ij}$), the current subtour contains the edge $(i,j)$ with $d_{ij}=7$; city $k$ has $d_{ik}=4$ and $d_{kj}=5$. By how much does the subtour length increase if $k$ is inserted between $i$ and $j$?
  1. $-2$
  2. $2$
  3. $9$
  4. $16$
Explanation. $\Delta(i,k,j)=d_{ik}+d_{kj}-d_{ij}=4+5-7=2$: the edge $(i,j)$ is replaced by the edges $(i,k)$ and $(k,j)$.
eh-f-039 · level facile · notes
For the knapsack problem (KP), the greedy scans the items in some order and takes every item that fits: by non-increasing profit ($GR_p$), by non-decreasing weight ($GR_w$) or by non-increasing efficiency $p_j/w_j$ ($GR$). Which statement is correct?
  1. Each of the three orders can give arbitrarily bad solutions
  2. $GR$ by efficiency always gives the optimal value
  3. $GR_w$ always gives the optimal value, because it picks more items
  4. $GR_p$ always gives at least half the optimal value
Explanation. For each order there is a family of instances on which the ratio to the optimum grows without bound (for $GR$: a tiny very efficient item blocking a large one); constant guarantees require algorithms such as $GR^e$.
eh-f-040 · level facile · notes
A constructive heuristic starts from the empty partial solution and extends it one element at a time. For $P\,||\,C_{\max}$ ($n$ jobs on $m$ identical machines), what are the elements?
  1. The loads of the machines, one at a time
  2. The swaps of two jobs between two machines
  3. The machines, opened one at a time
  4. The assignments of a job to a machine
Explanation. Every step assigns a job to a machine. Swaps are local search moves, which modify a complete solution.
eh-f-041 · level facile · notes
What does the quality of the solution of a constructive heuristic (which extends the empty partial solution one element at a time) mainly depend on?
  1. On the complete solution the search starts from
  2. On the number of improvement iterations performed
  3. On how the element to add is chosen at every step
  4. On the dual bound used as stopping criterion
Explanation. It always starts from the empty solution and stops when the solution is complete: everything lies in the choice criterion.
eh-f-042 · level facile · notes
When does a constructive heuristic, which starts from the empty partial solution and adds one element at a time, stop?
  1. When the gap to the dual bound is zero
  2. When the solution is complete
  3. When no small change improves it
  4. After a fixed number of iterations
Explanation. It does not examine changes of complete solutions (that is local search) and does not know the gap.
eh-f-043 · level facile · notes
In $P\,||\,C_{\max}$, $mach_j$ is the machine of job $j$ and $L_h$ the load (sum of times) of machine $h$. With $m=3$, times $t=(5,5,4,4,3,3,3)$ and $mach=(1,2,3,3,1,2,1)$, what are the loads and the makespan?
  1. $(11,8,8)$, makespan $11$
  2. $(11,8,8)$, makespan $8$
  3. $(9,9,9)$, makespan $9$
  4. $(13,8,6)$, makespan $13$
Explanation. Machine $1$: jobs $1,5,7$, $5+3+3=11$; machine $2$: jobs $2,6$, $8$; machine $3$: jobs $3,4$, $8$. The makespan is the maximum load, not the minimum.
eh-f-044 · level facile · notes
Bin packing with $c=7$ and weights $w=(4,4,5,3,2,3)$. A solution has $bin=(2,3,1,2,1,3)$ ($bin_j$ = bin of item $j$). What are the residual capacities of bins $1,2,3$?
  1. $(0,1,2)$: only one bin is full
  2. $(7,7,7)$: the bins are empty
  3. $(2,3,3)$: space is left in all bins
  4. $(0,0,0)$: three full bins, optimal solution
Explanation. Bin $1$: items $3,5$, $5+2=7$; bin $2$: items $1,4$, $7$; bin $3$: items $2,6$, $7$. The total weight is $21=3c$, hence $3$ bins are optimal.
eh-f-045 · level facile · notes
In constructive heuristics, the feasibility test checks whether the extended partial solution can still be completed. For which of the problems knapsack, bin packing, TSP and $P\,||\,C_{\max}$ is this test always passed?
  1. The knapsack and bin packing
  2. Only the TSP, not the others
  3. TSP and $P\,||\,C_{\max}$
  4. None of the four problems
Explanation. Every sequence of cities closes into a tour and every assignment of jobs is a schedule. In the knapsack an item may not fit, in bin packing an item may not fit into a bin.
eh-f-046 · level facile · notes
In a greedy algorithm a selection criterion is static if the value of an element does not depend on the partial solution, dynamic if it changes as the solution grows. Which criterion is dynamic?
  1. The processing time of the $P\,||\,C_{\max}$ jobs
  2. The distance from the last city of a partial tour
  3. The efficiency $p_j/w_j$ of the knapsack items
  4. The weight of the bin packing items
Explanation. The last city changes at every step, so the distances must be recomputed. The other criteria allow sorting the elements once, in $O(n\log n)$.
eh-f-047 · level facile · notes
Knapsack with $c=9$, $p=(10,7,6,4)$, $w=(5,4,3,3)$ (optimum $17$). Greedy takes every item that fits, scanning them by profit ($GR_p=17$), by weight ($GR_w=10$) or by efficiency $p_j/w_j$ ($GR=16$). What does the example show?
  1. Here profit wins, but no order is the best on every instance
  2. The order by efficiency is the best on every instance
  3. The order by weight always finds the optimum
  4. The greedy by profit is an exact algorithm for the knapsack
Explanation. On this instance $GR_p$ fills the knapsack exactly with $\{1,2\}$; but each of the three orders can be arbitrarily bad on other instances.
eh-f-048 · level facile · notes
Knapsack with $c=10$ and two items $(p_1,w_1)=(2,1)$, $(p_2,w_2)=(10,10)$. Greedy takes every item that fits, scanning them by non-increasing profit ($GR_p$), non-decreasing weight ($GR_w$) or non-increasing efficiency $p_j/w_j$ ($GR$). What are their values?
  1. $GR_p=2$, $GR_w=2$, $GR=2$
  2. $GR_p=10$, $GR_w=10$, $GR=2$
  3. $GR_p=10$, $GR_w=2$, $GR=10$
  4. $GR_p=10$, $GR_w=2$, $GR=2$
Explanation. Item $1$ has efficiency $2$ and weight $1$: $GR_w$ and $GR$ take it first, and then item $2$ does not fit. $GR_p$ takes item $2$, which is optimal. With large $c$ the ratio $z/GR=c/2$ grows without bound.
eh-f-049 · level facile · notes
In bin packing with capacity $c$, the «sort first, then fill» heuristics insert the heaviest items first. Why?
  1. Because large items are worth more in the objective function
  2. Because with sorting First Fit becomes an exact algorithm
  3. Large items fit only into nearly empty bins; small ones fill the gaps
  4. Because small items, if they arrive late, no longer fit
Explanation. Two items larger than $c/2$ never share a bin; if small items come first they occupy the space the large ones will need. Sorting improves the guarantee but does not make the algorithm exact.
eh-f-050 · level facile · notes
Bin packing with $c=7$ and weights $w=(4,4,5,3,2,3)$ (optimum $3$). First Fit (every item, in the given order, into the first bin where it fits) uses $4$ bins; First Fit Decreasing (the same, after sorting by non-increasing weight) uses $3$. What explains the difference?
  1. FFD opens all of its bins at the very beginning
  2. FF puts the item of weight $2$ where the $3$ was needed
  3. FFD uses the minimum residual capacity instead of the first bin
  4. FF keeps only a single bin open at any time
Explanation. In FF item $5$ (weight $2$) goes into bin $2$ and item $6$ (weight $3$) no longer fits anywhere; in FFD the item of weight $2$ comes last and fills the gap of bin $1$.
eh-f-051 · level facile · notes
First Fit Decreasing for bin packing sorts the $n$ items by non-increasing weight and then inserts them by First Fit, scanning the open bins. How much time does it take?
  1. $O(n^2)$, like First Fit
  2. $O(n\log n)$, the time of the sorting
  3. $O(n)$, one pass over the items
  4. $O(2^n)$, because it tries all orders
Explanation. Sorting costs $O(n\log n)$, but scanning the bins for every item costs $O(n^2)$ overall, as in First Fit.
eh-f-052 · level facile · notes
Best Fit Decreasing for bin packing sorts the items by non-increasing weight and puts each one into the bin with minimum residual capacity among those where it fits (ties: the first opened). With $c=7$, after three items the residuals are $(2,3,3)$ and an item of weight $3$ arrives. Where does it go?
  1. Into bin $3$
  2. Into a new bin
  3. Into bin $1$
  4. Into bin $2$
Explanation. It fits in bins $2$ and $3$, both with residual $3$: the tie goes to the first opened. Bin $1$ has the minimum residual but the item does not fit.
eh-f-053 · level facile · notes
In bin packing, how does Best Fit Decreasing differ from First Fit Decreasing (both first sort the items by non-increasing weight)?
  1. In the sorting: by non-decreasing instead of non-increasing weight
  2. In the number of open bins: only one instead of all
  3. In the choice of the bin: minimum residual instead of the first
  4. In the feasibility test: it allows exceeding the capacity
Explanation. The sorting is the same; the filling loop is that of Best Fit instead of First Fit.
eh-f-054 · level facile · notes
For First Fit Decreasing in bin packing $FFD(I)\le\frac{11}9z(I)+\frac69$ holds for every instance, and the bound is tight ($z(I)$ = optimal number of bins). If $z(I)=9$, at most how many bins can FFD use?
  1. $18$
  2. $11$
  3. $12$
  4. $15$
Explanation. $\frac{11}9\cdot9+\frac69\approx11.67$, and the number of bins is an integer: at most $11$. $15$ comes from the factor $\frac{17}{10}$ of First Fit, $18$ from $2z(I)$.
eh-f-055 · level facile · notes
Six items of weight $2,2,3,2,2,3$ (in this order) and bins of capacity $7$: compare First Fit (FF), which keeps the given order, and First Fit Decreasing (FFD), which first reorders the weights from the largest (ties by index); both use the first bin that can take the item. Result?
  1. FF $2$ bins, FFD $3$
  2. FF $3$ bins, FFD $2$
  3. $2$ bins for both
  4. $3$ bins for both
Explanation. FF: $2+2+3=7$ and again $2+2+3=7$. FFD puts the two items of weight $3$ together (residual $1$), then three items of weight $2$ (residual $1$), and the last one opens a third bin. A better guarantee does not mean a better solution on every instance.
eh-f-056 · level facile · notes
In $P\,||\,C_{\max}$ (jobs on $m$ identical machines, minimize the makespan) a greedy rule assigns every job to the least loaded machine. What are the two independent choices of a heuristic of this kind?
  1. The machine to close and the one to open
  2. The lower bound and the stopping criterion
  3. The number of machines and the duration of the jobs
  4. The machine to assign to and the order of the jobs
Explanation. As in bin packing, the rule chooses the machine; the order in which the jobs are scanned is a second choice ($LIST$ with the given list, $LPT$ by non-increasing duration).
eh-f-057 · level facile · notes
Why, in $P\,||\,C_{\max}$, do greedy heuristics assign every job to the machine that is currently the least loaded?
  1. To use as few machines as possible
  2. Because it always gives the optimal makespan
  3. To make the loads grow as evenly as possible
  4. To reduce the running time of the heuristic
Explanation. The makespan is the maximum load: keeping the loads balanced contains it. The rule does not guarantee the optimum (on the reference instance $LPT$ gives $11$ against $9$).
eh-f-058 · level facile · notes
In $P\,||\,C_{\max}$, $LIST$ assigns the jobs in the order of a list to the least loaded machine. With $m=3$, $t=(5,5,4,4,3,3,3)$ and the reversed list $(7,6,5,4,3,2,1)$ it gives makespan $12$, while the lower bound is $9$. What does the example show?
  1. The lower bound $9$ is wrong on this instance
  2. A long job at the end of the list raises the makespan
  3. $LIST$ exceeds its guarantee $(2-\frac1m)z(I)$
  4. The reversed list is always the worst possible
Explanation. The last job ($t_1=5$) arrives when the least loaded machine already has load $7$: makespan $12\le\frac53\cdot9=15$, so the guarantee holds. $z(I)=9$ is attained.
eh-f-059 · level facile · notes
In $P\,||\,C_{\max}$, $LPT$ assigns the jobs by non-increasing duration to the least loaded machine, and $LPT(I)\le(\frac43-\frac1{3m})z(I)$. Graham's family has $2m+1$ jobs of duration $2m-1,2m-1,2m-2,2m-2,\dots,m+1,m+1,m,m,m$. With $m=4$, what are $LPT$ and $z$?
  1. $LPT=15$, $z=12$
  2. $LPT=12$, $z=12$
  3. $LPT=16$, $z=12$
  4. $LPT=15$, $z=14$
Explanation. Durations $7,7,6,6,5,5,4,4,4$: after eight jobs the loads are $(11,11,11,11)$ and the last $4$ brings it to $15=4m-1$; the optimum $\{7,5\},\{7,5\},\{6,6\},\{4,4,4\}$ is $12=3m$. The ratio $\frac{15}{12}=\frac43-\frac1{12}$ attains the bound.
eh-f-060 · level facile · notes
Constructive heuristics for the TSP split into two families, «append» and «insert». What distinguishes them?
  1. The number of starting cities: one or all
  2. The feasibility test: present only when inserting
  3. Which city is chosen: the nearest or the farthest
  4. Where the city goes: at the end of a path or into a subtour
Explanation. Appending extends a path from its end (nearest neighbour); inserting puts the city between two consecutive ones of a closed subtour, where it costs least. The feasibility test is trivial in both.
eh-f-061 · level facile · notes
In the TSP every tour built by nearest neighbour (appending at the end of a path) could also be built by an insertion heuristic, but not conversely. What advantage does insertion have?
  1. It does not require computing the distances between the cities
  2. It always guarantees the optimal tour on metric instances
  3. The subtour stays closed: the closing edge is paid from the start
  4. It takes less running time than nearest neighbour
Explanation. In nearest neighbour the edge back to the starting city is forced at the end; in insertion the subtour is always closed.
eh-f-062 · level facile · notes
Starting from city $4$, the rule «always go to the nearest city not yet visited» (on ties, the one with smaller index; at the end return to $4$) builds a tour on four cities with $d_{12}=2$, $d_{13}=3$, $d_{14}=4$, $d_{23}=3$, $d_{24}=5$, $d_{34}=2$. Which one?
  1. $(4,3,1,2)$, of length $10$
  2. $(4,3,1,2)$, of length $12$
  3. $(4,3,2,1)$, of length $11$
  4. $(4,1,2,3)$, of length $11$
Explanation. From $4$: $d_{43}=2$, city $3$; from $3$: $d_{31}=d_{32}=3$, tie won by $1$; from $1$: city $2$; return $d_{24}=5$. Total $2+3+2+5=12$; the tour $(4,3,2,1)$, of length $11$, would require the other tie rule.
eh-f-063 · level facile · notes
Nearest neighbour for the TSP with $n$ cities goes from the last visited city to the nearest unvisited one. Is its criterion static or dynamic, and how much time does it take?
  1. Dynamic; $O(n^2)$
  2. Static; $O(n\log n)$
  3. Dynamic; $O(n^3)$
  4. Static; $O(n^2)$
Explanation. The last city changes at every step, so the relevant distances change: dynamic. Every step examines $O(n)$ cities, for $n$ steps. $O(n^3)$ is the multi-start from all cities.
eh-f-064 · level facile · notes
On the $5$-city reference TSP instance (optimum $18$) nearest neighbour gives, from cities $1,\dots,5$, tours of length $25,18,18,19,18$. The multi-start runs it from every city and keeps the shortest tour. What does the example show?
  1. The multi-start is always exact on metric instances
  2. Starting from city $1$ is always the best
  3. Nearest neighbour finds the optimum from every city
  4. The start matters, and here the multi-start finds the optimum
Explanation. Three starts give the optimal tour, traversed from different cities; the multi-start returns $18=z(I)$. On other instances it does not find it (on the $6$-city instance it stays at $24$ against $19$).
eh-f-065 · level facile · notes
Why does it make sense to run nearest neighbour for the TSP from every starting city?
  1. Because from a single city the tour found is not feasible
  2. Because this decreases the overall running time
  3. The tour has no natural first city: the start is arbitrary
  4. Because the starting city does not affect the result
Explanation. Every start gives a different tour, and the best one is kept: an arbitrary choice becomes a small search, at $n$ times the cost.
eh-f-066 · level facile · notes
In the TSP, farthest insertion inserts at every step the city farthest from the subtour, into the cheapest edge. On the reference instance, starting from $1$, it first chooses city $5$ ($d_{15}=9$), then inserts $2$, $3$, $4$ at cost $0$, finding the optimum $18$. What does it show?
  1. Insertion costs are always zero on metric instances
  2. The outline is built first; the cities «on the way» cost little
  3. The farthest city must always be placed last
  4. Farthest insertion finds the optimum on every instance
Explanation. The far cities fix the outline of the tour; the others lie on paths already paid for ($d_{12}+d_{25}=d_{15}$, etc.) and are inserted for free. On metric instances the costs are $\ge0$, not zero.
eh-f-067 · level facile · notes
On a TSP instance with $6$ cities in the plane (optimum $19$), from city $1$ nearest insertion gives $23$, farthest insertion $19$ and cheapest insertion $20$, while the best tour of the nearest neighbour multi-start is $24$. What does the comparison show?
  1. On larger instances the rules separate: here farthest insertion wins
  2. Insertion heuristics always give the same tour
  3. The nearest neighbour multi-start is the best rule
  4. Cheapest insertion is always better than nearest insertion
Explanation. On the $5$-city instance they all found the optimum; here farthest insertion finds it, and the multi-start stays $26\%$ above. A single instance does not establish a general rule.
eh-f-068 · level facile · notes
In vertex coloring, the greedy heuristic $GC$ assigns the colors one at a time: every vertex gets the smallest integer that none of its already colored neighbors has. Why is the result always a feasible coloring?
  1. Because it scans the vertices by non-increasing degree
  2. Because at the end it fixes the remaining conflicts
  3. Because it always uses at most $\chi(G)$ colors
  4. The color classes are stable sets by construction
Explanation. A vertex never gets the color of an already colored neighbor, so two adjacent vertices have different colors. The number of colors can exceed $\chi(G)$.
eh-f-069 · level facile · notes
How much time does greedy coloring $GC$ (vertices in the order of a list, each gets the smallest color not used by its already colored neighbors) take on a graph with $n$ vertices and $|E|$ edges?
  1. $O(n^2\log n)$
  2. $O(n\,|E|)$
  3. $O(n+|E|)$
  4. $O(2^n)$
Explanation. For every vertex one looks at the colors of its neighbors: overall every edge is examined a constant number of times.
eh-f-070 · level facile · notes
On the Petersen graph ($\chi=3$) greedy coloring (each vertex, in list order, gets the smallest free color) uses $3$ colors with the list $(1,2,\dots,10)$ and $4$ colors with the list $(1,2,3,4,5,7,8,6,9,10)$. What does the example show?
  1. Greedy coloring always uses $\Delta+1$ colors
  2. The order of the list can change the number of colors
  3. The Petersen graph has chromatic number $4$
  4. Greedy coloring is not feasible with the second list
Explanation. With the second list vertex $8$ gets color $2$ and vertices $9$ and $10$ see all three colors among their neighbors. The outer $5$-cycle forces $\chi=3$.
eh-f-071 · level facile · notes
Graph with edges $\{1,2\},\{1,3\},\{2,3\},\{3,4\},\{4,5\}$. Greedy coloring scans the vertices in the order $(5,4,1,2,3)$ and gives each one the smallest color not used by its already colored neighbors. What colors do vertices $1,2,3,4,5$ get?
  1. $(1,2,3,2,1)$: $3$ colors
  2. $(1,2,3,1,2)$: $3$ colors
  3. $(1,2,1,2,1)$: $2$ colors
  4. $(1,2,3,4,1)$: $4$ colors
Explanation. $5\to1$, $4\to2$ (neighbor $5$), $1\to1$, $2\to2$ (neighbor $1$), $3\to3$ (neighbors $1,2,4$ with colors $1,2,2$). The triangle $1,2,3$ requires $3$ colors, so it is optimal.
eh-f-072 · level facile · notes
$DSATUR$ colors at every step the uncolored vertex with maximum saturation degree (number of distinct colors among its neighbors), on ties the one with more uncolored neighbors, then the smallest index. Three vertices have (saturation, uncolored neighbors) $=a:(2,1)$, $b:(1,2)$, $c:(2,0)$. Which one does it choose?
  1. $c$
  2. The vertex of smallest index among the three
  3. $b$
  4. $a$
Explanation. Maximum saturation $2$ for $a$ and $c$; the tie goes to the one with more uncolored neighbors, $a$. $b$ has more uncolored neighbors but lower saturation.
eh-f-073 · level facile · notes
Why does $DSATUR$, for vertex coloring, color first the vertices with many distinct colors among their neighbors (high saturation degree)?
  1. Because they are the vertices of maximum degree in the graph
  2. Because then the number of colors is always $\chi(G)$
  3. Few colors are left: postponing them may force a new color
  4. Because their neighbors are already all colored
Explanation. It is the «hardest first» idea of FFD and $LPT$, updated after every assignment. It does not guarantee $\chi(G)$ colors in general.
eh-f-074 · level facile · notes
Greedy coloring (vertices in the order of a list, each gets the smallest free color) can use many more colors than $\chi(G)$ with a bad list. Is there always a list with which it uses $\chi(G)$ colors?
  1. No: no list guarantees it on general graphs
  2. Yes: the vertices class by class of an optimal coloring
  3. Yes: the vertices by non-increasing degree
  4. Yes: the vertices in increasing index order
Explanation. With first the vertices of $Q_1$, then those of $Q_2$, etc., every vertex of $Q_c$ gets a color at most $c$. The whole difficulty lies in finding that list.
eh-f-075 · level facile · notes
$DSATUR$ (at every step the vertex with most distinct colors among its neighbors) has no performance guarantee on general graphs. Why is it nevertheless widely used?
  1. It usually needs few colors beyond $\chi(G)$; it guides exact B&B
  2. Because it always finds an optimal coloring in polynomial time
  3. Because it does not require knowing the edges of the graph
  4. Because it always uses exactly $\Delta(G)+1$ colors
Explanation. On most graphs it uses few colors more than $\chi(G)$, often none; exact algorithms branch on the vertex chosen by its rule.
eh-f-076 · level ipotesi · notes
$DSATUR$ uses at most $2$ colors on every bipartite graph (Brélaz, 1979). Why can it not have a constant performance guarantee on general graphs, if $P\neq NP$?
  1. Because on general graphs it always uses $\Delta+1$ colors
  2. Because on bipartite graphs the guarantee fails
  3. Because its running time is exponential
  4. Because vertex coloring is not approximable
Explanation. A polynomial algorithm with constant ratio would contradict the inapproximability of coloring. $DSATUR$ is polynomial, $O(n^2)$.
eh-f-077 · level facile · notes
In randomized construction, a candidate is drawn from a restricted list $RCL$ of $|RCL|$ elements, listed by increasing index, taking position $\lfloor u\cdot|RCL|\rfloor+1$, with random $u\in(0,1)$. With $RCL=\{2,3,4\}$ and $u=0.7556$, which city is chosen?
  1. City $3$
  2. City $2$
  3. City $4$
  4. City $5$
Explanation. $\lfloor0.7556\cdot3\rfloor+1=2+1=3$: the third element, city $4$. City $3$ would come from forgetting the $+1$.
eh-f-078 · level facile · notes
Randomized nearest neighbour for the TSP appends at every step a city drawn at random from a restricted candidate list, and is repeated several times keeping the best tour. Why is the generator seed NOT reinitialized between two runs?
  1. Because the restricted list would become empty
  2. Otherwise every run would give the same tour
  3. Because reinitializing it would make the results irreproducible
  4. Because the generator would overflow
Explanation. The same seed gives the same sequence of numbers, hence the same choices. Reproducibility comes precisely from the fixed initial seed.
eh-f-079 · level facile · notes
To reduce the myopia of a greedy criterion («which choice is best now?») regret and look-ahead are used. Which question does regret ask?
  1. What do I lose if I postpone this choice?
  2. Where does this choice lead, completing the solution?
  3. Which choice is best now?
  4. Which earlier choice should be revised?
Explanation. An element with a single good option must be served before it loses it. «Where does it lead» is look-ahead; revising earlier choices is not allowed in a constructive heuristic.
eh-f-080 · level facile · notes
Regret and look-ahead improve a greedy constructive heuristic. What do they have in common?
  1. They turn the heuristic into an exact algorithm
  2. They have the same cost per step as the greedy criterion
  3. They allow going back and revising a choice
  4. They cost more time per step, and the choice made stays final
Explanation. Both evaluate more before choosing, but keep the essential feature of a constructive heuristic: no choice is revised.
eh-f-081 · level facile · notes
In the TSP, the regret of a city $q$ is $reg_q=\Delta^2_q-\Delta^1_q$, the difference between the two smallest insertion costs in the subtour. With costs $(2,2,7)$ for city $2$, $(4,7,8)$ for city $4$ and $(6,5,6)$ for city $5$, which city do cheapest insertion ($CI$, minimum cost) and $REG_2$ (maximum regret) insert?
  1. $CI$ city $4$, $REG_2$ city $2$
  2. Both city $2$
  3. $CI$ city $2$, $REG_2$ city $4$
  4. $CI$ city $2$, $REG_2$ city $5$
Explanation. Minimum costs $2,4,5$: $CI$ chooses city $2$. Regrets $0,3,1$: $REG_2$ chooses city $4$, which has a single good position, while city $2$ has two and can wait.
eh-f-082 · level facile · notes
$REG_2$ insertion for the TSP inserts the city with maximum regret $reg_q=\Delta^2_q-\Delta^1_q$, on ties the one with minimum cost $\Delta^1_q$, then the smallest index. As long as all regrets are $0$, which heuristic is it equivalent to?
  1. Nearest neighbour
  2. Cheapest insertion
  3. Nearest insertion
  4. Farthest insertion
Explanation. With all regrets zero the tie rule decides: the minimum insertion cost, i.e. the rule of cheapest insertion.
eh-f-083 · level facile · notes
The pilot method with nearest neighbour as pilot ($PILOT$-$NN$) tries every next city, completes the tour with $NN$ and chooses the best. On the reference TSP instance (optimum $18$), from city $1$ it first goes to the farthest city and finds $22$, against $25$ for $NN$. What does it show?
  1. Look-ahead chooses unlike greedy, but is only as good as its pilot
  2. The pilot method always finds the optimal tour of the instance
  3. The pilot method can be worse than its own pilot
  4. Going to the farthest city is always the right choice
Explanation. $22<25$ but $22>18$: look-ahead improves $NN$ without guaranteeing the optimum. The pilot method is never worse than the pilot from the same city.
eh-f-084 · level facile · notes
The pilot method for the TSP, with nearest neighbour ($O(n^2)$) as pilot, at every step completes the tour with the pilot once for every candidate city. How much time does it take?
  1. $O(n^3)$
  2. $O(2^n)$
  3. $O(n^2)$
  4. $O(n^4)$
Explanation. $n$ steps, up to $n$ candidates per step, each with an $O(n^2)$ completion: $O(n^4)$. $O(n^3)$ is the nearest neighbour multi-start.
eh-f-085 · level facile · notes
On the reference TSP instance the constructive heuristics find a tour of length $18$, which is optimal, while the best available dual bound is $17$ (gap $5.9\%$). What can be said?
  1. The tour is not optimal, because the gap is positive
  2. The gap proves the tour is $5.9\%$ away from the optimum
  3. The tour is optimal, but the bound $17$ cannot prove it
  4. The heuristic knows it has found the optimum
Explanation. The gap is only an upper bound on the error: here the error is $0$, but a dual bound $18$ would be needed to prove it. The heuristic does not know which situation it is in.
eh-f-086 · level facile · notes
In $P\,||\,C_{\max}$ with $m=3$ and $t=(5,5,4,4,3,3,3)$, $LPT$ (jobs by non-increasing duration to the least loaded machine) reaches the last job with loads $(8,8,8)$ and ends with makespan $11$, while the optimum is $9$. What does it illustrate?
  1. The last job should have been left without a machine
  2. Earlier choices are final: there is no going back
  3. $LPT$ violates its own performance guarantee
  4. The lower bound $9$ cannot be attained on this instance
Explanation. The makespan $11$ is fixed by choices already made; a better solution looks close, but a constructive heuristic has no mechanism to go back. $\frac{11}9$ is exactly the guarantee of $LPT$ for $m=3$.
eh-f-087 · level facile · notes
A greedy algorithm builds a solution by choosing each time, among the candidate elements, the best one according to a selection criterion. Which property does each of its decisions have?
  1. It is taken once and for all: a choice, once made, is never revised
  2. It is revised at the end by a built-in local search
  3. It is undone if the partial solution becomes infeasible
  4. It is taken at random among equal-valued elements and then optimized
Explanation. The greedy adds one element at a time and never goes back: this is why it is fast, and why an early short-sighted choice can weigh on the whole solution.
eh-f-088 · level facile · notes
In the greedy template, what happens to a candidate element that, added to the partial solution, would make it infeasible (for example an item that does not fit in the knapsack)?
  1. The algorithm stops and returns the partial solution
  2. It is added anyway and another element is removed
  3. It is put back at the end of the list and examined later
  4. It is discarded and the algorithm moves to the next candidate
Explanation. In the knapsack greedy with order $\rho$, an item that does not fit is skipped and the algorithm continues: later, lighter items may still fit.
eh-f-089 · level facile · notes
0-1 knapsack with capacity $c=10$ and items $(p_j,w_j)$: $(10,5)$, $(6,4)$, $(5,3)$, $(3,2)$. The greedy examines the items in an order and takes every item that fits; ties go to the smaller index. What is the value of the greedy by non-increasing profit ($GR_p$)?
  1. $21$
  2. $18$
  3. $16$
  4. $14$
Explanation. $GR_p$ takes items $1$ and $2$ (weight $9$) and then nothing else fits: $16$. By efficiency ($GR$) items $1,3,4$ are taken: $18$; by non-decreasing weight ($GR_w$) $4,3,2$: $14$.
eh-f-090 · level facile · notes
Bin packing with capacity $c=10$ and items of weight $2,3,4,5,6$ in this order. First Fit (FF) puts each item, in the given order, into the first bin where it fits; First Fit Decreasing (FFD) does the same after sorting the weights in non-increasing order. How many bins do they use?
  1. FF $3$, FFD $3$
  2. FF $3$, FFD $2$
  3. FF $2$, FFD $3$
  4. FF $2$, FFD $2$
Explanation. FF: $2,3,4$ in the first ($9$), $5$ in the second, $6$ in the third. FFD: $6,4$ in the first, $5,3,2$ in the second. The bound $\lceil 20/10\rceil=2$ proves FFD optimal here.
eh-f-091 · level teorema · notes
Scheduling $P\,||\,C_{\max}$ with $m=2$ machines and processing times $t=(3,3,2,2,2)$. $LPT$ sorts the jobs by non-increasing time and assigns each to the least loaded machine (ties: smaller index). What are the makespan of $LPT$ and the optimal one?
  1. $7$ and $6$: the ratio $\frac76$ attains the guarantee $\frac43-\frac1{3m}$
  2. $6$ and $6$: $LPT$ is optimal on this instance
  3. $7$ and $7$: no schedule does better than $7$
  4. $8$ and $6$: the ratio exceeds the guarantee
Explanation. $LPT$: $3\to M_1$, $3\to M_2$, $2\to M_1$, $2\to M_2$, $2\to M_1$: loads $7$ and $5$. The schedule $\{3,3\},\{2,2,2\}$ has makespan $6$. With $m=2$ the guarantee is $\frac43-\frac16=\frac76$, attained exactly.
eh-f-092 · level facile · notes
In the TSP, multi-start nearest neighbour runs the nearest neighbour rule ($NN$: from the current city to the nearest unvisited one) from every starting city and returns the shortest tour. Which statement is correct?
  1. It always finds the optimal tour, because it tries all starts
  2. It always gives the same tour as $NN$, because tours are cyclic
  3. It is worse than $NN$ on some instances, because it picks the start at random
  4. It is never worse than $NN$ from a fixed city, but needs $n$ runs
Explanation. The $NN$ tour from the fixed city is one of the $n$ tours tried, so the best one is not longer; but there are only $n$ starts and the optimum is not guaranteed.
eh-f-093 · level facile · notes
In an insertion heuristic for the symmetric TSP, city $k$ is inserted into the edge $(i,j)$ of the subtour with minimum cost $\Delta(i,k,j)=d_{ik}+d_{kj}-d_{ij}$. Subtour $(1,2,3)$ with $d_{12}=4$, $d_{23}=5$, $d_{31}=6$; city $4$ with $d_{14}=3$, $d_{24}=2$, $d_{34}=7$. How long is the subtour after the insertion?
  1. $20$
  2. $15$
  3. $16$
  4. $19$
Explanation. The costs are $\Delta(1,4,2)=3+2-4=1$, $\Delta(2,4,3)=2+7-5=4$, $\Delta(3,4,1)=7+3-6=4$: the city goes between $1$ and $2$, and the length goes from $15$ to $16$.
eh-f-094 · level facile · notes
In $DSATUR$ for vertex coloring, the saturation degree of an uncolored vertex is the number of distinct colors already used by its neighbours. A vertex has four neighbours: two of color $1$, one of color $2$ and one uncolored. What is its saturation degree?
  1. $4$
  2. $2$
  3. $1$
  4. $3$
Explanation. The distinct colors among the colored neighbours count: $\{1,2\}$, hence $2$. The degree of the vertex is $4$, the colored neighbours are $3$.
eh-f-095 · level facile · notes
The greedy coloring $GC$ examines the vertices in the order of a list and gives each the smallest color (integer $1,2,\dots$) not used by its already colored neighbours. On the path $1-2-3-4$ (edges $\{1,2\},\{2,3\},\{3,4\}$) with list $(1,4,2,3)$, how many colors does it use?
  1. $3$
  2. $2$
  3. $4$
  4. $1$
Explanation. $1\to1$, $4\to1$, $2\to2$ (neighbour $1$ has color $1$), $3\to3$ (neighbours $2$ and $4$ have colors $2$ and $1$). The path has $\chi=2$: the order of the list matters.
eh-f-096 · level facile · notes
In a randomized construction for a minimization criterion, the restricted candidate list is $RCL=\{q: g(q)\le g^{\min}+\alpha(g^{\max}-g^{\min})\}$. The candidates have values $g=(10,12,15,18,30)$ and $\alpha=0.25$. How many candidates does the $RCL$ contain?
  1. $2$
  2. $1$
  3. $4$
  4. $3$
Explanation. The threshold is $10+0.25\cdot 20=15$, so the values $10$, $12$ and $15$ enter. The candidate is then drawn at random from the $RCL$.
eh-f-097 · level facile · notes
In the randomized construction with restricted candidate list $RCL=\{q: g(q)\le g^{\min}+\alpha(g^{\max}-g^{\min})\}$, what is obtained with $\alpha=0$ and with $\alpha=1$?
  1. With $\alpha=0$ the $RCL$ is empty; with $\alpha=1$ it contains only the best
  2. With $\alpha=0$ a random choice; with $\alpha=1$ the greedy
  3. With $\alpha=0$ the greedy (with random ties); with $\alpha=1$ a fully random choice
  4. In both cases the greedy, since the $RCL$ always contains the best
Explanation. With $\alpha=0$ only the candidates of value $g^{\min}$ remain; with $\alpha=1$ the threshold is $g^{\max}$ and all candidates are admitted. $\alpha$ balances quality and variety of the solutions.
eh-f-098 · level facile · notes
In regret insertion $REG_2$ for the TSP, $\Delta^1_q\le\Delta^2_q$ are the two smallest insertion costs of city $q$ into the edges of the subtour, and the regret is $reg_q=\Delta^2_q-\Delta^1_q$. City $a$ has $\Delta^1=3$, $\Delta^2=10$; city $b$ has $\Delta^1=2$, $\Delta^2=4$. Which city does $REG_2$ insert?
  1. City $b$, with regret $2$
  2. City $a$, with regret $7$
  3. City $a$, with insertion cost $3$
  4. City $b$, with insertion cost $2$
Explanation. $REG_2$ inserts the city of largest regret: $reg_a=7>reg_b=2$. Postponing $a$ risks losing its only convenient edge; cheapest insertion would choose $b$ instead.
eh-f-099 · level facile · notes
The pilot method turns a constructive heuristic $\mathscr{H}$ (the pilot) into a stronger one: at each step it tries every candidate, completes the partial solution with $\mathscr{H}$ and chooses the candidate with the best completion. Which statement is correct?
  1. It is never worse than the pilot, but runs the pilot once per candidate at each step
  2. It always finds the optimal solution, because it tries all candidates
  3. It may be worse than the pilot, because it changes the first choice
  4. It costs as much as the pilot, because it runs it only once
Explanation. At the first step the candidate chosen by the pilot is among those tried, and its completion is the pilot solution: the method finds at least as much, at a much larger cost.
eh-f-100 · level facile · notes
A constructive heuristic returns a feasible solution. What is needed, besides its value, to say how far the solution is from the optimum?
  1. A second run of the same heuristic
  2. The order in which the elements were chosen
  3. Nothing: the value of a constructive heuristic is always close to the optimum
  4. A dual bound, to compute the gap
Explanation. The value is a primal bound and gives only one side of the interval containing the optimum; with a dual bound (for example a relaxation) the gap follows.
eh-f-101 · level facile · notes
Constructive heuristics stop as soon as the solution is complete, and every choice made is final. How are they usually used in a larger heuristic algorithm?
  1. They are never combined with other methods
  2. As the final algorithm, after a local search
  3. As the starting point of a local search or a metaheuristic, which improve the complete solution
  4. As a dual bound for branch-and-bound
Explanation. They are fast but do not revise choices: a local search starts from their solution and corrects wrong decisions with moves in the neighbourhood.
eh-f-102 · level facile · notes
A constructive heuristic starts from the empty partial solution and extends it one element at a time. Which feature distinguishes it from a local search?
  1. It always starts from a complete feasible solution
  2. Every choice is final: an element added is never removed
  3. It guarantees an optimal solution
  4. It examines all neighbours of the current solution
Explanation. Local search modifies a complete solution; a constructive heuristic builds the solution and never goes back. Look-ahead and regret also keep the choices final.
eh-f-103 · level facile · notes
A greedy algorithm is a constructive heuristic that at every step adds the best element according to a criterion. For the 0/1 knapsack, which greedy criterion leads to the Dantzig bound when a fraction of the split item is allowed?
  1. Non-increasing efficiency $p_j/w_j$
  2. Non-decreasing profit $p_j$
  3. Non-increasing weight $w_j$
  4. Increasing index $j$
Explanation. The greedy by efficiency stops at the split item; completing with the fraction $\mathit{rc}/w_s$ gives the LP relaxation, and its rounding down is the Dantzig bound.
eh-f-104 · level facile · notes
In heuristics, $\mathscr{A}(I)$ is the value of the solution of heuristic $\mathscr{A}$ on instance $I$ and $z(I)$ the optimal value. For a minimization problem like bin packing, which relation always holds?
  1. $\mathscr{A}(I)\le z(I)$
  2. $\mathscr{A}(I)=z(I)$
  3. $\mathscr{A}(I)\ge 2z(I)$
  4. $\mathscr{A}(I)\ge z(I)$
Explanation. The heuristic solution is feasible, so in a minimization problem it cannot be worth less than the optimum: it is a primal bound (upper bound).
eh-f-105 · level facile · notes
Bin packing with $c=10$ and weights, in input order, $w=(2,2,2,8,8,8)$. How many bins does First Fit use (every item, in order, into the first bin where it fits) and how many First Fit Decreasing (first sorted by non-increasing weight)?
  1. FF: $6$, FFD: $3$
  2. FF: $4$, FFD: $4$
  3. FF: $4$, FFD: $3$
  4. FF: $3$, FFD: $3$
Explanation. FF puts the three $2$s into the first bin (load $6$) and then every $8$ into a new bin: $4$. FFD opens three bins with the $8$s and puts a $2$ into each: $3$, which is optimal ($\lceil30/10\rceil=3$).
eh-f-106 · level facile · notes
In bin packing with $c=10$ three open bins have loads $(4,7,6)$ and an item of weight $3$ arrives. Into which bin do First Fit (the first where it fits), Best Fit (the one with minimum residual capacity among those where it fits) and Worst Fit (maximum residual) put it?
  1. FF: $1$, BF: $1$, WF: $2$
  2. FF: $1$, BF: $2$, WF: $1$
  3. FF: $2$, BF: $2$, WF: $3$
  4. FF: $1$, BF: $3$, WF: $1$
Explanation. The residual capacities are $6,3,4$ and the item fits everywhere. FF takes bin $1$; BF the one with residual $3$ (bin $2$), which it fills exactly; WF the one with residual $6$ (bin $1$).
eh-f-107 · level facile · notes
For $P\,||\,C_{\max}$ (jobs of duration $t_j$ on $m$ identical machines, the makespan is minimized) constructive heuristics assign one job at a time. Why is the feasibility test trivial and everything depends on the order of the jobs?
  1. Every assignment of jobs to machines is feasible; the rule «least loaded machine» depends on the order in which the jobs arrive
  2. Because the makespan does not depend on the assignment
  3. Because every machine has a capacity to respect
  4. Because jobs can be split among the machines
Explanation. There are no capacities: one only chooses where to put the job. With the same greedy criterion, different lists give different makespans.
eh-f-108 · level facile · notes
$P\,||\,C_{\max}$ with $m=2$ machines and jobs of duration $t=(3,3,2,2,4)$. $LIST$ assigns the jobs in list order to the least loaded machine (ties: smallest index); $LPT$ does the same after sorting them by non-increasing duration. What are $LIST(I)$ with the list $(1,2,3,4,5)$ and $LPT(I)$?
  1. $LIST(I)=8$, $LPT(I)=7$
  2. $LIST(I)=9$, $LPT(I)=7$
  3. $LIST(I)=7$, $LPT(I)=8$
  4. $LIST(I)=9$, $LPT(I)=8$
Explanation. $LIST$: loads $(3,3)\to(5,5)\to(9,5)$, makespan $9$: the long job arrives last. $LPT$: $4,3,3,2,2$ gives $(4,0)\to(4,3)\to(4,6)\to(6,6)\to(8,6)$. The optimum is $7$ ($\{4,3\}$ and $\{3,2,2\}$).
eh-f-109 · level teorema · notes
For $P\,||\,C_{\max}$ Graham (1966) proved $LIST(I)\le(2-\frac1m)z(I)$ for every list. On an instance with $m=2$ machines $LIST$ finds makespan $9$. What follows about the optimal value $z(I)$?
  1. $z(I)\ge9$
  2. $4.5\le z(I)\le9$
  3. $6\le z(I)\le9$
  4. $z(I)=6$
Explanation. The $LIST$ solution is feasible: $z(I)\le9$. The guarantee gives $9\le\frac32z(I)$, i.e., $z(I)\ge6$. Dividing by $2$ instead of $2-\frac12$ gives the wrong $4.5$.
eh-f-110 · level facile · notes
In the insertion heuristic for the TSP the partial solution is the subtour $(1,2,3)$ with $d_{12}=4$, $d_{23}=5$, $d_{31}=6$; city $4$ has $d_{14}=3$, $d_{24}=2$, $d_{34}=6$. Inserting $4$ between two consecutive cities $i,j$ the increase is $d_{i4}+d_{4j}-d_{ij}$. Where should it be inserted and with which increase?
  1. Between $2$ and $3$, increase $3$
  2. Between $1$ and $2$, increase $1$
  3. Between $3$ and $1$, increase $3$
  4. Between $1$ and $2$, increase $5$
Explanation. Increases: $3+2-4=1$ between $1$ and $2$; $2+6-5=3$ between $2$ and $3$; $6+3-6=3$ between $3$ and $1$. Forgetting to subtract $d_{ij}$ gives $5$.
eh-f-111 · level facile · notes
TSP with $5$ cities and distances $d_{12}=5$, $d_{13}=2$, $d_{14}=2$, $d_{15}=9$, $d_{23}=4$, $d_{24}=3$, $d_{25}=4$, $d_{34}=4$, $d_{35}=7$, $d_{45}=7$ (optimal value $18$). Nearest neighbour starts from a city and always moves to the nearest unvisited city (ties: smallest index). What is the length of the tour found starting from city $5$?
  1. $18$
  2. $22$
  3. $25$
  4. $20$
Explanation. $5\to2$ ($4$), $2\to4$ ($3$), $4\to1$ ($2$), $1\to3$ ($2$), closing $3\to5$ ($7$): $18$, the optimum. From city $1$, instead, the tour $(1,3,2,4,5)$ is worth $25$: the result depends on the start.
eh-f-112 · level facile · notes
On a TSP instance with $6$ cities nearest neighbour, from every starting city, finds at best a tour of length $24$ (optimum $19$), and all its tours contain the longest edge of the instance, between two cities at opposite ends. Which weakness does this show?
  1. Nearest neighbour requires exponential time
  2. Nearest neighbour never finds a feasible tour
  3. Nearest neighbour ignores the starting city
  4. The last remaining cities are far from each other, and the closing edge is never chosen for its length
Explanation. The criterion only looks at the last city: at the end «awkward» cities remain, and the arc back to the start is forced. Insertion heuristics partly avoid the problem.
eh-f-113 · level facile · notes
Greedy coloring $GC$ colors the vertices in the order of a list $\lambda$, giving every vertex the smallest color not used by its already colored neighbours. On the path $1-2-3-4$ (edges $\{1,2\},\{2,3\},\{3,4\}$) with the list $\lambda=(1,4,2,3)$, how many colors does it use?
  1. $4$
  2. $1$
  3. $3$
  4. $2$
Explanation. $1\to1$, $4\to1$, $2\to2$ (neighbour of $1$), $3$: its neighbours $2$ and $4$ have colors $2$ and $1$, hence $3$. With the list $(1,2,3,4)$ two colors suffice: the order matters.
eh-f-114 · level teorema · notes
The crown graph $G_k$ has vertices $u_1,\dots,u_k,v_1,\dots,v_k$ and edges $\{u_i,v_j\}$ for $i\ne j$: it is bipartite, hence $\chi(G_k)=2$. With the list $(u_1,v_1,u_2,v_2,\dots)$ greedy coloring uses $k$ colors. For $k=5$, what does this example show?
  1. That $GC$ is always optimal on bipartite graphs
  2. A bad list can make $GC$ use $n/2=5$ colors on a $2$-colorable graph: there is no performance guarantee
  3. That $\chi(G_5)=5$
  4. That $GC$ always uses $\Delta(G)+1$ colors
Explanation. $u_i$ and $v_i$ are not adjacent and get the same color $i$: every new pair sees all previous colors. $DSATUR$, instead, colors bipartite graphs with $2$ colors.
eh-f-115 · level facile · notes
$DSATUR$ is the greedy coloring that chooses at every step the uncolored vertex with the most distinct colors among its neighbours. What holds for $DSATUR$ on bipartite graphs and on general graphs?
  1. On bipartite graphs it uses at most $2$ colors; on general graphs it has no performance guarantee
  2. It always uses $\omega(G)$ colors
  3. On bipartite graphs it may use $n/2$ colors; on general graphs it is a $2$-approximation
  4. It is optimal on all graphs
Explanation. Brélaz (1979) showed that $DSATUR$ is exact on bipartite graphs; since the VCP is not approximable, no polynomial heuristic has a constant guarantee on general graphs.
eh-f-116 · level facile · notes
To reduce the myopia of greedy one uses regret and look-ahead. What does look-ahead (the pilot method) do?
  1. It serves first the element that would lose most if postponed
  2. It undoes choices already made if they worsen the solution
  3. It chooses a random candidate among the best ones
  4. It evaluates every candidate by completing the partial solution with a fast heuristic, and chooses the candidate with the best completion
Explanation. Regret asks what is lost by postponing; look-ahead where the choice leads. Both cost more per step and keep the choices final.
eh-f-117 · level ipotesi · notes
First Fit Decreasing for bin packing sorts the items by non-increasing weight before filling the bins with First Fit. Which assumption on the instance does it need, which First Fit does not need?
  1. That the weights are all different
  2. That the capacity is even
  3. That all items are known in advance (offline case); First Fit also works when they arrive one at a time
  4. That every item weighs more than half the capacity
Explanation. To sort, the whole instance must be known. When it is known, it pays to place the large items first: two items larger than $c/2$ never fit together.
eh-f-381 · level teorema · notes
With $m=4$ identical machines, which factor does Graham's result guarantee for $LIST$ (any list), and which one for $LPT$?
  1. $\frac74$ for both
  2. $\frac54$ for $LIST$, $\frac74$ for $LPT$
  3. $\frac74$ for $LIST$, $\frac54$ for $LPT$
  4. $2$ for $LIST$, $\frac43$ for $LPT$
Explanation. $2-\frac1m=\frac74$ and $\frac43-\frac1{3m}=\frac43-\frac1{12}=\frac54$. The factors $2$ and $\frac43$ are the limits as $m$ grows; sorting the jobs improves the guarantee.
eh-f-382 · level teorema · notes
A graph $G$ has maximum degree $\Delta(G)=4$. At most how many colors does the greedy coloring $GC$ use, whatever the list of vertices?
  1. $2\Delta(G)$
  2. $5$
  3. $4$
  4. $\chi(G)+1$
Explanation. $GC(I)\le\Delta(G)+1=5$ for every list: when a vertex is colored, at most $4$ neighbours already have a color. $\chi(G)+1$ is not guaranteed (crown graph).
eh-f-383 · level teorema · notes
On the crown graph $G_k$ ($n=2k$ vertices, $\chi(G_k)=2$) the greedy coloring, with a suitable list, uses $k=\frac n2$ colors. What does this result show?
  1. No bound $GC\le c\,\chi(G)$, $c$ constant, holds for every list
  2. $GC$ is optimal on bipartite graphs, with every list
  3. $DSATUR$ also uses $k$ colors on the graph $G_k$
  4. The bound $\Delta(G)+1$ fails on bipartite graphs
Explanation. The ratio $GC/\chi=\frac k2$ grows with $k$: no constant bounds it. The bound $\Delta+1=k$ holds and is attained; $DSATUR$ colors bipartite graphs with $2$ colors.
eh-f-384 · level ipotesi · notes
The guarantee $LPT(I)\le(\frac43-\frac1{3m})z(I)$ is better than that of $LIST$. Which feature of $LPT$ does the proof use?
  1. The machines have different speeds
  2. There are at least $3$ machines
  3. The processing times are all distinct
  4. The jobs are sorted by non-increasing time
Explanation. $LPT$ is $LIST$ with the jobs sorted by non-increasing time: the last assigned job is the shortest, and the better factor comes from this. The machines are identical and $m$ is arbitrary.
eh-f-385 · level ipotesi · notes
Why does the bound $GC(I)\le\Delta(G)+1$ hold for every list $\lambda$ of the vertices?
  1. The graph to be colored is always bipartite
  2. $GC$ recolors the colored vertices when needed
  3. At most $\Delta(G)$ neighbours of a vertex already have a color
  4. $GC$ always colors the vertices by decreasing degree
Explanation. The vertex takes the smallest color not used by its colored neighbours, which are at most $\Delta(G)$: one of the colors $1,\dots,\Delta(G)+1$ is free. No order or graph property is needed.
eh-f-386 · level ipotesi · notes
For which problem does the greedy algorithm by non-increasing efficiency $p_j/w_j$ always give an optimal solution?
  1. The bounded knapsack, with several copies per item
  2. The continuous knapsack, with divisible items
  3. The 0/1 knapsack with integer profits and weights
  4. The 0/1 knapsack with capacity $c\ge\frac12\sum_jw_j$
Explanation. The greedy by efficiency solves the continuous relaxation (Dantzig), where the split item enters in part. On the 0/1 knapsack and its integer variants it does not guarantee the optimum.
eh-f-387 · level ipotesi · notes
Which ingredient does a greedy constructive algorithm need?
  1. A selection rule for each step, never revised
  2. A complete feasible starting solution
  3. A neighbourhood of the feasible solutions
  4. A dual bound on the optimal value
Explanation. The greedy starts from the empty solution and adds one element at a time chosen by a rule, never going back. A starting solution and a neighbourhood are what local search needs.
eh-f-388 · level ipotesi · notes
Nearest neighbour always gives a feasible tour on a complete graph. Why can it fail on a graph that is not complete?
  1. On incomplete graphs distances are asymmetric
  2. It needs the triangle inequality
  3. The number of cities must be even
  4. The last city may have no edge back to the start
Explanation. On a complete graph every unvisited city can be reached and the tour always closes. On an incomplete graph the path may get stuck or fail to close at the starting city.
eh-f-418 · level ipotesi · notes
First Fit Decreasing sorts the items by weight before filling the bins. In which situation can only First Fit in the arrival order be used?
  1. When the instance has many items
  2. When the items arrive one at a time (online)
  3. When all the items have the same weight
  4. When the bins have different capacities
Explanation. Sorting requires knowing the whole instance in advance. With equal weights the order does not matter, and different capacities or large instances do not prevent sorting.
eh-f-434 · level teorema · notes
$P\,||\,C_{\max}$ with $m=2$ machines: $LPT$ finds makespan $14$. What follows from the guarantee $LPT(I)\le(\frac43-\frac1{3m})z(I)$?
  1. $z(I)\le 12$
  2. $z(I)\ge 12$
  3. $z(I)\ge 10.5$
  4. $z(I)\ge 7$
Explanation. With $m=2$ the factor is $\frac43-\frac16=\frac76$: $z(I)\ge14\cdot\frac67=12$. $10.5$ uses the factor $\frac43$, $7$ the factor $2$; the guarantee gives a lower bound on $z(I)$.
eh-f-435 · level teorema · notes
$P\,||\,C_{\max}$ with $m=2$ and times $t=(1,1,2)$ in the order of the list: $LIST$ assigns each job to the least loaded machine. What is $LIST(I)/z(I)$?
  1. $\frac32=2-\frac1m$
  2. $\frac43$, below the guarantee
  3. $2$, above the guarantee
  4. $1$: $LIST$ is optimal
Explanation. The two short jobs go one per machine, then the long job gives makespan $3$; the optimum is $2$ ($\{1,1\}$ and $\{2\}$). The ratio $\frac32=2-\frac12$: the guarantee is attained.
eh-f-436 · level teorema · notes
On the complete graph $K_6$ how many colors does the greedy coloring $GC$ use, and how does it compare with the bound $\Delta(G)+1$?
  1. $5$: one color below the bound
  2. $6$: one above the bound
  3. $2$: the graph is bipartite
  4. $6$: the bound is attained
Explanation. In $K_6$ all the vertices are adjacent: $6$ colors are needed, and $\Delta(K_6)+1=5+1=6$. The bound $\Delta+1$ cannot be improved in general.
eh-f-437 · level teorema · notes
How many colors does $DSATUR$ use on a bipartite graph with at least one edge?
  1. It depends on the initial list
  2. Exactly $\frac n2$
  3. Exactly $2$
  4. At most $\Delta(G)+1$, not fewer
Explanation. $DSATUR$ is exact on bipartite graphs (Brélaz, 1979): it uses $2$ colors, while the greedy with a bad list may use $\frac n2$ (crown graph).
eh-f-438 · level teorema · notes
For every graph $G$ there is a list of the vertices for which the greedy coloring uses $\chi(G)$ colors. Why?
  1. Because the graph always has $\chi(G)=2$
  2. Follow the classes of an optimal coloring
  3. Because $GC$ always uses $\Delta(G)+1$ colors
  4. Because every list gives the same result
Explanation. With the vertices in the class order of an optimal coloring, $GC$ never uses a color beyond $\chi(G)$. Finding that list, however, is as hard as coloring the graph.
eh-f-439 · level teorema · notes
0/1 knapsack with $c=100$, item $1$ with $p_1=2$, $w_1=1$ and item $2$ with $p_2=w_2=100$. The greedy by efficiency takes item $1$ and then item $2$ does not fit. What does the instance show?
  1. The greedy by efficiency has no constant guarantee
  2. The greedy is optimal when the weights differ
  3. The linear relaxation is worth $2$
  4. The greedy by profit is always worse
Explanation. The greedy is worth $2$, the optimum $100$: stretching the instance ($p_2=w_2=c=M$) the ratio grows without bound. The relaxation is worth $2+\frac{99}{100}\cdot100=101$.
eh-f-440 · level ipotesi · notes
For which lists and which machines does Graham's guarantee $LIST(I)\le(2-\frac1m)z(I)$ hold?
  1. Only for lists sorted by time
  2. Only with two machines
  3. Also with machines of different speeds
  4. For every list, with identical machines
Explanation. The proof holds for any order of the jobs, on $m$ identical machines; sorting by non-increasing time ($LPT$) gives the better guarantee $\frac43-\frac1{3m}$.
eh-f-441 · level ipotesi · notes
$DSATUR$ first colors the vertex of maximum saturation. What is the saturation of a vertex?
  1. The number of its uncolored neighbours
  2. The smallest color free for it
  3. The distinct colors among its neighbours
  4. The number of its neighbours
Explanation. The saturation counts the distinct colors already used by the neighbours; ties are broken by maximum degree. The number of neighbours is the degree.
eh-f-442 · level ipotesi · notes
Multi-start nearest neighbour repeats the method from every starting city and keeps the best tour. What is it based on?
  1. It is needed to compute a dual bound
  2. The tour depends on the starting city
  3. Nearest neighbour is random
  4. Every start gives the same tour
Explanation. The method is deterministic but the tour changes with the starting city: trying all of them costs $n$ times more and never gives a worse result than the start from city $1$.
eh-f-443 · level ipotesi · notes
In insertion heuristics for the TSP, into what is each new city inserted?
  1. Into a cycle on the cities already inserted
  2. Into a path starting at city $1$
  3. Into a spanning tree of the cities
  4. Into a matching of the cities
Explanation. One starts from a small subtour and each city is inserted between two consecutive cities of the current cycle, at cost $d_{ik}+d_{kj}-d_{ij}$; nearest neighbour instead appends to a path.
eh-f-444 · level ipotesi · notes
Regret insertion chooses the city of maximum regret. How is the regret of a city $q$ defined?
  1. The smallest insertion cost
  2. The distance from the nearest city
  3. The sum of the insertion costs
  4. The second insertion cost minus the first
Explanation. $reg_q=\Delta^2_q-\Delta^1_q$: how much is lost if the best place for $q$ is taken. The city that would lose most by waiting is inserted first.
eh-f-445 · level ipotesi · notes
Why is a constructive heuristic randomized, choosing at random among the best candidates?
  1. To reduce the time of one construction
  2. To obtain a dual bound
  3. To get different solutions
  4. To make it exact
Explanation. A deterministic construction always gives the same solution; with the random choice among the best candidates each run gives a different solution, and the best one is kept (it is the basis of GRASP).
eh-f-118 · level teorema · notes
A local search $LS$ for a minimization problem with integer-valued objective $f$ and optimal value $z(I)$ starts from $x^0$ and always moves to a strictly better neighbor. Which statement is correct?
  1. It may never stop, if the neighborhood used is not exact
  2. It stops at a global optimum after at most $f(x^0)-z(I)$ moves
  3. It stops at a local optimum after at most $f(x^0)-z(I)$ moves
  4. It stops at a local optimum after exactly $f(x^0)-z(I)$ moves
Explanation. Every move improves $f$ by at least $1$ and $f$ does not go below $z(I)$; when no neighbour is better, the solution is a local optimum, not necessarily a global one.
eh-f-119 · level ipotesi · notes
A local search $LS$ for a minimization problem (integer objective $f$, optimal value $z(I)$) starts from $x^0$ and moves to strictly better neighbors. Which facts are needed to prove that it stops at a local optimum after at most $f(x^0)-z(I)$ moves?
  1. The problem has a unique optimal solution; every move strictly improves $f$; $f$ is integer
  2. Every move strictly improves $f$; solutions are finite; with integer $f$ every move improves by at least $1$ and $f\ge z(I)$
  3. The rule is best improvement; solutions are finite; $f$ is convex and $f\ge z(I)$
  4. The neighborhood is exact; solutions are finite; with integer $f$ every move improves by at least $1$ and $f\ge z(I)$
Explanation. Termination follows from the strict improvement over a finite set; the number of moves from the decrease of at least $1$ per move down to at most $z(I)$. The neighbourhood need not be exact.
eh-f-120 · level facile · notes
In the symmetric TSP, a 2-opt move removes two non-adjacent edges of the tour and reconnects the two paths in the only other way that gives a tour. How many moves does the 2-opt neighborhood of a tour with $n=10$ cities have?
  1. $35$
  2. $45$
  3. $90$
  4. $100$
Explanation. The 2-opt neighbourhood has $\frac{n(n-3)}{2}=\frac{10\cdot 7}{2}=35$ moves: the pairs of non-adjacent edges of the tour. $45=\binom{10}{2}$ counts all the pairs of cities.
eh-f-121 · level facile · notes
In scheduling $P\,||\,C_{\max}$, the move neighborhood moves one job to another machine and the swap neighborhood exchanges two jobs on different machines. An $LPT$ solution is a local optimum for the move neighborhood. What can be concluded?
  1. It is a global optimum, because move examines all the jobs
  2. It is a local optimum for the swap neighborhood too
  3. It is a local optimum for every neighborhood of the problem
  4. Nothing about global optimality: a swap move may still improve it
Explanation. A local optimum depends on the neighborhood: in the notes an $LPT$ solution is a local optimum for move but not for swap, which improves it.
eh-f-122 · level facile · notes
In local search for bin packing (or for $P\,||\,C_{\max}$) one minimizes $SQ=\sum_b L_b^2$, where $L_b$ is the load (total weight) of bin $b$. A move shifts an item of weight $\delta=2$ from bin $a$, with $L_a=9$, to bin $b$, with $L_b=5$. By how much does $SQ$ change?
  1. $0$
  2. $8$
  3. $-8$
  4. $-16$
Explanation. Only the two loads change: $(L_a-\delta)^2+(L_b+\delta)^2-L_a^2-L_b^2=2\delta(L_b-L_a+\delta)=2\cdot 2\cdot(5-9+2)=-8$; indeed $49+49-81-25=-8$.
eh-f-123 · level facile · notes
A local search $LS$ with neighborhood $N$ is an improvement heuristic. What does it start from?
  1. From an optimal solution of the relaxation
  2. From a complete feasible solution
  3. From the empty partial solution
  4. From a dual bound of the problem
Explanation. It starts from a feasible solution and moves to better neighbors; starting from the empty solution is typical of constructive heuristics.
eh-f-124 · level facile · notes
Two local searches start from the same feasible solution, but use different neighborhoods $N_1$ and $N_2$ (and move only to strictly better neighbors). Do they reach the same solution?
  1. Not necessarily: the local optimum depends on the neighborhood
  2. Yes: a local optimum is unique for every instance
  3. Yes, if both use first improvement
  4. No: with different neighborhoods the search does not terminate
Explanation. A local optimum for $N_1$ may have better neighbors in $N_2$ (the $LPT$ solution is a local optimum for move but not for swap). Both terminate.
eh-f-125 · level facile · notes
A local search with neighborhood $N$ starts from a solution that is already a local optimum with respect to $N$. What does it do?
  1. It restarts from a new random solution
  2. It declares the solution a global optimum
  3. It moves anyway to the best neighbor, even if worse
  4. It finds no better neighbor and returns it unchanged
Explanation. It accepts only strictly better neighbors: it stops at once. It cannot say anything about the global optimum, and moving to worse neighbors is an idea of metaheuristics.
eh-f-126 · level facile · notes
In $P\,||\,C_{\max}$ the load $L_h$ of a machine is the sum of the times of its jobs, and a machine is critical if its load equals the makespan $C_{\max}=\max_hL_h$. With loads $(9,11,7)$, which machines are critical?
  1. Machines $1$ and $2$
  2. Only machine $3$
  3. Only machine $2$
  4. All three
Explanation. $C_{\max}=11$ and only machine $2$ has load $11$. Machine $3$ is the least loaded, not the critical one.
eh-f-127 · level facile · notes
To study a local search for bin packing from many random starting solutions, how is a random (always feasible) solution generated?
  1. First Fit Decreasing with random ties
  2. First Fit on a random order of the items
  3. A random bin for every item
  4. Next Fit on the given order of the items
Explanation. A random bin for every item can exceed the capacity; First Fit on a shuffled order (Fisher–Yates) always gives a feasible solution and varies with the seed.
eh-f-128 · level facile · notes
What are the four ingredients that define a local search?
  1. Start, neighborhood, acceptance criterion, stopping criterion
  2. Candidates, selection criterion, feasibility test, ordering
  3. Population, recombination, mutation, selection
  4. Relaxation, branching, bound, pruning
Explanation. The second option describes a greedy heuristic, the third a genetic algorithm, the fourth branch-and-bound.
eh-f-129 · level facile · notes
A local search for a minimization problem with integer-valued objective moves only to strictly better neighbors. It starts from a solution of value $40$, and the optimal value is $31$. At most how many moves does it make?
  1. $40$
  2. No bound: it can cycle
  3. $31$
  4. $9$
Explanation. Every move improves by at least $1$ and the value does not go below $31$: at most $40-31=9$ moves. It never visits the same solution twice, so it does not cycle.
eh-f-130 · level facile · notes
In local search, for every neighborhood the order in which moves are examined is fixed. Why?
  1. It guarantees that the local optimum is also global
  2. It changes the set of neighbors of the current solution
  3. It decides first improvement's choice, and the ties
  4. It reduces the size of the neighborhood to explore
Explanation. The neighbors are the same in any order; but first improvement accepts the first improving one, and best improvement breaks ties in favor of the first examined.
eh-f-131 · level facile · notes
In local search, what does the size of a neighborhood (the number of neighbors of a solution) determine?
  1. The optimal value of the given instance
  2. The cost of an iteration: the neighbors to evaluate
  3. The number of iterations before the search stops
  4. The quality of the starting solution used
Explanation. At every iteration (at most) all neighbors are evaluated: the neighborhood size times the cost of evaluating a move gives the cost of an iteration.
eh-f-132 · level facile · notes
In local search for the 0/1 knapsack, the flip neighborhood adds or removes an item, and the swap neighborhood removes a selected item and adds an unselected one. Which of the two can change the number of selected items?
  1. Only flip
  2. Only swap
  3. Both
  4. Neither
Explanation. A flip adds or removes one item, a swap keeps the number of items: the two neighborhoods are complementary, and flip+swap is their union.
eh-f-133 · level facile · notes
0/1 knapsack with $n=4$ items and selected items $S=\{1,3\}$. Swaps (an item $j\in S$ out, an item $k\notin S$ in) are examined by increasing $j$ and, for every $j$, by increasing $k$. In which order?
  1. $(2,1),(4,1),(2,3),(4,3)$
  2. $(1,3),(2,4),(1,4),(2,3)$
  3. $(1,2),(3,2),(1,4),(3,4)$
  4. $(1,2),(1,4),(3,2),(3,4)$
Explanation. The pair $(j,k)$ means $j$ out and $k$ in: first $j=1$ with $k=2,4$, then $j=3$ with $k=2,4$. Overall $|S|(n-|S|)=4$ swaps.
eh-f-134 · level facile · notes
Local search for bin packing with $c=10$. The swap exchanges item $j$ (weight $3$, in bin $a$ of load $8$) with item $k$ (weight $5$, in bin $b$ of load $9$), if both bins stay within capacity. Is it allowed, and with which loads?
  1. No: bin $a$ exceeds $10$
  2. Yes: loads $6$ and $11$
  3. Yes: loads $10$ and $7$
  4. No: the items have different weights
Explanation. $L_a-3+5=10\le10$ and $L_b-5+3=7\le10$: allowed. Swaps with equal weights are the excluded ones, because they change no load.
eh-f-135 · level facile · notes
In local search for bin packing, the move neighborhood moves an item into another nonempty bin where it fits, and has at most $n\,(nb-1)$ elements ($n$ items, $nb$ bins). With $n=6$ and $nb=4$, at most how many elements?
  1. $36$
  2. $18$
  3. $24$
  4. $15$
Explanation. Every item can go into one of the other $nb-1=3$ bins: $6\cdot3=18$, before the capacity test. $15=\frac{6\cdot5}2$ is the bound of swap.
eh-f-136 · level facile · notes
In the TSP the 2-opt move with positions $i<j$ removes the edges $\{\sigma_i,\sigma_{i+1}\}$ and $\{\sigma_j,\sigma_{j+1}\}$ and reverses the path $\sigma_{i+1},\dots,\sigma_j$. From the tour $(1,2,3,4,5,6)$, with $i=2$ and $j=5$, which tour is obtained?
  1. $(1,2,5,4,3,6)$
  2. $(1,2,4,3,5,6)$
  3. $(1,5,4,3,2,6)$
  4. $(1,2,3,5,4,6)$
Explanation. The edges $\{2,3\}$ and $\{5,6\}$ are removed and the path $3,4,5$ is reversed: $(1,2,5,4,3,6)$, with the new edges $\{2,5\}$ and $\{3,6\}$.
eh-f-137 · level facile · notes
In the TSP the Or-opt move moves a segment of $\ell\in\{1,2,3\}$ consecutive cities between two other consecutive cities, and the neighborhood has $\sum_{\ell=1}^3(n-\ell)(n-\ell-1)$ elements. How many with $n=6$?
  1. $20$
  2. $216$
  3. $9$
  4. $38$
Explanation. $5\cdot4+4\cdot3+3\cdot2=20+12+6=38$. $9=\frac{n(n-3)}2$ is the size of 2-opt, $20$ counts only one-city segments.
eh-f-138 · level facile · notes
In $P\,||\,C_{\max}$, the swap exchanges two jobs $j<k$ on different machines with different durations. With durations $t=(5,4,4,3)$ and machines $mach=(1,1,2,2)$, how many swaps are considered?
  1. $4$
  2. $6$
  3. $3$
  4. $2$
Explanation. Pairs on different machines: $(1,3)$, $(1,4)$, $(2,3)$, $(2,4)$; $(2,3)$ has equal durations ($4$ and $4$) and would change no load: $3$ remain.
eh-f-139 · level facile · notes
In local search for $P\,||\,C_{\max}$ the move neighborhood moves a job to another machine. Why, unlike bin packing, is no feasibility test needed?
  1. Because all machines always have the same load
  2. There is no capacity: every assignment of the jobs is feasible
  3. Because a move never changes the makespan at all
  4. Because only the shortest jobs are ever moved
Explanation. Machines have no load limit: any vector $mach$ is a schedule. In bin packing a bin cannot exceed $c$.
eh-f-140 · level facile · notes
A best improvement local search for a minimization problem evaluates four neighbors of a solution worth $20$ and obtains, in order, $17$, $15$, $15$, $18$. On equal values the neighbor evaluated first wins. To which one does it move?
  1. The second, of value $15$
  2. The third, of value $15$
  3. The first, of value $17$
  4. The fourth, of value $18$
Explanation. The minimum value $15$ is tied between the second and third neighbor: the first examined wins. First improvement would have chosen the first neighbor ($17<20$).
eh-f-141 · level facile · notes
With the first improvement rule the result of a local search depends on the order in which neighbors are examined. How is this exploited?
  1. Fixing the order avoids examining the whole neighborhood
  2. Reversing the order turns the search into best improvement
  3. Sorting the neighbors always gives the global optimum
  4. Randomizing the order gives different local optima
Explanation. From the same starting solution, different orders lead into different valleys: a simple form of diversification.
eh-f-142 · level facile · notes
Knapsack with $c=9$, $p=(10,7,6,4)$, $w=(5,4,3,3)$, solution $x=(0,0,1,1)$ (profit $10$). The flips $1,2,3,4$ (add/remove the item) are examined in this order, then the swaps «$3$ out, $1$ in», «$3$ out, $2$ in», «$4$ out, $1$ in», «$4$ out, $2$ in». Which neighbor does first improvement accept?
  1. $(1,0,1,0)$, profit $16$
  2. $(0,0,1,0)$, profit $6$
  3. $(1,0,0,1)$, profit $14$
  4. $(1,1,0,0)$, profit $17$
Explanation. Flips $1$ and $2$ exceed $9$, flips $3$ and $4$ remove an item (profit $4$ and $6$); the first swap, «$3$ out, $1$ in», gives weight $8$ and profit $14>10$. $(1,0,1,0)$ is the choice of best improvement.
eh-f-143 · level facile · notes
In the first improvement rule, what decides which improving neighbor is accepted when there are several?
  1. The neighbor farthest from the current solution
  2. The fixed order in which neighbors are examined
  3. The value of the neighbor: the best is taken
  4. A random choice among the improving neighbors
Explanation. The first neighbor better than the current solution in the order of examination is accepted; choosing the best is the best improvement rule.
eh-f-144 · level facile · notes
In the TSP, the current tour has length $25$ and its $5$ 2-opt moves, in order of examination, have length changes $\Delta=+4,\,0,\,-3,\,-1,\,-6$. How long is the tour after one best improvement move, and after one first improvement move?
  1. Best $19$, first $22$
  2. Best $22$, first $19$
  3. Best $19$, first $25$
  4. Best $21$, first $22$
Explanation. Best chooses $\Delta=-6$: $25-6=19$. First accepts the first move with $\Delta<0$, the third: $25-3=22$. $\Delta=0$ is not improving.
eh-f-145 · level facile · notes
The best improvement rule performs the «steepest descent». What does each of its iterations cost?
  1. The evaluation of neighbors up to the first improving one
  2. An exploration of the whole search space
  3. The evaluation of a single neighbor
  4. A complete exploration of the neighborhood
Explanation. It examines all neighbors and takes the best, so every move improves as much as possible; stopping at the first improving one is first improvement.
eh-f-146 · level facile · notes
On the knapsack with $c=9$, $p=(10,7,6,4)$, $w=(5,4,3,3)$, from $x=(0,0,1,1)$ with the flip+swap neighborhood, first improvement follows the profit path $10\to14\to17$ ($14$ neighbors examined) and best improvement $10\to16\to17$ ($18$ neighbors). What does the example show?
  1. Best improvement always examines fewer neighbors
  2. First improvement never reaches the optimal solution
  3. Two paths to the same optimum; first examines fewer here
  4. The two search paths are always the same
Explanation. Both reach $17$ with $2$ moves, but along different paths. The flip neighborhood alone would have stopped at once at $10$.
eh-f-147 · level facile · notes
A local search reaches a local optimum. How much does the last iteration cost with first improvement, compared with best improvement?
  1. Nothing: first skips the last iteration
  2. The same: both examine the whole neighborhood
  3. Less: first stops at the first neighbor
  4. More: first examines the neighborhood twice
Explanation. In a local optimum there is no improving neighbor, so first improvement too must examine all of them to find out.
eh-f-148 · level facile · notes
In $P\,||\,C_{\max}$, the change of makespan for a move is computed from the current loads: $\max\{L_a-t_j,\,L_h+t_j,\,\max_{q\ne a,h}L_q\}-\max_qL_q$. Why does it cost $O(m)$ and not $O(1)$?
  1. The maximum over the other machines' loads is needed
  2. The loads must be recomputed from scratch
  3. The jobs of every machine must be re-sorted
  4. All $m$ target machines must be tried
Explanation. Only two loads change, but the new makespan also depends on the other $m-2$. This is why a move iteration costs $O(nm^2)$.
eh-f-149 · level facile · notes
In local search for the knapsack with incremental evaluation, the profit and weight of the current solution are stored: $16$ and $8$. A swap removes item $j$ ($p_j=6$, $w_j=3$) and adds item $k$ ($p_k=7$, $w_k=4$). What are the new profit and weight?
  1. Profit $15$, weight $7$
  2. Profit $17$, weight $7$
  3. Profit $23$, weight $11$
  4. Profit $17$, weight $9$
Explanation. $16+7-6=17$ and $8+4-3=9$, in $O(1)$ time. $23$ and $11$ forget to remove item $j$.
eh-f-150 · level facile · notes
On the $5$-city reference TSP instance (optimum $18$), 2-opt local search from the nearest neighbour tour (length $25$) reaches the optimum with $2$ moves both with first improvement ($12$ evaluations) and best improvement ($15$ evaluations), along different paths. What does it show?
  1. Best improvement always needs fewer evaluations than first
  2. 2-opt search always finds the optimal tour of the instance
  3. On small instances both reach the optimum at similar cost
  4. First improvement always makes more moves than best
Explanation. With $5$ cities the neighborhood has only $5$ moves and both rules find the optimum; on the $10$-city instance they stop instead in different local optima.
eh-f-151 · level facile · notes
In 2-opt local search for the TSP city $1$ always stays in the first position ($\sigma_1=1$). Why does no move shift it?
  1. Because city $1$ belongs to no edge
  2. The reversed path always starts at position $i+1\ge2$
  3. Because city $1$ has the minimum distance to all
  4. Because moves with $i=1$ are excluded
Explanation. The move reverses $\sigma_{i+1},\dots,\sigma_j$ with $i\ge1$: position $1$ is never touched. Moves with $i=1$ exist (only $i=1$, $j=n$ is excluded).
eh-f-152 · level facile · notes
In the TSP an Or-opt move removes the segment $s_1,\dots,s_\ell$ between $p$ and $q$ and inserts it between $a$ and $b$: $\Delta=d_{pq}+d_{as_1}+d_{s_\ell b}-d_{ps_1}-d_{s_\ell q}-d_{ab}$. Segment $(9)$ between $p=7$ and $q=8$, inserted between $a=3$ and $b=4$, with $d_{78}=3$, $d_{39}=4$, $d_{94}=3$, $d_{79}=4$, $d_{98}=4$, $d_{34}=4$. What is $\Delta$?
  1. $-2$
  2. $+2$
  3. $-6$
  4. $0$
Explanation. Added edges $3+4+3=10$, removed edges $4+4+4=12$: $\Delta=-2$, the move shortens the tour.
eh-f-153 · level facile · notes
An Or-opt move in the TSP removes three edges and reinserts a segment of at most $3$ cities without reversing it. What is its relation with the 3-opt neighborhood?
  1. It is disjoint from 3-opt: it removes only two edges
  2. It coincides with 2-opt applied twice
  3. It contains all 3-opt moves
  4. It is the part of 3-opt explored in $O(n^2)$ time
Explanation. 3-opt considers all ways to remove three edges and reconnect, with $O(n^3)$ moves; Or-opt takes the part with short segments and preserved orientation.
eh-f-154 · level facile · notes
On a $10$-city TSP instance (optimum $39$), from the nearest neighbour tour (length $49$) 2-opt search with first improvement stops at $41$ after $138$ evaluations, and with best improvement reaches $39$ after $140$. What does it show?
  1. First improvement is always faster than best improvement
  2. Best improvement always finds the global optimum
  3. The two rules can stop in different local optima
  4. The 2-opt neighborhood is exact on this instance
Explanation. From the same tour the paths diverge; of the $181\,440$ solutions, $3$ are 2-opt local optima ($39$, $41$, $43$), so the neighborhood is not exact.
eh-f-155 · level facile · notes
How does the Lin–Kernighan heuristic for the TSP work?
  1. It solves the ILP model of the TSP on a subset of cities
  2. It builds a variable number of edge exchanges, one at a time, greedily
  3. It explores the whole 3-opt neighborhood at every iteration
  4. It tries all $k$-opt moves for every $k$ up to $n$
Explanation. It stops when the total gain can no longer become positive: it explores part of the $k$-opt neighborhood for every $k$ in time close to that of 2-opt.
eh-f-156 · level facile · notes
The 3-opt neighborhood of the TSP removes three edges and reconnects the three paths in all ways. How much does an iteration cost, and how is it used in practice?
  1. $O(n^3)$; in practice it is explored only in part
  2. $O(n^2)$; it is always explored in full
  3. $O(n)$; it costs less than the 2-opt one
  4. $O(2^n)$; this is why it is never used
Explanation. Its local optima are better than those of 2-opt, but the cost $O(n^3)$ per iteration leads to exploring it only in part (Or-opt, Lin–Kernighan).
eh-f-157 · level facile · notes
In $P\,||\,C_{\max}$ the makespan change of a move transferring $\delta$ from machine $a$ to machine $b$ is $F=\max\{L_a-\delta,\,L_b+\delta,\,\max_{q\ne a,b}L_q\}-\max_qL_q$. With loads $(12,7,9)$ and $\delta=3$ from machine $1$ to $2$, what is $F$?
  1. $+1$
  2. $0$
  3. $-3$
  4. $-2$
Explanation. New loads $(9,10,9)$: makespan $10$ against $12$, hence $F=-2$. $-3$ looks only at machine $1$ and forgets that machine $2$ rises to $10$.
eh-f-158 · level facile · notes
In local search for $P\,||\,C_{\max}$ with $n$ jobs and $m$ machines, the makespan change is evaluated in $O(m)$. How much does an iteration cost with the move and with the swap neighborhood?
  1. Move $O(nm)$, swap $O(n^2)$
  2. Move $O(n^2m)$, swap $O(nm^2)$
  3. Move $O(nm^2)$, swap $O(n^2m)$
  4. Both $O(nm)$
Explanation. Move: $n(m-1)$ moves times $O(m)$; swap: $O(n^2)$ pairs times $O(m)$. Without the factor $O(m)$ one would get $O(nm)$ and $O(n^2)$.
eh-f-159 · level facile · notes
$P\,||\,C_{\max}$ with loads $(12,7,10)$: machine $1$ is the only critical one. A move shifts a job of duration $4$ from machine $1$ to machine $2$. What does the makespan become?
  1. $12$
  2. $11$
  3. $8$
  4. $10$
Explanation. New loads $(8,11,10)$: the makespan drops from $12$ to $11$, the load of the machine receiving the job. $8$ looks only at machine $1$.
eh-f-160 · level facile · notes
$P\,||\,C_{\max}$ with $m=3$: the $LPT$ solution has loads $(11,8,8)$, and machine $1$ (critical) holds jobs of duration $5$, $3$, $3$. Why does no move (a job to another machine) lower the makespan?
  1. Moving the $5$ brings the receiving machine to $13$, a $3$ to $11$
  2. Because machine $1$ is not the only critical machine
  3. Because moves never change the load of machine $1$
  4. Because jobs of duration $3$ cannot be moved
Explanation. Every move from machine $1$ raises another machine from $8$ to at least $11$; moves from the other machines raise machine $1$. The solution is a local optimum for move, but not for swap.
eh-f-161 · level facile · notes
$P\,||\,C_{\max}$ with loads $(11,8,8)$. A swap exchanges job $1$ (duration $5$, on machine $1$) with job $3$ (duration $4$, on machine $3$). What are the new loads?
  1. $(10,9,8)$
  2. $(6,8,13)$
  3. $(12,8,7)$
  4. $(10,8,9)$
Explanation. $\delta=5-4=1$ is transferred from machine $1$ to machine $3$: $(10,8,9)$, makespan $10<11$. $(6,8,13)$ would be the move of job $1$ alone.
eh-f-162 · level facile · notes
$P\,||\,C_{\max}$ with $m=4$ and $12$ jobs, optimal makespan $19$: $LPT$ gives loads $(20,19,18,19)$, and this solution is a local optimum for both move and swap. What does the example show?
  1. Swap always improves the solution found by $LPT$
  2. $LPT$ always finds the optimal makespan of the instance
  3. Even two neighborhoods together can stop above the optimum
  4. The lower bound $19$ cannot be attained on this instance
Explanation. On the $7$-job instance swap led to the optimum; here neither move nor swap improves $20$, although the optimum $19=\lceil76/4\rceil$ exists.
eh-f-163 · level facile · notes
In local search for bin packing and for $P\,||\,C_{\max}$ the landscape is made of wide plateaus (many solutions with the same value). Why?
  1. Because random solutions are almost all infeasible
  2. The bin count takes few values; the makespan depends on critical machines
  3. Because the move and swap neighborhoods are too large to explore
  4. Because the two problems always have a unique optimal solution
Explanation. The objectives are «coarse»: almost all moves leave the number of bins unchanged, and a move not touching the critical machine does not change the makespan.
eh-f-164 · level facile · notes
Bin packing with $c=10$ and $12$ items: the $100$ First Fit solutions on random orders have $2374$ move and swap neighbors in total, and all have the same number of bins as the current solution. What does it show?
  1. With the objective «number of bins» the search is blind
  2. The $100$ solutions are all already optimal
  3. Move and swap produce only infeasible solutions
  4. The instance has a single local optimum
Explanation. No neighbor improves or worsens: a search accepting only strictly improving moves does not move. Only $14$ of the $100$ solutions are optimal.
eh-f-165 · level facile · notes
As auxiliary objective the sum of squared loads is used: in bin packing $\sum_bL_b^2$ is maximized, in $P\,||\,C_{\max}$ $\sum_hL_h^2$ is minimized. Why opposite directions?
  1. Because bin packing is a maximization problem
  2. Because in $P\,||\,C_{\max}$ the total time changes with moves
  3. Because in bin packing loads can be negative
  4. BPP wants unbalanced loads, $P\,||\,C_{\max}$ balanced ones
Explanation. At fixed total the sum of squares is large when the loads are unbalanced. In bin packing one wants a few full bins and the others empty; in $P\,||\,C_{\max}$ equal loads. The total ($\sum_jw_j$ or $\sum_jt_j$) does not change with the moves.
eh-f-166 · level facile · notes
If a quantity $\delta>0$ moves from load $L_a$ to load $L_b$, the sum of squared loads changes by $2\delta(L_b-L_a+\delta)$. When does it increase?
  1. If and only if $L_b>L_a$
  2. If and only if $\delta>L_a$
  3. If and only if $L_b+\delta>L_a$
  4. If and only if $L_b+\delta<L_a$
Explanation. With $\delta>0$ the sign is that of $L_b-L_a+\delta$: the element goes into a load that, after the move, exceeds the one it left.
eh-f-167 · level facile · notes
Bin packing with $c=7$, move search with objective $SQ=\sum_bL_b^2$ to maximize and best improvement (ties: the move examined first). With loads $(7,2,5,7)$ two moves have the maximum gain $20$: item $3$ (weight $5$, examined first) from bin $3$ to bin $2$, and item $5$ (weight $2$) from bin $2$ to bin $3$. Which one is applied, and with what result?
  1. None: the number of bins does not change
  2. Item $3$: loads $(7,7,7)$, three bins
  3. Item $5$: loads $(7,7,7)$, three bins
  4. Item $3$: loads $(7,2,0,12)$, four bins
Explanation. The tie goes to the move examined first, item $3$: it empties bin $3$ and leaves $(7,7,7)$, $SQ=147$, which is optimal. Item $5$ would also empty a bin, but comes later.
eh-f-168 · level facile · notes
In move local search for bin packing with objective $f=nb$ (number of bins), the gain of a move is the improvement of $f$. What is it?
  1. $1$ if the move empties a bin, $0$ otherwise
  2. The weight of the moved item
  3. The difference between the loads of the two bins
  4. $-1$ if the move opens a new bin
Explanation. Moves go only into nonempty bins, so they never open bins: $nb$ drops by $1$ if the source bin becomes empty, otherwise it stays the same.
eh-f-169 · level facile · notes
In bin packing, swap local search (exchanging two items of different weight in different bins) is used only with the auxiliary objective $SQ=\sum_bL_b^2$, not with the number of bins. Why?
  1. Because with $SQ$ the swap becomes a move
  2. Because a swap always increases the number of bins
  3. Because a swap always produces infeasible bins
  4. A swap never changes the number of bins
Explanation. Both bins stay nonempty and none is created: with $f=nb$ no swap would be improving.
eh-f-170 · level facile · notes
Bin packing with $c=7$ and objective $SQ=\sum_bL_b^2$ (to maximize). A swap exchanges item $j$ (weight $4$, bin $a$ of load $6$) with item $k$ (weight $2$, bin $b$ of load $5$): $\delta=w_j-w_k$ moves from $a$ to $b$, and $SQ$ changes by $2\delta(L_b-L_a+\delta)$. By how much?
  1. $-4$
  2. $+8$
  3. $+4$
  4. $0$
Explanation. $\delta=2$: $2\cdot2\cdot(5-6+2)=4$. The loads go from $(6,5)$ to $(4,7)$, both within $7$: $16+49-36-25=4$.
eh-f-171 · level facile · notes
Bin packing with $c=7$: the loads $(5,5)$ use $2$ bins and give $SQ=\sum_bL_b^2=50$, the loads $(7,2,1)$ use $3$ and give $SQ=54$. What does the comparison teach?
  1. The objective $SQ$ can only be used for $P\,||\,C_{\max}$
  2. $SQ$ is a guide: quality is measured by the number of bins
  3. Maximizing $SQ$ is equivalent to minimizing the bins
  4. The solution with $3$ bins is the better of the two
Explanation. A solution with more bins can have a larger $SQ$: the auxiliary objective is a guide, not the objective.
eh-f-172 · level facile · notes
Bin packing with $c=7$ and weights $(4,4,5,3,2,3)$ (optimum $3$). From the Next Fit solution ($5$ bins), move search with objective «number of bins» stops at $4$; with objective $SQ=\sum_bL_b^2$ it reaches $3$, through a move that does not change the number of bins. What does it show?
  1. A move «neutral» for the objective can prepare the improving one
  2. With $SQ$ every move reduces the number of bins
  3. The Next Fit solution is already a local optimum
  4. With $SQ$ the search can worsen the number of bins
Explanation. The second move ($SQ$ from $115$ to $127$) leaves $4$ bins but makes the third possible, which empties a bin. With $SQ$ a move never increases the number of bins.
eh-f-173 · level facile · notes
Bin packing with $c=10$ and $12$ items (optimum $5$): from $100$ First Fit solutions on random orders ($14$ already optimal), move search with objective «number of bins» ends with $5$ bins in $14$ cases, with objective $SQ=\sum_bL_b^2$ in $76$. What does the experiment show?
  1. Move search with $SQ$ always finds the optimal solution
  2. First Fit solutions are almost always optimal
  3. The auxiliary objective worsens the starting solutions
  4. With the bin count it stays on plateaus; with $SQ$ it does not
Explanation. With $f=nb$ none of the $100$ solutions improves; with $SQ$ another $62$ runs reach the optimum, but not all.
eh-f-174 · level facile · notes
Knapsack with $c=9$, $p=(10,7,6,4)$, $w=(5,4,3,3)$: $x=(1,0,1,0)$ (profit $16$) is a local optimum for the flip neighborhood restricted to feasible solutions, while the optimum is $(1,1,0,0)$. Why do flips not get there?
  1. Because item $2$ never fits into the knapsack
  2. Because flips cannot remove items from the knapsack
  3. Two flips are needed; the middle step is infeasible or worse
  4. Because $(1,1,0,0)$ is not a feasible solution
Explanation. One must add $2$ and remove $3$: through $(1,1,1,0)$ (weight $12$) or $(1,0,0,0)$ (profit $10<16$). Swap does the two flips together; penalties let the search cross the infeasible vector.
eh-f-175 · level facile · notes
In penalized local search for the knapsack one maximizes $g_\alpha(x)=\sum_jp_jx_j-\alpha\max\{0,\sum_jw_jx_j-c\}$. With $c=9$, $p=(10,7,6,4)$, $w=(5,4,3,3)$, $x=(1,1,1,0)$ and $\alpha=2$, what is $g_\alpha(x)$?
  1. $14$
  2. $17$
  3. $23$
  4. $20$
Explanation. Profit $23$, weight $12$, excess $3$: $23-2\cdot3=17$. $20$ and $14$ correspond to $\alpha=1$ and $\alpha=3$.
eh-f-176 · level facile · notes
Flip+swap local search for the 0/1 knapsack with $n$ items examines the flips and then the swaps, discarding neighbors exceeding the capacity. How much does an iteration cost?
  1. $O(n^2)$, because of the swaps
  2. $O(n)$, because of the flips
  3. $O(n\log n)$, for the sorting
  4. $O(2^n)$, for the subsets
Explanation. There are $n$ flips and up to $|S|(n-|S|)\le n^2/4$ swaps, each evaluated in $O(1)$ with stored profit and weight.
eh-f-177 · level facile · notes
In flip+swap local search for the knapsack (flips examined before swaps) with the first improvement rule, what happens in an iteration where there is an improving flip?
  1. The flip and the best swap are applied together
  2. The flip is discarded in favor of the swaps
  3. All swaps are examined anyway
  4. The swaps are not examined
Explanation. First improvement accepts the first improving neighbor in the order of examination: the flip found ends the iteration.
eh-f-178 · level facile · notes
On a $10$-city TSP instance (optimum $39$), variable neighbourhood descent ($VND$) with $N_1=$ 2-opt and $N_2=$ Or-opt (first improvement) brings the nearest neighbour tour from $49$ to $41$ with 2-opt moves, then to $39$ with an Or-opt move, and stops. What does it show?
  1. Or-opt alone always finds the optimal tour
  2. $VND$ uses only the largest neighborhood
  3. Or-opt improves a 2-opt local optimum
  4. 2-opt and Or-opt have the same local optima
Explanation. $41$ is a 2-opt local optimum but not an Or-opt one; the optimal tour is the only local optimum for both neighborhoods on this instance.
eh-f-179 · level facile · notes
$P\,||\,C_{\max}$ with $m=4$ and $12$ jobs: from $100$ random assignments, move search with objective $\sum_hL_h^2$ reaches the optimum in $4$ cases, $VND$ (move then swap) with the same objective in $68$, $VND$ with the makespan in $15$. What do the numbers show?
  1. $VND$ always finds the optimal solution
  2. Combining neighborhoods and auxiliary objective adds up
  3. Swap alone is always better than $VND$
  4. The makespan is a better guide than $\sum_hL_h^2$
Explanation. Each of the two ideas helps by itself, and together they give $68$ optimal runs out of $100$, against $4$ and $15$.
eh-f-180 · level facile · notes
On a $10$-city TSP (optimum $39$), from $100$ random tours: 2-opt with first improvement ends in the optimum in $46$ cases, with best improvement in $87$, and $VND$ (2-opt and Or-opt) in all $100$. What does it show?
  1. Here best beats first, and $VND$ always finds the optimum
  2. First improvement is always better than best improvement
  3. Every random tour leads to the optimum with 2-opt
  4. Multi-start is useless with $VND$ on every instance
Explanation. On this instance the optimal tour is the only local optimum for both 2-opt and Or-opt, so $VND$ reaches it from every start; on large instances this does not happen.
eh-f-181 · level facile · notes
On a $30$-city TSP (optimum $478$), $100$ random tours of average length about $1769$ become, after 2-opt search, tours of average length about $488$ ($2\%$ above the optimum); only about one run in eight reaches the optimum. What does it show?
  1. Random tours are good starting solutions for 2-opt
  2. More runs never increase the probability of finding the optimum
  3. 2-opt search finds the optimum in almost all runs
  4. Close to the optimum on average, but each run stays in its valley
Explanation. There are more than $50$ distinct local optima: the search improves enormously, but the optimum depends on the starting valley.
eh-f-182 · level facile · notes
In a multi-start local search every run reaches the optimum with probability $q=0.12$, independently of the others, so $M$ runs all miss it with probability $0.88^M$. At least how many runs are needed for this probability to drop below $1\%$?
  1. $10$
  2. $9$
  3. $37$
  4. $100$
Explanation. $0.88^{36}\approx0.0100$ and $0.88^{37}\approx0.0088<0.01$: $37$ runs are needed. With $10$ the probability of missing it is still about $0.28$.
eh-f-183 · level facile · notes
In multi-start local search, why does the probability $q$ that a single run from a random start reaches the optimum decrease on large instances?
  1. Because the local search no longer terminates
  2. The number of local optima grows very fast with $n$
  3. Because the runs become dependent on each other
  4. Because the neighborhood becomes exact for large $n$
Explanation. With $10$ cities there are $3$ 2-opt local optima, with $30$ cities $100$ runs find more than $50$ distinct ones: the valleys multiply.
eh-f-184 · level facile · notes
What does a local search give, and what does it not give?
  1. A better primal bound; no dual bound
  2. A better dual bound; no feasible solution
  3. The optimal solution, but without a proof
  4. An interval always containing the optimal value
Explanation. The value of the local optimum is one side of the gap; the other side must be computed in another way (relaxations, MIP solvers).
eh-f-185 · level facile · notes
A local search for a minimization problem stops in a local optimum of value $f^*$ ($z(I)$ = optimal value). Which relation can be written with certainty?
  1. $f^*=z(I)$
  2. $z(I)\ge f^*/2$
  3. $f^*\le z(I)$
  4. $z(I)\le f^*$
Explanation. The local optimum is a feasible solution: for a minimum its value is an upper bound. Having stopped does not mean it reached the optimum.
eh-f-186 · level facile · notes
In the 2-opt local search for the symmetric TSP, the tour $(1,3,2,4,5)$ has length $25$. The move removing edges $\{3,2\}$ and $\{4,5\}$ and adding $\{3,4\}$ and $\{2,5\}$ has $d_{32}=4$, $d_{45}=6$, $d_{34}=3$, $d_{25}=5$. With incremental evaluation, how long is the new tour?
  1. $17$
  2. $27$
  3. $23$
  4. $25$
Explanation. $\Delta=d_{34}+d_{25}-d_{32}-d_{45}=3+5-4-6=-2$, hence $25-2=23$. Looking at the four edges that change is enough, instead of recomputing the whole tour.
eh-f-187 · level facile · notes
In the 2-opt local search for the TSP with $n$ cities, the neighbourhood has $\frac{n(n-3)}{2}$ moves. What does a best-improvement iteration cost with incremental evaluation ($O(1)$ per move), and recomputing every tour from scratch ($O(n)$ per move)?
  1. $O(n^2)$ and $O(n^2)$
  2. $O(n^2)$ and $O(n^3)$
  3. $O(1)$ and $O(n)$
  4. $O(n)$ and $O(n^2)$
Explanation. The cost of an iteration is the number of neighbours times the cost of evaluating one. Incremental evaluation changes neither the local optima nor the search path, only the time.
eh-f-188 · level facile · notes
In a local search for a minimization problem, the neighbours of the current solution are examined in a fixed order and have objective changes $\Delta=(+2,-1,-5,-3)$. Which neighbour do the first-improvement and the best-improvement rules choose?
  1. First improvement the second ($-1$), best improvement the third ($-5$)
  2. Both the third ($-5$)
  3. First improvement the first ($+2$), best improvement the third ($-5$)
  4. First improvement the second ($-1$), best improvement the fourth ($-3$)
Explanation. First improvement stops at the first improving neighbour, best improvement examines the whole neighbourhood and takes the most negative change. With first improvement the result depends on the order of examination.
eh-f-189 · level facile · notes
In local search the first-improvement and best-improvement rules are compared. Which statement is correct?
  1. Best improvement always finds a better local optimum than first improvement
  2. First improvement does not terminate if the neighbourhood is large
  3. The two rules always follow the same path, with different times
  4. First improvement makes cheaper iterations but usually more moves; the two rules may stop in different local optima
Explanation. In the local optimum both examine the whole neighbourhood. Before getting there they follow different paths, and neither dominates the other on all instances.
eh-f-190 · level facile · notes
In a local search for bin packing minimizing the number of bins, almost all moves (moving an item to another bin) leave the objective unchanged. What happens to a search that accepts only strictly improving moves?
  1. It becomes a random search, because all moves are equivalent
  2. It never terminates, because zero-value moves are infinite
  3. It stops on a plateau, even if a sequence of zero-value moves would lead to a better solution
  4. It always finds the optimum, because the objective is integer
Explanation. On a plateau the objective does not distinguish the solutions and the search is blind. The remedy is an auxiliary objective, for example the sum of the squared loads.
eh-f-191 · level facile · notes
In the local search for the 0-1 knapsack with penalties, the search space is $\{0,1\}^n$ and the profit minus a penalty proportional to the excess weight over the capacity is maximized. What must the search remember?
  1. The vector with the highest penalty, to be avoided
  2. The best feasible solution visited, because the final local optimum may be infeasible
  3. Nothing: with the penalty every local optimum is feasible
  4. Only the last vector visited, which is always feasible
Explanation. With penalties the search may cross and stop in the infeasible region; the returned solution is the best feasible one met along the way.
eh-f-192 · level facile · notes
In the local search for the 0-1 knapsack with a penalty on the excess weight, how does the penalty per unit of excess matter?
  1. Large: local optima are feasible but the search never leaves the feasible region; small: it crosses it but may stop outside
  2. Large: the search becomes random; small: the search becomes exact
  3. It does not matter: the penalty changes only the value, not the chosen moves
  4. Small: local optima are always feasible; large: never
Explanation. A high penalty makes every infeasible vector unattractive, a low one makes them attractive: the value balances freedom of movement and feasibility of the result.
eh-f-193 · level facile · notes
In a multi-start local search every run, from a random starting solution, reaches the optimum with probability $q=0.1$, independently of the others. With $M=10$ runs, what is approximately the probability that none finds it?
  1. $0\%$
  2. $10\%$
  3. $90\%$
  4. $35\%$
Explanation. All runs miss the optimum with probability $(1-q)^M=0.9^{10}\approx 0.35$. The runs have no memory, and for large $n$ the probability $q$ shrinks quickly.
eh-f-194 · level facile · notes
In multi-start local search $M$ local searches are run from different starting solutions and the best local optimum is kept. Which statement is correct?
  1. With $M\ge n$ runs the optimum is guaranteed
  2. Every run restarts from the local optimum of the previous one
  3. The runs are independent and parallelizable, but none uses what the others found
  4. The result depends on the order of the runs
Explanation. Multi-start is the simplest form of diversification: without memory, every run starts from scratch and spends most of its moves on the descent.
eh-f-195 · level facile · notes
Local search for $P\,||\,C_{\max}$ with $3$ machines of loads $(10,10,6)$. A job of time $3$ is moved from machine $1$ to machine $3$. How does the makespan change, and why?
  1. It drops to $7$, the new load of machine $1$
  2. It stays $10$: machine $2$ still has load $10$, and a move improves only if it leaves the unique critical machine
  3. It rises to $13$, because machine $3$ receives the job
  4. It drops to $9$, because machine $3$ reaches $9$
Explanation. The new loads are $(7,10,9)$: the maximum stays $10$. With two critical machines no single move improves the makespan, which is why an auxiliary objective is needed.
eh-f-196 · level facile · notes
For $P\,||\,C_{\max}$ the move neighbourhood moves a job to another machine and the swap neighbourhood exchanges two jobs on different machines. What structural difference is there between the two moves?
  1. A swap keeps the number of jobs on every machine, a move changes it: the two neighbourhoods complement each other
  2. A move keeps the number of jobs on every machine, a swap changes it
  3. A swap changes the loads of three machines, a move of two
  4. No difference: a swap is always a move
Explanation. A swap equals two moves, but as a single move it cannot fix a machine with too many jobs; a local optimum for move may not be one for swap, and vice versa.
eh-f-197 · level facile · notes
A local search needs a starting solution. Which choice is typical, and what limit does it have on bin packing if the First Fit Decreasing (FFD) solution is already optimal?
  1. An infeasible solution, which the search makes feasible
  2. The LP relaxation solution, always integer
  3. The empty solution, because local search adds elements
  4. The solution of a constructive heuristic; if it is already optimal no move improves it, and starting from worse solutions is better to study the search
Explanation. Local search improves a complete feasible solution, usually a constructive one. From an optimal solution there is no improving move: for bin packing the notes start from Next Fit and First Fit.
eh-f-198 · level facile · notes
To study a local search on many starting solutions, random solutions are generated with a pseudo-random number generator (Park and Miller) from a seed. Why is the seed fixed?
  1. Because the seed is the number of iterations of the search
  2. Because a fixed seed gives better starting solutions
  3. The same seed gives the same starting solutions in every language and computer: experiments are reproducible
  4. Because without a seed the generator produces only infeasible solutions
Explanation. The sequence is determined by the seed: notes, exercises and code can obtain exactly the same results, and comparisons between methods use the same starts.
eh-f-199 · level facile · notes
In the TSP with Euclidean distances (cities in the plane), what can be said about a tour that is a local optimum for the 2-opt neighbourhood?
  1. All its edges have the same length
  2. It has no crossing edges
  3. It contains the shortest edge of the instance
  4. It is always the optimal tour
Explanation. If two edges cross, the triangle inequality shows that the 2-opt move uncrossing them shortens the tour; so a local optimum has no crossings, but it may not be optimal.
eh-f-200 · level facile · notes
In the TSP, the Or-opt move relocates a short segment of consecutive cities elsewhere in the tour, without reversing it. Which statement on the two neighbourhoods 2-opt and Or-opt is correct?
  1. A local optimum for 2-opt may not be one for Or-opt, and vice versa
  2. Every local optimum for 2-opt is also one for Or-opt
  3. Or-opt contains all the 2-opt moves
  4. The two neighbourhoods have the same number of moves
Explanation. The two moves change different edges (two for 2-opt, three for Or-opt) and contain different moves: combining them, for example in a variable neighbourhood descent, improves the results.
eh-f-201 · level facile · notes
Variable neighbourhood descent ($VND$) uses the neighbourhoods $N_1,\dots,N_K$, ordered from the smallest to the largest. How does it proceed?
  1. It runs a complete local search in every $N_k$, once, in order
  2. It chooses a random neighbourhood at every iteration
  3. It uses only $N_K$, the largest, since it contains the others
  4. It looks for a better neighbour in $N_1$, then in $N_2$ and so on; after every improvement it returns to $N_1$; it stops when no $N_k$ improves
Explanation. The expensive neighbourhoods are explored only when the cheap ones are exhausted; $VND$ is deterministic and terminates by the same argument as local search.
eh-f-202 · level facile · notes
When variable neighbourhood descent ($VND$) with neighbourhoods $N_1,\dots,N_K$ stops, what is known about the returned solution?
  1. It is the best solution of $N_1$ from the starting solution
  2. It is a global optimum, because it tried all the neighbourhoods
  3. It is a local optimum with respect to each of the neighbourhoods $N_1,\dots,N_K$
  4. It is a local optimum only with respect to the last neighbourhood $N_K$
Explanation. The last exploration of every neighbourhood found no improvement and the solution did not change any more: it is a local optimum for all of them. A global optimum would be one for every neighbourhood, but not conversely.
eh-f-203 · level facile · notes
A local search with neighbourhood $N$ starts from a feasible solution and moves to a better neighbour as long as it finds one. What does the final solution guarantee?
  1. It is a dual bound
  2. It is a local optimum with respect to $N$: no neighbour in $N$ is better
  3. It is an optimal solution of the problem
  4. It is better than every other solution obtainable with the same neighbourhood
Explanation. A local optimum may be much worse than the global optimum; with larger neighbourhoods local optima are better but cost more.
eh-f-204 · level facile · notes
In local search neighbourhoods are defined by small changes of the solution representation. What happens to a change producing an infeasible solution (without penalties)?
  1. It does not belong to the neighbourhood: only feasible neighbours are considered
  2. It is accepted and repaired at the end
  3. It is accepted only if it improves the objective
  4. It becomes the new current solution
Explanation. In basic local searches the neighbourhood contains only feasible neighbours; the alternative is to admit infeasible solutions with a penalty in the objective.
eh-f-205 · level facile · notes
In local search for the 0/1 knapsack with $n=10$ items, the current solution selects $|S|=4$ items. How many elements do the flip neighbourhood (adds or removes one item) and the swap neighbourhood (removes a selected item and adds an unselected one) have, before the capacity test?
  1. Flip $4$, swap $6$
  2. Flip $6$, swap $24$
  3. Flip $10$, swap $45$
  4. Flip $10$, swap $24$
Explanation. Flip: one element per item, $n=10$. Swap: $|S|(n-|S|)=4\cdot6=24$. $45=\binom{10}2$ would also count pairs of items both selected.
eh-f-206 · level ipotesi · notes
In the bin packing move neighbourhood an item is moved into another non-empty bin where it fits; moves into an empty bin are not allowed. Why does this restriction lose no useful move?
  1. Because empty bins have smaller capacity
  2. Because a move into an empty bin is always infeasible
  3. Moving an item into an empty bin cannot decrease the number of bins
  4. Because the number of bins never changes with a move
Explanation. The move would open a bin: at best it empties another one, leaving the number unchanged. A useful move must empty a bin without opening one.
eh-f-207 · level facile · notes
For $P\,||\,C_{\max}$ with $n=7$ jobs and $m=3$ machines, how many elements does the move neighbourhood have (one job goes to another machine), and why does swap consider only pairs of jobs with different durations?
  1. $7$; every job has a single move
  2. $14$; swapping two jobs of equal duration changes no load
  3. $21$; swapping two jobs of equal duration is infeasible
  4. $14$; swaps with equal durations always worsen
Explanation. Move: $n(m-1)=7\cdot2=14$, all feasible. A swap with $t_j=t_k$ leaves the loads unchanged, so there is no need to examine it.
eh-f-208 · level facile · notes
Minimization problem, current solution of value $20$. Its neighbours, in the fixed examination order, are worth $22$, $18$, $15$, $19$. Which neighbour does the first improvement rule choose and which the best improvement rule?
  1. First: the one of value $18$; best: the one of value $15$
  2. First: $22$; best: $15$
  3. First: $15$; best: $15$
  4. First: $18$; best: $18$
Explanation. First improvement takes the first neighbour better than $20$ in the order ($18$); best improvement examines all and takes the best ($15$).
eh-f-209 · level facile · notes
In local search, the best improvement rule examines the whole neighbourhood at every iteration. What can be said in general with respect to first improvement?
  1. First improvement always performs fewer iterations
  2. The two rules always reach the same local optimum
  3. Best improvement always finds the global optimum
  4. Every iteration costs more; neither rule guarantees a better local optimum than the other
Explanation. The two rules follow different paths and may stop in different local optima; best improvement makes larger but more expensive steps.
eh-f-210 · level facile · notes
A 2-opt move in the TSP removes two non-adjacent edges $\{a,b\}$ and $\{c,d\}$ of the tour $(\dots,a,b,\dots,c,d,\dots)$ and replaces them by $\{a,c\}$ and $\{b,d\}$, reversing the stretch from $b$ to $c$. By how much does the length change?
  1. $d_{ab}+d_{cd}-d_{ac}-d_{bd}$
  2. $d_{ac}+d_{bd}$
  3. $d_{ac}+d_{bd}-d_{ab}-d_{cd}$
  4. $d_{ad}+d_{bc}-d_{ab}-d_{cd}$
Explanation. The two new edges are added and the two old ones removed; with symmetric distances the reversed stretch has the same length. The move improves if the change is negative.
eh-f-211 · level facile · notes
A TSP instance with $10$ cities has an optimal tour of length $39$, and nearest neighbour from city $1$ finds a tour of length $49$. How many distinct tours does the instance have, and what relative gap does the initial tour have?
  1. $2^{10}$ tours; gap $10\%$
  2. $9!/2=181\,440$ tours; gap $\frac{49-39}{39}\approx25.6\%$
  3. $10!=3\,628\,800$ tours; gap $\approx25.6\%$
  4. $9!/2$ tours; gap $\frac{49-39}{49}\approx20.4\%$
Explanation. $(n-1)!/2$ with $n=10$. The gap with respect to the optimum is measured dividing by $z(I)=39$; 2-opt local search starts from here to reduce it.
eh-f-212 · level facile · notes
In the TSP, the sequence of neighbourhoods 2-opt, 3-opt, $k$-opt (Lin–Kernighan) illustrates a general trade-off of local search. Which one?
  1. A larger neighbourhood has better local optima but costs more to explore (3-opt: $O(n^3)$ per iteration)
  2. A larger neighbourhood has worse local optima
  3. Larger neighbourhoods are always faster
  4. Lin–Kernighan guarantees the global optimum
Explanation. Lin–Kernighan builds a variable number of exchanges greedily and stops when it no longer pays: it gets very good local optima at a reasonable cost.
eh-f-213 · level facile · notes
In $P\,||\,C_{\max}$ a swap exchanges job $j$ (duration $7$, on machine $a$) with job $k$ (duration $4$, on machine $b$). How do the loads $L_a$ and $L_b$ change?
  1. $L_a+3$ and $L_b-3$
  2. They do not change: a swap does not modify the loads
  3. $L_a-7$ and $L_b+4$
  4. $\delta=3$ is transferred from machine $a$ to machine $b$: $L_a-3$, $L_b+3$
Explanation. $L_a$ loses $7$ and gains $4$, $L_b$ the opposite: a swap transfers $t_j-t_k$, a move transfers $t_j$.
eh-f-214 · level facile · notes
In local search for bin packing, the objective «number of bins» rarely changes with a move or a swap. Why is the auxiliary objective $SQ=\sum_bL_b^2$ ($L_b$ = load of bin $b$) used?
  1. Because $SQ$ equals the number of bins
  2. Because $SQ$ decreases when the loads become more equal
  3. The landscape of the number of bins is flat; $SQ$ rewards moves concentrating the load, preparing the emptying of a bin
  4. Because $SQ$ is a dual bound
Explanation. With fixed total load, $\sum_bL_b^2$ is larger when the loads are unbalanced: increasing it progressively empties the least loaded bins.
eh-f-215 · level facile · notes
In the move local search for bin packing with objective $SQ=\sum_bL_b^2$ (to be maximized), moving item $j$ of weight $w_j$ from bin $a$ to bin $b$ changes $SQ$ by $2w_j(L_b-L_a+w_j)$. With $w_j=3$, $L_a=5$, $L_b=6$ (capacity $10$), is the move improving?
  1. Yes, but the change is $6$
  2. Yes: the change is $2\cdot3\cdot(6-5+3)=24>0$
  3. No: the change is $2\cdot3\cdot(6-5-3)=-12$
  4. No: bin $b$ exceeds the capacity
Explanation. $L_b+w_j=9\le10$, so the move is feasible, and it moves weight towards the more loaded bin: $SQ$ increases by $24$.
eh-f-216 · level facile · notes
The swap local search for bin packing exchanges two items of different weight in different bins, if both bins stay feasible. Why are items of equal weight not swapped, and what effect does a swap have on the number of bins?
  1. A swap of equal weights changes no load; a swap never changes the number of bins
  2. A swap of equal weights is infeasible; a swap may empty a bin
  3. A swap of equal weights increases $SQ$; a swap always reduces the bins
  4. No reason; a swap always increases the bins
Explanation. Every bin gives one item and receives one, so none is emptied: the swap serves to change the loads, and only the auxiliary objective $SQ$ sees its benefit.
eh-f-217 · level teorema · notes
For bin packing with auxiliary objective $SQ=\sum_bL_b^2$, a move of item $j$ from bin $a$ to the non-empty bin $b$ changes $SQ$ by $2w_j(L_b-L_a+w_j)$. Why does a move emptying bin $a$ always increase $SQ$?
  1. Because emptying a bin decreases $\sum_bL_b$
  2. It is not true: it may decrease $SQ$
  3. Because $L_b>L_a$ in every move
  4. Emptying $a$ means $L_a=w_j$, so the change is $2w_jL_b>0$
Explanation. With $L_a=w_j$ the term becomes $2w_j(L_b-w_j+w_j)=2w_jL_b$, positive since $b$ is not empty. Hence every move reducing the number of bins also improves $SQ$.
eh-f-218 · level teorema · notes
For $P\,||\,C_{\max}$ the auxiliary objective $\sum_hL_h^2$ (to be minimized) is used with move and swap. Which relation with the makespan holds?
  1. A move decreasing $\sum_hL_h^2$ always decreases the makespan
  2. The two functions are independent
  3. A move decreasing the makespan decreases $\sum_hL_h^2$, and one decreasing $\sum_hL_h^2$ does not increase the makespan
  4. A move decreasing the makespan increases $\sum_hL_h^2$
Explanation. Transferring load from the most loaded machine to a less loaded one reduces the sum of squares; the auxiliary objective also sees moves that are neutral for the makespan and balance the other machines.
eh-f-219 · level facile · notes
Bin packing with $c=7$: a solution has four bins with loads $(7,6,5,3)$. What is the auxiliary objective $SQ=\sum_bL_b^2$, and what would it be with the same weights in loads $(7,7,7)$?
  1. $441$ and $147$
  2. $119$ and $147$
  3. $21$ and $21$
  4. $119$ and $119$
Explanation. $49+36+25+9=119$; with three full bins $3\cdot49=147$. The total weight ($21$) does not change, but $SQ$ grows when the loads concentrate.
eh-f-220 · level facile · notes
In local search for the 0/1 knapsack, binary vectors exceeding the capacity can be excluded or admitted with a penalty. What does the second strategy maximize?
  1. The profit minus a penalty proportional to the weight in excess of the capacity
  2. The profit, ignoring the capacity
  3. The total weight
  4. The profit divided by the weight
Explanation. The function is $\sum_jp_jx_j-\alpha\max\{0,\sum_jw_jx_j-c\}$: the search space becomes all of $\{0,1\}^n$, and the search can cross the infeasible region.
eh-f-221 · level facile · notes
In the flip+swap local search for the 0/1 knapsack that stays feasible, with the first improvement rule, which flips can be improving?
  1. All flips
  2. No flip: only swaps improve
  3. Only those removing an item
  4. Only those adding an item (which fits in the residual capacity)
Explanation. With positive profits removing an item always worsens; a flip adding an item improves if the item fits. If one exists, the swaps are not examined.
eh-f-222 · level ipotesi · notes
In penalized local search for the 0/1 knapsack one maximizes $g_\alpha(x)=\sum_jp_jx_j-\alpha\max\{0,\sum_jw_jx_j-c\}$, with integer data. Why, with $\alpha>\max_jp_j$, does no flip from a feasible vector to an infeasible one increase $g_\alpha$?
  1. Because the penalty is $0$ on infeasible vectors
  2. Because with large $\alpha$ no item fits
  3. Adding item $k$ creates an excess $e\ge1$, and the change $p_k-\alpha e$ is negative
  4. Because $\alpha$ must be smaller than $\min_jp_j$
Explanation. With integer data the excess is at least $1$, hence $p_k-\alpha e\le p_k-\alpha<0$. With small $\alpha$, instead, the search may stop at an infeasible vector.
eh-f-223 · level teorema · notes
A local search stops at a local optimum of value $478$ on a TSP instance. What is known about the optimal value, without further information?
  1. That it is at most $478/2$
  2. Only that it is at most $478$: local search gives a primal bound, not a dual bound
  3. That it is exactly $478$, since the search stopped
  4. That it is at least $478$
Explanation. The local optimum is a feasible solution, i.e., one side of the gap. To know that $478$ is optimal a dual bound is needed, for instance from a MIP solver.
eh-f-224 · level ipotesi · notes
The change of a 2-opt move in the TSP is computed from the four edges involved only, $d_{ac}+d_{bd}-d_{ab}-d_{cd}$, even though the stretch between $b$ and $c$ is travelled backwards. Which assumption allows it?
  1. The distances are symmetric: reversing the stretch does not change its length
  2. The removed edges are adjacent
  3. The distances satisfy the triangle inequality
  4. The tour has an even number of cities
Explanation. In the asymmetric TSP the reversed stretch would change length, and the change would require summing all arcs of the stretch: this is why in the ATSP moves that do not reverse (like Or-opt) are preferred.
eh-f-225 · level facile · notes
The local search of the chapter is illustrated on four problems: 0/1 knapsack (KP), bin packing (BPP), TSP and $P\,||\,C_{\max}$. Which of them is a maximization problem?
  1. The BPP
  2. The TSP
  3. $P\,||\,C_{\max}$
  4. The KP: the profit is maximized
Explanation. BPP (number of bins), TSP (tour length) and $P\,||\,C_{\max}$ (makespan) are minimization problems: «better» means smaller value.
eh-f-226 · level facile · notes
A local search needs a feasible starting solution. Where does it usually come from?
  1. From the LP relaxation, without rounding
  2. From a dual bound
  3. From a constructive heuristic (greedy by efficiency, First Fit, nearest neighbour, LPT) or from a random feasible solution
  4. From an optimal solution
Explanation. The quality and diversity of the starting solutions influence the local optimum reached; multi-start repeats the search from many starts.
eh-f-227 · level facile · notes
In a local search experiment on $P\,||\,C_{\max}$ with $m=4$ machines and times $t=(11,10,9,8,7,7,6,5,4,4,3,2)$, the optimal value is $19$. Which simple lower bound certifies it?
  1. $\max_jt_j=11$
  2. $\lceil\sum_jt_j/m\rceil=\lceil76/4\rceil=19$
  3. $\sum_jt_j=76$
  4. $\lceil76/12\rceil=7$
Explanation. The sum of the times is $76$: a solution with makespan $19$ equals the average-load bound and is therefore optimal.
eh-f-389 · level teorema · notes
A tour of the symmetric TSP of length $40$; a 2-opt move removes the edges $\{u_1,v_1\}$ and $\{u_2,v_2\}$, with $d_{u_1v_1}=7$ and $d_{u_2v_2}=9$, and adds $\{u_1,u_2\}$ and $\{v_1,v_2\}$, with $d_{u_1u_2}=4$ and $d_{v_1v_2}=5$. How long is the new tour?
  1. $47$
  2. $25$
  3. $40$
  4. $33$
Explanation. $\Delta=d_{u_1u_2}+d_{v_1v_2}-d_{u_1v_1}-d_{u_2v_2}=4+5-7-9=-7$, hence $40-7=33$. The stretch between $v_1$ and $u_2$ is travelled backwards but, with symmetric distances, it has the same length.
eh-f-390 · level teorema · notes
Two loads $L_a=10$ and $L_b=6$; the amount $\delta=3$ is transferred from $a$ to $b$. How does the sum of the squared loads change?
  1. It decreases by $24$
  2. It does not change
  3. It decreases by $6$
  4. It increases by $6$
Explanation. The change is $2\delta(L_b-L_a+\delta)=2\cdot3\cdot(6-10+3)=-6$: indeed $7^2+9^2=130$ and $10^2+6^2=136$. The sum of the loads does not change, that of the squares does.
eh-f-391 · level teorema · notes
Local search for the 0/1 knapsack (maximization, integer profits) that moves only to strictly better neighbours: it starts from a solution of profit $9$ and the optimal value is $17$. At most how many moves does it make?
  1. $2^n$
  2. $8$
  3. $17$
  4. Exactly $8$
Explanation. Every move increases the profit by at least $1$ and the profit cannot exceed $z(I)=17$: at most $z(I)-f(x^0)=8$ moves. It may make fewer, stopping at a local optimum that is not global.
eh-f-392 · level teorema · notes
Variable neighbourhood descent uses the neighbourhoods $N_1,\dots,N_k$: it goes back to $N_1$ after every improvement and moves to the next neighbourhood when the current one does not improve. Where does it stop?
  1. At a local optimum for all the $k$ neighbourhoods
  2. At a local optimum for the neighbourhood $N_k$ only
  3. At an optimal solution of the instance
  4. After exactly $k$ moves
Explanation. It stops when none of the $k$ neighbourhoods contains a better neighbour: it is a local optimum for each of them. It is not necessarily a global optimum, and the number of moves is not fixed.
eh-f-393 · level ipotesi · notes
Why does a local search that moves only to strictly better neighbours terminate from every starting solution, even without an integer objective?
  1. The neighbourhood of the search is exact
  2. The choice rule is first improvement
  3. The objective function is convex
  4. The solutions are finite and $f$ always improves
Explanation. No solution is visited twice (the value improves strictly) and the solutions are finitely many. The integer objective is needed only for the bound $f(x^0)-z(I)$ on the number of moves.
eh-f-394 · level ipotesi · notes
Multi-start local search repeats the search from several starting solutions. Why must the starts be different (for instance random)?
  1. The neighbourhood changes with the starting solution
  2. Different starts are needed to compute the gap
  3. The same start leads to the same local optimum
  4. Otherwise the local search does not terminate
Explanation. With a deterministic choice rule the local search from a fixed start always reaches the same local optimum: repeating it is useless. Different starts explore different valleys.
eh-f-395 · level ipotesi · notes
Why does local search for bin packing need an auxiliary objective such as $\sum_bL_b^2$?
  1. $\sum_bL_b^2$ equals the number of bins used
  2. Almost every move leaves the number of bins unchanged
  3. The number of bins is not an integer value
  4. The moves often make the solutions infeasible
Explanation. The landscape of the number of bins is flat: almost every neighbour has the same value and the search stops at once. $\sum_bL_b^2$ rewards full bins and guides towards emptying one.
eh-f-396 · level ipotesi · notes
For $P\,||\,C_{\max}$ the swap neighbourhood (exchange of two jobs on different machines) is used besides move. In which situation is it needed?
  1. When every move overloads the receiving machine
  2. When there are more machines than jobs to assign
  3. When all the jobs have the same processing time
  4. When the makespan already equals the lower bound
Explanation. A solution can be a local optimum for move (every transfer creates a higher load) but not for swap, which moves jobs in both directions: this is the case of the $LPT$ solution.

4. Metaheuristics (107)

eh-f-228 · level facile · notes
In simulated annealing for a minimization problem the Metropolis rule is used. At temperature $T=3$ a neighbor that worsens the objective by $\delta=6$ is proposed. With which probability is it accepted?
  1. $1$
  2. $e^{-1/2}$
  3. $e^{-2}$
  4. $e^{2}$
Explanation. Metropolis rule: a worsening $\delta>0$ is accepted with probability $e^{-\delta/T}=e^{-6/3}=e^{-2}\approx 0.14$; an improvement is always accepted.
eh-f-229 · level facile · notes
Tabu search is a local search metaheuristic with a tabu list of moves forbidden for a number of iterations (the tabu tenure). Which statement is correct?
  1. It moves to the best non-tabu neighbor only if better; a tabu move is never allowed, even if it beats the best
  2. It moves to the best non-tabu neighbor even if worse; a tabu move is allowed if it beats the best solution found
  3. It moves to a random neighbor, accepted with probability $e^{-\delta/T}$; the tabu list forbids visited solutions forever
  4. It moves to the overall best neighbor; the tabu list only serves to stop the algorithm when full
Explanation. The tabu list is a short-term memory: the moves that undo the recent moves are forbidden for a number of iterations (the tenure). With tenure $0$ tabu search reduces to a local search.
eh-f-230 · level facile · notes
Metaheuristics (simulated annealing, tabu search, ILS, VNS, GRASP, LNS, genetic algorithms) explore the space of feasible solutions. Which kind of bounds do they produce?
  1. Only primal bounds: they do not know how far they are from the optimum
  2. The optimal value, if run long enough
  3. Only dual bounds: every solution found bounds the optimum
  4. Primal and dual bounds, whose gap closes over time
Explanation. Metaheuristics build feasible solutions; to measure their quality a dual bound from another source (relaxation, exact algorithm) is needed.
eh-f-231 · level facile · notes
GRASP (Greedy Randomized Adaptive Search Procedure) is a multi-start metaheuristic. What does it do at every iteration?
  1. It perturbs the current local optimum with a random kick and reapplies local search to the perturbed solution
  2. It destroys part of the current solution, repairs it with a heuristic and accepts the result if it is better
  3. It selects two parents from the population, recombines them and mutates the child, which replaces the worst individual
  4. It builds a solution with a randomized greedy on the restricted candidate list and improves it by local search
Explanation. GRASP is a multi-start method: randomized construction plus local search, and at the end the best solution found. The kick belongs to ILS, destroy and repair to LNS, recombination to genetic algorithms.
eh-f-232 · level facile · notes
A metaheuristic guides a local search beyond the first local optimum. In which ways does it get out?
  1. It solves the linear relaxation and rounds the solution found
  2. It sorts the elements and adds them one at a time to the solution
  3. It accepts worse solutions, jumps to a new start or combines solutions
  4. It shrinks the neighborhood, stops earlier or relaxes the constraints
Explanation. Accepting worsenings (simulated annealing, tabu search), jumping (ILS, VNS, GRASP, LNS), combining (genetic algorithms). The last two options describe an ILP-based and a constructive heuristic.
eh-f-233 · level facile · notes
What must every metaheuristic (simulated annealing, tabu search, ILS, VNS, GRASP, LNS, genetic algorithms) balance?
  1. Primal bounds and dual bounds
  2. Intensification and diversification
  3. Feasibility and optimality
  4. Construction time and memory
Explanation. Going down to the bottom of the current valley (intensifying) and leaving it for another (diversifying); every method has parameters fixing the balance.
eh-f-234 · level facile · notes
A metaheuristic is a strategy guiding a local search beyond the first local optimum. Which of the following methods is NOT a metaheuristic in this sense?
  1. A best improvement descent stopping at the first local optimum
  2. GRASP with randomized construction and local search
  3. Simulated annealing with the 2-opt neighborhood for the TSP
  4. Tabu search with the move neighborhood for $P\,||\,C_{\max}$
Explanation. The descent stops exactly where a metaheuristic starts working; the other three methods escape local optima.
eh-f-235 · level facile · notes
In the chapter on metaheuristics the algorithms are described for a minimization problem. How are they adapted to the 0/1 knapsack?
  1. The signs of the item weights are changed
  2. The weight of the chosen items is minimized
  3. They are not adapted: the knapsack needs other methods
  4. The inequalities are reversed: it is a maximization problem
Explanation. The knapsack maximizes profit: «better» becomes «larger», and the worsening of a move is $f(\text{current})-f(\text{neighbor})$.
eh-f-236 · level facile · notes
Which assumptions do the knapsack and bin packing instances (weights $w_j$, capacity $c$) used in the chapter on metaheuristics satisfy?
  1. All weights distinct and $\sum_jw_j=2c$
  2. $w_j\ge c$ for every item
  3. $w_j\le c$ for every item and $\sum_jw_j>c$
  4. $w_j<c/2$ for every item and $\sum_jw_j\le c$
Explanation. Every item fits alone, and they do not all fit together: otherwise knapsack and bin packing would be trivial.
eh-f-237 · level facile · notes
For $P\,||\,C_{\max}$ the metaheuristics compare two solutions lexicographically: first the makespan $C_{\max}$, on ties the sum $\sum_hL_h^2$ of squared loads. Three solutions have $(C_{\max},\sum_hL_h^2)$: $A=(11,249)$, $B=(11,267)$, $C=(12,245)$. What is the order from the best?
  1. $C$, $A$, $B$
  2. $A$, $B$, $C$
  3. $A$, $C$, $B$
  4. $B$, $A$, $C$
Explanation. $C$ has the worst makespan and comes last, even with the smallest sum; between $A$ and $B$, with equal makespan, the smaller sum wins.
eh-f-238 · level facile · notes
The local searches used inside metaheuristics are best improvement descents. How are ties between equally good moves broken?
  1. The first one found wins, with indices in increasing order
  2. All tied moves are performed together
  3. A move chosen at random among the tied ones wins
  4. The last one found wins, with indices in increasing order
Explanation. The fixed rule makes descents deterministic and examples reproducible; randomness enters only where the metaheuristic provides for it.
eh-f-239 · level facile · notes
In metaheuristics a random element of a list of $K$ elements is the one in position $1+\lfloor u\cdot K\rfloor$, where $u\in(0,1)$ is the random number. With $K=5$ and $u=0.7556$, which position is chosen?
  1. $3$
  2. $5$
  3. $1$
  4. $4$
Explanation. $\lfloor0.7556\cdot5\rfloor=\lfloor3.778\rfloor=3$, plus $1$: position $4$. Without the $+1$ one would get $3$.
eh-f-240 · level facile · notes
With the Park–Miller generator ($seed\leftarrow16807\,seed\,\mathrm{mod}\,(2^{31}-1)$, $u=seed/(2^{31}-1)$) and $seed=1$, the first number is $u\approx0.0000078$. Is it an error?
  1. Yes: the first number must always be discarded
  2. No, but the following numbers are all close to $0$
  3. No: with a small seed the first number is always close to $0$
  4. Yes: the generator must be initialized with a large seed
Explanation. $16807/(2^{31}-1)$ is small by construction; the following numbers ($0.1315$, $0.7556$, …) are spread normally over the interval.
eh-f-241 · level facile · notes
Which metaheuristic escapes a local optimum by accepting worsening moves deterministically, with a memory forbidding a return to the solutions just visited?
  1. Simulated annealing
  2. Tabu search
  3. Iterated local search
  4. GRASP
Explanation. Simulated annealing accepts worsenings at random; ILS and GRASP jump to new starts.
eh-f-242 · level facile · notes
Among metaheuristics, which keep a single current solution and change the acceptance rule, which jump to new starting points, and which works with many solutions?
  1. SA and TS; ILS, VNS, GRASP and LNS; genetic algorithms
  2. TS and LNS; SA, ILS, VNS and GRASP; genetic algorithms
  3. ILS and VNS; SA, TS, GRASP and LNS; genetic algorithms
  4. SA and GRASP; TS, ILS, VNS and LNS; genetic algorithms
Explanation. Simulated annealing and tabu search go through worse solutions; ILS, VNS, GRASP and LNS generate a new starting point; genetic algorithms keep a population.
eh-f-243 · level facile · notes
Which metaheuristic–idea pair for escaping a local optimum is correct?
  1. GRASP: perturb the local optimum and restart from there
  2. VNS: restart every time from a randomized construction
  3. ILS: use a larger neighborhood when the search is stuck
  4. LNS: destroy and repair a large part of the solution
Explanation. Perturbing the local optimum is ILS, restarting from a randomized construction is GRASP, changing the neighborhood is VNS.
eh-f-244 · level facile · notes
Why does simulated annealing (random neighbor, accepted if better or, if worse, with a probability depending on the temperature) store the best visited solution separately?
  1. To be able to restart from scratch at each new temperature
  2. Because the final temperature is always too high
  3. It leaves local optima: the final solution may be worse
  4. Because the current solution is always infeasible
Explanation. A local optimum is left as soon as a worsening move is accepted, so the best solution may have been visited long before the end.
eh-f-245 · level facile · notes
In simulated annealing for a minimization problem, a neighbor with worsening $\delta$ is accepted with probability $1$ if $\delta\le0$ and $e^{-\delta/T}$ if $\delta>0$. What happens to moves with $\delta=0$?
  1. They are accepted with probability $\frac12$, at random
  2. Always accepted: the search moves across plateaus
  3. They are never accepted, at any temperature
  4. They are accepted only with probability $e^{-1/T}$
Explanation. $\delta=0$ falls into the first case: probability $1$. This is what lets simulated annealing cross the plateaus of flat objectives.
eh-f-246 · level facile · notes
Simulated annealing with geometric schedule $T\leftarrow\alpha T$, $L$ moves per temperature, and stop when $T\le T_{\min}$. With $T_0=10$, $\alpha=0.5$, $T_{\min}=1$ and $L=4$, how many iterations does it perform?
  1. $16$
  2. $40$
  3. $12$
  4. $20$
Explanation. Temperatures $10$, $5$, $2.5$, $1.25$; the next, $0.625\le1$, stops the search: $4$ temperatures times $4$ moves.
eh-f-247 · level facile · notes
In simulated annealing a rule for the initial temperature sets $T_0=-\bar\delta/\mathrm{ln}\,\chi_0$, where $\bar\delta$ is the average worsening of random moves and $\chi_0$ the desired initial acceptance rate. With $\bar\delta=10$ and $\chi_0=0.8$, what is $T_0$ approximately?
  1. $8$
  2. $12.5$
  3. $2.2$
  4. $44.8$
Explanation. $\mathrm{ln}\,0.8\approx-0.223$, hence $T_0\approx10/0.223\approx44.8$, and $e^{-10/44.8}\approx0.8$.
eh-f-248 · level facile · notes
Simulated annealing with the 2-opt neighborhood on the $5$-city TSP (optimum $18$), temperatures $5$, $4$, $3.2$: at iterations $1$ and $3$ it accepts worse tours ($25\to29$, $22\to24$), at iterations $5$ and $6$, at a lower temperature, it rejects two worsenings, and it returns $18$. What does it show?
  1. At low temperature every move is accepted
  2. The returned tour is the last visited, not the best
  3. The mechanism: worsenings accepted early, rejected later
  4. Simulated annealing always worsens the solution
Explanation. The probability $e^{-\delta/T}$ drops with $T$; the best visited tour is returned. On this instance 2-opt would also find the optimum: the example shows the mechanism.
eh-f-249 · level facile · notes
Penalized simulated annealing on the knapsack ($c=9$, optimum $(1,1,0,0)$ of profit $17$): from $(1,0,1,0)$, a local optimum for feasible flips, it moves to the infeasible solution $(1,1,1,0)$ (weight $12$) and then, removing item $3$, reaches the optimum. What does it show?
  1. Infeasible solutions must always be discarded
  2. The infeasible region acts as a bridge between two valleys
  3. The penalty makes every vector feasible
  4. The optimum is found only with feasible flips
Explanation. With feasible flips alone $(1,0,1,0)$ is stuck; with the penalty the search crosses an infeasible vector and reaches another valley.
eh-f-250 · level facile · notes
In penalized simulated annealing for the knapsack one maximizes $f_\beta(x)=\sum_jp_jx_j-\beta\max\{0,\sum_jw_jx_j-c\}$ over all $x\in\{0,1\}^n$. Which solutions can update the stored best solution?
  1. Only the feasible ones
  2. Only those accepted at the minimum temperature
  3. Any solution with larger $f_\beta$
  4. Only those with weight excess at most $1$
Explanation. The search can visit infeasible vectors, but the returned solution must be feasible: the best is updated only with those.
eh-f-251 · level facile · notes
Simulated annealing on a $20$-city TSP (optimum $291$), $10$ runs per parameter setting: with $\alpha=0.9$ and $T_0=1$ ($700$ iterations) the optimum is found $1$ time; with $\alpha=0.99$ and $T_0=20$ ($36\,800$ iterations) $10$ times. What does the table show?
  1. A low initial temperature always gives the best results
  2. The number of iterations does not affect the result
  3. A single run is enough to compare parameters
  4. Slow cooling helps, but costs many more iterations
Explanation. With $T_0=1$ few worsenings are accepted and the search is almost a local search; with $\alpha$ close to $1$ more iterations are spent at each temperature. Parameters trade quality for time.
eh-f-252 · level teorema · notes
At fixed temperature simulated annealing is a Markov chain. Under which assumptions is its unique stationary distribution the Boltzmann distribution $\pi_T(S)\propto e^{-f(S)/T}$?
  1. Integer and positive objective values
  2. Exact neighborhood of constant size
  3. Symmetric and connected neighborhood
  4. Geometric cooling schedule
Explanation. Symmetric ($S'\in N(S)$ if and only if $S\in N(S')$, neighborhoods of the same size) and connected (every solution reaches every other). The cooling schedule plays no role: the temperature is fixed.
eh-f-253 · level facile · notes
Hajek (1988) proved that simulated annealing with the logarithmic schedule $T_k=\Gamma/\mathrm{ln}\,(k+1)$ ($\Gamma$ large enough) drives the probability of being in an optimal solution to $1$. Why is the geometric schedule used in practice?
  1. Because the logarithmic schedule holds only for the TSP
  2. It is a guarantee in the limit: too many iterations are needed
  3. Because the geometric schedule has the same guarantee
  4. Because the logarithmic schedule never converges
Explanation. The iterations required can exceed the number of solutions; the geometric schedule is much faster, but without guarantees.
eh-f-254 · level facile · notes
Tabu search for $P\,||\,C_{\max}$ (move neighborhood, lexicographic comparison, tabu tenure $6$) from the $LPT$ solution with loads $(11,8,8)$: at iteration $5$ the neighbors with makespan $11$ are all tabu, and the search moves to a neighbor with makespan $12$; at iteration $8$ it reaches $(9,9,9)$. What does it show?
  1. A worsening non-tabu move gets it off the plateau
  2. Makespan $12$ is the returned value
  3. Tabu search never accepts worsening moves
  4. The tabu list prevents reaching the optimum
Explanation. A local search would stop on the plateau of makespan $11$; tabu search goes to the best non-tabu neighbor even if worse, and then drops to $10$ and to $9=\mathrm{LB}$.
eh-f-255 · level facile · notes
In tabu search for the TSP with the 2-opt neighborhood, what are the tabu attributes?
  1. The two cities just moved, which stay fixed forever
  2. The tours already visited, stored in full
  3. The edges just added, which cannot be removed
  4. The two edges just removed, which cannot come back for a while
Explanation. For $tenure$ iterations the removed edges cannot be put back into the tour, unless the move gives a tour shorter than the best (aspiration).
eh-f-256 · level facile · notes
Tabu search on the medium instances: on the $20$-city TSP a tabu tenure $1$ suffices to reach the optimum ($0$ stays at $319$), on $P\,||\,C_{\max}$ with $15$ jobs a tenure $15$ is needed (with $20$ or more the optimum is lost again). What do the results show?
  1. The tabu tenure does not affect the result
  2. Without memory tabu search always finds the optimum
  3. The tabu tenure must be tuned to problem and instance
  4. A long tabu tenure is always the best choice
Explanation. With tenure $0$ the search cycles; on the plateau of $P\,||\,C_{\max}$ a long list is needed, but a list that is too long forbids too much.
eh-f-257 · level facile · notes
Iterated local search has three components: local search, perturbation (kick) and acceptance criterion. What role does each play?
  1. Diversifies; intensifies; balances the two
  2. Intensifies; diversifies; balances the two
  3. Balances; intensifies; diversifies
  4. Intensifies; balances; diversifies
Explanation. Local search goes to the bottom of the valley, the kick moves to another valley, acceptance (only better optima or worse ones too) decides the balance.
eh-f-258 · level facile · notes
Iterated local search on a $20$-city TSP (optimum $291$): from the 2-opt local optimum of length $319$, the first double bridge kick gives a tour of length $432$, which 2-opt search brings to $303$ (accepted); the second kick leads to $291$. What does it show?
  1. The kick worsens; the descent repairs and keeps the good parts
  2. ILS accepts only tours worse than the current one
  3. The kick must immediately improve the perturbed tour
  4. Local search always undoes the effect of the kick
Explanation. The perturbed tour is much worse, but local search repairs the long edges created by the kick and keeps the good parts; with $100$ iterations the optimum is found with all $10$ seeds.
eh-f-259 · level facile · notes
In VNS for $P\,||\,C_{\max}$, the neighborhood $N_k$ contains the assignments obtained by moving $k$ jobs. Why does $N_2$ contain the swap neighborhood (exchange of two jobs on different machines)?
  1. Because $N_2$ contains all solutions
  2. Because a swap moves a single job
  3. Because $N_2$ coincides with the move neighborhood
  4. A swap is the combination of two moves
Explanation. Exchanging $j$ and $k$ amounts to moving $j$ to $k$'s machine and $k$ to $j$'s: shaking with $k=2$ reproduces the swaps the move neighborhood cannot see.
eh-f-260 · level facile · notes
VNS for $P\,||\,C_{\max}$ (local search with the move neighborhood) on the instance with initial loads $(11,8,8)$: at iteration $3$, with $k=2$, two random moves and the descent in effect swap jobs $1$ and $4$, reaching the optimum $(9,9,9)$. What does it show?
  1. Shaking with $k=1$ is always enough
  2. VNS does not use local search
  3. Shaking in $N_2$ finds a swap that move cannot see
  4. Move local search finds the optimum by itself
Explanation. The current solution was a local optimum for move; the jump into $N_2$ followed by the descent performs an improving swap.
eh-f-261 · level facile · notes
GRASP for the knapsack: the restricted list contains the candidate items with efficiency $p_j/w_j\ge e_{\max}-\alpha(e_{\max}-e_{\min})$. The efficiencies of the four candidate items are $2$, $1.75$, $2$, $\frac43$. With $\alpha=\frac14$, which items enter the list?
  1. Items $1$, $3$ and $2$
  2. Items $1$ and $3$
  3. Only item $1$
  4. All four items
Explanation. Threshold $2-\frac14\cdot\frac23=\frac{11}6\approx1.83$: only the efficiencies $2$ pass. With $\alpha=\frac12$ the threshold is $\frac53$ and item $2$ also enters.
eh-f-262 · level facile · notes
GRASP with $20$ iterations, $10$ runs: on the $20$-city TSP with $\alpha=0$ the result is $319$ in every run, with $\alpha=0.1$ it is the optimum $291$ in every run. What does it show?
  1. $\alpha=0$ repeats one run; a little randomness suffices
  2. The value of $\alpha$ does not affect the result
  3. With $\alpha=0$ GRASP always finds the optimum
  4. More randomness always worsens the result
Explanation. With $\alpha=0$ every iteration builds the greedy tour and local search always reaches the same local optimum; a little randomization diversifies the starts.
eh-f-263 · level facile · notes
GRASP iterations are independent and do not learn from one another. What does «reactive» GRASP add?
  1. A tabu list of the solutions already built
  2. An exact local search at every single iteration
  3. Crossover between the best solutions found
  4. It adapts the parameter $\alpha$ to the results obtained
Explanation. It is one of the extensions with memory; another is path relinking, which explores the solutions between two good local optima.
eh-f-264 · level facile · notes
LNS on the $5$-city TSP (optimum $18$): from the tour $(1,3,2,4,5)$ of length $25$ cities $3$ and $2$ are removed and reinserted by cheapest insertion, giving $(1,4,2,5,3)$ of length $18$. What does the example show?
  1. LNS is a 2-opt local search
  2. Removing cities always worsens the final tour
  3. A single destroy-and-repair step changes many edges
  4. Repair always puts the cities back where they were
Explanation. The step changes four edges of the tour, which a single 2-opt move cannot do: the LNS neighborhood is large.
eh-f-265 · level facile · notes
In large neighbourhood search for the TSP $q$ cities are removed and reinserted. Why is its neighborhood not explored move by move, as in a local search?
  1. Because it contains a single solution
  2. It is huge: the repair method explores it implicitly
  3. Because moves cannot be evaluated
  4. Because destruction is always deterministic
Explanation. There are $\binom{n-1}{q}$ ways to choose the removed cities and many ways to reinsert them: the repair method (heuristic or exact) searches for a good neighbor.
eh-f-266 · level teorema · notes
LNS for bin packing from the First Fit Decreasing solution ($10$ bins, optimum $9$): emptying $q=3$ bins and repairing exactly reaches $9$ in every run, but with $q=2$ even exact repair always fails. Why?
  1. The items of two FFD bins never fit into one
  2. Because FFD already uses the minimum number of bins
  3. Because exact repair with two bins is too slow
  4. Because with $q=2$ the fullest bin is always emptied
Explanation. FFD is an Any Fit algorithm: two of its bins together weigh more than $c$, so reoptimizing two never saves a bin. With three, the items can fit into two.
eh-f-267 · level facile · notes
In LNS for bin packing some bins are emptied and the removed items repacked. When is the new packing accepted?
  1. Only if it uses fewer bins than the current solution
  2. Always, even if it uses more bins than the current one
  3. If $\sum_bL_b^2$ decreases, whatever the number of bins
  4. If it uses fewer bins, or as many and $\sum_bL_b^2$ not smaller
Explanation. On the plateaus of the number of bins, the auxiliary objective $\sum_bL_b^2$ ($L_b$ load of bin $b$) pushes towards fuller bins.
eh-f-268 · level facile · notes
Adaptive LNS on the $20$-city TSP with two destroy methods (random removal and worst removal, which removes the cities whose removal shortens the tour most): at the end the weights are between $0.77$ and $0.98$ for random, between $0.03$ and $0.08$ for worst removal. What does it show?
  1. The weights do not depend on the results of the iterations
  2. Random removal is almost never used
  3. The method learned that worst removal does not pay here
  4. Worst removal is always the best method
Explanation. From a good tour, removing the badly placed cities and reinserting them by cheapest insertion almost always rebuilds a tour that is not better: the weight of worst removal collapses.
eh-f-269 · level facile · notes
On the $20$-city TSP simple LNS with random removal does slightly better than adaptive LNS (ALNS). When does adaptivity pay off?
  1. With a single destroy method available
  2. With many methods of unknown quality and long runs
  3. Only on very small and easy instances
  4. Never: simple LNS is always better than ALNS
Explanation. ALNS learns the weights of the methods during the search: it helps when there are many methods to choose from and enough iterations to learn.
eh-f-270 · level facile · notes
Genetic algorithm for the knapsack ($c=9$, $p=(10,7,6,4)$, $w=(5,4,3,3)$): repair removes the selected item of minimum efficiency $p_j/w_j$ (ties: largest index) until the weight does not exceed $c$. Which individual is obtained from the child $(1,1,0,1)$, of weight $12$?
  1. $(1,1,0,0)$
  2. $(1,1,0,1)$
  3. $(0,1,0,1)$
  4. $(1,0,0,1)$
Explanation. Efficiencies of the selected items: $2$, $1.75$, $1.33$; item $4$ is removed: weight $9$, profit $17$, the optimum.
eh-f-271 · level facile · notes
In a steady-state genetic algorithm, the child replaces the worst individual if it is better and not already in the population. Why are duplicates discarded?
  1. Because a duplicate is always infeasible
  2. Because selection does not work with duplicates
  3. Because a duplicate always has minimum fitness
  4. They would make the population lose diversity
Explanation. With many copies of the same individual, crossover and selection always produce the same children and the search gets stuck.
eh-f-272 · level facile · notes
The final table of the chapter compares the metaheuristics on four medium instances, with $10$ runs each. Does it establish a ranking of the methods?
  1. Yes: the method with the lowest average wins
  2. No, because the methods are all deterministic
  3. No: many instances and equal running times would be needed
  4. Yes: the method with most optimal runs wins
Explanation. It shows that results depend on parameters and components; a ranking needs many instances and a comparison at equal time.
eh-f-273 · level facile · notes
In every metaheuristic a parameter fixes the balance between intensification and diversification. Which one fixes it in GRASP (randomized construction plus local search)?
  1. The tabu tenure of the forbidden moves
  2. The parameter $\alpha$ of the restricted list
  3. The initial temperature $T_0$ of the cooling
  4. The maximum shaking size $k_{\max}$
Explanation. $\alpha$ decides how random the construction is; the tabu tenure belongs to tabu search, $T_0$ to simulated annealing, $k_{\max}$ to VNS.
eh-f-274 · level facile · notes
In a genetic (or memetic) algorithm, which components intensify the search?
  1. Selection and replacement (plus local search if memetic)
  2. Only the random generation of the initial population
  3. Crossover and mutation of the generated children
  4. Only the mutation of the child's genes
Explanation. Selection and replacement concentrate the population on good solutions; crossover and mutation diversify.
eh-f-275 · level facile · notes
In tuning the parameters of a metaheuristic, why is adjusting one parameter at a time a bad idea?
  1. Because it requires different training instances
  2. Because the parameters do not affect the result
  3. Because every parameter should keep its default value
  4. It ignores interactions: for SA the best $T_0$ depends on $\alpha$
Explanation. Tools like irace tune all parameters together; evaluating on instances different from the training ones remains necessary.
eh-f-276 · level facile · notes
Two metaheuristics have the same average quality on the test instances. Which one is preferable according to the notes?
  1. The one with more parameters to tune
  2. The one tuned on the same test instances
  3. The one that works well over a wide range of parameters
  4. The one that works very well over a narrow range
Explanation. A method robust to its parameters transfers better to new instances; tuning on the evaluation instances gives an optimistic picture.
eh-f-277 · level facile · notes
What do the metaheuristics of the chapter (simulated annealing, tabu search, ILS, VNS, GRASP, LNS, genetic algorithms) NOT use?
  1. Neighborhoods and local searches on solutions
  2. Problem relaxations and MIP solvers
  3. Random numbers from the Park–Miller generator
  4. Starting solutions from constructive heuristics
Explanation. They handle only feasible (or penalized) solutions and produce only primal bounds; quality was measured thanks to optima computed separately.
eh-f-278 · level facile · notes
In LNS for bin packing, exact repair (reoptimizing the items of a few bins, with the rest fixed) reached the optimum where FFD repair failed. What does it suggest?
  1. Exactly reoptimizing a part gives very powerful neighborhoods
  2. Repair does not matter: only destruction matters
  3. Metaheuristics must always use exact algorithms
  4. FFD is an exact algorithm for bin packing
Explanation. It is the idea of ILP-based heuristics: fix part of the solution and solve the remaining subproblem exactly.
eh-f-279 · level facile · notes
In the metaheuristics for bin packing and $P\,||\,C_{\max}$, solutions with the same objective are compared by the sum of the squared loads. In which direction is it optimized in the two problems?
  1. Minimized in both, because balanced loads are always better
  2. Maximized in both, because the total is fixed
  3. Bin packing: minimized; $P\,||\,C_{\max}$: maximized
  4. Bin packing: maximized (items in few full bins); $P\,||\,C_{\max}$: minimized (balanced loads)
Explanation. In bin packing we want to empty a bin, and the sum of squares grows when weight concentrates; in $P\,||\,C_{\max}$ we want to lower the largest load, and the sum decreases when loads balance.
eh-f-280 · level facile · notes
The metaheuristics of the module use pseudo-random numbers generated by the Park and Miller method from a seed. Why are the results reported over several seeds?
  1. Because different seeds change the instance solved
  2. Because every seed gives a different global optimum
  3. The result of a metaheuristic depends on the random numbers: a single seed is not enough to evaluate it
  4. Because with a single seed the metaheuristic does not terminate
Explanation. The instance is the same, but the random choices change the path: minimum, average and maximum over several runs are reported, as recommended for every randomized heuristic.
eh-f-281 · level facile · notes
In simulated annealing the temperature is lowered with the rule $T\leftarrow\alpha T$, with $0<\alpha<1$. What effect does the temperature have on accepting a neighbour worse by $\delta>0$, accepted with probability $e^{-\delta/T}$?
  1. The temperature changes only the number of iterations, not the acceptance
  2. At high temperature worsenings are often accepted (diversification); at low temperature almost never (intensification)
  3. At low temperature all neighbours are accepted
  4. At high temperature worsenings are never accepted
Explanation. $e^{-\delta/T}$ tends to $1$ for large $T$ and to $0$ for small $T$: cooling moves gradually from exploration to descent, as in the annealing of metals.
eh-f-282 · level facile · notes
In tabu search the tabu list does not store the visited solutions but attributes of the recent moves (for example «job $j$ on machine $h$»), for a fixed tabu tenure. Which problem does this create, and how is it repaired?
  1. It also forbids solutions never visited; the aspiration criterion admits a tabu move that beats the best solution found
  2. It does not prevent going back to the solution just left; it is repaired with infinite tenure
  3. It makes the search random; it is repaired with the Metropolis criterion
  4. It forbids only the current solution; it is repaired by storing the whole path
Explanation. An attribute forbids all solutions containing it, not only the one left. Aspiration restores the tabu moves that would lead to a new record.
eh-f-283 · level facile · notes
Iterated local search ($ILS$) repeats: perturbation of the current local optimum, local search, acceptance criterion. What role does the strength of the perturbation play?
  1. The stronger, the better the result always is
  2. It does not matter: the local search undoes any perturbation
  3. Too weak: the search does not terminate; too strong: the search becomes exact
  4. Too weak: the local search returns to the same optimum; too strong: it nearly restarts from a random solution
Explanation. The perturbation must leave the current valley without losing the structure of the good solution: with too strong a perturbation $ILS$ degenerates into multi-start.
eh-f-284 · level facile · notes
In iterated local search ($ILS$) for the TSP with the 2-opt local search, the double bridge is used as perturbation: it cuts the tour into four segments $A,B,C,D$ and reconnects them as $A\,C\,B\,D$. Why is it suitable?
  1. It changes a single edge, so it does not lose the tour structure
  2. It is a 2-opt move, so the local search always accepts it
  3. It changes three edges without reversing segments, and a single 2-opt move does not easily undo it
  4. It always returns a shorter tour
Explanation. The double bridge is a move that 2-opt does not contain and cannot undo in one step: it moves the search to another valley while keeping most of the tour.
eh-f-285 · level facile · notes
In variable neighbourhood search ($VNS$) the neighbourhood $N_k$ contains the solutions obtained with $k$ moves. At every iteration a random solution of $N_k$ is chosen (shaking) and improved by a local search. How is $k$ updated?
  1. If the local optimum is better $k+1$; otherwise back to $k=1$
  2. If the local optimum found is better it is accepted and $k=1$ again; otherwise $k+1$
  3. $k$ is chosen at random at every iteration
  4. $k$ always increases by $1$, whatever the result
Explanation. The search explores close to the current optimum first and goes farther only when the neighbourhood gives no improvement: shaking diversifies, local search intensifies.
eh-f-286 · level facile · notes
What is the difference between variable neighbourhood descent ($VND$) and variable neighbourhood search ($VNS$)?
  1. $VND$ explores the neighbourhoods completely and deterministically; $VNS$ draws random solutions from them (shaking) and then applies a local search
  2. $VND$ is randomized, $VNS$ is deterministic
  3. $VND$ uses one neighbourhood, $VNS$ several
  4. They are the same algorithm with two names
Explanation. $VND$ stops at a local optimum for all the neighbourhoods; $VNS$ uses the growing neighbourhoods to jump out of local optima, and is a metaheuristic.
eh-f-287 · level facile · notes
In $GRASP$ every iteration builds a solution with a randomized greedy (restricted candidate list with parameter $\alpha$) and improves it with a local search. What happens with $\alpha=0$?
  1. The construction becomes completely random
  2. The local search is no longer run
  3. $GRASP$ always finds the global optimum
  4. Every iteration builds the same greedy solution: $GRASP$ becomes a single local search
Explanation. With $\alpha=0$ the list contains only the best candidates, and up to ties the construction is always the same; a little randomness is enough to get different solutions.
eh-f-288 · level facile · notes
In large neighbourhood search ($LNS$) a destroy method removes part of the solution and a repair method rebuilds it. What roles do the two methods play?
  1. Both intensify: $LNS$ does not diversify
  2. Destroy intensifies, repair diversifies
  3. Destroy (usually random) diversifies, repair intensifies
  4. Both diversify, and local search intensifies
Explanation. Removing different parts moves the search, and the number $q$ of removed elements controls how far; repair rebuilds the removed part as well as possible, with a heuristic or even exactly.
eh-f-289 · level facile · notes
In $LNS$ for bin packing, some bins of a First Fit Decreasing (FFD) solution are emptied and the removed items are repacked by FFD itself. What happens?
  1. The solution becomes infeasible
  2. The solution never improves: FFD repacks the removed items the same way
  3. The optimum is always obtained after one iteration
  4. The solution always improves by at least one bin
Explanation. Repairing with the same algorithm that built the solution repeats the same choices; with an exact repair of the subproblem, instead, $LNS$ can empty a bin.
eh-f-290 · level facile · notes
In a genetic algorithm for the 0-1 knapsack with binary encoding, one-point crossover with cut $cut=2$ combines parents $(1,1,0,0,1)$ and $(0,1,1,1,0)$. Which child does it produce, taking the first $cut$ genes from the first parent?
  1. $(1,1,1,1,0)$
  2. $(0,1,0,0,1)$
  3. $(1,1,0,1,0)$
  4. $(1,1,0,0,0)$
Explanation. Genes $1,2$ from the first parent, $(1,1)$, and genes $3,4,5$ from the second, $(1,1,0)$. The child may exceed the capacity and must be repaired, for example by removing the items of minimum efficiency.
eh-f-291 · level facile · notes
What distinguishes a memetic algorithm from a genetic algorithm?
  1. It uses no crossover, only mutation
  2. It uses a single solution instead of a population
  3. It accepts worsenings with the Metropolis rule
  4. Every new individual is improved by a local search before entering the population
Explanation. The memetic algorithm combines recombination of the population (diversification) with local search on every child (intensification).
eh-f-292 · level facile · notes
A metaheuristic is a general strategy guiding a local search beyond the first local optimum. Why is it called a scheme and not an algorithm?
  1. Because it never uses local search
  2. Because it guarantees the optimum only for some problems
  3. It becomes an algorithm only by choosing representation, neighbourhoods, local search and parameters
  4. Because it never terminates
Explanation. The same scheme (e.g., tabu search) gives very different algorithms for the TSP and for $P\,||\,C_{\max}$, depending on the choices and the calibration.
eh-f-293 · level facile · notes
Multi-start repeats local search from many starting solutions. Which limit do metaheuristics try to overcome?
  1. Multi-start is deterministic
  2. Every start ignores what was learned before, while good valleys are usually close to other good valleys
  3. Multi-start never finds local optima
  4. Multi-start requires a dual bound
Explanation. Metaheuristics escape a local optimum while staying close to what was found: accepting worse moves (SA), forbidding recent moves (TS), perturbing (ILS) or changing neighbourhood (VNS).
eh-f-294 · level facile · notes
In simulated annealing for a minimization problem, a neighbour worse by $\delta>0$ is accepted with probability $e^{-\delta/T}$, where $T$ is the temperature. With $\delta=3$ and $T=3$, about how much is it?
  1. $e^{-1}\approx0.37$
  2. $e^{-3}\approx0.05$
  3. $1$
  4. $e^{-9}\approx0.0001$
Explanation. $\delta/T=1$. At high temperature almost all worse moves are accepted; as $T$ decreases the search becomes a descent.
eh-f-295 · level facile · notes
In simulated annealing with penalties for the 0/1 knapsack one maximizes $f_\beta(x)=\sum_jp_jx_j-\beta\max\{0,\sum_jw_jx_j-c\}$. A vector has profit $30$ and weight $14$, with $c=10$ and $\beta=2$. What is $f_\beta$, and can it become the best solution found?
  1. $30$; no
  2. $2$; no
  3. $22$; yes, because $f_\beta$ is high
  4. $22$; no, the best solution is updated only with feasible solutions
Explanation. $30-2\cdot4=22$. The vector is infeasible: the search may cross it, but does not return it.
eh-f-296 · level facile · notes
In a simulated annealing experiment on the TSP with $20$ cities, starting from a tour of length $326$, in the first iterations the current tour reaches length $765$. How is this explained?
  1. Simulated annealing has an implementation bug
  2. The initial tour was infeasible
  3. At the start the temperature is high compared to typical worsenings, and almost all worse moves are accepted
  4. The initial temperature was too low
Explanation. At high temperature the search is almost a random walk (diversification); cooling, it concentrates on good solutions (intensification).
eh-f-297 · level teorema · notes
At fixed temperature $T$ and with a symmetric neighbourhood, simulated annealing has stationary distribution $\pi_T(S)\propto e^{-f(S)/T}$ (minimization). With $f(S_1)=10$, $f(S_2)=12$ and $T=2$, what is $\pi_T(S_1)/\pi_T(S_2)$?
  1. $e^{2}\approx7.39$
  2. $e\approx2.72$
  3. $e^{-1}\approx0.37$
  4. $\frac56$
Explanation. $\pi_T(S_1)/\pi_T(S_2)=e^{(f(S_2)-f(S_1))/T}=e^{2/2}=e$: the better solution is more likely, the more so the lower $T$.
eh-f-298 · level facile · notes
In tabu search for $P\,||\,C_{\max}$ with the move neighbourhood, after moving job $j$ from machine $h$ to another one, the attribute $(j,h)$ becomes tabu for a number of iterations. What does it forbid?
  1. To bring job $j$ back to machine $h$, so as not to return immediately to the solution just left
  2. To move any job to machine $h$
  3. To move job $j$ again anywhere
  4. To use machine $h$ until the end
Explanation. Tabu search moves to the best non-tabu neighbour even if worse; the tabu list prevents undoing the move immediately, and hence cycling.
eh-f-299 · level facile · notes
In tabu search for the TSP with the 2-opt neighbourhood, the edges removed by a move stay tabu for a number of iterations called tabu tenure. What happens with a tenure that is too short or too long?
  1. The tenure has no effect on the results
  2. Too long: tabu search becomes simulated annealing
  3. Too short: the search stops at once; too long: it cycles
  4. Too short: the search may cycle; too long: it forbids too many moves and the search becomes rigid
Explanation. The tenure balances diversification and intensification; the experiments on the medium instances show that the right value depends on the instance.
eh-f-300 · level facile · notes
Iterated local search for the TSP uses 2-opt local search and, as perturbation (kick), the double bridge move. Why is a kick used that local search cannot easily undo?
  1. Because the double bridge always improves the tour
  2. Because local search does not accept worse tours
  3. If local search could undo it with a single move, it would immediately return to the starting local optimum
  4. Because the kick must make the tour infeasible
Explanation. The double bridge is a 4-opt move: 2-opt does not undo it in one step, so the next descent explores a nearby but different valley.
eh-f-301 · level facile · notes
In variable neighbourhood search with neighbourhoods $N_1,\dots,N_{k_{\max}}$ of increasing size, after shaking in $N_k$ and local search, what is done if the new local optimum is better and if it is not?
  1. In both cases one restarts from a random solution
  2. If better: it is accepted and one goes back to $k=1$; otherwise one moves to $k+1$
  3. If better: one moves to $k+1$; otherwise back to $k=1$
  4. In both cases one moves to $k+1$
Explanation. The neighbourhood is enlarged only when needed: an improvement brings back to the smallest neighbourhood, which is the cheapest.
eh-f-302 · level facile · notes
In GRASP for the TSP the next city is chosen at random in the restricted candidate list (RCL), the unvisited cities at distance at most $d_{\min}+\alpha(d_{\max}-d_{\min})$ from the last city. What happens with $\alpha=0$ and with $\alpha=1$?
  1. $\alpha=0$: nearest neighbour (greedy choice, apart from ties); $\alpha=1$: completely random choice
  2. $\alpha=0$: random choice; $\alpha=1$: nearest neighbour
  3. In both cases the optimal tour is obtained
  4. $\alpha$ only changes the number of iterations
Explanation. $\alpha$ tunes the trade-off between construction quality and diversity of the starting solutions of local search.
eh-f-303 · level facile · notes
In adaptive LNS (ALNS) the destroy method $o$ is chosen with probability $w_o/\sum_{o'}w_{o'}$, and after use the weight is updated with $w_o\leftarrow(1-\rho)w_o+\rho\psi$, where $\psi$ rewards the outcome. With $w_o=2$, $\rho=0.5$ and $\psi=4$, what is the new weight?
  1. $2.5$
  2. $6$
  3. $4$
  4. $3$
Explanation. $0.5\cdot2+0.5\cdot4=3$: methods that work are chosen more often, but the factor $\rho$ keeps memory of the past.
eh-f-304 · level facile · notes
In simulated annealing, which parameter tunes the balance between intensification and diversification, and how?
  1. The tabu tenure: long intensifies
  2. The number of items: more items diversify
  3. The temperature: high diversifies (accepts many worsenings), low intensifies
  4. The size of the RCL
Explanation. Every metaheuristic has its own knob: the temperature for SA, the tabu tenure for TS, the kick strength for ILS, $\alpha$ for GRASP.
eh-f-305 · level facile · notes
The parameters of a metaheuristic must be calibrated. Which procedure avoids an overly optimistic picture of the performance?
  1. Do not calibrate: always use the literature values
  2. Calibrate on training instances and evaluate on different instances
  3. Calibrate and evaluate on the same instances
  4. Choose the parameters giving the best result on a single instance
Explanation. Evaluating on the instances used for calibration overestimates the performance; moreover calibrating one parameter at a time ignores their interactions.
eh-f-306 · level ipotesi · notes
The metaheuristics of the chapter use neither relaxations nor MIP solvers. Yet for $P\,||\,C_{\max}$ and bin packing some of them stopped certifying the optimum. How is that possible?
  1. They reached a simple lower bound (e.g., $\lceil\sum_jt_j/m\rceil$), which is a dual bound computed separately
  2. Because a metaheuristic that stops is always optimal
  3. Because tabu search computes an LP relaxation
  4. Because those instances had a single local optimum
Explanation. Without a dual bound a metaheuristic cannot know how good it is; when it finds a solution equal to a simple lower bound, optimality is certified.
eh-f-307 · level ipotesi · notes
Tabu search always moves to the best non-tabu neighbour, even if worse than the current solution. What would happen with zero tabu tenure (no move forbidden) at a local optimum?
  1. The search would become a simulated annealing
  2. The search would find the global optimum
  3. The search would stop at the local optimum, like a descent
  4. The search may immediately return to the solution just left and cycle between two solutions
Explanation. From the local optimum one goes to the best (worse) neighbour; from there the best neighbour is often the previous local optimum. The tabu list prevents exactly this return.
eh-f-308 · level teorema · notes
Tabu search explores the whole neighbourhood and moves to the best non-tabu neighbour, even if worse. How does it differ from simulated annealing in the way it escapes a local optimum?
  1. It restarts from a random solution
  2. It never escapes a local optimum
  3. It is deterministic: it escapes because it always moves, and the tabu memory prevents it from going back; simulated annealing accepts worsenings at random
  4. It accepts worsenings with probability $e^{-\delta/T}$
Explanation. With the same data and starting solution tabu search always makes the same moves; diversification comes from the tabu list, not from chance.
eh-f-309 · level facile · notes
The metaheuristics of the chapter are illustrated on the same four problems as local search (KP, BPP, TSP, $P\,||\,C_{\max}$). Why are the same neighbourhoods reused?
  1. Because metaheuristics solve only the TSP
  2. A metaheuristic guides a local search: representation and neighbourhoods remain those of the problem
  3. Because metaheuristics use no neighbourhoods
  4. Because the four problems have the same neighbourhood
Explanation. What changes is the strategy to escape local optima, not the structure of the moves: flip and swap for the KP, move and swap for BPP and $P\,||\,C_{\max}$, 2-opt for the TSP.
eh-f-310 · level facile · notes
The experiments on metaheuristics use instances whose optimal value was computed separately with an exact algorithm. Why is it needed?
  1. Metaheuristics give only primal bounds: without the optimum one could not measure how far they are
  2. Because otherwise metaheuristics do not terminate
  3. It is not needed: metaheuristics certify the optimum
  4. Because metaheuristics need the optimum as input
Explanation. A metaheuristic does not know when it has found the optimum, unless it reaches a dual bound computed in another way.
eh-f-311 · level facile · notes
On the medium instances the metaheuristics are run $10$ times with different seeds, reporting minimum, average and maximum of the value found. Why several runs?
  1. Because the first run is always a test
  2. Because every run uses a different instance
  3. To compute a dual bound
  4. Many metaheuristics are randomized: a single run may be lucky or unlucky
Explanation. The seed fixes the random choices; several seeds show the variability of the method, and the number of runs reaching the optimum measures its reliability.
eh-f-312 · level facile · notes
In the final comparison of the metaheuristics on the medium instances, for every method the number of runs (out of $10$) reaching the optimal value is also reported. What does it add with respect to the best value alone?
  1. It measures the computing time
  2. It measures the dual bound
  3. It measures reliability: a method finding the optimum once in ten runs is less robust than one finding it always
  4. Nothing: only the best value counts
Explanation. Minimum, average, maximum and number of successes describe the distribution of the results, which also depends on the parameters.
eh-f-397 · level teorema · notes
Simulated annealing for a minimization problem, at temperature $T=5$: a neighbour worse by $\delta=10$. With which probability does the Metropolis rule accept it?
  1. $e^{-10}\approx 0.00005$
  2. $e^{-2}\approx 0.14$
  3. $e^{-0.5}\approx 0.61$
  4. $1-e^{-2}\approx 0.86$
Explanation. For $\delta>0$ the probability is $e^{-\delta/T}=e^{-10/5}=e^{-2}\approx0.14$. Neighbours that are not worse ($\delta\le0$) are accepted with probability $1$.
eh-f-398 · level teorema · notes
Geometric cooling $T\leftarrow\alpha T$ with $T_0=100$ and $\alpha=0.9$. What is the temperature after three coolings?
  1. $72.9$
  2. $70$
  3. $81$
  4. $27.1$
Explanation. $T=100\cdot0.9^3=72.9$. $70$ subtracts $10$ each time (linear cooling), $81$ is the value after two steps.
eh-f-399 · level teorema · notes
In tabu search a move is tabu, but it leads to a solution better than the best one found so far. What does the algorithm do?
  1. It does not make it while it is tabu
  2. It restarts from a random solution
  3. It doubles the tenure
  4. It may make it: aspiration criterion
Explanation. The aspiration criterion allows a tabu move that leads to a solution better than the best one found: that solution has certainly not been visited yet.
eh-f-400 · level ipotesi · notes
Which choice of the parameters makes simulated annealing similar to a random walk among the solutions?
  1. A high minimum temperature
  2. A single move per temperature
  3. A very high temperature
  4. A factor $\alpha$ close to $0$
Explanation. With a very high $T$, $e^{-\delta/T}\approx1$: almost every worse neighbour is accepted. With $\alpha$ close to $0$ the temperature collapses at once and the algorithm behaves like a descent.
eh-f-401 · level ipotesi · notes
What happens in tabu search if the tenure is too long?
  1. The aspiration criterion stops acting
  2. Too many moves are forbidden, missing good solutions
  3. The search goes back to cycling among few solutions
  4. It behaves like a simulated annealing
Explanation. A long tabu list forbids too much (on the instances of the chapter, with a large tenure the optimum is lost); it is a tenure that is too short that lets the search cycle.
eh-f-402 · level ipotesi · notes
In iterated local search the perturbation is too weak. What happens?
  1. The local search undoes it: same local optimum
  2. It becomes a restart from a random solution
  3. The algorithm no longer terminates
  4. The acceptance criterion rejects every optimum
Explanation. A weak perturbation stays in the same valley: the local search brings it back to the same local optimum. A perturbation that is too strong, on the contrary, is a random restart.
eh-f-403 · level ipotesi · notes
GRASP with a restricted candidate list (RCL) of a single element: what does it reduce to?
  1. A local search from random starting solutions
  2. Simulated annealing with temperature $T=0$
  3. A large neighbourhood search on the greedy
  4. The same improved greedy solution every iteration
Explanation. With an RCL of one element the construction always picks the best one: it is the deterministic greedy, and every iteration repeats the same solution and the same local optimum.
eh-f-404 · level ipotesi · notes
In large neighbourhood search the destroy step removes $q$ elements and the repair step reinserts them. What does $q$ control?
  1. The initial temperature and the cooling
  2. The size of the population of solutions
  3. The neighbourhood size and the repair cost
  4. The tenure of the tabu list of the moves
Explanation. The more elements are removed, the more solutions can be reached by one repair, but the repair costs more.
eh-f-405 · level ipotesi · notes
Why does the genetic algorithm for the 0/1 knapsack need a repair step?
  1. Mutation always decreases the profit
  2. Crossover and mutation can exceed the capacity
  3. The population could become empty
  4. The profits change at every generation
Explanation. The child of two feasible solutions, and a mutation that sets a bit to $1$, can violate the capacity constraint: the repair removes items until the vector is feasible again.
eh-f-419 · level ipotesi · notes
Why do the experiments of the chapter on metaheuristics use a random number generator with a fixed seed?
  1. So that the metaheuristics become exact
  2. Because without a seed the algorithm never stops
  3. Because it guarantees reaching the optimum
  4. So that every run is reproducible
Explanation. The same seed gives the same numbers and hence the same run, in the notes, in the code and in the app. The seed does not change the heuristic nature of the method.
eh-f-420 · level ipotesi · notes
In variable neighbourhood search the shaking takes a random solution in $N_k$, and $k$ grows after every failure. Why?
  1. Because $N_k$ is smaller for larger $k$
  2. To reduce the computing time of each iteration
  3. To diversify: farther solutions leave the valley
  4. To intensify the search around the incumbent
Explanation. If the local search brings back the same optimum, a stronger perturbation is needed to change valley; after an improvement the search goes back to $k=1$ to intensify.
eh-f-421 · level teorema · notes
Simulated annealing at temperature $T=2$: two worse neighbours, with $\delta_1=2$ and $\delta_2=6$. How many times more likely is accepting the first one?
  1. $e^{-2}\approx0.14$ times
  2. $e^{2}\approx7.4$ times
  3. $3$ times
  4. $e^{4}\approx54.6$ times
Explanation. The ratio is $\frac{e^{-2/2}}{e^{-6/2}}=e^{-1+3}=e^2\approx7.4$. It is not the ratio of the worsenings ($3$): the probability decreases exponentially with $\delta/T$.
eh-f-446 · level teorema · notes
Simulated annealing: for a fixed worsening $\delta>0$, how does the probability of accepting it behave as $T\to0$?
  1. It tends to $0$, like a descent
  2. It tends to $1$: every neighbour is accepted
  3. It stays $e^{-\delta}$
  4. It tends to $\frac12$
Explanation. $e^{-\delta/T}\to0$ as $T\to0$: the algorithm becomes a (randomized) descent. As $T\to\infty$ instead $e^{-\delta/T}\to1$ and almost everything is accepted.
eh-f-447 · level teorema · notes
Iterated local search with the criterion that accepts every new local optimum, even a worse one. What does the search do?
  1. It intensifies: it accepts only better optima
  2. It becomes a plain local search
  3. It stops at the first local optimum
  4. It diversifies: a walk among local optima
Explanation. Accepting only better optima intensifies; accepting all of them diversifies, because the search moves from valley to valley. Intermediate criteria accept a worse optimum with a probability, as in $SA$.
eh-f-448 · level teorema · notes
In variable neighbourhood search, what happens to $k$ when the solution obtained by shaking and local search is better than the current one?
  1. It is discarded and $k$ goes back to $1$
  2. It is kept and $k$ stays the same
  3. It becomes current and $k$ goes back to $1$
  4. It becomes current and $k$ grows by $1$
Explanation. After an improvement the search restarts from the smallest neighbourhood to intensify; after a failure $k$ grows (up to $k_{\max}$) to diversify.
eh-f-449 · level teorema · notes
Large neighbourhood search with destruction of all the $n$ elements and exact repair. What does the first iteration do?
  1. It only computes a dual bound
  2. It solves the instance to optimality
  3. It returns the starting solution
  4. It performs a 2-opt move
Explanation. If everything is removed, the exact repair must solve the whole instance: the neighbourhood contains all the solutions. This is why $q$ is kept small, so that the repair stays fast.
eh-f-450 · level teorema · notes
Tabu search starts from a local optimum and always moves to the best non-tabu neighbour. How can it improve the best solution found?
  1. By crossing worse solutions to another valley
  2. By accepting worsenings with probability $e^{-\delta/T}$
  3. By restarting from a random solution
  4. By solving a sub-MIP
Explanation. From the bottom of the valley the best non-tabu neighbour is worse, and the tabu list prevents going back: the search climbs out and descends into another valley. The probabilistic rule is that of $SA$.
eh-f-451 · level teorema · notes
What does GRASP return after its iterations of randomized construction and local search?
  1. The last local optimum found
  2. The deterministic greedy solution
  3. The average of the solutions found
  4. The best local optimum found
Explanation. Each iteration builds a solution with the restricted candidate list and improves it by local search; GRASP keeps the best local optimum over all the iterations.
eh-f-452 · level ipotesi · notes
Why does the tabu list store attributes of the moves (for instance «job $j$ has left machine $h$») instead of the visited solutions?
  1. The visited solutions are not feasible
  2. So the tenure is no longer needed
  3. Comparing whole solutions costs too much
  4. Attributes forbid fewer solutions
Explanation. Comparing each neighbour with all the visited solutions is too expensive. Attributes actually forbid more than needed (even solutions never seen), and this is why the aspiration criterion is needed.
eh-f-453 · level ipotesi · notes
Why does simulated annealing with geometric cooling $T\leftarrow\alpha T$ need a minimum temperature $T_{\min}$?
  1. It is needed to compute the dual bound
  2. $\alpha^kT_0$ never reaches $0$
  3. Below $T_{\min}$ the Metropolis rule fails
  4. With a small $T$ no improvement is accepted
Explanation. With $0<\alpha<1$ the temperature decreases but stays positive: a stopping rule is needed, such as $T\le T_{\min}$. Improvements are accepted at every temperature.
eh-f-454 · level ipotesi · notes
In adaptive large neighbourhood search (ALNS), how are the destroy and repair operators chosen?
  1. With weights from their past success
  2. Always the same two operators
  3. In a fixed order, in turn
  4. By the aspiration criterion
Explanation. ALNS keeps a weight for every operator, which grows when the operator produces good solutions: the operators that work better on the instance are chosen more often.
eh-f-455 · level ipotesi · notes
Besides the random choice, what does the construction phase of GRASP need?
  1. A feasible starting solution
  2. A tabu list of the moves
  3. A temperature and a cooling schedule
  4. A greedy function scoring the candidates
Explanation. The restricted candidate list collects the best candidates according to a greedy function (for the knapsack, the efficiency); the random choice is made among them.

5. MIP heuristics for the classical problems (83)

eh-f-313 · level facile · notes
In scheduling $P\,||\,C_{\max}$ an assignment is a binary vector $\vet x$ with $x_{ij}=1$ if job $j$ is on machine $i$; the distance $\Delta(\vet x,\bar{\vet x})$ counts the differing components. Two assignments differ in the machine of $3$ jobs. What is $\Delta(\vet x,\bar{\vet x})$?
  1. $3m$
  2. $3$
  3. $9$
  4. $6$
Explanation. Every moved job changes two components (one from $1$ to $0$, the other from $0$ to $1$): $\Delta=2r=6$.
eh-f-314 · level facile · notes
In the models of bin packing and $P\,||\,C_{\max}$, the binary variables $x_{jb}$ assign every item (job) $j$ to a bin (machine) $b$. Why does rounding the LP relaxation solution to the nearest integer almost always fail?
  1. The LP relaxation of these models is unbounded, so there is no solution to round
  2. The LP relaxation of these models always has an integer solution, so rounding changes nothing
  3. The constraints $\sum_b x_{jb}=1$ are equalities: fractional values rounded one by one almost never sum to $1$
  4. The capacity constraints are inequalities: fractional values rounded one by one always satisfy them
Explanation. With $\sum_b x_{jb}=1$ and fractional values, rounding each variable separately leaves items unassigned or assigned twice.
eh-f-315 · level facile · notes
In integer programming heuristics, diving fixes variables in sequence solving the LP relaxation, and RINS solves an integer subproblem close to the incumbent (best known) solution. Which statement is correct?
  1. A dive explores the whole tree; RINS guarantees a solution better than the incumbent
  2. A dive is a single path in the tree; RINS fixes the variables on which relaxation and incumbent agree
  3. A dive is a single path in the tree; RINS fixes the variables on which relaxation and incumbent differ
  4. A dive explores the whole tree; RINS fixes the variables on which relaxation and incumbent agree
Explanation. The first wrong fixing of a dive is never revised; RINS solves a sub-MIP with the agreeing variables fixed, so it cannot find solutions that change them.
eh-f-316 · level facile · notes
ILP-based heuristics use the rounding $[v]=\lfloor v+\frac12\rfloor$ and the distance $\Delta(\vet x,\bar{\vet x})=\sum_j|x_j-\bar x_j|$ from an integer point. What are $[0.5]$, $[0.25]$ and $\Delta\big((1,0,1,0),(1,1,0,0)\big)$?
  1. $1$, $0$ and $2$
  2. $1$, $0$ and $1$
  3. $1$, $1$ and $4$
  4. $0$, $0$ and $2$
Explanation. $\lfloor1\rfloor=1$, $\lfloor0.75\rfloor=0$; the two vectors differ in components $2$ and $3$: $\Delta=2$.
eh-f-317 · level facile · notes
The bin packing model for ILP heuristics has binary variables $x_{jb}$ (item $j$ in bin $b$) and $y_b$ (bin $b$ used), assignment constraints (one per item) and capacity constraints (one per bin). With $n=6$ items and $m=6$ bins, how many variables and constraints does it have?
  1. $48$ variables and $18$ constraints
  2. $36$ variables and $12$ constraints
  3. $42$ variables and $6$ constraints
  4. $42$ variables and $12$ constraints
Explanation. $6\cdot6=36$ variables $x_{jb}$ plus $6$ variables $y_b$; $6$ assignment and $6$ capacity constraints.
eh-f-318 · level facile · notes
In ILP-based heuristics the methods are described for a minimization problem. How are the knapsack model $\mathrm{ILP}_{\mathrm{KP}}$ ($\max\sum_jp_jx_j$) and its cutoffs handled?
  1. By replacing the capacity constraint with an equality
  2. By relaxing the binary variables to continuous ones
  3. By swapping $\min$ and $\max$, $\le$ and $\ge$ in comparisons of values
  4. By changing the sign of the weights and keeping the cutoffs
Explanation. For the knapsack the cutoff becomes $\sum_jp_jx_j\ge f(\bar{\vet x})+\theta$: a solution of larger profit is sought.
eh-f-319 · level facile · notes
Knapsack with $c=9$, $p=(10,7,6,4)$, $w=(5,4,3,3)$. The linear relaxation takes the items by non-increasing efficiency $p_j/w_j$: items $1$ and $3$ (weight $8$) in full, then the critical item $2$ for a fraction. Which fraction, and what is $z(\mathrm{LP})$?
  1. $\frac14$, and $z(\mathrm{LP})=17$
  2. $\frac14$, and $z(\mathrm{LP})=17.75$
  3. $\frac12$, and $z(\mathrm{LP})=19.5$
  4. $1$, and $z(\mathrm{LP})=23$
Explanation. Capacity $9-8=1$ remains out of a weight $4$: fraction $\frac14$, value $10+6+\frac74=17.75$. Rounded down, $17$ is a valid bound, not the LP value.
eh-f-320 · level facile · notes
In the bin packing model ($y_b=1$ if bin $b$ is used, $x_{jb}=1$ if item $j$ is in bin $b$, capacity $c$) the constraint is $-\sum_jw_jx_{jb}+c\,y_b\ge0$ for every $b$. What does it impose?
  1. A used bin holds at most $c$, an unused one is empty
  2. Every item goes into exactly one used bin
  3. Bins are used in increasing index order
  4. Every bin is used by at least one item of the instance
Explanation. With $y_b=0$ the constraint becomes $\sum_jw_jx_{jb}\le0$; with $y_b=1$ it becomes $\sum_jw_jx_{jb}\le c$. Unique assignment is another constraint.
eh-f-321 · level facile · notes
In the bin packing model one minimizes $\sum_by_b$, with capacity constraints $-\sum_jw_jx_{jb}+c\,y_b\ge0$. In an optimal solution, what is $y_b$ for a bin holding no items?
  1. $1$, because the capacity constraint requires it
  2. $1$: every available bin must always be opened
  3. Any value between $0$ and $1$ inclusive
  4. $0$: the constraint holds and the objective wants it low
Explanation. Without items the constraint becomes $c\,y_b\ge0$, true also with $y_b=0$, and minimizing $\sum_by_b$ drives $y_b$ to $0$.
eh-f-322 · level facile · notes
The model $\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{DFJ}}$ has the subtour elimination constraints on the subsets $S\subseteq\mathscr{V}\setminus\{1\}$ with $|S|\ge2$. How many are there with $n=5$ cities?
  1. $26$
  2. $10$
  3. $11$
  4. $16$
Explanation. The subsets of $\{2,3,4,5\}$ are $2^4=16$; removing the empty set and the $4$ singletons leaves $11$. With the $5+5$ constraints on entering and leaving arcs one gets $21$.
eh-f-323 · level facile · notes
On the $5$-city instance used for the heuristics, the linear relaxation of the DFJ model of the TSP already has the optimal tour as solution. Why is the TSP not used in the other examples of the chapter on ILP heuristics?
  1. Because ILP heuristics do not apply to the TSP
  2. Every method would find the optimum at once: integer LP
  3. Because the DFJ model has no binary variables at all
  4. Because the TSP linear relaxation is infeasible
Explanation. With an integer LP solution rounding, diving and the other methods stop at the first step. The MTZ model has a weaker relaxation ($17$).
eh-f-324 · level facile · notes
In the model of $P\,||\,C_{\max}$ (binaries $x_{jh}$, continuous $C_{\max}$), RINS, local branching and proximity search use the distance $\Delta(\vet x,\bar{\vet x})=\sum_{j\in\mathscr{D}}|x_j-\bar x_j|$ over the integer variables $\mathscr{D}$. Over which variables is it computed?
  1. Only over the binaries $x_{jh}$: $C_{\max}$ does not enter
  2. Only over the continuous variable $C_{\max}$
  3. Only over the fractional variables of the relaxation
  4. Over all variables of the model, $C_{\max}$ included
Explanation. $C_{\max}$ is the only continuous variable; this is why the feasibility pump, guided by $\Delta$, ignores the loads.
eh-f-325 · level facile · notes
In the model of $P\,||\,C_{\max}$ (variables $x_{jh}$, times $t_j$) the constraint is $-\sum_jt_jx_{jh}+C_{\max}\ge0$ for every machine $h$. What does it mean?
  1. The total load of all jobs is at most $C_{\max}$
  2. Every machine has load exactly equal to $C_{\max}$
  3. Every job goes on one and only one machine
  4. $C_{\max}$ is not smaller than the load of any machine
Explanation. Minimizing $C_{\max}$ under these constraints gives the maximum load. The total load is $\sum_jt_j$, which in general exceeds $C_{\max}$.
eh-f-326 · level facile · notes
For $P\,||\,C_{\max}$ with $m=3$ and $t=(5,5,4,4,3,3,3)$, the linear relaxation has value $\frac{27}3=9$, and the solution returned by the solver assigns jobs $2$ and $3$ fractionally, with three loads equal to $9$. Why does the LP have infinitely many optimal solutions?
  1. Because the model lacks the assignment constraints
  2. Because the optimal integer value of the instance is $10$
  3. Any fractional assignment with three loads of $9$ is optimal
  4. Because the variable $C_{\max}$ is not bounded below
Explanation. The LP sees only the loads: any way of spreading job fractions that levels the loads at $9$ is optimal. The integer optimum is $9$.
eh-f-327 · level facile · notes
Rounding heuristic on $P\,||\,C_{\max}$: in the solution of the linear relaxation job $3$ has $\tilde x_{32}=\tilde x_{33}=\frac12$ (machines $2$ and $3$), and rounding is done with $[v]=\lfloor v+\frac12\rfloor$. What happens?
  1. The rounded makespan becomes $10$
  2. Job $3$ goes on two machines: the assignment is violated
  3. Job $3$ is left without a machine
  4. Job $3$ goes on machine $2$, and the solution is feasible
Explanation. $[\frac12]=1$ for both: $\bar x_{31}+\bar x_{32}+\bar x_{33}=2\neq1$, and rounding fails.
eh-f-328 · level facile · notes
Rounding the LP solution works on the knapsack but fails on bin packing and $P\,||\,C_{\max}$. Why?
  1. The LP splits items: rounding violates the assignments
  2. Because the bin packing LP is always infeasible
  3. Because bin packing weights are not integer
  4. Because the knapsack has only continuous variables
Explanation. On the knapsack, a single packing constraint with nonnegative coefficients, rounding down is safe; the assignment constraints $\sum_bx_{jb}=1$ are almost always violated by independent roundings.
eh-f-329 · level facile · notes
Fractional diving on the knapsack ($c=9$, $p=(10,7,6,4)$, $w=(5,4,3,3)$, optimum $\{1,2\}$ of profit $17$): from the LP $\tilde{\vet x}=(1,\frac14,1,0)$ it fixes $x_2:=[\frac14]=0$, then $x_4:=0$, and ends with $\{1,3\}$, of profit $16$. What does it show?
  1. Fixing $x_2:=0$ is always the right choice for diving
  2. Diving always finds the optimal solution of the instance
  3. The linear relaxation of the knapsack is infeasible
  4. The first decision was wrong: the branch $x_2=1$ contained the optimum
Explanation. Diving does not backtrack: a badly fixed variable is not recovered. The branch abandoned at the first step contained $\{1,2\}$.
eh-f-330 · level facile · notes
Guided diving on $P\,||\,C_{\max}$: the fractional variable closest to the incumbent is fixed, at the incumbent's value. Fractional variables $\tilde x_{21}=\frac35$, $\tilde x_{23}=\frac25$, $\tilde x_{32}=\frac12$, $\tilde x_{33}=\frac12$; incumbent $\bar x_{21}=\bar x_{23}=\bar x_{32}=0$, $\bar x_{33}=1$. Which fixing?
  1. $x_{33}:=1$
  2. $x_{32}:=0$
  3. $x_{23}:=0$
  4. $x_{21}:=1$
Explanation. Distances from the incumbent: $\frac35$, $\frac25$, $\frac12$, $\frac12$: the smallest is that of $x_{23}$, which is fixed at the incumbent's value, $0$.
eh-f-331 · level facile · notes
The feasibility pump alternates projection onto the LP (minimizing the distance $\Delta$ from the current integer point) and rounding. On $P\,||\,C_{\max}$ (optimum $9$) it finds in two projections a solution of makespan $11$, like $LPT$. Why not better?
  1. Because the pump restarts from the $LPT$ solution
  2. The distance looks at assignments, not at loads
  3. Because the pump always fails on $P\,||\,C_{\max}$
  4. Because the projection maximizes the makespan
Explanation. The pump looks for a feasible solution, not a good one: $C_{\max}$ is continuous and does not appear in the distance. For $P\,||\,C_{\max}$ feasibility was not hard.
eh-f-332 · level facile · notes
Feasibility pump on bin packing ($c=7$, optimum $3$): with one seed it opens $5$ bins, two of them empty, although the items are distributed optimally in $3$ bins. Why is the solution worth $5$?
  1. Nothing in the distance asks to close empty bins
  2. Because the chosen seed makes the LP infeasible
  3. Because empty bins violate the capacity
  4. Because the pump cannot produce feasible solutions
Explanation. The pump minimizes the distance from an integer point, not $\sum_by_b$: a $y_b=1$ on an empty bin stays. Only with one seed out of ten is the solution optimal.
eh-f-333 · level facile · notes
RINS, local branching and proximity search start from an incumbent $\bar{\vet x}$ and solve a sub-MIP with a cutoff constraint. What distinguishes them?
  1. All three minimize $\Delta$, with different cutoffs
  2. RINS minimizes $\Delta$; LB fixes where LP and incumbent agree; PS imposes $\Delta\le k$
  3. RINS imposes $\Delta\le k$; LB minimizes $\Delta$; PS fixes where they agree
  4. RINS fixes where LP and incumbent agree; LB imposes $\Delta\le k$; PS minimizes $\Delta$
Explanation. $\Delta(\vet x,\bar{\vet x})$ is the distance from the incumbent; local branching increases $k$ when it finds nothing.
eh-f-334 · level facile · notes
Local branching on the 0/1 knapsack solves a sub-MIP with the constraint $\Delta(\vet x,\bar{\vet x})\le k$ (at most $k$ binary components different from the incumbent). Which local search neighborhoods do $k=1$ and $k=2$ correspond to?
  1. $k=1$: move; $k=2$: 2-opt
  2. $k=1$ and $k=2$: both flip only
  3. $k=1$: flip; $k=2$: also contains swap
  4. $k=1$: swap; $k=2$: also contains flip
Explanation. A flip changes one component, a swap two. For the assignments of $P\,||\,C_{\max}$, instead, $\Delta\le2$ is the move neighborhood.
eh-f-335 · level facile · notes
RINS on the knapsack ($c=9$, $p=(10,7,6,4)$, $w=(5,4,3,3)$): incumbent $(1,0,1,0)$ of profit $16$, LP solution $(1,\frac14,1,0)$. One fixes $x_1=1$, $x_3=1$, $x_4=0$ and imposes profit at least $17$. What does RINS return, and why?
  1. No solution: RINS does not apply to the knapsack
  2. The incumbent: with $x_3=1$ fixed, the sub-MIP is infeasible
  3. $\{1,2\}$, because the sub-MIP sets $x_2=1$
  4. $\{1,2,3\}$, because the cutoff is satisfied
Explanation. Capacity requires $x_2=0$, the cutoff $x_2=1$. The optimum $\{1,2\}$ has $x_3=0$, but $x_3$ is fixed because LP and incumbent agree.
eh-f-336 · level facile · notes
RINS on $P\,||\,C_{\max}$ from the $LPT$ incumbent (makespan $11$): incumbent and LP solution agree on only $8$ of the $21$ binary variables, and the sub-MIP with cutoff $C_{\max}\le10$ finds the optimum $9$. On the knapsack, instead, RINS did not improve. What does the comparison show?
  1. With different incumbent and LP the RINS neighborhood is large
  2. Fixing more variables makes RINS more effective
  3. The cutoff $C_{\max}\le10$ suffices to find the optimum
  4. RINS works only on minimization problems
Explanation. On the knapsack the two solutions were too similar and a single variable remained free; here $13$ remain, enough to contain the optimum.
eh-f-337 · level facile · notes
Proximity search on $P\,||\,C_{\max}$ from the $LPT$ incumbent: with cutoff $C_{\max}\le10$ the closest solution is at distance $\Delta=4$ (makespan $10$), with $C_{\max}\le9$ again at distance $4$ (makespan $9$), with $C_{\max}\le8$ the sub-MIP is infeasible. What do $\Delta=4$ and the last infeasibility mean?
  1. Four machines used; makespan $9$ is optimal
  2. Four jobs reassigned; makespan $8$ is optimal
  3. Two jobs reassigned; the search failed
  4. Two jobs reassigned; makespan $9$ is optimal
Explanation. For assignments $\Delta=2r$, with $r$ jobs changing machine. With integer objective and $\theta=1$, an infeasible sub-MIP proves that the incumbent is optimal.
eh-f-338 · level facile · notes
Proximity search on the knapsack ($c=9$, $p=(10,7,6,4)$, $w=(5,4,3,3)$) from the incumbent $(1,0,1,0)$ of profit $16$: the sub-MIP looks for the closest solution (distance $\Delta=\sum_j|x_j-\bar x_j|$) of profit at least $17$. Which does it find, and at what distance?
  1. $(1,1,0,0)$, at distance $1$
  2. $(0,1,1,1)$, at distance $3$
  3. $(1,1,0,0)$, at distance $2$
  4. $(1,1,1,0)$, at distance $1$
Explanation. Item $3$ leaves and item $2$ enters: two components change, weight $9$, profit $17$. $(1,1,1,0)$ and $(0,1,1,1)$ exceed the capacity.
eh-f-339 · level facile · notes
Relax-and-fix on a capacitated lot sizing (optimum $160$, with setups in periods $1,2,5$): at step $2$, with future setups relaxed, $y_2=0$ costs $132.38$ and $y_2=1$ costs $142.38$, so it fixes $y_2:=0$; then capacity forces a setup in period $3$, and the result is $170$. What does it show?
  1. Fixing $y_2:=0$ is always the right choice
  2. Myopic choice: relaxed future setups look cheap
  3. Relax-and-fix always finds the optimal solution
  4. The linear relaxation of lot sizing is strong
Explanation. The relaxation had paid for the setup of period $3$ only for a fraction $0.143$; when it becomes integer, the saving in period $2$ turns out to be a mistake.
eh-f-340 · level facile · notes
Fix-and-optimize on the capacitated lot sizing starts from the relax-and-fix solution (setups in periods $1,3,5$, cost $170$) and reoptimizes the windows $\{y_t,y_{t+1}\}$ with the other setups fixed: the window $\{y_2,y_3\}$ moves the setup from period $3$ to $2$ and brings the cost to $160$, the optimum. What does it show?
  1. Reoptimizing small windows corrects earlier mistakes
  2. Larger windows always worsen the solution
  3. Relax-and-fix was already optimal
  4. Fix-and-optimize builds the solution from scratch
Explanation. Every window is a small MIP solved exactly; the windows are swept again until a pass does not improve.
eh-f-341 · level facile · notes
Bin packing with $60$ items (lower bound $23$, FFD $24$) solved with Gurobi: with default parameters the optimum $23$ arrives after $2533$ nodes; with more effort on heuristics $23$ is found at the root, about $30$ times sooner; without heuristics it is not found within the limit. The bound is $23$ already at the root. What does it show?
  1. Branch-and-bound is never useful on bin packing
  2. The difficulty is proving the bound $23$
  3. The solver heuristics always slow the solution down
  4. The difficulty is primal: heuristics and MIP start matter
Explanation. With a strong bound, solution time is the time to find a good solution. A single instance proves nothing in general: the lesson is qualitative.
eh-f-342 · level facile · notes
In the Gurobi experiments of the chapter on ILP heuristics a limit in «work units» is set instead of seconds. Why?
  1. Because a work unit counts the nodes explored
  2. Because this way the solver uses more threads
  3. A deterministic measure of effort, hence reproducible
  4. Because seconds cannot be measured precisely
Explanation. Time in seconds depends on the machine and its load; the work unit measures computational effort deterministically (about one second each).
eh-f-343 · level facile · notes
Capacitated lot sizing: relax-and-fix gives $170$ with LP bound $102.38$ (gap $66\%$); fix-and-optimize gives $160$. What closes the gap and proves $160$ optimal?
  1. A second full pass of relax-and-fix
  2. The solver's branch-and-bound: the LP bound is weak
  3. The bound of the linear relaxation rounded up
  4. The fact that fix-and-optimize stops by itself
Explanation. Here the linear relaxation is weak; the dual bound of branch-and-bound rises to $160$. A heuristic stopping proves nothing.
eh-f-344 · level facile · notes
Bin packing with $60$ items: FFD uses $24$ bins and the lower bound is $\lceil2271/100\rceil=23$. What is the relative gap $(\mathscr{A}(I)-\mathrm{LB})/\mathrm{LB}$ of the FFD solution?
  1. About $4.3\%$
  2. About $1\%$
  3. $0\%$
  4. About $4.2\%$
Explanation. $(24-23)/23\approx4.3\%$; $4.2\%$ divides by $24$. Gurobi finds $23$ and closes the gap to $0\%$.
eh-f-345 · level facile · notes
In heuristics based on integer linear programming (MIP), $\tilde{\vet x}$ denotes an optimal solution of the LP relaxation and $\bar{\vet x}$ the incumbent. What is the incumbent?
  1. The rounded LP relaxation solution
  2. The current dual bound of branch-and-bound
  3. The first fractional solution found by the simplex
  4. The best feasible integer solution found so far
Explanation. The incumbent is a primal bound: improvement heuristics (RINS, local branching, proximity search) start from $\bar{\vet x}$ and look for a better nearby solution.
eh-f-346 · level facile · notes
Which advantage do heuristics based on integer linear programming (MIP) have over problem-specific heuristics?
  1. They are always faster than constructive heuristics
  2. They always guarantee the optimum in polynomial time
  3. They use only the model, so they apply to every formulated problem, and the relaxation also gives a dual bound
  4. They need no model of the problem
Explanation. They work on the variables and constraints of the model, not on the structure of the problem; the LP relaxation (and the solver branch-and-bound) gives the other side of the gap.
eh-f-347 · level facile · notes
On the reference instances of knapsack, bin packing, TSP and $P\,||\,C_{\max}$, the LP relaxation value rounded in the direction of the bound (down for maximization, up for minimization) equals the optimal value. What does this mean for MIP heuristics?
  1. Heuristics are useless, because the relaxation is already integer
  2. The relaxations are strong: finding a good solution is the hard part, and the rounded bound can prove its optimality
  3. The relaxation is useless, because it is always weak
  4. The instances are wrong, because a relaxation is never exact
Explanation. When the bound is already tight, the practical problem is to find an integer solution of that value: it is the typical situation in which MIP heuristics are useful.
eh-f-348 · level facile · notes
In the rounding heuristic the LP relaxation solution is rounded to the nearest integer. Why is rounding down always feasible for the 0-1 knapsack ($\max\sum p_jx_j$, a single constraint $\sum w_jx_j\le c$, non-negative weights)?
  1. Lowering the $x_j$ never increases the weight, so the constraint stays satisfied
  2. Because the split item always has $x_s=0$
  3. Because the relaxation always has an integer solution
  4. Because rounding down always gives the optimal solution
Explanation. With non-negative coefficients in a $\le$ constraint, decreasing the variables keeps feasibility; in bin packing and $P\,||\,C_{\max}$ the assignment constraints are equalities and rounding fails.
eh-f-349 · level facile · notes
The 0-1 knapsack with $c=9$ has LP relaxation $\tilde x=(1,1,0.25,0)$ (items by non-increasing efficiency, weights $w=(5,4,4,3)$). What do rounding to the nearest integer and rounding down give?
  1. $(1,1,1,0)$, of weight $13$: infeasible
  2. $(1,1,0,1)$, of weight $12$: infeasible
  3. $(0,0,0,0)$: everything is lost
  4. Both $(1,1,0,0)$, of weight $9$: feasible
Explanation. $0.25$ rounds to $0$ in both cases, and the integer variables stay: the point $(1,1,0,0)$ weighs $5+4=9\le c$.
eh-f-350 · level facile · notes
In diving one fractional variable at a time is fixed and the LP relaxation is solved again. What is the difference between fractional diving and guided diving?
  1. Fractional explores the whole tree; guided a single path
  2. Fractional uses the incumbent; guided uses only the relaxation
  3. Fractional fixes the least fractional variable to its nearest integer; guided fixes the one closest to its incumbent value, at that value
  4. Fractional fixes the most fractional variable to $1$; guided fixes a random variable
Explanation. Both follow a single path in the branch-and-bound tree; guided diving uses a known solution to choose the direction.
eh-f-351 · level facile · notes
In diving on $P\,||\,C_{\max}$ the LP relaxation value stays the same for many successive fixings. Why?
  1. Because diving no longer solves the relaxation after the first fixing
  2. The relaxation has a huge set of optimal solutions: fixing a variable moves the point to another one of equal value
  3. Because the makespan is an integer variable
  4. Because every fixing makes the relaxation infeasible
Explanation. The relaxation splits the jobs among the machines and is worth $\sum_j t_j/m$ in many ways: its value says nothing about the quality of the path until the fixings bind the loads.
eh-f-352 · level facile · notes
The feasibility pump alternates the projection of an integer point onto the LP relaxation region (an LP minimizing the distance $\Delta$) and the rounding of the projection. What is its goal?
  1. Finding a first feasible solution; quality is the job of improvement methods
  2. Improving an already known incumbent
  3. Finding the optimal solution with a single projection
  4. Computing a dual bound better than the relaxation
Explanation. The pump almost ignores the objective: it looks for an integer feasible point. Heuristics such as RINS or proximity search then start from that solution.
eh-f-353 · level facile · notes
In the feasibility pump, the distance between a rounded binary point $\hat{\vet x}$ and a point $\vet x$ of the relaxation is $\Delta(\vet x,\hat{\vet x})=\sum_{j:\hat x_j=0}x_j+\sum_{j:\hat x_j=1}(1-x_j)$. What is it for $\hat{\vet x}=(1,0,1)$ and $\vet x=(0.8,\ 0.3,\ 0.5)$?
  1. $1.6$
  2. $0.4$
  3. $0.7$
  4. $1$
Explanation. $(1-0.8)+0.3+(1-0.5)=0.2+0.3+0.5=1$. If $\Delta=0$ the relaxation point is integer and the pump has found a feasible solution.
eh-f-354 · level facile · notes
In local branching for the 0-1 knapsack the sub-MIP is solved with the constraint $\Delta(\vet x,\bar{\vet x})\le k$, where $\Delta$ counts the binary components different from the incumbent $\bar{\vet x}$. Which local search neighbourhood does it correspond to with $k=1$?
  1. The whole space $\{0,1\}^n$
  2. No neighbourhood: the sub-MIP is empty
  3. The flip neighbourhood, adding or removing one item
  4. The swap neighbourhood, exchanging an item inside with one outside
Explanation. A single different component means changing one item; with $k=2$ swaps are included too. The solver explores the neighbourhood exactly.
eh-f-355 · level teorema · notes
In proximity search, for a minimization problem with integer objective values, a sub-MIP is solved with the constraint $f(\vet x)\le f(\bar{\vet x})-\theta$, with $\theta=1$, minimizing the distance from the incumbent $\bar{\vet x}$. What follows if the sub-MIP is infeasible?
  1. The incumbent is infeasible
  2. The incumbent is optimal: no solution has value at least $1$ lower
  3. $\theta$ must be increased to find a solution
  4. The LP relaxation is unbounded
Explanation. With integer values, a better solution would have $f(\vet x)\le f(\bar{\vet x})-1$; if none exists, $\bar{\vet x}$ is optimal. The proof comes from the solver, which proves infeasibility with its bounds.
eh-f-356 · level facile · notes
In relax-and-fix for lot sizing, the setup variables $y_t$ are divided into blocks of consecutive periods. How does the method proceed?
  1. It solves a MIP with the first block binary and the others relaxed, fixes the first block, then moves to the next block
  2. It solves every block as an independent problem, without the stocks
  3. It solves the LP relaxation once and rounds all the blocks together
  4. It fixes all setups to $1$ and optimizes the quantities
Explanation. Every sub-MIP has few binaries; the decisions of the fixed blocks stay, and the future ones are only relaxed. Fix-and-optimize then improves the solution by freeing one block at a time.
eh-f-357 · level facile · notes
In capacitated lot sizing, why are the only hard decisions in MIP heuristics the $m$ setup variables $y_t$?
  1. Because the produced quantities always equal the demands
  2. Because stocks are always zero in an optimal plan
  3. Because the LP relaxation is exact even with fractional setups
  4. With the setups fixed, the rest is an LP with a network matrix and integer data, which has an integer optimal solution
Explanation. With $y$ fixed the balance and capacity constraints remain, a flow structure: the simplex gives integer quantities. The relaxation with fractional $y$ is weak instead.
eh-f-358 · level facile · notes
Modern MIP solvers, such as Gurobi, run many heuristics during branch-and-bound and accept an initial solution (MIP start). What is a MIP start for?
  1. It guarantees that the solver returns exactly that solution
  2. It switches off the internal heuristics of the solver
  3. It gives an incumbent at once: the solver prunes nodes with worse bounds and starts with a finite gap
  4. It replaces the LP relaxation at the root
Explanation. A good initial incumbent allows pruning by bound from the start; the solver may still find better ones.
eh-f-359 · level facile · notes
The internal heuristics of a MIP solver are compared on a single instance, and one parameter setting finds the optimal solution earlier. What can be concluded?
  1. That this setting is the best for every instance
  2. Little: results depend on instance, solver version and machine, and a single instance proves nothing
  3. That the other settings are wrong
  4. That the solver is exact only with that setting
Explanation. As for every heuristic, comparisons need many instances and equal conditions; the time to find the optimum varies a lot from one instance to another.
eh-f-360 · level facile · notes
Constructive heuristics, local search and metaheuristics give only a primal bound. What do MIP heuristics run inside a solver add?
  1. A dual bound from the relaxation and branch-and-bound, hence a gap and sometimes a proof of optimality
  2. A guaranteed polynomial running time
  3. A constant approximation guarantee
  4. Solutions always better than those of metaheuristics
Explanation. With the model comes its relaxation: for the reference knapsack $\lfloor 17.75\rfloor=17$, so a solution of value $17$ is optimal.
eh-f-361 · level facile · notes
For a 0-1 knapsack with integer profits, the LP relaxation equals $17.75$ and a MIP heuristic finds a solution of value $17$. What can be concluded?
  1. The solution is $0.75$ away from the optimum
  2. Another heuristic is needed to know whether it is optimal
  3. The optimum is $18$, the round-up of the relaxation
  4. The solution is optimal, because $\lfloor 17.75\rfloor=17$ is an upper bound
Explanation. With integer profits every solution has integer value at most $17.75$, hence at most $17$: the solution found attains the bound.
eh-f-362 · level facile · notes
In the bin packing model used by MIP heuristics there are $m$ available bins, with variables $x_{jb}$ and $y_b$. Which value of $m$ is always valid, and which is used on the reference instance with $n=6$ items?
  1. $m=1$, because bins are added during the search
  2. $m=2n$, for some margin; on the instance $m=12$
  3. $m=n$, always valid: one bin per item; on the instance $m=6$
  4. $m=\lceil\sum_j w_j/c\rceil$, always valid; on the instance $m=3$
Explanation. With $m=n$ there is always a solution (one item per bin). The weight bound is a lower bound: if it were below the optimum, the model would have no solution.
eh-f-363 · level teorema · notes
In the $P\,||\,C_{\max}$ model with binary variables $x_{jh}$ (job $j$ on machine $h$), the distance between two feasible assignments is $\Delta(\vet x,\bar{\vet x})=\sum_{(j,h):\bar x_{jh}=1}(1-x_{jh})+\sum_{(j,h):\bar x_{jh}=0}x_{jh}$. If $r$ jobs change machine, what is $\Delta$, and why?
  1. $r^2$: every pair of moved jobs counts once
  2. $2r$: every moved job leaves a $0$ where $\bar x$ has $1$ and puts a $1$ where $\bar x$ has $0$
  3. $r$: every moved job changes one component
  4. $rm$: every moved job changes all its $m$ components
Explanation. A job on the same machine contributes $0$; one moved from machine $h$ to $h'$ contributes $1$ for $h$ and $1$ for $h'$. This is why $\Delta\le 2$ is the move neighbourhood of local search.
eh-f-364 · level facile · notes
A MIP-based heuristic (matheuristic) for a problem with a MIP model, what does it use to look for a feasible solution, unlike metaheuristics?
  1. The LP relaxation of the model and a MIP solver
  2. Only local search moves
  3. Only a greedy construction
  4. A population of solutions
Explanation. Matheuristics (rounding, diving, feasibility pump, RINS, local branching, ...) exploit the model; metaheuristics only manipulate solutions.
eh-f-365 · level facile · notes
In the ILP model of $P\,||\,C_{\max}$ with binary variables $x_{jh}$ (job $j$ on machine $h$) and $C_{\max}$, which variable is continuous, and which value does it take given the assignment?
  1. All the $x_{jh}$; $C_{\max}$ is integer
  2. None: the model is purely binary
  3. Only $C_{\max}$; it equals the average load
  4. Only $C_{\max}$; it equals the maximum load $\max_h\sum_jt_jx_{jh}$
Explanation. The constraints $C_{\max}\ge\sum_jt_jx_{jh}$ for every machine and the minimization bring $C_{\max}$ to the maximum load.
eh-f-366 · level facile · notes
RINS, local branching and proximity search solve a sub-MIP starting from an incumbent solution $\bar{\vet x}$, with the cutoff constraint $f(\vet x)\le f(\bar{\vet x})-\theta$ (minimization). Why can one set $\theta=1$ on the instances of the chapter?
  1. Because the cutoff is optional
  2. Because $\theta$ must always be $1$
  3. Because the objective values are integer: a better solution is worth at least $1$ less
  4. Because the sub-MIP has a single variable
Explanation. With an integer objective, improving means decreasing by at least $1$; the cutoff excludes the solutions not improving the incumbent.
eh-f-367 · level teorema · notes
In the model $\mathrm{ILP}_{\mathrm{KP}}$ of the 0/1 knapsack ($\max\sum_jp_jx_j$, $\sum_jw_jx_j\le c$, $x_j\in\{0,1\}$), why does rounding down a solution of the LP relaxation always give a feasible solution?
  1. Because rounding up is infeasible
  2. Decreasing the variables does not increase the weight, and the weights are non-negative: the constraint $\le c$ stays satisfied
  3. It is not true: it may exceed the capacity
  4. Because the LP relaxation always has an integer solution
Explanation. With $\le$ constraints with non-negative coefficients, rounding down is safe; in the KP the rounded solution only removes the split item.
eh-f-368 · level facile · notes
The model $\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{DFJ}}$ uses arc variables $x_{ij}$, degree constraints and subtour elimination constraints. Why does rounding a fractional solution of the relaxation rarely give a tour?
  1. The rounded vector may violate the degree constraints or form subtours: TSP feasibility is not preserved by rounding
  2. Because the DFJ relaxation is always integer
  3. Because the distances are integer
  4. Because the TSP has no constraints
Explanation. Unlike the KP, the equality and connectivity constraints of the TSP break easily; more structured MIP heuristics are needed (diving, feasibility pump, sub-MIPs).
eh-f-369 · level facile · notes
On an instance of the 0/1 knapsack ($c=9$, $p=(6,5,8,9,6,7)$, $w=(2,3,6,7,5,9)$) the LP relaxation is worth $\frac{49}{3}$ and the optimum $15$. Is the solution of the relaxation integer?
  1. Yes: the knapsack relaxation is always integer
  2. Yes, and it coincides with the optimum
  3. No, because all variables are fractional
  4. No: the split item $3$ is taken for $\frac23$, and the gap with the optimum is $\frac{49}{3}-15=\frac43$
Explanation. Dantzig's solution has at most one fractional variable, here $x_3=\frac46=\frac23$; MIP heuristics start from this solution to find integer solutions.
eh-f-406 · level teorema · notes
Local branching for $P\,||\,C_{\max}$ (binary variables $x_{jh}$) adds the constraint $\Delta(\vet x,\bar{\vet x})\le 2$, with $\bar{\vet x}$ the incumbent. Which assignments remain feasible for the sub-MIP?
  1. Only the incumbent $\bar{\vet x}$
  2. Those that swap two jobs
  3. Those that move at most one job
  4. Those that move at most two jobs
Explanation. For two assignments $\Delta=2r$, with $r$ the number of jobs on different machines: $\Delta\le2$ means $r\le1$, that is, the move neighbourhood. A swap moves two jobs ($\Delta=4$).
eh-f-407 · level teorema · notes
Relax-and-fix solves a sequence of MIPs: the variables of the current block are integer, those of the previous blocks fixed, those of the next blocks relaxed. Which statement holds?
  1. It needs a feasible starting solution
  2. It can end without a solution: fixings are not revised
  3. It always finds an optimal solution of the MIP
  4. It solves only linear programming problems
Explanation. The variables fixed in the first blocks never change again: a wrong choice can make the next blocks infeasible (or give a non-optimal solution). It starts from the relaxation, not from an incumbent.
eh-f-408 · level teorema · notes
The feasibility pump alternates a rounding and a linear program that minimizes the distance $\Delta(\vet x,\bar{\vet x})$ from the rounded point $\bar{\vet x}$. When does it stop with success?
  1. When the solution of the linear program is integer
  2. When the distance increases between two iterations
  3. Right after the first rounding
  4. When the linear program is infeasible
Explanation. Zero distance means that the point feasible for the relaxation coincides with an integer point: it is a feasible solution of the MIP. The method looks for feasibility, not for the optimum.
eh-f-409 · level teorema · notes
Diving fixes a fractional variable at every step and solves the linear relaxation again. Which outcome is possible?
  1. It always finds a feasible solution
  2. It proves the optimality of the solution
  3. It never fixes a variable to $0$
  4. The relaxation becomes infeasible
Explanation. Diving is a dive into a single branch of the tree, without going back: a sequence of fixings can empty the feasible region. It gives no bound to prove optimality.
eh-f-410 · level teorema · notes
Minimization problem with integer objective: a MIP heuristic stops with an incumbent of value $18$ and the linear relaxation is $17$. What can be concluded?
  1. The optimal value is $17$
  2. The gap is zero: $18$ is optimal
  3. The optimal value is $17$ or $18$
  4. The optimal value is $18$
Explanation. $17\le z(I)\le18$ and $z(I)$ is an integer: the doubt between the two values remains. The gap is $\frac{18-17}{17}\approx5.9\%$; closing it requires a better bound or a proof of optimality.
eh-f-411 · level ipotesi · notes
Rounding down a solution of the linear relaxation gives a feasible solution for the 0/1 knapsack. For which model is this not guaranteed?
  1. The 0/1 knapsack with a large capacity
  2. Bin packing, with $\sum_bx_{jb}=1$ for every item
  3. The 0/1 knapsack with integer data
  4. Any model with $\le$ constraints and non-negative coefficients
Explanation. With $\le$ constraints, non-negative coefficients and right-hand sides, decreasing the variables violates nothing. In bin packing an item split between two bins, rounded down, is no longer assigned.
eh-f-412 · level ipotesi · notes
RINS fixes the variables that have the same value in the incumbent $\bar{\vet x}$ and in the solution $\tilde{\vet x}$ of the relaxation, and solves the sub-MIP on the others. What does it need?
  1. An incumbent and a solution of the relaxation
  2. Only the solution of the relaxation
  3. A dual bound equal to the incumbent
  4. An integer solution of the relaxation
Explanation. Comparing $\bar{\vet x}$ and $\tilde{\vet x}$ requires both; if $\tilde{\vet x}$ were integer the problem would already be solved, and a bound equal to the incumbent would prove it optimal.
eh-f-413 · level ipotesi · notes
What does a MIP-based heuristic (matheuristic) use, by definition?
  1. A neighbourhood defined on permutations
  2. A population of solutions to recombine
  3. Only constructive rules of greedy type
  4. The linear relaxation of the model and a MIP solver
Explanation. A MIP heuristic works on the model of the problem, through its linear relaxation and a MIP solver; constructive heuristics, local search and metaheuristics work on a representation of the solutions.
eh-f-414 · level ipotesi · notes
Local branching with the constraint $\Delta(\vet x,\bar{\vet x})\le k$ explores the solutions close to the incumbent. What happens if $k$ is too small?
  1. The solution found is not feasible
  2. A stronger relaxation is needed
  3. The sub-MIP may contain no better solution
  4. The sub-MIP becomes as large as the MIP
Explanation. With a small $k$ the sub-MIP is easy but the neighbourhood is small: it may contain only solutions not better than the incumbent. With a large $k$ it approaches the whole MIP, which is hard.
eh-f-415 · level ipotesi · notes
What is a heuristic solution passed to the solver as a MIP start used for in branch-and-bound?
  1. It reduces the number of variables
  2. It gives an incumbent at once to prune nodes
  3. It gives a better dual bound
  4. It strengthens the linear relaxation
Explanation. The MIP start is a primal bound: the nodes whose relaxation bound is not better than the incumbent are pruned. The dual bound comes from the relaxations, not from feasible solutions.
eh-f-422 · level teorema · notes
For binary variables the distance $\Delta(\vet x,\bar{\vet x})=\sum_j|x_j-\bar x_j|$ from a point $\bar{\vet x}\in\{0,1\}^n$ can be written linearly as:
  1. $\sum_jx_j\bar x_j+\sum_j(1-x_j)(1-\bar x_j)$
  2. $\sum_{j:\bar x_j=1}x_j+\sum_{j:\bar x_j=0}(1-x_j)$
  3. $\sum_{j:\bar x_j=0}x_j+\sum_{j:\bar x_j=1}(1-x_j)$
  4. $\sum_{j:\bar x_j=1}(x_j-1)+\sum_{j:\bar x_j=0}x_j$
Explanation. If $\bar x_j=0$ then $|x_j-0|=x_j$, if $\bar x_j=1$ then $|x_j-1|=1-x_j$ (with $0\le x_j\le1$); the sum of products counts the agreements instead, $n-\Delta$. It is the form used by the feasibility pump, local branching and proximity search.
eh-f-423 · level ipotesi · notes
Proximity search replaces the objective with the distance $\Delta(\vet x,\bar{\vet x})$ and adds $f(\vet x)\le f(\bar{\vet x})-\theta$. Why does it need an incumbent?
  1. It is needed to obtain a dual bound of the problem
  2. The constraint and the distance use $\bar{\vet x}$
  3. It is needed to solve the linear relaxation
  4. It is needed to fix variables as in RINS
Explanation. Both the new objective and the improvement constraint depend on the incumbent $\bar{\vet x}$: without a feasible solution the method cannot start. It fixes no variables and gives no dual bound.
eh-f-424 · level ipotesi · notes
Fix-and-optimize improves a solution by re-optimizing one block of variables at a time, with the others fixed. What does it need that relax-and-fix does not?
  1. A feasible starting solution
  2. The linear relaxation of the model
  3. A MIP solver for the subproblems
  4. An integer-valued objective function
Explanation. Fix-and-optimize fixes the variables outside the block at the values of a feasible solution, which must therefore exist; relax-and-fix starts from the relaxation and builds the solution block by block.
eh-f-425 · level ipotesi · notes
For the 0/1 knapsack, rounding down the solution of the relaxation gives a feasible solution. Why does rounding to the nearest integer $\lfloor x_j+\frac12\rfloor$ not guarantee it?
  1. The solution of the relaxation may be integer
  2. The profits may not be integers
  3. It changes the sign of the objective function
  4. Rounding up can exceed the capacity
Explanation. A variable with $x_j\ge\frac12$ goes to $1$ and the total weight may exceed $c$. Rounding down only decreases the weight, so it stays feasible.
eh-f-426 · level ipotesi · notes
The experiment with the parameters of Gurobi's heuristics uses a work limit instead of a time limit. Why?
  1. With a work limit the optimum is found
  2. The work limit switches the heuristics off
  3. Work is deterministic: runs are reproducible
  4. There is no time limit in gurobipy
Explanation. Time depends on the computer and its load, the work measured by the solver does not: with a single thread the runs repeat identically. The limit does not change what the heuristics do.
eh-f-456 · level teorema · notes
0/1 knapsack: incumbent $\bar{\vet x}=(1,0,1,0)$ and solution of the relaxation $\tilde{\vet x}=(1,\frac14,1,0)$. Which variables remain free in the RINS sub-MIP?
  1. Only $x_2$
  2. $x_2$ and $x_4$
  3. All except $x_1$
  4. None
Explanation. RINS fixes the variables with the same value in $\bar{\vet x}$ and $\tilde{\vet x}$: $x_1=1$, $x_3=1$, $x_4=0$. Only $x_2$ remains free, fractional in the relaxation.
eh-f-457 · level teorema · notes
Local branching for the 0/1 knapsack with the constraint $\Delta(\vet x,\bar{\vet x})\le1$. Which solutions does the sub-MIP explore?
  1. Only the vectors with one more item
  2. All the feasible solutions
  3. The vectors differing in two variables
  4. $\bar{\vet x}$ and the vectors at distance $1$
Explanation. $\Delta\le1$ allows changing at most one variable: it is the flip neighbourhood of local search (removing or adding one item), plus the incumbent itself.
eh-f-458 · level teorema · notes
Proximity search, minimization problem: each sub-MIP requires $f(\vet x)\le f(\bar{\vet x})-\theta$. By how much does a successful iteration improve the incumbent?
  1. Up to the optimal value
  2. By at most $\theta$
  3. By at least $\theta$
  4. By exactly $1$
Explanation. The new solution satisfies the improvement constraint, hence it is worth at most $f(\bar{\vet x})-\theta$: the improvement is at least $\theta$, and it may be larger.
eh-f-459 · level teorema · notes
During the diving of a maximization problem, how does the value of the linear relaxation change at each fixing?
  1. It increases by at least $1$
  2. It never increases
  3. It never decreases
  4. It always stays the same
Explanation. Fixing a variable adds a constraint to the relaxation: the region shrinks and the optimal value of a maximization problem cannot grow.
eh-f-460 · level teorema · notes
Relax-and-fix with a single block containing all the integer variables: what does it solve?
  1. The whole MIP, to optimality
  2. Only the linear relaxation
  3. An infeasible problem
  4. A sub-MIP with fixed variables
Explanation. With a single block there is nothing to relax or to fix: the first and only subproblem is the MIP itself. Blocks are used to make the subproblems smaller.
eh-f-461 · level teorema · notes
Why does fix-and-optimize never worsen the current solution?
  1. Because it solves the whole MIP every time
  2. Because it relaxes the next blocks
  3. Because it accepts worsenings with a probability
  4. The current solution is feasible for every sub-MIP
Explanation. The variables outside the block are fixed at the values of the current solution, which stays feasible for the sub-MIP: the optimum of the sub-MIP is at least as good.
eh-f-462 · level ipotesi · notes
What must a solution passed to the solver as a MIP start satisfy to become the incumbent at once?
  1. Have all the variables at $0$
  2. Have value equal to the dual bound
  3. Be feasible for the model
  4. Be optimal for the relaxation
Explanation. The solver checks the MIP start: if it is feasible it becomes the incumbent (primal bound) and is used for pruning; an infeasible point gives no primal bound.
eh-f-463 · level ipotesi · notes
The local branching constraint $\Delta(\vet x,\bar{\vet x})\le k$ is a linear constraint on the original variables only when:
  1. The relaxation has an integer solution
  2. The variables are binary
  3. The problem is a maximization problem
  4. $k$ is even
Explanation. For binary variables $|x_j-\bar x_j|$ is $x_j$ or $1-x_j$: the sum is linear. For general integer variables auxiliary variables are needed.
eh-f-464 · level ipotesi · notes
In which case can RINS not give a solution different from the incumbent?
  1. If $\bar{\vet x}$ and $\tilde{\vet x}$ coincide
  2. If the relaxation has a fractional variable
  3. If the incumbent is better than the relaxation
  4. If the problem is a maximization problem
Explanation. If the two solutions coincide, RINS fixes all the integer variables at the values of the incumbent: the sub-MIP has no other solution (and an integer $\tilde{\vet x}$ proves optimality).
eh-f-465 · level ipotesi · notes
How are the blocks of variables chosen in fix-and-optimize?
  1. A single block with all the variables
  2. One block for each constraint
  3. At random, each time different
  4. Small, with fast sub-MIPs
Explanation. Each block gives a sub-MIP that the solver must solve quickly, but a block that is too small improves little: the choice balances the two (for instance, a window of periods in lot sizing).
eh-f-466 · level ipotesi · notes
Diving may end in an infeasible relaxation. Why can it not go back as branch-and-bound does?
  1. Because the solver does not allow it
  2. Because it does not use the linear relaxation
  3. It follows a single branch, without exploring the tree
  4. Because the fixed variables are continuous
Explanation. Diving is a heuristic: it goes down a single branch of the tree fixing variables. Variants with a little backtracking exist, but pure diving stops without a solution.

Generated questions (14)

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

1. Heuristic algorithms: definitions (2)

Example 1 · eh-g-heur-gap · level media · notes
Symmetric TSP with $5$ cities and distances $\begin{array}{c|ccccc} d_{ij} & 1 & 2 & 3 & 4 & 5\\ \hline 1 & - & 9 & 10 & 13 & 14\\ 2 & 9 & - & 3 & 13 & 10\\ 3 & 10 & 3 & - & 10 & 14\\ 4 & 13 & 13 & 10 & - & 2\\ 5 & 14 & 10 & 14 & 2 & -\end{array}$. Nearest neighbour from city $1$ (each time the nearest unvisited city, ties smallest index, then back to $1$) gives the tour $\mathscr{A}(I)$; the bound $\mathrm{LB}=\left\lceil\frac12\sum_i(a_i+b_i)\right\rceil$ uses the two smallest distances $a_i,b_i$ of every city. What is the gap $\frac{\mathscr{A}(I)-\mathrm{LB}}{\mathrm{LB}}$?
  1. $\frac{2}{19}$
  2. $4$
  3. $\frac{2}{17}$
  4. $\frac{19}{17}$
Explanation. $\mathscr{A}(I)=38$ and $\mathrm{LB}=34$: gap $\frac{2}{17}$. The relative error of the tour with respect to the optimum does not exceed this value.
Example 2 · eh-g-heur-gap · level media · notes
Symmetric TSP with $5$ cities and distances $\begin{array}{c|ccccc} d_{ij} & 1 & 2 & 3 & 4 & 5\\ \hline 1 & - & 7 & 13 & 6 & 3\\ 2 & 7 & - & 7 & 14 & 13\\ 3 & 13 & 7 & - & 11 & 14\\ 4 & 6 & 14 & 11 & - & 12\\ 5 & 3 & 13 & 14 & 12 & -\end{array}$. Nearest neighbour from city $1$ (each time the nearest unvisited city, ties smallest index, then back to $1$) gives the tour $\mathscr{A}(I)$; the bound $\mathrm{LB}=\left\lceil\frac12\sum_i(a_i+b_i)\right\rceil$ uses the two smallest distances $a_i,b_i$ of every city. What is the gap $\frac{\mathscr{A}(I)-\mathrm{LB}}{\mathrm{LB}}$?
  1. $\frac{3}{37}$
  2. $\frac{3}{40}$
  3. $\frac{40}{37}$
  4. $3$
Explanation. $\mathscr{A}(I)=40$ and $\mathrm{LB}=37$: gap $\frac{3}{37}$. The relative error of the tour with respect to the optimum does not exceed this value.
Example 1 · eh-g-heur-flip · level facile · notes
0-1 knapsack with capacity $c=13$ and items $\begin{array}{c|ccccc}j & 1 & 2 & 3 & 4 & 5\\ \hline p_j & 9 & 4 & 10 & 8 & 6\\ w_j & 5 & 2 & 6 & 6 & 5\end{array}$. The current solution is $x=(1,0,0,1,0)$; the flip neighbourhood contains the feasible solutions obtained by changing a single component of $x$ (adding or removing one item). What is the value of the best neighbour?
  1. $27$
  2. $22$
  3. $21$
  4. $17$
Explanation. The current solution is worth $17$ and weighs $11$; among the feasible neighbours the best is worth $21$. Ignoring the capacity one would reach $27$, but that neighbour is infeasible.
Example 2 · eh-g-heur-flip · level facile · notes
0-1 knapsack with capacity $c=10$ and items $\begin{array}{c|ccccc}j & 1 & 2 & 3 & 4 & 5\\ \hline p_j & 4 & 12 & 3 & 3 & 9\\ w_j & 2 & 6 & 6 & 4 & 3\end{array}$. The current solution is $x=(0,0,0,1,1)$; the flip neighbourhood contains the feasible solutions obtained by changing a single component of $x$ (adding or removing one item). What is the value of the best neighbour?
  1. $16$
  2. $12$
  3. $17$
  4. $24$
Explanation. The current solution is worth $12$ and weighs $7$; among the feasible neighbours the best is worth $16$. Ignoring the capacity one would reach $24$, but that neighbour is infeasible.

2. Constructive heuristics (5)

Example 1 · eh-g-bpp-ffd · level facile · notes
Bin packing (BPP: items into bins of capacity $c$, minimizing the bins) with $c=11$ and weights $w=(6,8,8,2,8,6,6)$ (items $1,\dots,7$). The sorting by non-increasing weight breaks ties by smaller index; bins are numbered in order of opening. Which vector $bin$ (bin of each item, in the original numbering) does Best Fit Decreasing (BFD) produce?
  1. $bin=(1,2,3,1,4,5,6)$
  2. $bin=(4,1,2,4,3,5,6)$
  3. $bin=(4,1,2,6,3,5,6)$
  4. $bin=(4,1,2,1,3,5,6)$
Explanation. First the items are sorted by non-increasing weight ($2,3,5,1,6,7,4$), then Best Fit is applied: $bin=(4,1,2,1,3,5,6)$, $6$ bins. Typical mistakes: forgetting the sorting or using the other selection rule.
Example 2 · eh-g-bpp-ffd · level facile · notes
Bin packing (BPP: items into bins of capacity $c$, minimizing the bins) with $c=11$ and weights $w=(8,4,2,5,8,8,7)$ (items $1,\dots,7$). The sorting by non-increasing weight breaks ties by smaller index; bins are numbered in order of opening. Which vector $bin$ (bin of each item, in the original numbering) does Best Fit Decreasing (BFD) produce?
  1. $bin=(1,4,1,5,2,3,4)$
  2. $bin=(1,5,5,5,2,3,4)$
  3. $bin=(1,2,1,2,3,4,5)$
  4. $bin=(1,5,4,5,2,3,4)$
Explanation. First the items are sorted by non-increasing weight ($1,5,6,7,4,2,3$), then Best Fit is applied: $bin=(1,4,1,5,2,3,4)$, $5$ bins. Typical mistakes: forgetting the sorting or using the other selection rule.
Example 1 · eh-g-vcp-gc · level facile · notes
Graph $G=(V,E)$ with $V=\{1,\dots,6\}$ and $E=\{\{1,3\},\{1,5\},\{2,3\},\{2,4\},\{2,5\},\{2,6\},\{4,5\},\{4,6\},\{5,6\}\}$. The greedy coloring $GC$ examines the vertices in the order of the list $\lambda=(2,1,5,3,6,4)$ and gives each the smallest color (integer $\ge 1$) not used by its already colored neighbors. Which coloring $col=(col[1],\dots,col[6])$ does it return?
  1. $col=(1,1,2,3,2,4)$
  2. $col=(2,4,1,1,3,2)$
  3. $col=(1,1,2,2,3,4)$
  4. $col=(1,1,2,4,2,3)$
Explanation. The vertices are examined in the order of $\lambda$ and each one gets the smallest color not used by its colored neighbours: $col=(1,1,2,4,2,3)$. The order matters: with the list $(1,\dots,6)$ one gets $(1,1,2,2,3,4)$.
Example 2 · eh-g-vcp-gc · level facile · notes
Graph $G=(V,E)$ with $V=\{1,\dots,6\}$ and $E=\{\{1,2\},\{1,3\},\{2,3\},\{2,5\},\{2,6\},\{4,5\},\{4,6\}\}$. The greedy coloring $GC$ examines the vertices in the order of the list $\lambda=(6,3,2,4,5,1)$ and gives each the smallest color (integer $\ge 1$) not used by its already colored neighbors. Which coloring $col=(col[1],\dots,col[6])$ does it return?
  1. $col=(1,2,3,2,1,1)$
  2. $col=(1,2,3,1,3,3)$
  3. $col=(3,2,1,2,1,1)$
  4. $col=(2,1,3,1,2,2)$
Explanation. The vertices are examined in the order of $\lambda$ and each one gets the smallest color not used by its colored neighbours: $col=(3,2,1,2,1,1)$. The order matters: with the list $(1,\dots,6)$ one gets $(1,2,3,1,3,3)$.
Example 1 · eh-g-vcp-dsatur · level facile · notes
Graph $G=(V,E)$ with $V=\{1,\dots,6\}$ and $E=\{\{1,2\},\{1,3\},\{2,3\},\{2,6\},\{3,4\},\{4,5\},\{4,6\}\}$. At every step $DSATUR$ colors the uncolored vertex of maximum saturation degree (number of distinct colors among its colored neighbors), with the smallest free color; ties: more uncolored neighbors, then smallest index. In which order does it color the vertices?
  1. $(2,3,1,4,5,6)$
  2. $(2,3,4,1,6,5)$
  3. $(1,2,3,4,6,5)$
  4. $(2,3,1,4,6,5)$
Explanation. At each step the uncolored vertex with the most different colors among its neighbours is chosen: order $(2,3,1,4,5,6)$, with $3$ colors. The tie-breaking degree counts the vertices not yet colored, and it is updated at each step.
Example 2 · eh-g-vcp-dsatur · level facile · notes
Graph $G=(V,E)$ with $V=\{1,\dots,6\}$ and $E=\{\{1,5\},\{2,4\},\{2,5\},\{2,6\},\{3,4\},\{3,5\},\{4,6\}\}$. At every step $DSATUR$ colors the uncolored vertex of maximum saturation degree (number of distinct colors among its colored neighbors), with the smallest free color; ties: more uncolored neighbors, then smallest index. In which order does it color the vertices?
  1. $(1,5,2,3,4,6)$
  2. $(2,4,6,5,1,3)$
  3. $(2,4,5,3,6,1)$
  4. $(2,4,6,5,3,1)$
Explanation. At each step the uncolored vertex with the most different colors among its neighbours is chosen: order $(2,4,6,5,1,3)$, with $3$ colors. The tie-breaking degree counts the vertices not yet colored, and it is updated at each step.
Example 1 · eh-g-tsp-nn · level facile · notes
Symmetric TSP (shortest tour visiting all cities) with distances $\begin{array}{c|ccccc} d_{ij} & 1 & 2 & 3 & 4 & 5\\ \hline 1 & - & 4 & 4 & 2 & 3\\ 2 & 4 & - & 5 & 7 & 3\\ 3 & 4 & 5 & - & 6 & 7\\ 4 & 2 & 7 & 6 & - & 9\\ 5 & 3 & 3 & 7 & 9 & -\end{array}$. The $NN$ (nearest neighbour) heuristic starts from city $1$, always moves to the closest unvisited city (ties: smaller index) and finally returns to the start. What is the length of the tour?
  1. $20$
  2. $16$
  3. $19$
  4. $27$
Explanation. $NN$ visits $(1,4,3,2,5)$ and goes back to $1$: length $19$. Typical mistake: forgetting the closing edge (one would get $16$).
Example 2 · eh-g-tsp-nn · level facile · notes
Symmetric TSP (shortest tour visiting all cities) with distances $\begin{array}{c|ccccc} d_{ij} & 1 & 2 & 3 & 4 & 5\\ \hline 1 & - & 11 & 10 & 3 & 12\\ 2 & 11 & - & 12 & 9 & 9\\ 3 & 10 & 12 & - & 4 & 9\\ 4 & 3 & 9 & 4 & - & 7\\ 5 & 12 & 9 & 9 & 7 & -\end{array}$. The $NN$ (nearest neighbour) heuristic starts from city $1$, always moves to the closest unvisited city (ties: smaller index) and finally returns to the start. What is the length of the tour?
  1. $25$
  2. $40$
  3. $46$
  4. $36$
Explanation. $NN$ visits $(1,4,3,5,2)$ and goes back to $1$: length $36$. Typical mistake: forgetting the closing edge (one would get $25$).
Example 1 · eh-g-pcmax-lpt · level facile · notes
Scheduling $P\,||\,C_{\max}$: $m=3$ identical machines, processing times $t=(2,4,6,3,5,5,7)$, the makespan (maximum load) is minimized. $LPT$ sorts the jobs by non-increasing time and assigns each to the least loaded machine (ties: smaller index). What is the makespan of the $LPT$ solution?
  1. $14$
  2. $11$
  3. $13$
  4. $12$
Explanation. $LPT$ sorts the jobs by non-increasing time and assigns each one to a least loaded machine: makespan $12$. $LIST$ in the given order gives $13$; the lower bound $\max\{\max_j t_j,\lceil\sum_j t_j/m\rceil\}$ is $11$.
Example 2 · eh-g-pcmax-lpt · level facile · notes
Scheduling $P\,||\,C_{\max}$: $m=3$ identical machines, processing times $t=(7,9,8,7,8,8,3)$, the makespan (maximum load) is minimized. $LPT$ sorts the jobs by non-increasing time and assigns each to the least loaded machine (ties: smaller index). What is the makespan of the $LPT$ solution?
  1. $18$
  2. $17$
  3. $20$
  4. $19$
Explanation. $LPT$ sorts the jobs by non-increasing time and assigns each one to a least loaded machine: makespan $18$. $LIST$ in the given order gives $17$; the lower bound $\max\{\max_j t_j,\lceil\sum_j t_j/m\rceil\}$ is $17$.

3. Local search (4)

Example 1 · eh-g-tsp-2opt · level media · notes
Symmetric TSP with distances $\begin{array}{c|cccccc} d_{ij} & 1 & 2 & 3 & 4 & 5 & 6\\ \hline 1 & - & 8 & 8 & 10 & 11 & 3\\ 2 & 8 & - & 10 & 8 & 8 & 11\\ 3 & 8 & 10 & - & 2 & 11 & 4\\ 4 & 10 & 8 & 2 & - & 4 & 2\\ 5 & 11 & 8 & 11 & 4 & - & 3\\ 6 & 3 & 11 & 4 & 2 & 3 & -\end{array}$. The current tour is $\sigma=(1,6,5,2,4,3)$, of length $32$. A 2-opt move removes two non-adjacent edges of the tour and reconnects the two paths in the other possible way; with the best-improvement rule the move that reduces the length the most is applied. What is the tour length after one iteration?
  1. $32$
  2. $31$
  3. $26$
  4. $33$
Explanation. For every move $\Delta=d_{u_1u_2}+d_{v_1v_2}-d_{u_1v_1}-d_{u_2v_2}$; the best one has $\Delta=-1$ (positions $i=1$, $j=4$), hence $32-1=31$. The first improving move ($\Delta=-1$) is the one of first improvement.
Example 2 · eh-g-tsp-2opt · level media · notes
Symmetric TSP with distances $\begin{array}{c|cccccc} d_{ij} & 1 & 2 & 3 & 4 & 5 & 6\\ \hline 1 & - & 6 & 11 & 5 & 3 & 6\\ 2 & 6 & - & 11 & 10 & 9 & 12\\ 3 & 11 & 11 & - & 10 & 9 & 11\\ 4 & 5 & 10 & 10 & - & 10 & 3\\ 5 & 3 & 9 & 9 & 10 & - & 12\\ 6 & 6 & 12 & 11 & 3 & 12 & -\end{array}$. The current tour is $\sigma=(1,3,2,5,4,6)$, of length $50$. A 2-opt move removes two non-adjacent edges of the tour and reconnects the two paths in the other possible way; with the best-improvement rule the move that reduces the length the most is applied. What is the tour length after one iteration?
  1. $40$
  2. $42$
  3. $45$
  4. $58$
Explanation. For every move $\Delta=d_{u_1u_2}+d_{v_1v_2}-d_{u_1v_1}-d_{u_2v_2}$; the best one has $\Delta=-8$ (positions $i=1$, $j=4$), hence $50-8=42$. The first improving move ($\Delta=-5$) is the one of first improvement.
Example 1 · eh-g-pcmax-move · level facile · notes
Scheduling $P\,||\,C_{\max}$ (minimize the makespan, the maximum load) with $m=3$ machines, times $t=(5,9,2,9,5,8)$ and current assignment $\mathrm{mach}=(3,2,1,3,3,1)$ ($\mathrm{mach}_j$ is the machine of job $j$; loads $(10,9,19)$). The move neighborhood moves a job $j$ to another machine $h$; best improvement chooses the move that decreases the makespan the most (moves examined for $j=1,\dots,n$ and $h=1,\dots,m$; ties: the first one is kept). Which move does it choose?
  1. job $1$ to machine $2$
  2. job $1$ to machine $1$
  3. job $4$ to machine $2$
  4. job $2$ to machine $1$
Explanation. The makespan change of the chosen move is $-5$, the most negative (makespan from $19$ to $14$). The first improving move (first improvement) has change $-4$; moving a job from a non-critical machine does not decrease the makespan.
Example 2 · eh-g-pcmax-move · level facile · notes
Scheduling $P\,||\,C_{\max}$ (minimize the makespan, the maximum load) with $m=3$ machines, times $t=(3,6,3,8,1,3)$ and current assignment $\mathrm{mach}=(1,3,2,3,3,1)$ ($\mathrm{mach}_j$ is the machine of job $j$; loads $(6,3,15)$). The move neighborhood moves a job $j$ to another machine $h$; best improvement chooses the move that decreases the makespan the most (moves examined for $j=1,\dots,n$ and $h=1,\dots,m$; ties: the first one is kept). Which move does it choose?
  1. job $1$ to machine $2$
  2. job $2$ to machine $1$
  3. job $4$ to machine $2$
  4. job $2$ to machine $2$
Explanation. The makespan change of the chosen move is $-6$, the most negative (makespan from $15$ to $9$). The first improving move (first improvement) has change $-3$; moving a job from a non-critical machine does not decrease the makespan.
Example 1 · eh-g-pcmax-descent · level complessa · notes
$P\,||\,C_{\max}$ with $m=3$ machines and jobs of duration $t=(2,6,5,7,7,9,4)$; the starting solution assigns the jobs to the machines $(1,1,2,1,1,1,1)$. Local search is applied with the move neighbourhood (one job goes to another machine) and the auxiliary objective $\sum_hL_h^2$ to be minimized ($L_h$ = load of machine $h$), with the best improvement rule: at every iteration the move decreasing $\sum_hL_h^2$ the most is applied (ties: smallest job index, then smallest machine index), until no move decreases it. What is the final makespan and how many moves are applied?
  1. final makespan $16$, after $3$ moves
  2. final makespan $35$, after $0$ moves
  3. final makespan $14$, after $10$ moves
  4. final makespan $15$, after $3$ moves
Explanation. Initial loads $(35,5,0)$, makespan $35$. Moving job $j$ from machine $a$ to $b$ changes $\sum_hL_h^2$ by $2t_j(L_b-L_a+t_j)$; the descent applies $3$ moves and stops with makespan $15$. With first improvement the descent would differ ($10$ moves, makespan $14$).
Example 2 · eh-g-pcmax-descent · level complessa · notes
$P\,||\,C_{\max}$ with $m=3$ machines and jobs of duration $t=(4,8,2,4,3,9,2)$; the starting solution assigns the jobs to the machines $(2,3,3,1,3,3,3)$. Local search is applied with the move neighbourhood (one job goes to another machine) and the auxiliary objective $\sum_hL_h^2$ to be minimized ($L_h$ = load of machine $h$), with the best improvement rule: at every iteration the move decreasing $\sum_hL_h^2$ the most is applied (ties: smallest job index, then smallest machine index), until no move decreases it. What is the final makespan and how many moves are applied?
  1. final makespan $24$, after $0$ moves
  2. final makespan $13$, after $3$ moves
  3. final makespan $12$, after $3$ moves
  4. final makespan $12$, after $6$ moves
Explanation. Initial loads $(4,4,24)$, makespan $24$. Moving job $j$ from machine $a$ to $b$ changes $\sum_hL_h^2$ by $2t_j(L_b-L_a+t_j)$; the descent applies $3$ moves and stops with makespan $12$. With first improvement the descent would differ ($6$ moves, makespan $12$).
Example 1 · eh-g-tsp-nn2opt · level complessa · notes
TSP with $6$ cities and symmetric distances $\begin{array}{c|cccccc} d_{ij} & 1 & 2 & 3 & 4 & 5 & 6\\ \hline 1 & - & 6 & 6 & 8 & 8 & 1\\ 2 & 6 & - & 8 & 6 & 6 & 8\\ 3 & 6 & 8 & - & 1 & 8 & 2\\ 4 & 8 & 6 & 1 & - & 3 & 1\\ 5 & 8 & 6 & 8 & 3 & - & 1\\ 6 & 1 & 8 & 2 & 1 & 1 & -\end{array}$. The nearest neighbour tour from city $1$ is built (ties: smallest city index), written as a sequence $(t_1,\dots,t_6)$ with $t_1=1$. Then 2-opt is applied with the first improvement rule: the pairs of positions $(i,j)$ with $i=1,\dots,5$ and $j=i+2,\dots,6$ (except $(1,6)$) are examined; the move removes the edges $\{t_i,t_{i+1}\}$ and $\{t_j,t_{j+1}\}$ (with $t_7=t_1$), adds $\{t_i,t_j\}$ and $\{t_{i+1},t_{j+1}\}$ reversing the stretch $t_{i+1},\dots,t_j$, and is applied as soon as it shortens the tour; after every move the scan restarts from $(1,3)$. What is the length of the final tour and how many moves are applied?
  1. final length $21$, after $3$ moves
  2. final length $21$, after $2$ moves
  3. final length $22$, after $2$ moves
  4. final length $25$, after $0$ moves
Explanation. Nearest neighbour gives $(1,6,4,3,2,5)$, length $25$. 2-opt applies $2$ moves and stops at the local optimum $(1,6,5,2,4,3)$, length $21$.
Example 2 · eh-g-tsp-nn2opt · level complessa · notes
TSP with $6$ cities and symmetric distances $\begin{array}{c|cccccc} d_{ij} & 1 & 2 & 3 & 4 & 5 & 6\\ \hline 1 & - & 8 & 7 & 1 & 7 & 3\\ 2 & 8 & - & 1 & 2 & 9 & 8\\ 3 & 7 & 1 & - & 8 & 1 & 8\\ 4 & 1 & 2 & 8 & - & 4 & 2\\ 5 & 7 & 9 & 1 & 4 & - & 9\\ 6 & 3 & 8 & 8 & 2 & 9 & -\end{array}$. The nearest neighbour tour from city $1$ is built (ties: smallest city index), written as a sequence $(t_1,\dots,t_6)$ with $t_1=1$. Then 2-opt is applied with the first improvement rule: the pairs of positions $(i,j)$ with $i=1,\dots,5$ and $j=i+2,\dots,6$ (except $(1,6)$) are examined; the move removes the edges $\{t_i,t_{i+1}\}$ and $\{t_j,t_{j+1}\}$ (with $t_7=t_1$), adds $\{t_i,t_j\}$ and $\{t_{i+1},t_{j+1}\}$ reversing the stretch $t_{i+1},\dots,t_j$, and is applied as soon as it shortens the tour; after every move the scan restarts from $(1,3)$. What is the length of the final tour and how many moves are applied?
  1. final length $17$, after $1$ moves
  2. final length $16$, after $1$ moves
  3. final length $17$, after $0$ moves
  4. final length $16$, after $2$ moves
Explanation. Nearest neighbour gives $(1,4,2,3,5,6)$, length $17$. 2-opt applies $1$ moves and stops at the local optimum $(1,5,3,2,4,6)$, length $16$.

4. Metaheuristics (2)

Example 1 · eh-g-sa-prob · level facile · notes
In simulated annealing for a minimization problem, at temperature $T=7$ a neighbour worsening the objective by $\delta=10$ is proposed. With the Metropolis rule, with which probability is it accepted?
  1. $e^{-\frac{7}{10}}$
  2. $e^{-\frac{10}{7}}$
  3. $e^{-70}$
  4. $1$
Explanation. A worsening $\delta>0$ is accepted with probability $e^{-\delta/T}=e^{-\frac{10}{7}}$; an improvement would be accepted with probability $1$.
Example 2 · eh-g-sa-prob · level facile · notes
In simulated annealing for a minimization problem, at temperature $T=9$ a neighbour worsening the objective by $\delta=5$ is proposed. With the Metropolis rule, with which probability is it accepted?
  1. $e^{-45}$
  2. $1$
  3. $e^{-\frac{5}{9}}$
  4. $e^{-\frac{9}{5}}$
Explanation. A worsening $\delta>0$ is accepted with probability $e^{-\delta/T}=e^{-\frac{5}{9}}$; an improvement would be accepted with probability $1$.
Example 1 · eh-g-ga-cross · level facile · notes
Genetic algorithm for the 0-1 knapsack with binary encoding ($x_j=1$ if item $j$ is chosen). One-point crossover with cut $cut=2$ takes genes $1,\dots,cut$ from the first parent and genes $cut+1,\dots,n$ from the second. Parents $(1,1,0,1,1,1,0)$ and $(1,1,1,1,0,0,0)$: which child is obtained?
  1. $(1,1,0,1,0,0,0)$
  2. $(1,1,1,1,0,0,0)$
  3. $(1,1,1,1,1,1,0)$
  4. $(1,1,0,1,1,1,0)$
Explanation. The first $2$ genes come from $(1,1,0,1,1,1,0)$ and the others from $(1,1,1,1,0,0,0)$: $(1,1,1,1,0,0,0)$. The child may exceed the capacity and then must be repaired.
Example 2 · eh-g-ga-cross · level facile · notes
Genetic algorithm for the 0-1 knapsack with binary encoding ($x_j=1$ if item $j$ is chosen). One-point crossover with cut $cut=5$ takes genes $1,\dots,cut$ from the first parent and genes $cut+1,\dots,n$ from the second. Parents $(1,0,0,0,1,0,0)$ and $(1,1,0,1,1,1,0)$: which child is obtained?
  1. $(1,1,0,1,1,1,0)$
  2. $(1,0,0,0,1,1,0)$
  3. $(1,1,0,1,1,0,0)$
  4. $(1,0,0,0,1,0,0)$
Explanation. The first $5$ genes come from $(1,0,0,0,1,0,0)$ and the others from $(1,1,0,1,1,1,0)$: $(1,0,0,0,1,1,0)$. The child may exceed the capacity and then must be repaired.

5. MIP heuristics for the classical problems (1)

Example 1 · eh-g-kp-round · level facile · notes
0/1 knapsack with capacity $c=12$ and items already sorted by non-increasing efficiency $p_j/w_j$: $\begin{array}{c|ccccc}j & 1 & 2 & 3 & 4 & 5\\ \hline p_j & 8 & 18 & 21 & 11 & 3\\ w_j & 2 & 5 & 6 & 8 & 3\end{array}$. The optimal solution of the linear relaxation of $\mathrm{ILP}_{\mathrm{KP}}$ is $\tilde{\vet x}=(1,1,\frac{5}{6},0,0)$. What is the profit of the solution $\lfloor\tilde{\vet x}\rfloor$ obtained by rounding down?
  1. $47$
  2. $29$
  3. $26$
  4. $\frac{87}{2}$
Explanation. Rounding down keeps items $1,\dots,2$ and drops the fractional item $3$: profit $26$, feasible because the weight only decreases. $\frac{87}{2}$ is the value of the relaxation; the greedy, which continues after the item that does not fit, may do better.
Example 2 · eh-g-kp-round · level facile · notes
0/1 knapsack with capacity $c=19$ and items already sorted by non-increasing efficiency $p_j/w_j$: $\begin{array}{c|ccccc}j & 1 & 2 & 3 & 4 & 5\\ \hline p_j & 11 & 26 & 16 & 5 & 3\\ w_j & 3 & 8 & 7 & 3 & 2\end{array}$. The optimal solution of the linear relaxation of $\mathrm{ILP}_{\mathrm{KP}}$ is $\tilde{\vet x}=(1,1,1,\frac{1}{3},0)$. What is the profit of the solution $\lfloor\tilde{\vet x}\rfloor$ obtained by rounding down?
  1. $55$
  2. $58$
  3. $53$
  4. $\frac{164}{3}$
Explanation. Rounding down keeps items $1,\dots,3$ and drops the fractional item $4$: profit $53$, feasible because the weight only decreases. $\frac{164}{3}$ is the value of the relaxation; the greedy, which continues after the item that does not fit, may do better.