Exercises on Optimization

Consider the problem of finding a corridor between two wildlife reserves, where both corridors and reserves are protected regions of land. This problem was described by Gomes (2009) in a previous reading.

For this exercise, we formalize the corridor design task as follows.

An expanse of land, called the territory, is represented as an N x M grid of patches, each patch is square and represents a unit of land (e.g., square mile), and all patches are of equal size. Since N need not equal M, the entire grid of patches need not form a square, but it forms a rectangle. The rectangle is filled (i.e., all patches have eight neighboring patches, including on diagonals, except for patches on the edges).

Each patch has a boolean variable called Protected? associated with it, and two real-valued variables associated with it — Cost and Utility. All costs are in the same unit of measure, such as dollars (though the particular unit does not matter for this exercise), and all utilities represent some measure of habitability for a species for which land is being protected.

Two patches are adjacent if they share a common side. A region of patches is protected if all patches in the region are protected (Protected? = True) and all pairs of patches in the region are connected by a chain of adjacent patches that are in the same region. A maximal protected region is one for which there is no proper superset of patches that form a protected region.

In the initial state of the corridor design problem there are two maximal protected regions (i.e., reserves) of patches. These two maximal regions are not connected by protected adjacent patches; and indeed, neither region would be maximal if they were so connected.

Part 1) For the first part of this exercise (due Monday), write pseudo code that identifies a corridor (i.e., a set of adjacent patches) that connect the identified maximal regions, thus forming a single larger maximal protected regions. The goal in this first exercise is to minimize the sum of patch costs (local or global) of the patches that form the corridor.

Give your pseudocode as part of a Powerpoint presentation (or using similar presentation software, even pdf) that you can speak to the class about. Illustrate your algorithm on at least one example (show a picture of the territory). Be able to explain how you are representing the two regions and the corridor. If you use a paper, from which you adopt or adapt the algorithm, feel free to do so, but cite the paper(s).