### COSC 6367 (Dr. Eick) - Spring 2010Project 1USING EC FOR 5x7 BALANCED TRANSPORTATION PROBLEMS

 Due Date: March 6, 2010, 11p (electronic submission) Last Updated: March 3, 2010, 5:55pm

Write a system that is capable of solving 5 source / 7 destination real-valued balanced transportation problems with respect to four given cost functions. Write an interactive EC-style system that
• reads the amount available at the five sources
• read the amount to be delived to the seven final destinations
• asks the user to select one of four possible cost functions (see below)
• reads an integer random seed (used to analyze random generators; because you program employs a probabilistic algorithms, different seeds usually lead to different results, particularly for transportation problems that cannot be solved analytically)
and finds a "good" solution for the transportation problem, and allows the user to rerun the system for the same or another cost-function.

For example, let us assume that the following source and destination capacities are given:

 source[1]=5source[2]=5source[3]=20source[4]=15source[5]=15 destination[1]=8destination[2]=8destination[3]=8destination[4]=8 destination[5]=8destination[6]=10destination[7]=10

Moreover, four different cost functions f1, f2, f3, and f4 will be used for the project:

```Let
i the source index (i=1,...,5)
j be the destination index(j=1,...,7)
u the number of units to be transported (>=0)

f1(i,j,u) := (|i*j - 17|)* u
f2(i,j,u) := (|i^2-(j^2)+1|)^2 * u^2
f3(i,j,u) := |i*j - 11|*sqrt(u)
f4(i,j,u) := |i*j - 17|*u + u^4
"general transportation problem1""general transportation problem2"

Assuming this framework, a solution found by your program could be:

8    8    8   8    8    10   10

5    5    0    0   0    0     0    0
5    3    2    0   0    0     0    0
20   0    6    8   6    0     0    0
15   0    0    0   2    8     5    0
15   0    0    0   0    0     5   10
```

The transportation cost of the above solution matrix, assuming that function f1 is used, would be:
```f1(1,1,5) + f1(2,1,3) +  f1(2,2,2) + f1(3,2,6) + f1(3,3,8) +
f1(3,4,6) + f1(4,4,2) +  f1(4,5,8) + f1(4,6,5) + f1(5,6,5) + f1(5,7,10)
```
In general, the elements of the solution matrix are floating point numbers; however, if you print the elements of the matrix, round those to two numbers after the decimal point(e.g. 27.14334344343434 is printed as 27.14 and 3.45500111232332 is printed as 3.46).

Provide a script like interface for your program that allows to run a large set of experiments, such as those mentioned above!

Write a program that displays the inputs, the evolution process, and the final results obtained by a program run in a nice and understandable form. Test and enhance your program assuming each of the 4 classes of supported cost-functions. Be prepared to demo your program!

Write a report (approx. 9 to 13 single spaced pages) that describes the evolution of the project, gives a clear description of the explored and employed search strategies, and summarizes the results of running your program using the four cost functions for:
 source[1]=5source[2]=5source[3]=20source[4]=15source[5]=15 destination[1]=8destination[2]=8destination[3]=5destination[4]=5 destination[5]=8destination[6]=20destination[7]=6
and for:
 source[1]=14source[2]=14source[3]=14source[4]=14source[5]=14 destination[1]=10destination[2]=10destination[3]=10destination[4]=10 destination[5]=10destination[6]=10destination[7]=10

Report the best found solutions for each cost function.  Finally, the report should interpret the empirical results and summarize the important findings and accomplishments of the project.