[2022] CSC 445/545 Operations Research: Linear Programming - Programming Project
CSC 445/545 - Programming Project
This assignment will be submitted electronically through BrightSpace (as described in ‘Submission Instructions’ below). All code submissions must be your own work. Sending or receiving code from other students is plagiarism.
1 Overview
This assignment requires implementing an LP solver which reads a text-based representation of a linear program from standard input and outputs the result of solving the LP (including whether the LP turned out to be infeasible or unbounded). Unlike the other assignments in this course, you are permitted to use floating-point computation to solve the LP (so it is not necessary to use exact fractional arithmetic).
Section 2 describes the input format and Section 3 describes the required output format. For this assignment, correctness is critical, and no marks will be given for any code that cannot be rigorously validated on actual inputs (so you should prioritize basic correctness over adding extra functionality).
The project will be marked based on a combination of empirical validation (i.e. running your solver on various test LPs), human inspection of your code (which, in general, will not be performed unless it is clear that your implementation is correct) and evaluation of the accompanying documentation.
You may implement the project in C, C++, Python or Java, and must design your solution to run correctly on the Computer Science login servers at linux.csc.uvic.ca (which requires working with the compiler or interpreter versions installed on that system). You may be allowed to use a different language at the instructor’s discretion (but only if given explicit permission in advance). Note that some aspects of the project might become more difficult depending on the language choice; this is entirely your responsibility.
2 Input Format
The input format is a simple text-based encoding of a maximization LP in standard form, which will be provided to your solver via standard input. An LP of the form will be encoded as follows:
· The first line of the input file will contain the values c1 c2 ... cn separated by whitespace (tabs or spaces)
· Each remaining line will encode one constraint. The line for constraint i will contain ai,1 ai,2 . . . ai,n bi separated by whitespace.
· Blank lines (lines which are empty or contain only whitespace characters) may be present and must be completely ignored.
· The non-negativity constraints (x1,x2,...,xn ≥ 0) do not appear in the input encoding, since they are implied by the use of standard form.
For example, the LP
Notice that the number of variables and constraints is implied by the number of values on each line (and the number of non-empty lines). You may assume that the input format is consistent: If the first line (containing the objective coefficients) contains n values (indicating n optimization variables), each subsequent line (a constraint) will contain n + 1 values. You are not required to write error-handling logic to address the case of a malformed input.
If your program does not use the required input format, or uses an input source other than standard input, it may be impossible to evaluate and will receive a mark of zero.
3 Output Format
This section describes the output format of the solver. The output must be printed to standard output, and the program must generate no other output to standard output besides what is described here. It is permissible for the program to generate other output to standard error (and such output will be ignored during marking).
If your program does not use the required output format, it may be impossible to evaluate and will receive a mark of zero.
For clarity, examples of output in the text below are shown in a box. The expected output is only the text in the box.
If the input LP is infeasible (that is, if the feasible region is the empty set), the output will consist of the single line below.
Output
infeasible
If the input LP is unbounded (that is, if it is possible to increase the objective function to arbitrarily large values on feasible points), the output will consist of the single line below.
Output
unbounded
Otherwise, if the input LP is bounded and feasible, the output will consist of three lines.
· The first line will be the single word “optimal”.
· The second line will contain the optimal objective value.
· The third line will contain an optimal assignment of each optimization variable x1, x2, . . . , xn, separated by whitespace (with no other separators, like commas). The optimal assignment should only include optimization variables, not slack variables. In cases where multiple fea- sible points attain the optimal solution, any feasible point is considered acceptable for this line (you do not have to ensure that your program finds a specific optimal assignment, only that the assignment provided does attain the optimal objective value).
For example, if the optimal objective value is 1.87 at the point (x1, x2, x3) = (6, 10, 1.7), the output will be
Output
optimal
1.87
6 10 1.7
The exact formatting of numerical values is somewhat flexible, although a minimum of seven signif- icant digits should be printed. It is not necessary to zero-pad values to provide sufficient significant digits (so the value ‘1.5’ can be written instead of ‘0001.500’ or ‘1.500000’). You are encouraged to use the equivalent of the C-style “%g” format specifier to output floating point values.
4 Submission Format
We will use automation to validate your submission before human inspection. To ease this process, we expect all submissions to be in a standard format, and we will not mark any submission that does not comply with the standard format.
Your submission must be a .tar.bz2 archive (using BZip2 compression) called lp.tar.bz2 con- taining a directory called lp (all-lowercase).
To create an archive to submit, run the following command (in the parent directory of your lp directory):
$ tar -jcvf lp.tar.bz2 lp/
5 Basic Features
All submissions must implement an LP solver with the following basic requirements.
· If the input LP has no feasible points, the solver will report a result of “infeasible”.
· If the input LP has any feasible points, whether or not the point x = 0 is feasible, the solver will report a result of “unbounded” or “optimal”. This means that your solver should have some mechanism for finding a feasible point in the event that the LP is not initially feasible (e.g. by solving an auxiliary problem).
· If the input LP has any feasible points and is unbounded, the solver will report a result of “unbounded”.
· If the input LP is both bounded and feasible, the solver will report a result of “optimal” and output the optimal objective value, along with a variable assignment that attains the optimal objective value.
· The solver must complete successfully (in a finite number of steps) on any LP. This will be assessed both by empirical evaluation and code inspection, so your code and/or documen- tation should contain a clear explanation of how the solver avoids infinite loops. It is your responsibility to make it clear why your solver will never cycle infinitely.
Additionally, it is expected that the solver will complete in a reasonable amount of time on each LP tested during marking. Normally, five seconds or less is considered reasonable, although for some inputs this time limit may be extended (for all submissions).
