• This project is worth 25% of your final grade.
• Due: 2018-04-14 17:30

Overview

In this project you will develop a simplex based solver for Linear Programs, possibly with extensions to solve integer programs. The project is divided into parts, with each part having it's own defined input and output format. Please stick to closely to these specifications, as this will make testing easier for both of us.

Implementation environment

You may use C++, Java, Python, or Racket to implement your project. Make sure you build and test your project in one of the Faculty Linux Labs. Include some way to build and run your code from the command line without using any IDE.

Part 1 Pivoting.

Write code that given a simplex tableau and indices of variables to leave and enter the basis, performs the corresponding pivot.

Input format

Input is whitespace delimited numbers. Your code should be able to cope with integer and decimal input.

• u is the entering column, v is the leaving column.

• m is the number of rows, n is the number of columns of the A matrix in equational form.

• B[1] to B[m] are the indices of the basic columns.

• N[1] to N[n-m] are the indices of the nonbasic columns, in the order present in the file.

• p is constant column of the tableau

• q is the coefficient matrix of the tableau

• z0 is the current value of the objective function

• r is the coefficent vector of the objective row

u	v
m	n
B[1]	B[2]	...	B[m]
N[1]	N[2]	...			N[n-m]
p[1]	q[1,1]	...	...	...	q[1,n-m]
		...	...	...
p[m]	q[m,1]				q[m,n-m]
z0	r[1]	...	...	...	r[n-m]

Output format

Same as input format, without the first line specifying leaving and entering variables.

Part 2 Ratio Testing.

Write a function or method that given a simplex tableau, chooses entering and leaving variables, or reports the tableau as optimal or unbounded.

Input format

Same as input format for question 1, without the first line specifying leaving and entering columns

Output format

Same as input format for question 1, unless the tableau is optimal or unbounded. In this case print the single word "OPTIMAL" or "UNBOUNDED" on a line by itself.

Part 3 Basic Solver.

Write a main loop that integrates your code from the first two questions and solves a linear program. In this part your code may assume that the initial tableau is feasible.

Input format

Same as input format for question 1, without the first line specifying leaving and entering variables.

Output format

Same as input format (although typically not the same tableau!).

Part 4 Finding a feasible basis

Using the basic solver of part 3, construct an auxilary problem find an initial feasible basis for an arbitrary LP in equational form.

Input and Output Format

Same as part 3.

Part 5 Resolve with additional constraint (Bonus)

Given an optimal basis, and one additional constraint

Input Format

Same as part 3, with one additional line

b[m+1]	a[m+1,1]	̣…			a[m+1,n+1]

representing the equation ∑ᵢa[m+1][i] x[i] = b[m+1] and the inequality x[n+1]≥ 0

Output Format

Same as part 3.

(Bonus) Part 6 0/1 LP solver

Use the parts developed above to write a solver for integer programs of the form

max cᵀx
Ax ≤ b
x ∈ {0,1}

Your solver should use branch and bound and/or cutting planes.

Input format

m	n
b[1]	a[1,1]	...	...	...	a[1,n]
		...	...	...
b[m]	a[m,1]				a[m,n]
0	c[1]	...	...	...	c[n]

Output format

A single line containing a space delimited lists of integers

z	x[1]		...		x[n]

Notes

Each program should take input from standard input and write to standard output. Note that numerical problems can be very difficult to debug. In C and C++ you can use gmp to avoid this; Java, Python, and Racket also have built in large number support. Make sure you test your answer to each question adequately. Some tests are available to help you get started.

Hand In

Hand in your source code, test data, and any build system scripts as a zip file or gzipped tarball. Make sure that you test several different sizes of input, and make sure you describe what case your test file is testing. Note that the input and output formats for parts 1 to 5 are set up to help you test by using the output of one program as the input to another.