12 Local Search¶

基本概念

Greedy method is a special case of local search.

答案

贪心算法的是不可逆的局部最优决策，目标是逼近或达到全局最优；局部搜索的核心是邻域迭代优化，目标是找到局部最优。二者的核心逻辑、执行流程不存在包含关系，因此贪心算法不是局部搜索的特例，答案为 $\textnormal{F}$

Consider a state-flipping algorithm for the Maximum-Cut problem. We say that partitions $(A, B)$ and $(A', B')$ are neighbors under the $k$-flip rule if $(A', B')$ can be obtained from $(A, B)$ by moving at most $k$ nodes from one side of the partition to the other. If $(A, B)$ is a local optimum under the $p$-flip rule, it is also a local optimum under the $k$-flip rule for every $k < p$.

答案

在更大的邻域中没有改进的移动，必然在更小的邻域中也没有改进的移动，故 (A, B) 也是 k-flip 规则下的局部最优，答案为 $\textnormal{T}$

局部最优情况

In local search, if the optimization function has a constant value in a neighborhood, there will be a problem.

答案

$\textnormal{T}$

Random restarts can help a local search algorithm to better find global maxima that are surrounded by local maxima.

答案

$\textnormal{T}$

For an optimization problem, given a neighborhood, if its local optimum is also a global optimum, one can reach an optimal solution with just one step of local improvements.

答案

局部改进的步数取决于初始解的位置，不一定仅需一步，故答案为 $\textnormal{F}$

Since finding a locally optimal solution is presumably easier than finding an optimal solution, we can claim that for any local search algorithm, one step of searching in neighborhoods can always be done in polynomial time.

答案

一步局部搜索的时间复杂度由邻域规模决定，存在指数级大小的邻域（如 TSP 的全路径邻域），无法在多项式时间内完成遍历与评估，答案为 $\textnormal{F}$

Metropolis 算法

In Metropolis Algorithm, the probability of jumping up depends on $T$, the temperature. When the temperature is high, it’ll be close to the original gradiant descent method.

答案

温度高时容易引起底部振荡，温度低时接近原始的梯度下降法，故答案为 $\textnormal{F}$

The Gradient Descent and the Metropolis Algorithm are local search algoritms. The former may not get a globle optimal solution and the latter can but more execution time is needed.

答案

固定温度的 Metropolis 算法不能保证收敛到全局最优解，需要结合模拟退火(simulated annealing) 算法才能得到全局最优解，故答案为 $\textnormal{F}$

SAT & N-Queen Problems 的搜索空间

Local search algorithm can be used to solve lots of classic problems, such as SAT and $N$-Queen problems. Define the configuration of SAT to be $X =$ vector of assignments of $N$ boolean variables, and that of $N$-Queen to be $Y =$ positions of the $N$ queens in each column. The sizes of the search spaces of SAT and $N$-Queen are $O(2^N)$ and $O(N^N)$, respectively.

答案

每个布尔变量有 $2$ 种赋值选择，$N$ 个变量的总赋值组合数为 $2^N$，故 SAT 问题的搜索空间为 $O(2^N)$

皇后放置时每列有 $N$ 种行号选择，搜索空间指的是所有可能，故总配置数为 $N^N$，$N-$ 皇后问题的搜索空间为 $O(N^N)$

综上所述，答案为 $\textnormal{T}$

Hopfield Neural Network

Starting from the following configuration of a Hopfield Neural Network, the state-flipping algorithm will terminate at a stable configuration after at most $32$ iterations.

答案

该算法在至多 $W = \sum_{e} |w_e|$ 次迭代后终止，答案为 $\textnormal{T}$

综合判断

How many of the following statements is/are TRUE?

The 0-1 knapsack problem cannot be solved by any local search algorithm.
The metropolis algorithm always improves the gradient descent algorithm.
In some cases, the state-flipping algorithm cannot terminate.
Unless $P=NP$, there is no $\rho$-approximation for the maximum cut problem for any $\rho<2$.

