Project #6: Resource Allocation by Linear Programming

In this project, you will solve a resource allocation problem using Linear Programming.

• Formulate a problem as a linear programming problem.
• Represent the problem in various useful forms.
• Implement the simplex algorithm (from the provided pseudo-code).
• Solve the problem using the simplex algorithm and gain further insight into how the algorithm works.

You are the operations director for a processing plant at a large mine. Your job is to devise a program (i.e., plan) for the plant that maximizes profits while operating within the given constraints. The plant produces four major minerals: copper, gold, silver and platinum. Your plan must specify how much copper, silver, gold, and platinum (all in ounces) you will produce, and you will need to report how much profit you will achieve.

In a given week, the mine can produce up to 2,000 tons of ore that must be processed into some combination of the four major minerals. A ton of ore contains 10 ounces of copper, 2 ounces of gold, 3 ounces of silver, and 1 ounce of platinum. To keep things simple, you may only extract one mineral from any batch (of arbitrary size) of ore processed (note that the amounts of ore processed for each type need not be integer valued).

Processing the ore requires power, water, labor and use of processing lines. Producing each of the minerals requires different amounts of processing resources.

One ounce of copper requires exactly:

• 30 kW hours
• 1,000 gallons of water
• 50 hours of labor
• 4 hours of processing time on a processing line

One ounce of gold requires exactly:

• 15 kW hours
• 6,000 gallons of water
• 20 hours of labor
• 6 hours of processing time on a processing line

One ounce of silver requires exactly:

• 19 kW hours
• 4,100 gallons of water
• 21 hours of labor
• 19 hours of processing time on a processing line

One ounce of platinum requires exactly:

• 12 kW hours
• 9,100 gallons of water
• 10 hours of labor
• 30 hours of processing time on a processing line

There is only a limited amount of power, water, labor and processing line time available. In a given week, you may use the following resources (but no more):

• 1,000 kW hours of power
• 1,000,000 gallons of water
• 640 hours of labor
• 432 hours on the processing lines (there are 3 processing lines that can run for 24 hours a day, 6 days a week)
  • Note: The number of processing lines is not particularly important. You can consider the 432 hours as a lump sum to be used as needed.

Finally, each ounce of finished mineral has an associated profit:

• an ounce of copper is worth $10.20
• an ounce of gold is worth $422.30
• an ounce of silver is worth $6.91
• and an ounce of platinum is worth $853.00

After converting an LP problem into the representation we referred to as “standard form up to step #1”, the conversion to matrix-vector form is quite straight-forward. Let $m$ be the number of constraints and $n$ be the number of variables in standard form up to step #1.

Matrix-vector form was introduced in Lecture #27 (slides #38 and #39 in the PowerPoint).

• essential elements: $A$ matrix, $b$ vector, $c$ vector, and $x$ vector
• $A$ is constructed from the coefficients in the less-than-or-equal-to constraints, with the ordering on columns reflecting the variable index order.
  • dimensions: $m \times n$
  • The elements of $A$ are denoted $a_{ij}$, with $i$ indicating the row and $j$ indicating the column of the matrix.
• $b$ is constructed from the constant limits on the less-than-or-equal-to constraints.
  • size: $m$
• $c$ is constructed from the coefficients in the objective function (in variable index order).
  • size: $n$
• $x$ consists of the variables in the problem (in variable index order).
  • size: $n$

For the implementation of the simplex algorithm, we require a padded version of matrix-vector form. The padded matrix-vector form reflects the presence of slack variables and is derived directly from matrix-vector form. The number of our original (now “non-basic”) variables is $n$, and the number of slack (now “basic”) variables is $m$, one for each of $m$ constraints. (Be sure to read the Linear Programming Notes linked from the course schedule in order to understand the terms “basic” and “non-basic” variables.)

Padded matrix-vector form was introduced in Lecture #29 (slide #21 in the PowerPoint).

• essential elements: set $N$, set $B$, scalar $v$, $A^\prime$ matrix, $b^\prime$ vector, $c^\prime$ vector, and $x^\prime$ vector
• $N$ is the set of indices of the non-basic variables ($x_1$ and $x_2$ in the example in the slides)
  • size: $n$
• $B$ is the set of indices of the basic variables ($x_3$ and $x_4$ in the example in the slides)
  • not to be confused with vector $b$
  • size: $m$
• $v$ is the constant term of the objective function.
• $A^\prime$ is the padded version of $A$
  • Matrix $A$ resides in the lower left corner of the larger padded matrix $A^\prime$ to indicate that the slack variables depend on the original variables
  • size: $(n+m) \times (n+m)$; there are $n+m$ rows in the padded version of $A$ to leave space to keep track of the coefficients for any of the $n+m$ variables that may play the role of a basic variable.
• $b^\prime$ is the padded version of $b$
  • The location of $b$ in $b^\prime$ indicates that the slack variables are limited by the limits on their corresponding constraints; thus, the $b$ vector is padded on the front.
  • size: $n + m$
• $c^\prime$ is the padded version of $c$
  • The additional 0s in $c^\prime$ indicate that the slack variables have 0 coefficients in the objective function; thus, the $c$ vector is padded on the back.
  • size: $n + m$
• $x^\prime$ is the extended list of variables, now including the slack variables
  • size: $n + m$

For part #1 of this project, use the “prime” notation ($A^\prime, b^\prime$, etc.). For part #2, when working with the Simplex and Pivot pseudo-code, drop the primes. e.g., $A^\prime$ is simply referred to as $A$ in the pseudo-code. Note also that the pseudo-code does not use the $x^\prime$ vector.

