COSC 6367 (Dr. Eick) - Spring 2010
Project 1

USING 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]=5
    source[2]=5
    source[3]=20
    source[4]=15
    source[5]=15
    		 destination[1]=8
    destination[2]=8
    destination[3]=8
    destination[4]=8
    destination[5]=8
    destination[6]=10
    destination[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
    		
"linear transportation problem"
    "quadratic transportation problem"
    
"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]=5
    source[2]=5
    source[3]=20
    source[4]=15
    source[5]=15    		 destination[1]=8
    destination[2]=8
    destination[3]=5
    destination[4]=5
    destination[5]=8
    destination[6]=20
    destination[7]=6
    and for:
    source[1]=14
    source[2]=14
    source[3]=14
    source[4]=14
    source[5]=14    		 destination[1]=10
    destination[2]=10
    destination[3]=10
    destination[4]=10
    destination[5]=10
    destination[6]=10
    destination[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.