答案

局部搜索算法可用于求解 $0-1$ 背包的近似解，故表述 $1$ 错误

Metropolis 算法的核心是允许以一定概率接受更差解以逃离局部最优，但并不能总是改进梯度下降法，如对于凸函数优化问题（如线性回归），梯度下降法能高效收敛到全局最优，而 Metropolis 算法接受差解的机制反而会浪费计算资源，故表述 $2$ 错误

离散优化问题的状态空间是有限的，状态反转算法总能终止，故表述 $3$ 错误

最大割问题存在经典的 $ρ<2$ 的近似算法，如 Goemans-Williamson 算法通过半定规划松弛实现近似比 $\approx 1.1382$，其正确性不依赖 $P=NP$，故表述 $4$ 错误

综上所述，正确陈述个数为 $0$

K-center Problems

We are given a set of sites $S = \{s_1, s_2, \cdots, s_n\}$ in the plane, and we want to choose a set of $k$ centers $C = \{c_1, c_2, \cdots, c_k\}$ so that the maximum distance from a site to the nearest center is minimized. Here $c_i$ can be an arbitrary point in the plane.

A local search algorithm arbitrarily choose $k$ points in the plane to be the centers, then - (1) divide $S$ into $k$ sets, where $S_i$ is the set of all sites for which $c_i$ is the nearest center; and - (2) for each $S_i$, compute the central position as a new center for all the sites in $S_i$.

If steps (1) and (2) cause the covering radius to strictly decrease, we perform another iteration, otherwise the algorithm stops.

When the above local search algorithm terminates, the covering radius of its solution is at most 2 times the optimal covering radius.

答案

设站点为 $A(0,0), B(0,1), C(100,0), D(100,1)，k=2$。最优解的中心为 $(0,0.5)$ 和 $(100,0.5)$，覆盖半径为 $0.5$。若局部搜索算法初始中心为 $(50,0)$ 和 $(50,1)$，则划分结果为 $S1={A,C}，S2={B,D}$，两个簇的最小包围圆中心分别为 $(50,0)$ 和 $(50,1)$，覆盖半径为 $50$。由于覆盖半径未严格减小，算法终止，但其覆盖半径 $50$ 远大于最优覆盖半径 $0.5$ 的 $2$ 倍。因此，该算法不能保证 $2$ 倍近似比，答案为 $\textnormal{F}$

Partition Problems

There are $n$ jobs, and each job $j$ has a processing time $t_j$. We will use a local search algorithm to partition the jobs into two groups $A$ and $B$, where set $A$ is assigned to machine $M_1$ and set $B$ to $M_2$. The time needed to process all of the jobs on the two machines is $T_1 = \sum_{j \in A} t_j$, $T_2 = \sum_{j \in B} t_j$. The problem is to minimize $|T_1 - T_2|$.

Local search: Start by assigning jobs $1, \dots, n/2$ to $M_1$, and the rest to $M_2$. The local moves are to move a single job from one machine to the other, and we only move a job if the move decreases the absolute difference in the processing times. Which of the following statement is true?

$\textnormal{A}$. The problem is NP-hard and the local search algorithm will not terminate.

$\textnormal{B}$. When there are many candidate jobs that can be moved to reduce the absolute difference, if we always move the job $j$ with maximum $t_j$, then the local search terminates in at most $n$ moves.

$\textnormal{C}$. The local search algorithm always returns an optimal solution.

$\textnormal{D}$. The local search algorithm always returns a local solution with $\frac{1}{2} T_1 \leq T_2 \leq 2T_1$.

答案

对于选项 $\textnormal{A}$，$|T_1 - T_2|$是非负整数，每次移动都会严格减小它，而其取值范围有限，因此算法必然终止，故 $\textnormal{A}$ 错误