When a formerly non-basic variable is pivoted to become a basic variable, then the new basic variable becomes the left side of a new constraint equation. In the algorithm, you need a simple way to find the new constraint equation for the new basic variable (with index $i$) at row $i$ of matrix A. Since any of the $n + m$ variables can be a basic variable during the run of the algorithm, you need $n + m$ rows. You also need $n + m$ columns, because the coefficient for variable $x_j$ (which might be 0 or might not be) in the constraint for variable $x_i$ needs a place to stay which is also easy to find later. A pivot operation allows any variable to end up in the constraints for any other variable so you need all $n + m$ columns in addition to all $n + m$ rows.

Also, to verify that your implementation is working properly, consider trying it out on the homework problem #7.1. If you are able to reproduce the result you computed (and which is provided in the homework key), then you can be confident in your implementation and your final answer on the given problem. You could also try your implementation on other examples worked in class for which you have the correct answers.

Another method of verification on the problem posed here is to try an online solver to replicate your result. If you fail to replicate, then you probably have a bug.

You are developing as a problem solver. You are also learning to solve a problem before you start writing code. In this project, we require you to step up to a whiteboard after reading these instructions before writing any code. Use the whiteboard to walk through the solution with a friend. Your friend could be another CS major, a CS 312 classmate, or another technical person with an eye for detail.

Make sure you walk through a step or two of the Simplex algorithm using the padded matrix-vector representation. Understand how the pseudo-code is doing the algebra we did by hand. Think out loud and with sketches. By the time you are done with the whiteboard experience, be sure that you understand the Simplex algorithm, including the pseudo-code. If you do not understand the pseudo-code, then you have not adequately finished the whiteboard experience. Doing so will save you a lot of time translating the algorithm into code.

In short, make sure you understand what you are going to do before you write a stitch of code. As you will note below, including a photo of your “whiteboard experience” is a required element of your project report.

Have a “whiteboard experience” and document it with a photograph of you next to the whiteboard sketches, etc.

Prepare a whiteboard experience report as a .pdf file. It should consist of one page with the following elements:

• your name
• your section number
• [5 points] your photo
• [5 points] a caption (2-3 sentences) explaining why you are ready to proceed to write code
• the names of the people in your audience

Submit the whiteboard experience report online by the whiteboard experience deadline for this project.

Your answer will have six sections:

1. Define your variables.
   • Be absolutely clear about the units (ounces, tons, etc.) associated with your variables.
   • In LP, you identify each independent quantity of interest and define a variable for each such quantity.
   • Hint: in the problem for this project, there are four independent quantities of interest, namely the amount of each substance to be extracted.
   • The objective function is also a quantity of interest, but it is a dependent quantity (i.e., not independent), since it is always computed directly from the variables.
   • The left-hand sides of each constraint are also quantities of interest, but they are dependent quantities, since they are always computed directly (as linear combinations) from the variables.
2. Formulate this resource allocation problem as a linear program directly from the description above.
3. Represent the problem in “standard form step #1”. (If the original algebraic formulation is already in this form, you can simply say so.)
4. Represent the problem in matrix-vector form.
5. Represent the problem in padded matrix-vector form.
6. Represent the problem in “standard form step #2” (i.e., slack form).

Have a “whiteboard experience” as directed above. Again, by the time you are done with the whiteboard experience, be sure that you understand the Simplex algorithm, including the pseudo-code. If you do not understand the pseudo-code, then you have not adequately finished the whiteboard experience. Submit it online by the deadline for the whiteboard experience.

• Write a simplex solver based on the pseudo-code provided in the '''Linear Programming Notes'''. Your code should implement the general algorithm, but you can hard-code this linear programming problem in global or class variables. Thus, you need not worry about file I/O to import the problem, for example.
  • Document your algorithm with legible comments in important places in the code that make it obvious to the reader what your solution is doing. This documentation also provides evidence of your comprehension. With the aid of adequate documentation, the correctness of your approach should be easy for the reader (e.g., TA) to verify. If the TA cannot easily determine the code's correctness, then fewer points will be awarded.

Solve the problem algebraically by hand.

Write a type-written report containing the following distinct sections as a single PDF document, and submit it by following the submission directions in the course syllabus. For Winter 2015: Submit online in PDF format as Homework #21 through Learning Suite.

• Place your name and section number at the top of the first page.
• State the definition of your variables. Be absolutely clear about the units (ounces, tons, etc.) associated with your variables.
• The formulation of the problem as a linear program (in step #1 toward standard form)
• The problem in matrix-vector form.
• The problem in padded matrix-vector form.
• The problem in standard form after step #2

Write a type-written report containing the following distinct sections as a single PDF document, and submit it by following the submission directions in the course syllabus. Note that the project report simply includes part 2, since part 1 was submitted earlier.

1. Place your name and section number at the top of the first page.
2. Also include an estimate of the amount of time you spent on this project at the top of the first page.
3. [50 points] Your C# source code.
   • Document your algorithm with legible comments in important places in the code that make it obvious to the reader what your solution is doing. This documentation also provides evidence of your comprehension. With the aid of adequate documentation, the correctness of your approach should be easy for the reader (e.g., TA) to verify. If the TA cannot easily determine the code's correctness, then fewer points will be awarded.
4. Your answer:
   • [25 points] how much copper, silver, gold, and platinum (all in ounces) you will produce
   • [25 points] the optimal value of the objective function (profit)