Important note: all code submitted must be your original work. If you use code taken from the internet, an API, or other sources and submit it as your own work you will not get credit for this assignment. Further if your source is not acknowledged, you are subject to the department policies for plagiarism.

Properties of nice code:

1. Indented properly.
2. Comments to explain what each function or method is doing.
3. Comments to explain the steps of each algorithm.
4. Comments to explain how your data structure is arranged (e.g. where is the z row)?
5. The tasks should be in functions or methods and not part of the main.
6. The functions or methods should be logically divided into the sub-tasks for the algorithm. Reuse code instead of making copies of it with slight modifications.
7. Efficiency is important. For example: determine if a dictionary is optimal at the same time as searching for a pivot column, and determine if it is unbounded when looking for a pivot row. Printing the dictionary should take time which is in O(m * (n+m)).
8. Try to make your code as elegant and as easy to understand as you can.

Add the following enhancements to your program:

1. Update your code so that problems requiring the 2-phase method are handled automatically.
   Suggested test problems: Problem 3.9, p. 44, parts (a), (b), and (c).
2. Modify your program so that the user can select one of the three rules for pivoting from Problem 4.1, p. 52 (see solutions, p. 466 for the names of the rules).
   Suggested test problem: Question 4.1, p. 52.
3. In the two-phase method, occasionally there is a degenerate optimal solution which results in x₀ still being in the basis at the end of phase 1. In this event, it is necessary to do one more pivot at the end of phase 1 to get x₀ out of the basis before the initial dictionary is set up for phase 2. The example given here arose in the process of my research and revealed a bug in my original program. When I ran it with the smallest subscript rule it said the problem was unbounded. When I fixed the bug, it gave an optimal solution. Test your program on this example using the smallest subscript rule to make sure that your code works properly.
   8 14
   1 0 0 0 0 0 0 0
   223 1 0 0 0 0 0 0 0
   0 1 -5 -2 0 0 0 0 0
   0 6 0 -1 -2 0 0 0 0
   720 0 1 1 1 0 0 0 0
   -720 0 -1 -1 -1 0 0 0 0
   600 1 0 0 0 1 1 1 1
   -600 -1 0 0 0 -1 -1 -1 -1
   0 4 0 0 0 -1 -2 -3 -4
   0 -4 0 0 0 1 2 3 4
   0 2 0 0 0 -2 -2 0 0
   0 0 5 2 0 -3 -1 0 0
   0 0 -5 -2 0 3 1 0 0
   36 0 1 0 0 0 0 0 0
   0 0 0 0 0 -1 0 0 0
   

   If you are programming in Java you may have to increase epsilon to a value such as 10^-5 in order to avoid pivoting on columns where there is a coefficient that should actually be zero. If your dictionary coefficients become very large it is a sign that you divided by a value that should actually have been zero.

Submissions

Upload your code to connex. The input should come from standard input and the output should go to standard output. The input formatting is the same as the project part 1.

Important Instructions for Connex submissions to facilitate marking

Please number the pivot rules as follows:
Pivot Rule:
1 - smallest subscript.
2 - largest coefficient
3 - maximum increase

Rules for everybody:

1. Do not tar or zip or gzip your files.
2. Upload them one at a time.
3. If I have exactly the files you uploaded for your program, all I should have to do to compile and run is to type what is indicated below for your programming language.

If you are programming in Java:

1. Do not use packages.
2. Your main should be in Simplex.java (and not any other class and not simplex.java and not Symplex.java).
3. I should be able to compile your java files with
   javac *.java
4. Then I will run it like this:
   java Simplex [pivot_rule] < my_input_file_name > my_output_file_name
   For example, for largest coefficient rule I might type:
   java Simplex 2 < in_test1 > out_test1

If you are programming in C:

1. I will compile using
   gcc *.c
2. I will run it like this:
   a.out [pivot_rule] < my_input_file_name > my_output_file_name
   For example, for largest coefficient rule I might type:
   a.out 2 < in_test1 > out_test1

If you are programming in C++:

1. I will compile using
   g++ *.cpp
2. I will run it like this:
   a.out [pivot_rule] < my_input_file_name > my_output_file_name
   For example, for largest coefficient rule I might type:
   a.out 2 < in_test1 > out_test1