对于选项 $\textnormal{B}$，当选择最大 $t_j$ 的作业移动时，每个作业最多被移动 $1$ 次，因此最多移动 $n$ 次算法终止，故 $\textnormal{B}$ 正确

对于选项 $\textnormal{C}$，局部搜索只能找到局部最优解，无法保证全局最优（例如存在更好的划分，但移动单个作业的局部操作无法到达），故 $\textnormal{C}$ 错误

对于选项 $\textnormal{D}$，存在反例 $A = \{1, 1\}$, $B = \{10\}$ 不满足条件，故 $\textnormal{D}$ 错误

综上所述，正确答案为 $\textnormal{B}$

Maximum Cut Problem

For any undirected graph $G$, the weight of its maximum cut is at least half of the total edge weight.

答案

$\textnormal{T}$

Insider the Kernighan and Lin's K-L heuristic (local search) for graph partition problem, locally optimal solutions are computable in polynomial time.

答案

K-L 启发式算法是一种多项式时间的启发式算法，但它并不保证在多项式时间内找到局部最优解。事实上，图划分问题在交换邻域下是PLS完全的，这意味着寻找局部最优解是计算困难的问题，除非PLS=P，否则不存在多项式时间算法，故答案为 $\textnormal{F}$

Given an undirected graph $G = (V, E)$ with positive integer edge weights $w_e$, find a node partition $(A, B)$ such that $w(A, B)$, the total weight of edges crossing the cut, is maximized. Let us define $S'$ be the neighbor of $S$ such that $S'$ can be obtained from $S$ by moving one node from $A$ to $B$, or one from $B$ to $A$. We only choose a node which, when flipped, increases the cut value by at least $w(A, B)/|V|$. Then which of the following is true?

$\textnormal{A}$. Upon the termination of the algorithm, the algorithm returns a cut $(A, B)$ so that $2.5w(A, B) \geq w(A^*, B^*)$, where $(A^*, B^*)$ is an optimal partition.

$\textnormal{B}$. The algorithm terminates after at most $O(\log |V| \log W)$ flips, where $W$ is the total weight of edges.

$\textnormal{C}$. Upon the termination of the algorithm, the algorithm returns a cut $(A, B)$ so that $2w(A, B) \geq w(A^*, B^*)$.

$\textnormal{D}$. The algorithm terminates after at most $O(|V|^2)$ flips.

答案

大提升翻转（big-improvement-flip）挑选能够提升至少 $\dfrac{2\varepsilon}{|V|}w(A,B)$ 割值的顶点进行翻转

算法中止后会返回一个割集 $(A,B)$，满足：$(2+\varepsilon)w(A,B)\geq w(A^*,B^*)$，因此该算法是一个 $(2+\varepsilon)-$近似算法
该算法最多在 $O\left(\frac{n}{\varepsilon}\log W\right)$ 次翻转后终止，其中 $W = \sum w$

故正确答案为 $\textnormal{A}$

Consider the maximum cut problem. Let $V$ be the set of vertices, let $n = |V|$, and let $W$ be the total edge weight. We have already learned a $(2+\epsilon)$-approximation local search algorithm that needs $O\left(\frac{n}{\epsilon} \log W\right)$ flips. In the following, we are trying to further reduce the number of flips by starting the algorithm with a good initial solution. Note that each vertex $V$ naturally forms a cut $(\{v\}, V - \{v\})$. Let $(\{v^*\}, V - \{v^*\})$ be the one with the largest weight among all such cuts. If we start the $(2+\epsilon)$-approximation local search algorithm with $(\{v^*\}, V - \{v^*\})$, how many flips do we need in the worst case?

$\textnormal{A}$. $\frac{n}{\epsilon} \log \frac{W}{n}$

$\textnormal{B}$. $\frac{n}{\epsilon} \log W$

$\textnormal{C}$. $\frac{n}{\epsilon} \log n$

$\textnormal{D}$. $\frac{n}{\epsilon}$

答案

