Project 4 - Linear Program Converter

This project is OPTIONAL and will only help your grade in the project category

Objectives:

Apply the steps to convert a linear program to slack form

Description:

Given an input file with a linear program, convert it into slack form (See Section 29.1). The input file will start with either "maximize" or "minimize", followed by the objective function. The second line will have "subject to" on it. Each of the remaining lines will have an equality or inequality, with a constant on the right-hand side. You can make the following assumptions about the input files:

All variables will have a nonnegativity constraint (e.g., x_i >= 0)
All coefficients and constants are (positive or negative) whole numbers

Requirements

Your program needs to meet the the following requirements for full points:

Convert minimization objective functions to maximization objective functions
Display basic variables on the left of an equality sign, following by a constant, if applicable, then all the of non-basic variables (and their coefficients)
Display the nonnegativity constraints for all variables
All variables will be of the form: x_NUMBER, and will appear in ascending numerical order
All of the non-basic variables will appear in the objective function

Additionally, do not use Swing components (to accommodate the grading pipeline).

Examples

Given the following contents of project4-testA.txt:

minimize -2x_1 + 3x_2
subject to
	x_1 + x_2 = 7
	x_1 - 2x_2 <= 4
		      
	x_1 >= 0
	x_2 >= 0

Your program should match the following output exactly:

Please enter the input filename (or simply press return to use ./project4-testA.txt) 
Converting the linear program in ./project4-testA.txt . . .

maximize 2x_1 - 3x_2
subject to
	x_3 = 7 - x_1 - x_2
	x_4 = -7 + x_1 + x_2
	x_5 = 4 - x_1 + 2x_2

	x_1, x_2, x_3, x_4, x_5 >= 0

Additionally, here's a second input file: project4-testB.txt:

minimize -x_1 - 2x_2 + x_3
subject to
	2x_1 + x_2 + x_3 <= 14
	4x_1 + 2x_2 + 3x_3 <= 28
	2x_1 + 5x_2 + 5x_3 <= 30

	x_1 >= 0
	x_2 >= 0
	x_3 >= 0

Furthermore, here's a third input file: project4-testC.txt:

maximize x_1 + 2x_2 - x_3
subject to
	-2x_1 - x_2 - x_3 >= -14
	4x_1 + 2x_2 + 3x_3 <= 28
	2x_1 + 5x_2 + 5x_3 <= 30
						    
	x_1 >= 0
	x_2 >= 0
	x_3 >= 0

Rubric:

Points      Item
----------  --------------------------------------------------------------
_____ / 10  Style
            + Code is indented correctly
            + Functions should be no longer than 1 page
            + Documentation: (written for another software developer)
              * All source code files include Javadoc header block with description, author, version/date, etc.
              * Javadoc (with block tags) before each method
              * All non-trivial variables are commented
              * Comments included before major portions of code
_____ /  0  Program compiles without errors
_____ /  0  Program executes without crashing
            Requirements met:
_____ / 10  + Objective function is presented in slack form (maximization)
_____ / 15  + Equalities in linear program are converted to inequalities
_____ / 10  + Greater-than inequalities in linear program are converted to less-than inequalities
_____ / 10  + Basic variables are on the left-hand side of the equality sign,
              followed by a constant,
              followed by all of the non-basic variables
_____ /  8  + Test files [that you made]
_____ /  2  Completed rubric

_____ / 65  Total


_____ Approximate number of hours spent

I, (REPLACE WITH YOUR FULL NAME), affirm that the code that I submitted is my own work and that I did not receive help that was not authorized by the instructor.

Copy and paste this rubric into a rubric-project4.txt file (not a .docx, .doc nor .rtf file). Think of this as a checklist to ensure that you receive the maximum points possible. For each grade item, fill in your estimate for the grade you deserve. Additionally, include your estimate of how many hours your spent. Lastly, replace, "(REPLACE WITH YOUR FULL NAME)" with your full name to indicate that what you are submitting is entirely your own work.

Submission

To facilitate grading, structure your program so that the following commands will compile and execute it:

javac *.java
java LPConverter

javac *.java -d .
java <package_name>.LPConverter

where <package_name> is replaced by the package name used. If this doesn't work, then please comment out the package statement.
Also, only include one .java file with a main() function. Before submitting this assignment, make sure that there are no compilation errors. If there are errors, fix them before submitting. You may need to edit and compile your program multiple times before it compiles successfully. Verify that the output is correct (meaning that every single character matches the output). Once you are able to successfully run the program with the correct output, you are ready to submit the program. Submit your source code, test files and rubric to the appropriate Assignment tab/folder in CougarVIEW.

Notes

Part of the grading process is automated by using diff. You can verify that your output matches the above output directly with the following commands:
```
javac *.java
# echo "" | ... is the same as typing RETURN	  
echo "" | java Converter    &>  project4Output.txt
diff  project4-answerKeyA.txt  project4Output.txt
```
If the two files match exactly (which is what you want) then there should be NO output from diff. If diff shows one or more differences, fix them and run it again. To get side-by-side output (with the answer key on the left and your output on the right), replace the last line with:
```
diff  --side-by-side  project4-answerKeyA.txt  project4Output.txt
```
For details about interpreting the output of diff, see the Using diff section on the Misc. webpage.

Academic Integrity

Academic integrity means that you submit for a grade work that is entirely yours. The following figure indicates where you can get help:

Algorithms Analysis and Design

CPSC 6109