This is a list of exercises that will be treated in class in the next sessions on Examples. It maybe good going through them before coming to the classes.
Consider a local search algorithm for GCP that uses the strategy k fixed/complete/unproper. That is, it solves a sequence of decision k-coloring problems with candidate solution any complete, possibly improper, assignment of colors to vertices. The neighborhood operator is the one-exchange and the evaluation function is the number of edges in conflict. How can we achieve a O(nk) complexity to choose the best improvement at each step of the local search?
Consider the Max k-SAT problem and a local search on the one-flip neighborhood with best improvement strategy. Indicate which auxiliary data structures can be maintained to speed up each step. Provide a computational analysis.
A possible application of local search to the GCP defines the following:
Show that any local optimum of this function corresponds to a feasible coloring. Does a global optimum correspond to a coloring that uses the minimal possible number of colors?
p-Median Problem
Input: A set U of locations for n users, a set F of locations for m facilities and a distance matrix D=[dij] ∈ Rn× m.
Task: Select a set J ⊆ F of p locations where to install facilities such that the sum of the distances of each user to its closest installed facility is minimized, i.e.,
| min | ⎧ ⎨ ⎩ |
|
| dij | J ⊆ F and |J|=p | ⎫ ⎬ ⎭ |
Design construction heuristics and local search algorithms.
Set Covering
Input: Collection C of subsets of a finite set S and a weight function ω: C → R.
Task: Find a set cover for S, i.e., a subset C′⊆ C such that every element in S belongs to at least one member of C′ and the sum of the costs associated with the subsets in C′ is minimal.
Is this problem NP-hard? If the problem is NP-hard, design at least one construction heuristic and at least one local search (solution representation + neighborhood + evaluation function).
Make a randomized version of the construction heuristic designed in the previous exercise.
Set Problems
|
|
|
Design a simple construction heuristic and a simple local search
algorithm for these problems.
Bin Packing Problem
Input: A finite set U of items, a size s(u) ∈ Z+ for each u∈ U, and a positive integer bin capacity B.
Task: Find the minimal number of bins K for which there exits a partition of U into disjoint sets U1, U2, …,Uk and the sum of the sizes of the items in each Ui is B or less.
Two-dimensional bin packing
Input: A finite set U of rectangular items, each with a width wu ∈ Z+ and a height hu ∈ Z+, u ∈ U, and an unlimited number of identical rectangular bins of width W ∈ Z+ and height H ∈ Z+.
Task: Allocate all the items into a minimum number of bins, such that the bin widths and heights are not exceeded and the original orientation is respected (no rotation of the items is allowed).
Make a Venn diagram (set diagram) representing the relation between the following classes of algorithms: construction heuristics (CH), metaheuristics (MH), local search (LS), stochastic local search (SLS), best improvement (BI), iterative improvement (II), first improvement (FI), uninformed random walk (RW), beam search (BS), rollout (RO), iterated greedy (IG), iterated local search (ILS).
Compare the pivot rules in tabu search and in simulated annealing. Think about computational issues and devise a guideline about the situations in which one or the other metaheuristic may be more appropriate.
Design a tabu search algorithm for the single machine total weighted tardiness problem using all three neighborhoods discussed in class.
Graph Partitioning Problem
Input: A graph G=(V,E), weights w(v) ∈ Z+ for each v ∈ V and l(e) ∈ Z+ for each e ∈ E.
Task: Find a partition of V into disjoint sets V1,V2,…,Vm such that ∑v ∈ Vi w(v) ≤ K for 1≤ i ≤ m and such that if E′ ⊆ E is the set of edges that have their two endpoints in two different sets Vi, then ∑e ∈ E′l(e) is minimal.
Consider the specific case of graph bipartitioning, that is, the case |V|=2n and K=n and w(v)=1, ∀ v ∈ V.
Linear Ordering Problem
The two following problems are equivalent.
Input: an n × n matrix C
Task: Find a permutation π of the column and row indices
{1,…,n} such that the value
| f(π)= |
|
| cπiπj |
is maximized. In other terms, find a permutation of the columns and rows of C such that the elements in the upper triangle is maximized.
Feedback arc set problem (FASP)
Input: A directed graph D=(V,A), where V={1,2,…,n}, and arc weights cij for all [ij] ∈ A
Task: Find a permutation π1, π2, … πn of V (that
is, a linear ordering of V) such that the total costs of those arcs
[πjπi] where j>i (that is, the arcs that point backwards in
the ordering)
| f(π)= |
|
| cπjπi |
is minimized.
Design a simple construction heuristic and a simple local search
algorithm.
Quadratic Assignment Problem
Input: A set of n locations with a matrix D=[dij] ∈
Rn× n of distances and a set of n units with a matrix
F=[fkl]∈ Rn× n of flows between them
Task: Find the assignment σ of units to locations that minimizes the sum of products between flows and distances, i.e.,
|
| fij dσ(i)σ(j) |
Define solution representation, evaluation function and neighborhood for
a local search algorithm. Make a computational analysis and show that a
single neighbor can be evaluated in O(n).
Graph Partitioning Problem
Input: A graph G=(V,E), weights w(v) ∈ Z+ for each v ∈ V and l(e) ∈ Z+ for each e ∈ E.
Task: Find a partition of V into disjoint sets V1,V2,…,Vm such that ∑v ∈ Vi w(v) ≤ K for 1≤ i ≤ m and such that if E′ ⊆ E is the set of edges that have their two endpoints in two different sets Vi, then ∑e ∈ E′l(e) is minimal.
Consider the specific case of graph bipartitioning, that is, the case |V|=2n and K=n and w(v)=1, ∀ v ∈ V.
Consider the following design problem: Dispose on a 8x8 board numbers from 1 to 256 in such a way that each number is placed only once and that the binary representaiton of the numbers have the minimum Hamming distance in the neighborhood, that is, the largest distance from any of the numbers in the 8 neighboring cells. Design a tabu search algorithm.