Iterative Improvement

Iterative improvement is an algorithmic strategy for finding good (but perhaps not the best!) solutions to optimization problems. Optimization problems are those problems for which there exists more than one feasible solution and further where each feasible solution can be assigned a comparative metric. The goal in solving optimization problems is then to find the specific solution or solutions from the set of all possible solutions which have the optimum score compared to all other solutions ('optimum' can be either the maximum or minimum score, depending on the specific problem at hand.). Each player's turn in a game of Scrabble, for example, can be viewed as an optimization problem. Each legal placement of letters from a player's hand onto the Scrabble board defines one possible solution to the problem of performing a player's turn; however, players are often interested in finding a placement that earns them the most number of points possible. That is to say a player prefers some solutions to others and searches for the most preferable solution among all possible solutions. (Note that different words may earn the player the same number of maximum possible points for a given turn. It is important to note that in optimization problems more than one solution may be considered optimum or "the best.")

Iterative improvement is one technique for searching through potential solutions to a problem in pursuit of the optimum solution. However, as we will see, iterative improvement is not guaranteed to actually find optimal solutions to optimization problems. While not perfect, iterative improvement has the practical benefit of often times being computationally fast and easy to implement.

The general outline of an iterative improvement algorithm is as follows:

  1. Quickly select an easy to compute solution from the set of all possible solutions.
  2. Score the first solution.
  3. Using the solution at hand, quickly compute a new set of solutions that are easily derived from the solution at hand.
  4. Score each solution in the derived set.
  5. Take the best solution from the derived set. If this solution is better than the solution at hand, make it the solution at hand and repeat steps 3-5. If not, return the solution at hand as the best found solution.

Conceptual Example: Hill Climbing

Imagine the task of manually finding the highest natural point in the the state of Texas. One possible iterative improvement algorithm for doing so is as follows:

  1. Walk outside. The first candidate solution is simply where you are standing. (Assuming you are currently in Texas.)
  2. Use an altimeter to score your current height.
  3. Observe your surroundings to identify all points in your field of view that appear higher than your current position and walk to each of them.
  4. Score each visited point with your altimeter. Walk to the highest position observed from these points. If there is a tie, choose a point randomly from the set of highest points.
  5. Repeat this process from step 3 until you are standing at a point where no higher points are in visual range.

As you can see, using this strategy may or may not lead us to the highest point in Texas. Arriving on at the highest point depends on where we start and whether there is a chain of increasingly taller hills within visual range of each other to lead us along a path to the highest point. It is possible that we "settle" on a hill that is the tallest in our visual range but not actually the highest point in Texas. These solutions are referred to as local optima. That is, solutions that are best relative to neighboring solutions but not the overall best possible solution. The best possible solutions to an optimization problem are, conversely, termed global optima.

The Job Assignment Problem

We define the Job Assignment Problem as follows:

Input: $n$ individuals, $n$ jobs, and an $n \times n$ cost matrix $C$, where $C[i,j]$ is the cost of assigning person $i$ to job $j$.
Output: set $S = \{(i, j)\}$ of $n$ pairs, indicating the assignment of each individual $i$ ($1 \le i \le n$) to a job $j$ ($1 \le j \le n$), such that each individual appears in exactly one pair in $S$, each job appears in exactly one pair in $S$, and the total cost of the assignments in $S$ is minimized.

Exercise 1. Problem Representation

Transform the Job Assignment Problem to a graph-theoretic problem on graphs. That is, formulate a problem whose input consists of a graph, and whose output can be used to identify a solution to the Job Assignment Problem. (All you are asked for here is to just describe the Input and Output; you are not asked to solve the problem in this part.)

Exercise 2. Example Instance

Consider the following input instance of the Job Assignment Problem: 3 individuals, 3 jobs, and the following cost matrix $C$:

1

10

10

10

1

10

10

10

1

Draw the graph that your transformation from Exercise 1 would produce from this input instance, clearly indicating the nodes, edges, and any other necessary information. Further, clearly describe the output of the problem you defined in Exercise 1 on this input, and how it translates back into a solution to the Job Assignment Problem.

Exercise 3. Iterative Improvement

Describe in pseudocode an iterative improvement algorithm for solving the graph-theoretic problem you defined above. Your algorithm might not be guaranteed to find a globally optimal assignment, but it must at least return a locally optimal assignment. Clearly describe the feasibility and optimality criteria, as well as the main operations that your algorithm uses as it searches for a solution.

Exercise 4. Implementation

Implement your algorithm from part Exercise 3 in Python. Verify it produces the same result as Exercise 2.

Submit your code

At the end of lab, submit your group's Python code here.