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?
The relative error of $\mathscr{A}$ on $I$ always equals $gap(I)$
The relative error of $\mathscr{A}$ on $I$ is at most $gap(I)$
$gap(I)$ is a lower bound on the performance ratio of $\mathscr{A}$
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)$.
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)}$?
$\mathscr{A}(I)\le 2\,z(I)$, because $\mathscr{A}$ is a $2$-approximation
$\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.
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?
$5.88\%$
$1$
$94.1\%$
$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.
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?
When every solution in $N(S)$ has a better value than $S$
When every global optimum is a local optimum with respect to $N$
When every local optimum with respect to $N$ is a global optimum
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.
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?
$\mathscr{A}(I)\ge z(I)/2$
$\mathscr{A}(I)\le z(I)$
$\mathscr{A}(I)\ge z(I)$
$\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.
Approximation algorithms are a special case of heuristic algorithms. What do they have in addition to most heuristics used in practice?
A proven guarantee on the ratio between $\mathscr{A}(I)$ and $z(I)$
The optimal solution on all small instances
The use of random choices to escape local optima
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.
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?
$10$, attained by $\{1,5,6\},\{2,3\},\{4,7\}$
$5=\max_jt_j$, attained by $\{1,5\},\{2,6\},\{3,4,7\}$
$9=\lceil27/3\rceil$, attained by $\{1,2\},\{3,4\},\{5,6,7\}$
$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$.
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?
To replace the dual bound in computing the gap
To choose the hardest instances for every heuristic
To measure exactly the error of every heuristic solution
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.
Heuristic algorithms are classified into constructive heuristics, local search, metaheuristics and ILP-based heuristics. What characterizes a constructive heuristic?
It accepts worse solutions to leave a local optimum
It extends a partial solution and never revises a choice
It starts from a complete solution and improves it by small changes
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.
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?
All four representations
The knapsack vector $x$ and the bin packing vector $bin$
Only the knapsack vector $x$
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.
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?
$n!$; yes, every vector is feasible
At most $n^n$; yes, every vector is a feasible partition
At most $n^n$; no, a bin can exceed the capacity
$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.
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?
No for both neighborhoods
Yes for flip, no for swap
No for flip, yes for swap
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.
A neighborhood is exact if every local optimum of it is a global optimum. Which of the following neighborhoods is exact?
Edge in and edge out, for the minimum spanning tree
The flip (adding or removing an item), for the knapsack
Moving one item, for bin packing
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.
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?
The borders of the search space; the global one is the farthest
The peaks of the hills; the global one is the highest peak
The passes between two valleys; the global one is the lowest
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.
Between intensification (searching better where good solutions already are) and diversification (moving to regions not yet explored), where does pure local search stand?
It balances the two thanks to worsening moves
It does neither: it chooses at random
Pure intensification: it stops at the first local optimum
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.
A heuristic algorithm can be evaluated by worst-case analysis or by experimental analysis. What does experimental analysis give?
A better dual bound for computing the gap
The typical behavior on benchmark instances
A guarantee valid for all instances of the problem
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.
According to the notes on heuristic algorithms, when can a heuristic algorithm be called good?
If it often finds, in the available time, solutions with a small gap
If it finds the optimal solution on at least one instance
If it is the fastest among the available algorithms
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.
For an optimization problem with optimal value $z(I)$ on instance $I$, what distinguishes a heuristic algorithm from an exact one?
It may return infeasible solutions, as long as their value is good
It always returns an optimal solution, but without proving it
It returns a dual bound instead of a solution
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.
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?
Because heuristics always find the optimum on large instances
Because heuristics also give a dual bound for free
Exact algorithms may take exponential time, while a good solution is often needed quickly
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.
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?
Because the split item would be the first one
It is trivial: all items fit, and taking them all is optimal
Because the instance has no feasible solution
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.
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$?
One job per machine would be optimal, with makespan $\max_j t_j$
The optimal makespan would be $\sum_j t_j/m$
Dynamic programming would be needed to solve it
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.
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?
$5$: the solution is exactly $5$ away from the optimum
$20\%$: the relative error of the solution is exactly $20\%$
$25\%$: the relative error of the solution is at least $25\%$
$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$.
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?
Constructive heuristics improve a complete solution, local search builds it
MIP heuristics never use solutions found by other heuristics
They are not alternatives: a local search usually starts from a constructive solution, and a metaheuristic contains local searches
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.
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?
Heuristic based on integer linear programming
Local search
Constructive heuristic
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.
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?
Restrict itself to feasible vectors, or accept infeasible ones and penalize them
Return them as a solution, if their profit is larger
Make them feasible by increasing the capacity
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.
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?
$18$
$216$
$90$
$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$.
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?
A global optimum may fail to be a local optimum, if the neighbourhood is large
A local optimum does not exist if the neighbourhood is not exact
A global optimum is a local optimum for every neighbourhood; a local optimum may not be global
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.
In heuristics one speaks of intensification and diversification of the exploration of the search space. What do they mean?
They are synonyms: both mean using random numbers
Intensifying is searching better near the good solutions found; diversifying is moving to unexplored regions
Intensifying is increasing the number of iterations; diversifying is using more processors
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.
How is a heuristic that makes random choices (for example with a pseudo-random number generator) evaluated correctly?
It cannot be evaluated: random results are not comparable
It is run once, with the seed giving the best result
Its best result is compared with the worst result of the other heuristics
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.
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?
It is enough to report the best value, $18$, as the quality of the heuristic
The optimal length is the average, $21.5$
A single instance or run proves nothing: many instances and comparisons at equal time are needed
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.
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?
To account for asymmetric distances
Summing over the cities every edge of the tour is counted twice, once per endpoint
Because only one of the two smallest distances is used
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.
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$?
$10$
$19$
$11$
$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.
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?
$S$ is an optimal solution
$S$ is optimal only with best improvement
$S$ has zero gap only with a dual bound
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.
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)}$?
It is at most $16.7\%$
It is exactly $20\%$
It is at least $20\%$
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$.
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?
$z(I)\ge 18$
$z(I)\le 19$
$z(I)\ge 19$
$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.
Which statement holds for every neighbourhood $N$ of an optimization problem?
A local optimum for $N$ has no neighbours
Every optimal solution is a local optimum for $N$
Every local optimum for $N$ is an optimal solution
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.
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?
$25\%$: the relative error of $40$ is at most $25\%$
$20\%$: the relative error is at least $20\%$
$25\%$: hence $z(I)=50$
$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$.
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?
The heuristic is a local search with an exact neighbourhood
The problem is a maximization problem
All the data of the instance are integers
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.
In the TSP bound $z(I)\ge\lceil\frac12\sum_i(a_i+b_i)\rceil$, why can the value be rounded up?
The number of cities is even
The tour always starts at city $1$
The distances are integers, and so is $z(I)$
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.
What does the definition of heuristic algorithm for an optimization problem $\mathscr{P}$ require?
A running time linear in the input size
A feasible solution for every instance
An optimal solution at least on small instances
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.
A neighbourhood associates with every feasible solution $S$ a set $N(S)$ of neighbours. What is required of the neighbours?
They are feasible solutions
They are better than $S$
They differ from $S$ in one variable
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.
Maximization problem with objective function $f$. When is $S$ a local optimum with respect to the neighbourhood $N$?
If $f(S)>f(S')$ for all $S'\in N(S)$
If $f(S)\ge f(S')$ for some $S'\in N(S)$
If $f(S)\le f(S')$ for all $S'\in N(S)$
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.
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?
Nothing: the gap is zero but the error is not
$\mathscr{A}(I)=z(I)$ only with integer data
$\mathscr{A}(I)$ is optimal, since $\mathrm{LB}(I)\le z(I)$
$\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.
For a problem with finitely many feasible solutions, which neighbourhood is exact whatever the instance?
The 2-opt neighbourhood of the TSP
The move neighbourhood of $P\,||\,C_{\max}$
The one where every solution neighbours all others
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).
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)}$?
Gap and error both $\approx47.1\%$
Gap $\approx47.1\%$, error $\approx38.9\%$
Gap $\approx32\%$, error $\approx28\%$
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.
Which class of heuristics builds a single solution, one element at a time, never revising a choice?
Local search from a solution
Metaheuristics, from a local optimum
MIP-based heuristics
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.
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.
What is meant by intensification in a heuristic algorithm?
Searching near the good solutions found
Moving to regions of the space not explored yet
Computing a stronger dual bound
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.
A heuristic diversifies too much and intensifies too little. What happens?
It stays trapped in the first valley
It always finds the global optimum
It stops at once at a local optimum
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.
How is the quality of a heuristic measured on an instance whose optimal value is unknown?
By the number of iterations performed
By the running time alone
By the gap with respect to the best dual bound
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.
Why must the experimental analysis of a heuristic use a large and varied set of instances?
To obtain a worst-case guarantee
To avoid conclusions that hold only on a few instances
Because on small instances it does not terminate
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.
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?
$LIST(I)\le\left(2-\frac1m\right)z(I)$ and $LPT(I)\le\left(\frac43-\frac1{3m}\right)z(I)$
$LIST(I)\le\left(2-\frac1m\right)z(I)$ and $LPT(I)\le\left(\frac54-\frac1{4m}\right)z(I)$
$LIST(I)\le\frac32\,z(I)$ and $LPT(I)\le\frac{17}{10}\,z(I)$
$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}$.
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?
$GC(I)\le\Delta(G)+1$ for every list, and on bipartite graphs it always gives $2$ colors
$GC(I)\le\Delta(G)$ for every connected graph and every vertex list
$GC(I)\le\chi(G)+1$ for every list, hence $GC$ is off by at most one color
$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$.
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?
FFD always uses the optimal number of bins
FF and FFD always use the same number of bins
There are instances on which FFD uses more bins than FF
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.
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$?
$-2$
$2$
$9$
$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)$.
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?
Each of the three orders can give arbitrarily bad solutions
$GR$ by efficiency always gives the optimal value
$GR_w$ always gives the optimal value, because it picks more items
$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$.
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?
The loads of the machines, one at a time
The swaps of two jobs between two machines
The machines, opened one at a time
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.
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?
$(11,8,8)$, makespan $11$
$(11,8,8)$, makespan $8$
$(9,9,9)$, makespan $9$
$(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.
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$?
$(0,1,2)$: only one bin is full
$(7,7,7)$: the bins are empty
$(2,3,3)$: space is left in all bins
$(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.
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?
The knapsack and bin packing
Only the TSP, not the others
TSP and $P\,||\,C_{\max}$
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.
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?
The processing time of the $P\,||\,C_{\max}$ jobs
The distance from the last city of a partial tour
The efficiency $p_j/w_j$ of the knapsack items
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)$.
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?
Here profit wins, but no order is the best on every instance
The order by efficiency is the best on every instance
The order by weight always finds the optimum
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.
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?
$GR_p=2$, $GR_w=2$, $GR=2$
$GR_p=10$, $GR_w=10$, $GR=2$
$GR_p=10$, $GR_w=2$, $GR=10$
$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.
In bin packing with capacity $c$, the «sort first, then fill» heuristics insert the heaviest items first. Why?
Because large items are worth more in the objective function
Because with sorting First Fit becomes an exact algorithm
Large items fit only into nearly empty bins; small ones fill the gaps
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.
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?
FFD opens all of its bins at the very beginning
FF puts the item of weight $2$ where the $3$ was needed
FFD uses the minimum residual capacity instead of the first bin
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$.
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?
$O(n^2)$, like First Fit
$O(n\log n)$, the time of the sorting
$O(n)$, one pass over the items
$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.
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?
Into bin $3$
Into a new bin
Into bin $1$
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.
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?
$18$
$11$
$12$
$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)$.
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?
FF $2$ bins, FFD $3$
FF $3$ bins, FFD $2$
$2$ bins for both
$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.
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?
The machine to close and the one to open
The lower bound and the stopping criterion
The number of machines and the duration of the jobs
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).
Why, in $P\,||\,C_{\max}$, do greedy heuristics assign every job to the machine that is currently the least loaded?
To use as few machines as possible
Because it always gives the optimal makespan
To make the loads grow as evenly as possible
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$).
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?
The lower bound $9$ is wrong on this instance
A long job at the end of the list raises the makespan
$LIST$ exceeds its guarantee $(2-\frac1m)z(I)$
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.
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$?
$LPT=15$, $z=12$
$LPT=12$, $z=12$
$LPT=16$, $z=12$
$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.
Constructive heuristics for the TSP split into two families, «append» and «insert». What distinguishes them?
The number of starting cities: one or all
The feasibility test: present only when inserting
Which city is chosen: the nearest or the farthest
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.
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?
It does not require computing the distances between the cities
It always guarantees the optimal tour on metric instances
The subtour stays closed: the closing edge is paid from the start
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.
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?
$(4,3,1,2)$, of length $10$
$(4,3,1,2)$, of length $12$
$(4,3,2,1)$, of length $11$
$(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.
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?
Dynamic; $O(n^2)$
Static; $O(n\log n)$
Dynamic; $O(n^3)$
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.
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?
The multi-start is always exact on metric instances
Starting from city $1$ is always the best
Nearest neighbour finds the optimum from every city
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$).
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?
Insertion costs are always zero on metric instances
The outline is built first; the cities «on the way» cost little
The farthest city must always be placed last
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.
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?
On larger instances the rules separate: here farthest insertion wins
Insertion heuristics always give the same tour
The nearest neighbour multi-start is the best rule
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.
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?
Because it scans the vertices by non-increasing degree
Because at the end it fixes the remaining conflicts
Because it always uses at most $\chi(G)$ colors
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)$.
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?
$O(n^2\log n)$
$O(n\,|E|)$
$O(n+|E|)$
$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.
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?
Greedy coloring always uses $\Delta+1$ colors
The order of the list can change the number of colors
The Petersen graph has chromatic number $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$.
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,2,3,2,1)$: $3$ colors
$(1,2,3,1,2)$: $3$ colors
$(1,2,1,2,1)$: $2$ colors
$(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.
$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?
$c$
The vertex of smallest index among the three
$b$
$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.
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?
No: no list guarantees it on general graphs
Yes: the vertices class by class of an optimal coloring
Yes: the vertices by non-increasing degree
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.
$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?
It usually needs few colors beyond $\chi(G)$; it guides exact B&B
Because it always finds an optimal coloring in polynomial time
Because it does not require knowing the edges of the graph
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.
$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$?
Because on general graphs it always uses $\Delta+1$ colors
Because on bipartite graphs the guarantee fails
Because its running time is exponential
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)$.
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?
City $3$
City $2$
City $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$.
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?
Because the restricted list would become empty
Otherwise every run would give the same tour
Because reinitializing it would make the results irreproducible
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.
To reduce the myopia of a greedy criterion («which choice is best now?») regret and look-ahead are used. Which question does regret ask?
What do I lose if I postpone this choice?
Where does this choice lead, completing the solution?
Which choice is best now?
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.
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?
$CI$ city $4$, $REG_2$ city $2$
Both city $2$
$CI$ city $2$, $REG_2$ city $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.
$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?
Nearest neighbour
Cheapest insertion
Nearest insertion
Farthest insertion
Explanation. With all regrets zero the tie rule decides: the minimum insertion cost, i.e. the rule of cheapest insertion.
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?
Look-ahead chooses unlike greedy, but is only as good as its pilot
The pilot method always finds the optimal tour of the instance
The pilot method can be worse than its own pilot
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.
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?
$O(n^3)$
$O(2^n)$
$O(n^2)$
$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.
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?
The tour is not optimal, because the gap is positive
The gap proves the tour is $5.9\%$ away from the optimum
The tour is optimal, but the bound $17$ cannot prove it
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.
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?
The last job should have been left without a machine
Earlier choices are final: there is no going back
$LPT$ violates its own performance guarantee
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$.
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?
It is taken once and for all: a choice, once made, is never revised
It is revised at the end by a built-in local search
It is undone if the partial solution becomes infeasible
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.
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)?
The algorithm stops and returns the partial solution
It is added anyway and another element is removed
It is put back at the end of the list and examined later
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.
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$)?
$21$
$18$
$16$
$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$.
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?
FF $3$, FFD $3$
FF $3$, FFD $2$
FF $2$, FFD $3$
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.
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?
$7$ and $6$: the ratio $\frac76$ attains the guarantee $\frac43-\frac1{3m}$
$6$ and $6$: $LPT$ is optimal on this instance
$7$ and $7$: no schedule does better than $7$
$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.
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?
It always finds the optimal tour, because it tries all starts
It always gives the same tour as $NN$, because tours are cyclic
It is worse than $NN$ on some instances, because it picks the start at random
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.
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?
$20$
$15$
$16$
$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$.
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?
$4$
$2$
$1$
$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$.
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?
$3$
$2$
$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.
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?
$2$
$1$
$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$.
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$?
With $\alpha=0$ the $RCL$ is empty; with $\alpha=1$ it contains only the best
With $\alpha=0$ a random choice; with $\alpha=1$ the greedy
With $\alpha=0$ the greedy (with random ties); with $\alpha=1$ a fully random choice
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.
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?
City $b$, with regret $2$
City $a$, with regret $7$
City $a$, with insertion cost $3$
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.
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?
It is never worse than the pilot, but runs the pilot once per candidate at each step
It always finds the optimal solution, because it tries all candidates
It may be worse than the pilot, because it changes the first choice
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.
A constructive heuristic returns a feasible solution. What is needed, besides its value, to say how far the solution is from the optimum?
A second run of the same heuristic
The order in which the elements were chosen
Nothing: the value of a constructive heuristic is always close to the optimum
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.
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?
They are never combined with other methods
As the final algorithm, after a local search
As the starting point of a local search or a metaheuristic, which improve the complete solution
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.
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?
It always starts from a complete feasible solution
Every choice is final: an element added is never removed
It guarantees an optimal solution
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.
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?
Non-increasing efficiency $p_j/w_j$
Non-decreasing profit $p_j$
Non-increasing weight $w_j$
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.
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?
$\mathscr{A}(I)\le z(I)$
$\mathscr{A}(I)=z(I)$
$\mathscr{A}(I)\ge 2z(I)$
$\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).
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)?
FF: $6$, FFD: $3$
FF: $4$, FFD: $4$
FF: $4$, FFD: $3$
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$).
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?
FF: $1$, BF: $1$, WF: $2$
FF: $1$, BF: $2$, WF: $1$
FF: $2$, BF: $2$, WF: $3$
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$).
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?
Every assignment of jobs to machines is feasible; the rule «least loaded machine» depends on the order in which the jobs arrive
Because the makespan does not depend on the assignment
Because every machine has a capacity to respect
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.
$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)$?
$LIST(I)=8$, $LPT(I)=7$
$LIST(I)=9$, $LPT(I)=7$
$LIST(I)=7$, $LPT(I)=8$
$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\}$).
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)$?
$z(I)\ge9$
$4.5\le z(I)\le9$
$6\le z(I)\le9$
$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$.
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?
Between $2$ and $3$, increase $3$
Between $1$ and $2$, increase $1$
Between $3$ and $1$, increase $3$
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$.
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$?
$18$
$22$
$25$
$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.
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?
Nearest neighbour requires exponential time
Nearest neighbour never finds a feasible tour
Nearest neighbour ignores the starting city
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.
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?
$4$
$1$
$3$
$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.
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?
That $GC$ is always optimal on bipartite graphs
A bad list can make $GC$ use $n/2=5$ colors on a $2$-colorable graph: there is no performance guarantee
That $\chi(G_5)=5$
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.
$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?
On bipartite graphs it uses at most $2$ colors; on general graphs it has no performance guarantee
It always uses $\omega(G)$ colors
On bipartite graphs it may use $n/2$ colors; on general graphs it is a $2$-approximation
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.
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?
That the weights are all different
That the capacity is even
That all items are known in advance (offline case); First Fit also works when they arrive one at a time
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.
With $m=4$ identical machines, which factor does Graham's result guarantee for $LIST$ (any list), and which one for $LPT$?
$\frac74$ for both
$\frac54$ for $LIST$, $\frac74$ for $LPT$
$\frac74$ for $LIST$, $\frac54$ for $LPT$
$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.
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?
$2\Delta(G)$
$5$
$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).
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?
No bound $GC\le c\,\chi(G)$, $c$ constant, holds for every list
$GC$ is optimal on bipartite graphs, with every list
$DSATUR$ also uses $k$ colors on the graph $G_k$
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.
The guarantee $LPT(I)\le(\frac43-\frac1{3m})z(I)$ is better than that of $LIST$. Which feature of $LPT$ does the proof use?
The machines have different speeds
There are at least $3$ machines
The processing times are all distinct
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.
Why does the bound $GC(I)\le\Delta(G)+1$ hold for every list $\lambda$ of the vertices?
The graph to be colored is always bipartite
$GC$ recolors the colored vertices when needed
At most $\Delta(G)$ neighbours of a vertex already have a color
$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.
For which problem does the greedy algorithm by non-increasing efficiency $p_j/w_j$ always give an optimal solution?
The bounded knapsack, with several copies per item
The continuous knapsack, with divisible items
The 0/1 knapsack with integer profits and weights
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.
Which ingredient does a greedy constructive algorithm need?
A selection rule for each step, never revised
A complete feasible starting solution
A neighbourhood of the feasible solutions
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.
Nearest neighbour always gives a feasible tour on a complete graph. Why can it fail on a graph that is not complete?
On incomplete graphs distances are asymmetric
It needs the triangle inequality
The number of cities must be even
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.
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?
When the instance has many items
When the items arrive one at a time (online)
When all the items have the same weight
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.
$P\,||\,C_{\max}$ with $m=2$ machines: $LPT$ finds makespan $14$. What follows from the guarantee $LPT(I)\le(\frac43-\frac1{3m})z(I)$?
$z(I)\le 12$
$z(I)\ge 12$
$z(I)\ge 10.5$
$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)$.
$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)$?
$\frac32=2-\frac1m$
$\frac43$, below the guarantee
$2$, above the guarantee
$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.
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$?
$5$: one color below the bound
$6$: one above the bound
$2$: the graph is bipartite
$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.
How many colors does $DSATUR$ use on a bipartite graph with at least one edge?
It depends on the initial list
Exactly $\frac n2$
Exactly $2$
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).
For every graph $G$ there is a list of the vertices for which the greedy coloring uses $\chi(G)$ colors. Why?
Because the graph always has $\chi(G)=2$
Follow the classes of an optimal coloring
Because $GC$ always uses $\Delta(G)+1$ colors
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.
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?
The greedy by efficiency has no constant guarantee
The greedy is optimal when the weights differ
The linear relaxation is worth $2$
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$.
For which lists and which machines does Graham's guarantee $LIST(I)\le(2-\frac1m)z(I)$ hold?
Only for lists sorted by time
Only with two machines
Also with machines of different speeds
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}$.
$DSATUR$ first colors the vertex of maximum saturation. What is the saturation of a vertex?
The number of its uncolored neighbours
The smallest color free for it
The distinct colors among its neighbours
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.
Multi-start nearest neighbour repeats the method from every starting city and keeps the best tour. What is it based on?
It is needed to compute a dual bound
The tour depends on the starting city
Nearest neighbour is random
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$.
In insertion heuristics for the TSP, into what is each new city inserted?
Into a cycle on the cities already inserted
Into a path starting at city $1$
Into a spanning tree of the cities
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.
Regret insertion chooses the city of maximum regret. How is the regret of a city $q$ defined?
The smallest insertion cost
The distance from the nearest city
The sum of the insertion costs
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.
Why is a constructive heuristic randomized, choosing at random among the best candidates?
To reduce the time of one construction
To obtain a dual bound
To get different solutions
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).
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?
It may never stop, if the neighborhood used is not exact
It stops at a global optimum after at most $f(x^0)-z(I)$ moves
It stops at a local optimum after at most $f(x^0)-z(I)$ moves
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.
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?
The problem has a unique optimal solution; every move strictly improves $f$; $f$ is integer
Every move strictly improves $f$; solutions are finite; with integer $f$ every move improves by at least $1$ and $f\ge z(I)$
The rule is best improvement; solutions are finite; $f$ is convex and $f\ge z(I)$
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.
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?
$35$
$45$
$90$
$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.
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?
It is a global optimum, because move examines all the jobs
It is a local optimum for the swap neighborhood too
It is a local optimum for every neighborhood of the problem
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.
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?
$0$
$8$
$-8$
$-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$.
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?
Not necessarily: the local optimum depends on the neighborhood
Yes: a local optimum is unique for every instance
Yes, if both use first improvement
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.
A local search with neighborhood $N$ starts from a solution that is already a local optimum with respect to $N$. What does it do?
It restarts from a new random solution
It declares the solution a global optimum
It moves anyway to the best neighbor, even if worse
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.
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?
Machines $1$ and $2$
Only machine $3$
Only machine $2$
All three
Explanation. $C_{\max}=11$ and only machine $2$ has load $11$. Machine $3$ is the least loaded, not the critical one.
To study a local search for bin packing from many random starting solutions, how is a random (always feasible) solution generated?
First Fit Decreasing with random ties
First Fit on a random order of the items
A random bin for every item
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.
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?
$40$
No bound: it can cycle
$31$
$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.
In local search, for every neighborhood the order in which moves are examined is fixed. Why?
It guarantees that the local optimum is also global
It changes the set of neighbors of the current solution
It decides first improvement's choice, and the ties
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.
In local search, what does the size of a neighborhood (the number of neighbors of a solution) determine?
The optimal value of the given instance
The cost of an iteration: the neighbors to evaluate
The number of iterations before the search stops
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.
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?
Only flip
Only swap
Both
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.
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?
$(2,1),(4,1),(2,3),(4,3)$
$(1,3),(2,4),(1,4),(2,3)$
$(1,2),(3,2),(1,4),(3,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.
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?
No: bin $a$ exceeds $10$
Yes: loads $6$ and $11$
Yes: loads $10$ and $7$
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.
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?
$36$
$18$
$24$
$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.
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,2,5,4,3,6)$
$(1,2,4,3,5,6)$
$(1,5,4,3,2,6)$
$(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\}$.
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$?
$20$
$216$
$9$
$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.
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?
$4$
$6$
$3$
$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.
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?
The second, of value $15$
The third, of value $15$
The first, of value $17$
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$).
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,0,1,0)$, profit $16$
$(0,0,1,0)$, profit $6$
$(1,0,0,1)$, profit $14$
$(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.
In the first improvement rule, what decides which improving neighbor is accepted when there are several?
The neighbor farthest from the current solution
The fixed order in which neighbors are examined
The value of the neighbor: the best is taken
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.
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?
Best $19$, first $22$
Best $22$, first $19$
Best $19$, first $25$
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.
The best improvement rule performs the «steepest descent». What does each of its iterations cost?
The evaluation of neighbors up to the first improving one
An exploration of the whole search space
The evaluation of a single neighbor
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.
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?
Best improvement always examines fewer neighbors
First improvement never reaches the optimal solution
Two paths to the same optimum; first examines fewer here
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$.
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)$?
The maximum over the other machines' loads is needed
The loads must be recomputed from scratch
The jobs of every machine must be re-sorted
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)$.
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?
Profit $15$, weight $7$
Profit $17$, weight $7$
Profit $23$, weight $11$
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$.
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?
Best improvement always needs fewer evaluations than first
2-opt search always finds the optimal tour of the instance
On small instances both reach the optimum at similar cost
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.
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?
Because city $1$ belongs to no edge
The reversed path always starts at position $i+1\ge2$
Because city $1$ has the minimum distance to all
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).
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$?
$-2$
$+2$
$-6$
$0$
Explanation. Added edges $3+4+3=10$, removed edges $4+4+4=12$: $\Delta=-2$, the move shortens the tour.
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?
It is disjoint from 3-opt: it removes only two edges
It coincides with 2-opt applied twice
It contains all 3-opt moves
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.
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?
First improvement is always faster than best improvement
Best improvement always finds the global optimum
The two rules can stop in different local optima
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.
How does the Lin–Kernighan heuristic for the TSP work?
It solves the ILP model of the TSP on a subset of cities
It builds a variable number of edge exchanges, one at a time, greedily
It explores the whole 3-opt neighborhood at every iteration
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.
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?
$O(n^3)$; in practice it is explored only in part
$O(n^2)$; it is always explored in full
$O(n)$; it costs less than the 2-opt one
$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).
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$
$0$
$-3$
$-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$.
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?
Move $O(nm)$, swap $O(n^2)$
Move $O(n^2m)$, swap $O(nm^2)$
Move $O(nm^2)$, swap $O(n^2m)$
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)$.
$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?
$12$
$11$
$8$
$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$.
$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?
Moving the $5$ brings the receiving machine to $13$, a $3$ to $11$
Because machine $1$ is not the only critical machine
Because moves never change the load of machine $1$
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.
$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?
$(10,9,8)$
$(6,8,13)$
$(12,8,7)$
$(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.
$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?
Swap always improves the solution found by $LPT$
$LPT$ always finds the optimal makespan of the instance
Even two neighborhoods together can stop above the optimum
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.
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?
Because random solutions are almost all infeasible
The bin count takes few values; the makespan depends on critical machines
Because the move and swap neighborhoods are too large to explore
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.
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?
With the objective «number of bins» the search is blind
The $100$ solutions are all already optimal
Move and swap produce only infeasible solutions
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.
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?
Because bin packing is a maximization problem
Because in $P\,||\,C_{\max}$ the total time changes with moves
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.
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?
None: the number of bins does not change
Item $3$: loads $(7,7,7)$, three bins
Item $5$: loads $(7,7,7)$, three bins
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.
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$ if the move empties a bin, $0$ otherwise
The weight of the moved item
The difference between the loads of the two bins
$-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.
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?
Because with $SQ$ the swap becomes a move
Because a swap always increases the number of bins
Because a swap always produces infeasible bins
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.
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?
$-4$
$+8$
$+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$.
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?
The objective $SQ$ can only be used for $P\,||\,C_{\max}$
$SQ$ is a guide: quality is measured by the number of bins
Maximizing $SQ$ is equivalent to minimizing the bins
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.
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?
A move «neutral» for the objective can prepare the improving one
With $SQ$ every move reduces the number of bins
The Next Fit solution is already a local optimum
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.
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?
Move search with $SQ$ always finds the optimal solution
First Fit solutions are almost always optimal
The auxiliary objective worsens the starting solutions
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.
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?
Because item $2$ never fits into the knapsack
Because flips cannot remove items from the knapsack
Two flips are needed; the middle step is infeasible or worse
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.
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)$?
$14$
$17$
$23$
$20$
Explanation. Profit $23$, weight $12$, excess $3$: $23-2\cdot3=17$. $20$ and $14$ correspond to $\alpha=1$ and $\alpha=3$.
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?
$O(n^2)$, because of the swaps
$O(n)$, because of the flips
$O(n\log n)$, for the sorting
$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.
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?
The flip and the best swap are applied together
The flip is discarded in favor of the swaps
All swaps are examined anyway
The swaps are not examined
Explanation. First improvement accepts the first improving neighbor in the order of examination: the flip found ends the iteration.
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?
Or-opt alone always finds the optimal tour
$VND$ uses only the largest neighborhood
Or-opt improves a 2-opt local optimum
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.
$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?
$VND$ always finds the optimal solution
Combining neighborhoods and auxiliary objective adds up
Swap alone is always better than $VND$
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$.
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?
Here best beats first, and $VND$ always finds the optimum
First improvement is always better than best improvement
Every random tour leads to the optimum with 2-opt
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.
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?
Random tours are good starting solutions for 2-opt
More runs never increase the probability of finding the optimum
2-opt search finds the optimum in almost all runs
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.
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\%$?
$10$
$9$
$37$
$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$.
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?
$f^*=z(I)$
$z(I)\ge f^*/2$
$f^*\le z(I)$
$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.
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?
$17$
$27$
$23$
$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.
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)?
$O(n^2)$ and $O(n^2)$
$O(n^2)$ and $O(n^3)$
$O(1)$ and $O(n)$
$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.
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?
First improvement the second ($-1$), best improvement the third ($-5$)
Both the third ($-5$)
First improvement the first ($+2$), best improvement the third ($-5$)
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.
In local search the first-improvement and best-improvement rules are compared. Which statement is correct?
Best improvement always finds a better local optimum than first improvement
First improvement does not terminate if the neighbourhood is large
The two rules always follow the same path, with different times
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.
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?
It becomes a random search, because all moves are equivalent
It never terminates, because zero-value moves are infinite
It stops on a plateau, even if a sequence of zero-value moves would lead to a better solution
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.
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?
The vector with the highest penalty, to be avoided
The best feasible solution visited, because the final local optimum may be infeasible
Nothing: with the penalty every local optimum is feasible
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.
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?
Large: local optima are feasible but the search never leaves the feasible region; small: it crosses it but may stop outside
Large: the search becomes random; small: the search becomes exact
It does not matter: the penalty changes only the value, not the chosen moves
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.
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?
$0\%$
$10\%$
$90\%$
$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.
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?
With $M\ge n$ runs the optimum is guaranteed
Every run restarts from the local optimum of the previous one
The runs are independent and parallelizable, but none uses what the others found
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.
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?
It drops to $7$, the new load of machine $1$
It stays $10$: machine $2$ still has load $10$, and a move improves only if it leaves the unique critical machine
It rises to $13$, because machine $3$ receives the job
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.
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?
A swap keeps the number of jobs on every machine, a move changes it: the two neighbourhoods complement each other
A move keeps the number of jobs on every machine, a swap changes it
A swap changes the loads of three machines, a move of two
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.
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?
An infeasible solution, which the search makes feasible
The LP relaxation solution, always integer
The empty solution, because local search adds elements
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.
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?
Because the seed is the number of iterations of the search
Because a fixed seed gives better starting solutions
The same seed gives the same starting solutions in every language and computer: experiments are reproducible
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.
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?
All its edges have the same length
It has no crossing edges
It contains the shortest edge of the instance
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.
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?
A local optimum for 2-opt may not be one for Or-opt, and vice versa
Every local optimum for 2-opt is also one for Or-opt
Or-opt contains all the 2-opt moves
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.
Variable neighbourhood descent ($VND$) uses the neighbourhoods $N_1,\dots,N_K$, ordered from the smallest to the largest. How does it proceed?
It runs a complete local search in every $N_k$, once, in order
It chooses a random neighbourhood at every iteration
It uses only $N_K$, the largest, since it contains the others
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.
When variable neighbourhood descent ($VND$) with neighbourhoods $N_1,\dots,N_K$ stops, what is known about the returned solution?
It is the best solution of $N_1$ from the starting solution
It is a global optimum, because it tried all the neighbourhoods
It is a local optimum with respect to each of the neighbourhoods $N_1,\dots,N_K$
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.
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?
It is a dual bound
It is a local optimum with respect to $N$: no neighbour in $N$ is better
It is an optimal solution of the problem
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.
In local search neighbourhoods are defined by small changes of the solution representation. What happens to a change producing an infeasible solution (without penalties)?
It does not belong to the neighbourhood: only feasible neighbours are considered
It is accepted and repaired at the end
It is accepted only if it improves the objective
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.
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?
Flip $4$, swap $6$
Flip $6$, swap $24$
Flip $10$, swap $45$
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.
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?
Because empty bins have smaller capacity
Because a move into an empty bin is always infeasible
Moving an item into an empty bin cannot decrease the number of bins
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.
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?
$7$; every job has a single move
$14$; swapping two jobs of equal duration changes no load
$21$; swapping two jobs of equal duration is infeasible
$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.
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?
First: the one of value $18$; best: the one of value $15$
First: $22$; best: $15$
First: $15$; best: $15$
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$).
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?
First improvement always performs fewer iterations
The two rules always reach the same local optimum
Best improvement always finds the global optimum
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.
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?
$d_{ab}+d_{cd}-d_{ac}-d_{bd}$
$d_{ac}+d_{bd}$
$d_{ac}+d_{bd}-d_{ab}-d_{cd}$
$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.
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?
$2^{10}$ tours; gap $10\%$
$9!/2=181\,440$ tours; gap $\frac{49-39}{39}\approx25.6\%$
$10!=3\,628\,800$ tours; gap $\approx25.6\%$
$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.
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?
A larger neighbourhood has better local optima but costs more to explore (3-opt: $O(n^3)$ per iteration)
A larger neighbourhood has worse local optima
Larger neighbourhoods are always faster
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.
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?
$L_a+3$ and $L_b-3$
They do not change: a swap does not modify the loads
$L_a-7$ and $L_b+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$.
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?
Because $SQ$ equals the number of bins
Because $SQ$ decreases when the loads become more equal
The landscape of the number of bins is flat; $SQ$ rewards moves concentrating the load, preparing the emptying of a bin
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.
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?
Yes, but the change is $6$
Yes: the change is $2\cdot3\cdot(6-5+3)=24>0$
No: the change is $2\cdot3\cdot(6-5-3)=-12$
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$.
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?
A swap of equal weights changes no load; a swap never changes the number of bins
A swap of equal weights is infeasible; a swap may empty a bin
A swap of equal weights increases $SQ$; a swap always reduces the bins
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.
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$?
Because emptying a bin decreases $\sum_bL_b$
It is not true: it may decrease $SQ$
Because $L_b>L_a$ in every move
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$.
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?
A move decreasing $\sum_hL_h^2$ always decreases the makespan
The two functions are independent
A move decreasing the makespan decreases $\sum_hL_h^2$, and one decreasing $\sum_hL_h^2$ does not increase the makespan
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.
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)$?
$441$ and $147$
$119$ and $147$
$21$ and $21$
$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.
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?
The profit minus a penalty proportional to the weight in excess of the capacity
The profit, ignoring the capacity
The total weight
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.
In the flip+swap local search for the 0/1 knapsack that stays feasible, with the first improvement rule, which flips can be improving?
All flips
No flip: only swaps improve
Only those removing an item
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.
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$?
Because the penalty is $0$ on infeasible vectors
Because with large $\alpha$ no item fits
Adding item $k$ creates an excess $e\ge1$, and the change $p_k-\alpha e$ is negative
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.
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?
That it is at most $478/2$
Only that it is at most $478$: local search gives a primal bound, not a dual bound
That it is exactly $478$, since the search stopped
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.
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?
The distances are symmetric: reversing the stretch does not change its length
The removed edges are adjacent
The distances satisfy the triangle inequality
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.
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?
The BPP
The TSP
$P\,||\,C_{\max}$
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.
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?
$\max_jt_j=11$
$\lceil\sum_jt_j/m\rceil=\lceil76/4\rceil=19$
$\sum_jt_j=76$
$\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.
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?
$47$
$25$
$40$
$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.
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?
It decreases by $24$
It does not change
It decreases by $6$
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.
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?
$2^n$
$8$
$17$
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.
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?
At a local optimum for all the $k$ neighbourhoods
At a local optimum for the neighbourhood $N_k$ only
At an optimal solution of the instance
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.
Why does a local search that moves only to strictly better neighbours terminate from every starting solution, even without an integer objective?
The neighbourhood of the search is exact
The choice rule is first improvement
The objective function is convex
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.
Multi-start local search repeats the search from several starting solutions. Why must the starts be different (for instance random)?
The neighbourhood changes with the starting solution
Different starts are needed to compute the gap
The same start leads to the same local optimum
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.
Why does local search for bin packing need an auxiliary objective such as $\sum_bL_b^2$?
$\sum_bL_b^2$ equals the number of bins used
Almost every move leaves the number of bins unchanged
The number of bins is not an integer value
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.
For $P\,||\,C_{\max}$ the swap neighbourhood (exchange of two jobs on different machines) is used besides move. In which situation is it needed?
When every move overloads the receiving machine
When there are more machines than jobs to assign
When all the jobs have the same processing time
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.
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$
$e^{-1/2}$
$e^{-2}$
$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.
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?
It moves to the best non-tabu neighbor only if better; a tabu move is never allowed, even if it beats the best
It moves to the best non-tabu neighbor even if worse; a tabu move is allowed if it beats the best solution found
It moves to a random neighbor, accepted with probability $e^{-\delta/T}$; the tabu list forbids visited solutions forever
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.
Metaheuristics (simulated annealing, tabu search, ILS, VNS, GRASP, LNS, genetic algorithms) explore the space of feasible solutions. Which kind of bounds do they produce?
Only primal bounds: they do not know how far they are from the optimum
The optimal value, if run long enough
Only dual bounds: every solution found bounds the optimum
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.
GRASP (Greedy Randomized Adaptive Search Procedure) is a multi-start metaheuristic. What does it do at every iteration?
It perturbs the current local optimum with a random kick and reapplies local search to the perturbed solution
It destroys part of the current solution, repairs it with a heuristic and accepts the result if it is better
It selects two parents from the population, recombines them and mutates the child, which replaces the worst individual
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.
A metaheuristic guides a local search beyond the first local optimum. In which ways does it get out?
It solves the linear relaxation and rounds the solution found
It sorts the elements and adds them one at a time to the solution
It accepts worse solutions, jumps to a new start or combines solutions
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.
What must every metaheuristic (simulated annealing, tabu search, ILS, VNS, GRASP, LNS, genetic algorithms) balance?
Primal bounds and dual bounds
Intensification and diversification
Feasibility and optimality
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.
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?
A best improvement descent stopping at the first local optimum
GRASP with randomized construction and local search
Simulated annealing with the 2-opt neighborhood for the TSP
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.
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?
$C$, $A$, $B$
$A$, $B$, $C$
$A$, $C$, $B$
$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.
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?
$3$
$5$
$1$
$4$
Explanation. $\lfloor0.7556\cdot5\rfloor=\lfloor3.778\rfloor=3$, plus $1$: position $4$. Without the $+1$ one would get $3$.
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?
Yes: the first number must always be discarded
No, but the following numbers are all close to $0$
No: with a small seed the first number is always close to $0$
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.
Which metaheuristic escapes a local optimum by accepting worsening moves deterministically, with a memory forbidding a return to the solutions just visited?
Simulated annealing
Tabu search
Iterated local search
GRASP
Explanation. Simulated annealing accepts worsenings at random; ILS and GRASP jump to new starts.
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?
SA and TS; ILS, VNS, GRASP and LNS; genetic algorithms
TS and LNS; SA, ILS, VNS and GRASP; genetic algorithms
ILS and VNS; SA, TS, GRASP and LNS; genetic algorithms
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.
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?
To be able to restart from scratch at each new temperature
Because the final temperature is always too high
It leaves local optima: the final solution may be worse
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.
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$?
They are accepted with probability $\frac12$, at random
Always accepted: the search moves across plateaus
They are never accepted, at any temperature
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.
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?
$16$
$40$
$12$
$20$
Explanation. Temperatures $10$, $5$, $2.5$, $1.25$; the next, $0.625\le1$, stops the search: $4$ temperatures times $4$ moves.
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?
$8$
$12.5$
$2.2$
$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$.
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?
At low temperature every move is accepted
The returned tour is the last visited, not the best
The mechanism: worsenings accepted early, rejected later
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.
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?
Infeasible solutions must always be discarded
The infeasible region acts as a bridge between two valleys
The penalty makes every vector feasible
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.
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?
Only the feasible ones
Only those accepted at the minimum temperature
Any solution with larger $f_\beta$
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.
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?
A low initial temperature always gives the best results
The number of iterations does not affect the result
A single run is enough to compare parameters
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.
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}$?
Integer and positive objective values
Exact neighborhood of constant size
Symmetric and connected neighborhood
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.
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?
Because the logarithmic schedule holds only for the TSP
It is a guarantee in the limit: too many iterations are needed
Because the geometric schedule has the same guarantee
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.
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?
A worsening non-tabu move gets it off the plateau
Makespan $12$ is the returned value
Tabu search never accepts worsening moves
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}$.
In tabu search for the TSP with the 2-opt neighborhood, what are the tabu attributes?
The two cities just moved, which stay fixed forever
The tours already visited, stored in full
The edges just added, which cannot be removed
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).
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?
The tabu tenure does not affect the result
Without memory tabu search always finds the optimum
The tabu tenure must be tuned to problem and instance
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.
Iterated local search has three components: local search, perturbation (kick) and acceptance criterion. What role does each play?
Diversifies; intensifies; balances the two
Intensifies; diversifies; balances the two
Balances; intensifies; diversifies
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.
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?
The kick worsens; the descent repairs and keeps the good parts
ILS accepts only tours worse than the current one
The kick must immediately improve the perturbed tour
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.
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)?
Because $N_2$ contains all solutions
Because a swap moves a single job
Because $N_2$ coincides with the move neighborhood
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.
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?
Shaking with $k=1$ is always enough
VNS does not use local search
Shaking in $N_2$ finds a swap that move cannot see
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.
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?
Items $1$, $3$ and $2$
Items $1$ and $3$
Only item $1$
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.
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?
$\alpha=0$ repeats one run; a little randomness suffices
The value of $\alpha$ does not affect the result
With $\alpha=0$ GRASP always finds the optimum
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.
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?
LNS is a 2-opt local search
Removing cities always worsens the final tour
A single destroy-and-repair step changes many edges
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.
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?
Because it contains a single solution
It is huge: the repair method explores it implicitly
Because moves cannot be evaluated
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.
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?
The items of two FFD bins never fit into one
Because FFD already uses the minimum number of bins
Because exact repair with two bins is too slow
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.
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?
The weights do not depend on the results of the iterations
Random removal is almost never used
The method learned that worst removal does not pay here
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.
On the $20$-city TSP simple LNS with random removal does slightly better than adaptive LNS (ALNS). When does adaptivity pay off?
With a single destroy method available
With many methods of unknown quality and long runs
Only on very small and easy instances
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.
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,0,0)$
$(1,1,0,1)$
$(0,1,0,1)$
$(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.
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?
Because a duplicate is always infeasible
Because selection does not work with duplicates
Because a duplicate always has minimum fitness
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.
In every metaheuristic a parameter fixes the balance between intensification and diversification. Which one fixes it in GRASP (randomized construction plus local search)?
The tabu tenure of the forbidden moves
The parameter $\alpha$ of the restricted list
The initial temperature $T_0$ of the cooling
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.
What do the metaheuristics of the chapter (simulated annealing, tabu search, ILS, VNS, GRASP, LNS, genetic algorithms) NOT use?
Neighborhoods and local searches on solutions
Problem relaxations and MIP solvers
Random numbers from the Park–Miller generator
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.
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?
Exactly reoptimizing a part gives very powerful neighborhoods
Repair does not matter: only destruction matters
Metaheuristics must always use exact algorithms
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.
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?
Minimized in both, because balanced loads are always better
Maximized in both, because the total is fixed
Bin packing: minimized; $P\,||\,C_{\max}$: maximized
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.
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?
Because different seeds change the instance solved
Because every seed gives a different global optimum
The result of a metaheuristic depends on the random numbers: a single seed is not enough to evaluate it
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.
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}$?
The temperature changes only the number of iterations, not the acceptance
At high temperature worsenings are often accepted (diversification); at low temperature almost never (intensification)
At low temperature all neighbours are accepted
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.
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?
It also forbids solutions never visited; the aspiration criterion admits a tabu move that beats the best solution found
It does not prevent going back to the solution just left; it is repaired with infinite tenure
It makes the search random; it is repaired with the Metropolis criterion
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.
Iterated local search ($ILS$) repeats: perturbation of the current local optimum, local search, acceptance criterion. What role does the strength of the perturbation play?
The stronger, the better the result always is
It does not matter: the local search undoes any perturbation
Too weak: the search does not terminate; too strong: the search becomes exact
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.
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?
It changes a single edge, so it does not lose the tour structure
It is a 2-opt move, so the local search always accepts it
It changes three edges without reversing segments, and a single 2-opt move does not easily undo it
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.
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?
If the local optimum is better $k+1$; otherwise back to $k=1$
If the local optimum found is better it is accepted and $k=1$ again; otherwise $k+1$
$k$ is chosen at random at every iteration
$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.
What is the difference between variable neighbourhood descent ($VND$) and variable neighbourhood search ($VNS$)?
$VND$ explores the neighbourhoods completely and deterministically; $VNS$ draws random solutions from them (shaking) and then applies a local search
$VND$ is randomized, $VNS$ is deterministic
$VND$ uses one neighbourhood, $VNS$ several
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.
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$?
The construction becomes completely random
The local search is no longer run
$GRASP$ always finds the global optimum
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.
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?
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.
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?
The solution becomes infeasible
The solution never improves: FFD repacks the removed items the same way
The optimum is always obtained after one iteration
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.
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,0)$
$(0,1,0,0,1)$
$(1,1,0,1,0)$
$(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.
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?
Because it never uses local search
Because it guarantees the optimum only for some problems
It becomes an algorithm only by choosing representation, neighbourhoods, local search and parameters
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.
Multi-start repeats local search from many starting solutions. Which limit do metaheuristics try to overcome?
Multi-start is deterministic
Every start ignores what was learned before, while good valleys are usually close to other good valleys
Multi-start never finds local optima
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).
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?
$e^{-1}\approx0.37$
$e^{-3}\approx0.05$
$1$
$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.
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?
$30$; no
$2$; no
$22$; yes, because $f_\beta$ is high
$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.
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?
Simulated annealing has an implementation bug
The initial tour was infeasible
At the start the temperature is high compared to typical worsenings, and almost all worse moves are accepted
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).
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)$?
$e^{2}\approx7.39$
$e\approx2.72$
$e^{-1}\approx0.37$
$\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$.
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?
To bring job $j$ back to machine $h$, so as not to return immediately to the solution just left
To move any job to machine $h$
To move job $j$ again anywhere
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.
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?
The tenure has no effect on the results
Too long: tabu search becomes simulated annealing
Too short: the search stops at once; too long: it cycles
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.
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?
Because the double bridge always improves the tour
Because local search does not accept worse tours
If local search could undo it with a single move, it would immediately return to the starting local optimum
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.
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?
In both cases one restarts from a random solution
If better: it is accepted and one goes back to $k=1$; otherwise one moves to $k+1$
If better: one moves to $k+1$; otherwise back to $k=1$
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.
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$?
$\alpha=0$: nearest neighbour (greedy choice, apart from ties); $\alpha=1$: completely random choice
$\alpha=0$: random choice; $\alpha=1$: nearest neighbour
In both cases the optimal tour is obtained
$\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.
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?
$2.5$
$6$
$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.
The parameters of a metaheuristic must be calibrated. Which procedure avoids an overly optimistic picture of the performance?
Do not calibrate: always use the literature values
Calibrate on training instances and evaluate on different instances
Calibrate and evaluate on the same instances
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.
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?
They reached a simple lower bound (e.g., $\lceil\sum_jt_j/m\rceil$), which is a dual bound computed separately
Because a metaheuristic that stops is always optimal
Because tabu search computes an LP relaxation
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.
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?
The search would become a simulated annealing
The search would find the global optimum
The search would stop at the local optimum, like a descent
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.
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?
It restarts from a random solution
It never escapes a local optimum
It is deterministic: it escapes because it always moves, and the tabu memory prevents it from going back; simulated annealing accepts worsenings at random
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.
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?
Because metaheuristics solve only the TSP
A metaheuristic guides a local search: representation and neighbourhoods remain those of the problem
Because metaheuristics use no neighbourhoods
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.
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?
Because the first run is always a test
Because every run uses a different instance
To compute a dual bound
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.
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?
It measures the computing time
It measures the dual bound
It measures reliability: a method finding the optimum once in ten runs is less robust than one finding it always
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.
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?
$e^{-10}\approx 0.00005$
$e^{-2}\approx 0.14$
$e^{-0.5}\approx 0.61$
$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$.
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?
It does not make it while it is tabu
It restarts from a random solution
It doubles the tenure
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.
Which choice of the parameters makes simulated annealing similar to a random walk among the solutions?
A high minimum temperature
A single move per temperature
A very high temperature
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.
What happens in tabu search if the tenure is too long?
The aspiration criterion stops acting
Too many moves are forbidden, missing good solutions
The search goes back to cycling among few solutions
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.
In iterated local search the perturbation is too weak. What happens?
The local search undoes it: same local optimum
It becomes a restart from a random solution
The algorithm no longer terminates
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.
GRASP with a restricted candidate list (RCL) of a single element: what does it reduce to?
A local search from random starting solutions
Simulated annealing with temperature $T=0$
A large neighbourhood search on the greedy
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.
Why does the genetic algorithm for the 0/1 knapsack need a repair step?
Mutation always decreases the profit
Crossover and mutation can exceed the capacity
The population could become empty
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.
Why do the experiments of the chapter on metaheuristics use a random number generator with a fixed seed?
So that the metaheuristics become exact
Because without a seed the algorithm never stops
Because it guarantees reaching the optimum
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.
In variable neighbourhood search the shaking takes a random solution in $N_k$, and $k$ grows after every failure. Why?
Because $N_k$ is smaller for larger $k$
To reduce the computing time of each iteration
To diversify: farther solutions leave the valley
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.
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?
$e^{-2}\approx0.14$ times
$e^{2}\approx7.4$ times
$3$ times
$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$.
Simulated annealing: for a fixed worsening $\delta>0$, how does the probability of accepting it behave as $T\to0$?
It tends to $0$, like a descent
It tends to $1$: every neighbour is accepted
It stays $e^{-\delta}$
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.
Iterated local search with the criterion that accepts every new local optimum, even a worse one. What does the search do?
It intensifies: it accepts only better optima
It becomes a plain local search
It stops at the first local optimum
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$.
In variable neighbourhood search, what happens to $k$ when the solution obtained by shaking and local search is better than the current one?
It is discarded and $k$ goes back to $1$
It is kept and $k$ stays the same
It becomes current and $k$ goes back to $1$
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.
Large neighbourhood search with destruction of all the $n$ elements and exact repair. What does the first iteration do?
It only computes a dual bound
It solves the instance to optimality
It returns the starting solution
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.
Tabu search starts from a local optimum and always moves to the best non-tabu neighbour. How can it improve the best solution found?
By crossing worse solutions to another valley
By accepting worsenings with probability $e^{-\delta/T}$
By restarting from a random solution
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$.
What does GRASP return after its iterations of randomized construction and local search?
The last local optimum found
The deterministic greedy solution
The average of the solutions found
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.
Why does the tabu list store attributes of the moves (for instance «job $j$ has left machine $h$») instead of the visited solutions?
The visited solutions are not feasible
So the tenure is no longer needed
Comparing whole solutions costs too much
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.
Why does simulated annealing with geometric cooling $T\leftarrow\alpha T$ need a minimum temperature $T_{\min}$?
It is needed to compute the dual bound
$\alpha^kT_0$ never reaches $0$
Below $T_{\min}$ the Metropolis rule fails
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.
In adaptive large neighbourhood search (ALNS), how are the destroy and repair operators chosen?
With weights from their past success
Always the same two operators
In a fixed order, in turn
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.
Besides the random choice, what does the construction phase of GRASP need?
A feasible starting solution
A tabu list of the moves
A temperature and a cooling schedule
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.
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})$?
$3m$
$3$
$9$
$6$
Explanation. Every moved job changes two components (one from $1$ to $0$, the other from $0$ to $1$): $\Delta=2r=6$.
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?
The LP relaxation of these models is unbounded, so there is no solution to round
The LP relaxation of these models always has an integer solution, so rounding changes nothing
The constraints $\sum_b x_{jb}=1$ are equalities: fractional values rounded one by one almost never sum to $1$
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.
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?
A dive explores the whole tree; RINS guarantees a solution better than the incumbent
A dive is a single path in the tree; RINS fixes the variables on which relaxation and incumbent agree
A dive is a single path in the tree; RINS fixes the variables on which relaxation and incumbent differ
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.
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$, $0$ and $2$
$1$, $0$ and $1$
$1$, $1$ and $4$
$0$, $0$ and $2$
Explanation. $\lfloor1\rfloor=1$, $\lfloor0.75\rfloor=0$; the two vectors differ in components $2$ and $3$: $\Delta=2$.
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?
$48$ variables and $18$ constraints
$36$ variables and $12$ constraints
$42$ variables and $6$ constraints
$42$ variables and $12$ constraints
Explanation. $6\cdot6=36$ variables $x_{jb}$ plus $6$ variables $y_b$; $6$ assignment and $6$ capacity constraints.
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?
By replacing the capacity constraint with an equality
By relaxing the binary variables to continuous ones
By swapping $\min$ and $\max$, $\le$ and $\ge$ in comparisons of values
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.
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})$?
$\frac14$, and $z(\mathrm{LP})=17$
$\frac14$, and $z(\mathrm{LP})=17.75$
$\frac12$, and $z(\mathrm{LP})=19.5$
$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.
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?
A used bin holds at most $c$, an unused one is empty
Every item goes into exactly one used bin
Bins are used in increasing index order
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.
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$, because the capacity constraint requires it
$1$: every available bin must always be opened
Any value between $0$ and $1$ inclusive
$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$.
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?
$26$
$10$
$11$
$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$.
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?
Because ILP heuristics do not apply to the TSP
Every method would find the optimum at once: integer LP
Because the DFJ model has no binary variables at all
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$).
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?
Only over the binaries $x_{jh}$: $C_{\max}$ does not enter
Only over the continuous variable $C_{\max}$
Only over the fractional variables of the relaxation
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.
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?
The total load of all jobs is at most $C_{\max}$
Every machine has load exactly equal to $C_{\max}$
Every job goes on one and only one machine
$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}$.
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?
Because the model lacks the assignment constraints
Because the optimal integer value of the instance is $10$
Any fractional assignment with three loads of $9$ is optimal
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$.
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?
The rounded makespan becomes $10$
Job $3$ goes on two machines: the assignment is violated
Job $3$ is left without a machine
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.
Rounding the LP solution works on the knapsack but fails on bin packing and $P\,||\,C_{\max}$. Why?
The LP splits items: rounding violates the assignments
Because the bin packing LP is always infeasible
Because bin packing weights are not integer
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.
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?
Fixing $x_2:=0$ is always the right choice for diving
Diving always finds the optimal solution of the instance
The linear relaxation of the knapsack is infeasible
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\}$.
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?
$x_{33}:=1$
$x_{32}:=0$
$x_{23}:=0$
$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$.
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?
Because the pump restarts from the $LPT$ solution
The distance looks at assignments, not at loads
Because the pump always fails on $P\,||\,C_{\max}$
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.
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$?
Nothing in the distance asks to close empty bins
Because the chosen seed makes the LP infeasible
Because empty bins violate the capacity
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.
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?
All three minimize $\Delta$, with different cutoffs
RINS minimizes $\Delta$; LB fixes where LP and incumbent agree; PS imposes $\Delta\le k$
RINS imposes $\Delta\le k$; LB minimizes $\Delta$; PS fixes where they agree
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.
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?
$k=1$: move; $k=2$: 2-opt
$k=1$ and $k=2$: both flip only
$k=1$: flip; $k=2$: also contains swap
$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.
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?
No solution: RINS does not apply to the knapsack
The incumbent: with $x_3=1$ fixed, the sub-MIP is infeasible
$\{1,2\}$, because the sub-MIP sets $x_2=1$
$\{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.
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?
With different incumbent and LP the RINS neighborhood is large
Fixing more variables makes RINS more effective
The cutoff $C_{\max}\le10$ suffices to find the optimum
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.
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?
Four machines used; makespan $9$ is optimal
Four jobs reassigned; makespan $8$ is optimal
Two jobs reassigned; the search failed
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.
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,0,0)$, at distance $1$
$(0,1,1,1)$, at distance $3$
$(1,1,0,0)$, at distance $2$
$(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.
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?
Fixing $y_2:=0$ is always the right choice
Myopic choice: relaxed future setups look cheap
Relax-and-fix always finds the optimal solution
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.
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?
Reoptimizing small windows corrects earlier mistakes
Larger windows always worsen the solution
Relax-and-fix was already optimal
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.
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?
Branch-and-bound is never useful on bin packing
The difficulty is proving the bound $23$
The solver heuristics always slow the solution down
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.
In the Gurobi experiments of the chapter on ILP heuristics a limit in «work units» is set instead of seconds. Why?
Because a work unit counts the nodes explored
Because this way the solver uses more threads
A deterministic measure of effort, hence reproducible
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).
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?
A second full pass of relax-and-fix
The solver's branch-and-bound: the LP bound is weak
The bound of the linear relaxation rounded up
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.
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?
About $4.3\%$
About $1\%$
$0\%$
About $4.2\%$
Explanation. $(24-23)/23\approx4.3\%$; $4.2\%$ divides by $24$. Gurobi finds $23$ and closes the gap to $0\%$.
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?
The rounded LP relaxation solution
The current dual bound of branch-and-bound
The first fractional solution found by the simplex
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.
Which advantage do heuristics based on integer linear programming (MIP) have over problem-specific heuristics?
They are always faster than constructive heuristics
They always guarantee the optimum in polynomial time
They use only the model, so they apply to every formulated problem, and the relaxation also gives a dual bound
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.
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?
Heuristics are useless, because the relaxation is already integer
The relaxations are strong: finding a good solution is the hard part, and the rounded bound can prove its optimality
The relaxation is useless, because it is always weak
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.
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)?
Lowering the $x_j$ never increases the weight, so the constraint stays satisfied
Because the split item always has $x_s=0$
Because the relaxation always has an integer solution
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.
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,0)$, of weight $13$: infeasible
$(1,1,0,1)$, of weight $12$: infeasible
$(0,0,0,0)$: everything is lost
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$.
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?
Fractional explores the whole tree; guided a single path
Fractional uses the incumbent; guided uses only the relaxation
Fractional fixes the least fractional variable to its nearest integer; guided fixes the one closest to its incumbent value, at that value
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.
In diving on $P\,||\,C_{\max}$ the LP relaxation value stays the same for many successive fixings. Why?
Because diving no longer solves the relaxation after the first fixing
The relaxation has a huge set of optimal solutions: fixing a variable moves the point to another one of equal value
Because the makespan is an integer variable
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.
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?
Finding a first feasible solution; quality is the job of improvement methods
Improving an already known incumbent
Finding the optimal solution with a single projection
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.
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.6$
$0.4$
$0.7$
$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.
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$?
The whole space $\{0,1\}^n$
No neighbourhood: the sub-MIP is empty
The flip neighbourhood, adding or removing one item
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.
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?
The incumbent is infeasible
The incumbent is optimal: no solution has value at least $1$ lower
$\theta$ must be increased to find a solution
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.
In relax-and-fix for lot sizing, the setup variables $y_t$ are divided into blocks of consecutive periods. How does the method proceed?
It solves a MIP with the first block binary and the others relaxed, fixes the first block, then moves to the next block
It solves every block as an independent problem, without the stocks
It solves the LP relaxation once and rounds all the blocks together
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.
In capacitated lot sizing, why are the only hard decisions in MIP heuristics the $m$ setup variables $y_t$?
Because the produced quantities always equal the demands
Because stocks are always zero in an optimal plan
Because the LP relaxation is exact even with fractional setups
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.
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?
That this setting is the best for every instance
Little: results depend on instance, solver version and machine, and a single instance proves nothing
That the other settings are wrong
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.
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?
$m=1$, because bins are added during the search
$m=2n$, for some margin; on the instance $m=12$
$m=n$, always valid: one bin per item; on the instance $m=6$
$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.
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?
$r^2$: every pair of moved jobs counts once
$2r$: every moved job leaves a $0$ where $\bar x$ has $1$ and puts a $1$ where $\bar x$ has $0$
$r$: every moved job changes one component
$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.
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?
All the $x_{jh}$; $C_{\max}$ is integer
None: the model is purely binary
Only $C_{\max}$; it equals the average load
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.
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?
Because the cutoff is optional
Because $\theta$ must always be $1$
Because the objective values are integer: a better solution is worth at least $1$ less
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.
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?
Because rounding up is infeasible
Decreasing the variables does not increase the weight, and the weights are non-negative: the constraint $\le c$ stays satisfied
It is not true: it may exceed the capacity
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.
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?
The rounded vector may violate the degree constraints or form subtours: TSP feasibility is not preserved by rounding
Because the DFJ relaxation is always integer
Because the distances are integer
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).
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?
Yes: the knapsack relaxation is always integer
Yes, and it coincides with the optimum
No, because all variables are fractional
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.
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?
Only the incumbent $\bar{\vet x}$
Those that swap two jobs
Those that move at most one job
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$).
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?
It needs a feasible starting solution
It can end without a solution: fixings are not revised
It always finds an optimal solution of the MIP
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.
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?
When the solution of the linear program is integer
When the distance increases between two iterations
Right after the first rounding
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.
Diving fixes a fractional variable at every step and solves the linear relaxation again. Which outcome is possible?
It always finds a feasible solution
It proves the optimality of the solution
It never fixes a variable to $0$
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.
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?
The optimal value is $17$
The gap is zero: $18$ is optimal
The optimal value is $17$ or $18$
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.
Rounding down a solution of the linear relaxation gives a feasible solution for the 0/1 knapsack. For which model is this not guaranteed?
The 0/1 knapsack with a large capacity
Bin packing, with $\sum_bx_{jb}=1$ for every item
The 0/1 knapsack with integer data
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.
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?
An incumbent and a solution of the relaxation
Only the solution of the relaxation
A dual bound equal to the incumbent
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.
What does a MIP-based heuristic (matheuristic) use, by definition?
A neighbourhood defined on permutations
A population of solutions to recombine
Only constructive rules of greedy type
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.
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?
The solution found is not feasible
A stronger relaxation is needed
The sub-MIP may contain no better solution
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.
What is a heuristic solution passed to the solver as a MIP start used for in branch-and-bound?
It reduces the number of variables
It gives an incumbent at once to prune nodes
It gives a better dual bound
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.
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:
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.
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?
It is needed to obtain a dual bound of the problem
The constraint and the distance use $\bar{\vet x}$
It is needed to solve the linear relaxation
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.
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?
A feasible starting solution
The linear relaxation of the model
A MIP solver for the subproblems
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.
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?
The solution of the relaxation may be integer
The profits may not be integers
It changes the sign of the objective function
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.
The experiment with the parameters of Gurobi's heuristics uses a work limit instead of a time limit. Why?
With a work limit the optimum is found
The work limit switches the heuristics off
Work is deterministic: runs are reproducible
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.
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?
Only $x_2$
$x_2$ and $x_4$
All except $x_1$
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.
Local branching for the 0/1 knapsack with the constraint $\Delta(\vet x,\bar{\vet x})\le1$. Which solutions does the sub-MIP explore?
Only the vectors with one more item
All the feasible solutions
The vectors differing in two variables
$\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.
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?
Up to the optimal value
By at most $\theta$
By at least $\theta$
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.
Relax-and-fix with a single block containing all the integer variables: what does it solve?
The whole MIP, to optimality
Only the linear relaxation
An infeasible problem
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.
Why does fix-and-optimize never worsen the current solution?
Because it solves the whole MIP every time
Because it relaxes the next blocks
Because it accepts worsenings with a probability
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.
What must a solution passed to the solver as a MIP start satisfy to become the incumbent at once?
Have all the variables at $0$
Have value equal to the dual bound
Be feasible for the model
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.
The local branching constraint $\Delta(\vet x,\bar{\vet x})\le k$ is a linear constraint on the original variables only when:
The relaxation has an integer solution
The variables are binary
The problem is a maximization problem
$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.
In which case can RINS not give a solution different from the incumbent?
If $\bar{\vet x}$ and $\tilde{\vet x}$ coincide
If the relaxation has a fractional variable
If the incumbent is better than the relaxation
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).
How are the blocks of variables chosen in fix-and-optimize?
A single block with all the variables
One block for each constraint
At random, each time different
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).
Diving may end in an infeasible relaxation. Why can it not go back as branch-and-bound does?
Because the solver does not allow it
Because it does not use the linear relaxation
It follows a single branch, without exploring the tree
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.
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}}$?
$\frac{2}{19}$
$4$
$\frac{2}{17}$
$\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.
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}}$?
$\frac{3}{37}$
$\frac{3}{40}$
$\frac{40}{37}$
$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.
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?
$27$
$22$
$21$
$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.
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?
$16$
$12$
$17$
$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.
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?
$bin=(1,2,3,1,4,5,6)$
$bin=(4,1,2,4,3,5,6)$
$bin=(4,1,2,6,3,5,6)$
$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.
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?
$bin=(1,4,1,5,2,3,4)$
$bin=(1,5,5,5,2,3,4)$
$bin=(1,2,1,2,3,4,5)$
$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.
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?
$col=(1,1,2,3,2,4)$
$col=(2,4,1,1,3,2)$
$col=(1,1,2,2,3,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)$.
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?
$col=(1,2,3,2,1,1)$
$col=(1,2,3,1,3,3)$
$col=(3,2,1,2,1,1)$
$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?
$(2,3,1,4,5,6)$
$(2,3,4,1,6,5)$
$(1,2,3,4,6,5)$
$(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,5,2,3,4,6)$
$(2,4,6,5,1,3)$
$(2,4,5,3,6,1)$
$(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.
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?
$14$
$11$
$13$
$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$.
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?
$18$
$17$
$20$
$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$.
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?
$32$
$31$
$26$
$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.
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?
$40$
$42$
$45$
$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?
job $1$ to machine $2$
job $1$ to machine $1$
job $4$ to machine $2$
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?
job $1$ to machine $2$
job $2$ to machine $1$
job $4$ to machine $2$
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?
final makespan $16$, after $3$ moves
final makespan $35$, after $0$ moves
final makespan $14$, after $10$ moves
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?
final makespan $24$, after $0$ moves
final makespan $13$, after $3$ moves
final makespan $12$, after $3$ moves
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?
final length $21$, after $3$ moves
final length $21$, after $2$ moves
final length $22$, after $2$ moves
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?
final length $17$, after $1$ moves
final length $16$, after $1$ moves
final length $17$, after $0$ moves
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$.
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?
$e^{-\frac{7}{10}}$
$e^{-\frac{10}{7}}$
$e^{-70}$
$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$.
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?
$e^{-45}$
$1$
$e^{-\frac{5}{9}}$
$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$.
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,0,1,0,0,0)$
$(1,1,1,1,0,0,0)$
$(1,1,1,1,1,1,0)$
$(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.
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,0,1,1,1,0)$
$(1,0,0,0,1,1,0)$
$(1,1,0,1,1,0,0)$
$(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.
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?
$47$
$29$
$26$
$\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.
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?
$55$
$58$
$53$
$\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.