已知局部搜索算法的翻转次数上界为 $O\left(\frac{n}{\epsilon} \log \frac{W}{w_0}\right)$，其中 $w_0$ 是初始割的权重

选择初始解为最大单顶点割 $(\{v'\}, V - \{v'\})$，其权重 $w_0 = \max_{v \in V} w(\delta(\{v\}))$

由于所有顶点关联边的权重之和为 $2W$，因此 $w_0 \geq \frac{2W}{n}$，即 $\frac{W}{w_0} \leq \frac{n}{2}$

代入上界得翻转次数为 $O\left(\frac{n}{\epsilon} \log \frac{n}{2}\right) = O\left(\frac{n}{\epsilon} \log n\right)$，故答案为 $\textnormal{C}$

Schedule Problems

Scheduling Job Problem: There are $n$ jobs and $m$ identical machines (running in parallel) to which each job may be assigned. Each job $j =1, \cdots, n$ must be processed on one of these machines for $t_j$ time units without interruption. Each machine can process at most one job at a time. The aim is to complete all jobs as soon as possible; that is, if job $j$ completes at a time $C_j$ (the schedule starts at time $0$), then we wish to minimize $C_{max} = max_{j=1,\cdots, n}C_j$. The length of an optimal schedule is denoted as $OPT(C_{max})$.

Local Search Algorithm: Start with any schedule; consider the job $l$ that finishes last; check whether or not there exists a machine to which it can be reassigned that would cause this job to finish earlier. If so, transfer job $l$ to this other machine. The local search algorithm repeats this procedure until the last job to complete cannot be transferred.

Which of the following statement is false?

$\textnormal{A}$. $OPT(C_{max}) \geq \sum\limits_{j=1}^{n} \frac{t_j}{m}$

$\textnormal{B}$. When transfering a job, if we always reassign that job to the machine that is currently finishing earliest, then no job is transferred twice.

$\textnormal{C}$. Upon the termination of the algorithm, the algorithm may return a schedule that has length at least $2OPT(C_{max})$

$\textnormal{D}$. Suppose that we first order the jobs in a list arbitrarily, then consequently assign each job to the machine that is currently of earliest completion time, the schedule obtained cannont be improved by the local search procedure.

答案

对于选项 $\textnormal{A}$，最优调度的完工时间至少为所有作业处理时间之和除以机器数，即 $OPT(C_{\text{max}}) \geq \frac{\sum_{j=1}^n t_j}{m}$，这是经典下界，故 $\textnormal{A}$ 表述正确

对于选项 $\textnormal{B}$，若每次都将作业重新分配到当前完工时间最早的机器上，则不会再有机器满足重新分配该任务后能够提前完成该任务，故每个作业至多被转移一次，$\textnormal{B}$ 表述正确

对于选项 $\textnormal{C}$，已知该局部搜索算法的近似比上界为 $2 - \frac{1}{m}$，不可能返回长度至少为 $2 \cdot OPT(C_{\text{max}})$ 的调度，故 $\textnormal{C}$ 表述错误

对于选项 $\textnormal{D}$，贪心算法得到的调度中，最后一个完成的作业无法通过转移到其他机器而更早完成，该调度已是局部最优，故 $\textnormal{D}$ 表述正确

综上所述，答案为 $\textnormal{C}$

$\textnormal{C}$ 选项的详细证明

设算法终止时得到的调度长度为 $C_{\max}$，最后完成的作业 $l$ 的处理时间为 $t_l$。

由于算法已终止，将作业 $l$ 转移到任何其他机器 $k$ 上均不能使其完成时间提前，即对任意 $k \neq i$（$i$ 为 $l$ 当前所在机器），有 $L_k + t_l \geq C_{\max}$，其中 $L_k$ 为机器 $k$ 的总负载。

所有机器的总负载为： $$ \sum_{j=1}^n t_j = \sum_{k=1}^m L_k = L_i + \sum_{k \neq i} L_k \geq C_{\max} + (m-1)(C_{\max} - t_l) = m C_{\max} - (m-1) t_l $$

