Homework #3 Iterative Refinement and Relaxation/Rounding

1 Iterative Refinement and Relaxation/Rounding
This homework will give you some familiarity with the design and implementation of optimization
methods based on iterative refinement, as well as with the concept of “relaxing” a hard optimization
problem to yield an easier problem, whose solution can then be “rounded” to obtain a high-quality
solution of the original problem.
The problem we will consider for this assignment is a type of linear arrangement problem. Just
as with the traveling salesman problem you have studied in lab, your goal will be to find a good
ordering of n items, numbered 0 . . . n − 1 (in the input we consider, n = 936). If you look at the
input file
/group/course/cpsc212/f14/hw3/wires.txt
you will find a list of m = 2664 pairs of numbers. Each pair (i, j) tells you that items i and j
are considered “connected”. In computer science terminology, this is typically called a graph or
network, with n nodes and m edges, each edge connecting a pair of nodes. Depending on the
application, a graph can represent many different things. For example, it could represent a social
network, with each node being a person and each edge (connection) representing a pair of friends.
In another application, the nodes could represent electrical components on a circuit board, and the
edges could represent wires connecting pairs of components.
The goal of this problem is to order the n nodes so that the sum of squared lengths of all edges is
minimized. More precisely, we want to assign each node i to a position xi on the number line so as
to minimize
X(xi − xj )
2
,
where the sum is taken over all edges (i, j). The positions x0 . . . xn−1 of the n nodes must be some
permutation of {0, 1, . . . , n − 1}. That is, the nodes are to be mapped to positions 0, 1, . . . , n − 1
on a number line in some optimal order.
This problem has several applications. In the context of a social network, it asks us to order the
n individuals so that friends tend to be located near each-other in the ordering (if two friends i
and j are far away from each-other, the term (xi − xj )
2
in the objective would be large, adding
a substantial penalty to the total objective). If our n nodes represent electrical components, this
problem asks us to arrange these components in a line so as to minimize the total squared lengths
of all wires connecting the components, which leads to an efficient circuit layout. Figure 1 shows
an example of a small problem instance on just 4 nodes, along with two possible orderings; the first
1
0 1 2 3
0 1 2 3
Objective Value:
1 + 4 + 4 + 9 = 18
1 + 1 + 1 + 9 = 12
wires.txt:
0 1
1 2
2 3
3 0
Ordering #1:
Ordering #2: 2 0 3 1
0 1
3 2
1 0 3 2
Figure 1: Example instance with 4 nodes and 4 edges, with two possible
orderings, one better than the other.
has objective value 12 + 12 + 12 + 32 = 12, which is better than the second, with objective value
1
2 + 22 + 22 + 32 = 18.
Since the problem above is known to be NP-hard, it is not known how to compute an optimal
solution in an efficient manner (for the input file given, we know the objective value of an optimal
solution is slightly less than 1 million, but we do not know the exact optimal solution). It will be
interesting to see the quality of solutions you, as a class, mange to compute.
2 First Approach: Iterative Refinement
Your first goal is to generate a good solution using iterative refinement. Much as with the TSP
lab, you will start with an arbitrary (random) ordering of the n nodes, which you will continually
refine until it becomes locally optimal.
How exactly you refine your solution is left slightly open-ended on purpose, to allow you to experiment with different ideas (this is often a key part of the process of developing an effective solution
based on iterative refinement). For example, in each refinement step, you could try all neighboring
solutions obtained by:
1. Swapping a pair of adjacent nodes in the ordering,
2. Swapping a pair of non-adjacent nodes in the ordering, or
3. Reversing part of the ordering (as with the TSP lab).
Of course, these are just suggestions – you certainly don’t need to try all of them, and you are
encouraged to try other ideas as well. Note that (i) involves checking only O(n) neighboring
solutions, while (ii) and (iii) involve checking O(n
2
) neighboring solutions, so with n = 936 the
latter two approaches will take substantially more time (although on the other hand, they may
identify improvements that the simpler approach (i) would miss). Also note that if you swap two
nodes, you can quickly compute the resulting change in objective value by only looking at the edges
connected to those two nodes and seeing how much these change in length (since all other edges
remain the same length); this can help speed up your search tremendously.
2
As with the TSP lab, you might want to consider whether you want to move immediately to a better
neighboring solution when it is found, or whether you want to search the entire neighborhood and
only then move to the best neighboring solution. In the first case, you may want to be cautious if
you only search for neighboring solutions, say from left to right in the ordering, since this may cause
your swaps to be concentrated only on the left side of the ordering (since you will likely discover a
good swap before scanning very far to the right); this might lead to slow convergence.
You should continue to refine your solution until it becomes locally optimal (where there are no
neighboring solutions that are better). Your code should print out the final ordering and its
objective value – the total squared length of all its edges. For full credit, you must obtain an
ordering of objective value less than 1 million with at most 10 minutes of running time.
If desired, you can restart your algorithm from several randomly chosen initial orderings (as with
the TSP lab). However, note that it may already take a few minutes to refine each ordering, so
you may not have much time to try too many orderings.
3 Second Approach: Relaxation and Rounding
Our original problem asks us to assign each node i to a position xi (where the xi
’s are restricted
to be a permutation of {0, 1, . . . , n − 1}) so as to minimize P(xi − xj )
2 over all edges (i, j). This
problem is unfortunately NP-hard, but if we relax the constraint that our nodes need to be assigned
to integer locations in the set {0, 1, . . . , n − 1}, the problem becomes efficiently solvable, leading to
another interesting method for generating good solutions via iterative refinement.
Suppose we guess that node a should be first in our ordering (xa = 0) and node b should be last
(xb = n − 1). For the remaining nodes, suppose that we want to assign them to locations between
0 and n − 1 which no longer need to be integers. That is, we might assign node i to a location
xi = 3.71. By removing the constraint that our nodes need to be embedded at integer positions, this
makes the problem of minimizing P(xi −xj )
2 much easier. By taking the gradient of the objective
function and setting it to zero, we get a linear system (if you know multi-variable calculus, you are
encouraged to give this a try, although it is not a necessary part of this assignment). By examining
the linear system, we find that in any optimal solution, the position xi of node i must be the average
of the positions of i’s neighbors in the network (the nodes connected to i).
The observation above gives us a simple iterative refinement method for optimally solving the
relaxed problem: start with xa = 0 and xb = n − 1, and xi set arbitrarily in the range 0 . . . n − 1
for all other nodes i. Then, we repeatedly replace the position xi of each node i with the average
of the positions of its neighbors (the only two nodes we do not update are a and b, which stay fixed
at the endpoints of the ordering). Over sufficiently many iterations, the positions of the nodes will
converge so as to minimize P(xi − xj )
2
. You can test for convergence by looking at how much the
positions of the nodes move in each iteration, stopping when they cease to move very much.
After solving the relaxed problem, we have a solution in which nodes are assigned to non-integer
positions like xi = 3.71. We can use this as a guide for obtaining a good solution for the original
problem, however, by simply sorting the nodes by their positions, and assigning them to locations
0, 1, 2, . . . , n − 1 in this order. By “rounding” our solution in this fashion, we will typically obtain
a reasonably good solution to the original problem.
The only question remaining is how to choose the endpoints a and b. You could try running the
approach above for all O(n
2
) possible choices of a and b, but this might take too long, so instead
3
you may want to run the approach above on a smaller number of random choices for a and b, taking
the best final solution you get. For full credit, your code should produce an ordering of objective
value less than 1 million in less than 10 minutes of compute time on the lab machines. Please print
out the final ordering of your nodes, along with the objective value of this ordering.
4 Submission and Grading
You should submit two programs for this homework, the first using iterative refinement and the
second using the relaxation and rounding approach (which is also based on iterative refinement,
of course). Each program should produce output in less than 10 minutes when run on the lab
computers (we will only run them for up to 10 minutes during grading).
If you wish, feel welcome to submit a text file containing the best ordering you can obtain for the
input file given in this assignment – irrespective of the technique used or the running time spent.
This is only for fun, to see who in the class manages to come up with the best solution overall. You
will earn no points for this part, only the respect and admiration of your instructor.
Please name your submissions for the two parts of this assignment part1.cpp and part2.cpp.