整理得： $$ C_{\max} \leq \frac{\sum_{j=1}^n t_j}{m} + \frac{m-1}{m} t_l. $$ 由下界 $OPT \geq \frac{\sum_{j=1}^n t_j}{m}$ 和 $OPT \geq t_l$，可得： $$ C_{\max} \leq OPT + \frac{m-1}{m} OPT = \left(2 - \frac{1}{m}\right) OPT. $$ 即算法返回的调度长度严格小于 $2 \cdot OPT$（当 $m \geq 2$ 时），不可能达到 $2 \cdot OPT$

Load balancing problem

Load balancing problem: We have $n$ jobs $j=1, 2, \ldots, n$ each with processing time $p_ j$ being an integer number. Our task is to find a schedule assigning $n$ jobs to $10$ identical machines so as to minimize the makespan (the maximum completion time over all the machines). We adopt the following local search to solve the above load balancing problem.

LocalSearch: Start with an arbitrary schedule.Repeat the following until no job can be re-assigned:

Let $l$ be a job that finishes last.
If there exists a machine $i$ such that assigning job $l$ to $i$ allows $l$ finish earlier, then re-assign $l$ to be the last job on machine $i$.
If such a machine is not unique, always select the one with the minimum completion time.

We claim the following four statements:

The algorithm LocalSearch finishes within polynomial time.
The Load-balancing problem is NP$-$hard.
Let OPT be the makespan of an optimal algorithm. Then the algorithm LocalSearch finds a schedule with the makespan at most of 1.8 OPT.
This algorithm finishes within $O(n^2)$.

How many statments are correct ?

答案

整体思路与 Schedule Problems 一致，近似比 $= 2 - \frac{1}{m} = 1.9$，表述 $3$ 错误，其余表述均正确，答案为 $3$

Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is a classic problem: given a set of cities and the distances between each pair of cities, the goal of TSP is to find the shortest cycle that visits each city exactly once and returns to the starting city.

The 2-opt method is a local search algorithm used to solve the TSP. Specifically, the searching strategy is as follows:

Starting at a feasible solution to the TSP (a valid cycle which visits each city exactly once and returns to the starting city).
In each iteration, the current cycle is denoted as $P$. The neighboring solution $P'$ is obtained by a 2-opt move. The 2-opt move contains the following steps:
1. Choosing two non-adjacent edges $(i, i+1)$ and $(j, j+1)$ from the cycle;
2. Removing these two edges, and replacing them with new edges $(i,j)$ and $(i+1,j+1)$, forming a new cycle $P'$. If the new cycle obtained by the 2-opt move is shorter than the current cycle, updating the current cycle as the new cycle.
Repeating the step (2) until no further improvement can be made by applying 2-opt moves.

Here is an illustration of a 2-opt move.

Which of the following statements is true?

$\textnormal{A}$. The TSP is NP-hard, so the 2-opt iteration will not terminate.

$\textnormal{B}$. When no 2-opt move can improve the current cycle, the algorithm reaches the global optimum.

$\textnormal{C}$. When applying the 2-opt method, different initial cycles may lead to different local optimums.

$\textnormal{D}$. After each 2-opt move, the solution is improved by at least a constant ratio.

答案

TSP 是 NP 难问题，但总距离无法无限减小，2-opt 迭代会终止，故 $\textnormal{A}$ 表述错误

2-opt 是局部搜索算法，仅能达到局部最优而非全局最优，故 $\textnormal{B}$ 表述错误

局部搜索算法的初始解会影响最终的局部最优，不同初始环的邻域（可通过 2-opt 移动到达的解）不同，因此会收敛到不同的局部最优，故 $\textnormal{C}$ 表述正确

每次 2-opt 移动的改进幅度是替换边的距离差，没有固定比例的保证，故 $\textnormal{D}$ 表述错误

综上，答案为 $\textnormal{C}$