CSC 445/545: Fall 2014, Assignment #4

Due: Friday Nov. 28, beginning of class
Late submissions accepted with 10% penalty until Tues. Dec. 2 at 12:30pm.

Instructions for all assignments:

1. Draw boxes for your marks on the top of the first page of your submission. Place a 0 in the corresponding box for any questions you omit. For this assignment:

   Question	1	2	3	4	5	6	7
   Marks	0	0	0	0	0	0	0

2. Questions should be in order.
3. Show your work unless otherwise stated.
4. Please put your name (last name underlined) and full student number on all submissions.

1. [20] Show each step of the revised Simplex method for this problem using the smallest subscript rule to decide the entering variable:

   Maximize
   2 x₁ + 4 x₂ + 8 x₃
   subject to
   0 x₁ + 1 x₂ + 2 x₃ <= 4
   0 x₁ + 1 x₂ - 3 x₃ <= 12
   1 x₁ + 1 x₂ + 1 x₃ <= 10
   x₁, x₂, x₃ >= 0
   At each iteration, show your work to:

   • Solve A_B^T y = c_B for y.
   • Compute [c_N^T - y^T A_N] * x_N to get coefficients of non-basic variables.
   • Solve for entering column d in the current dictionary: d= A_B^-1 a where a is the entering column taken from the initial problem.

   If you have a revised Simplex method question on the final exam, then I will include these instructions so you do not have to memorize the formulas.

2. Consider the following LP problem:
   Maximize 5 x₁ + 4 x₂ + 3 x₃
   subject to

     2  x1  + 3  x2  + 1  x3    <=  5 
     4  x1  + 1  x2  + 2  x3    <=  11 
     3  x1  + 4  x2  + 2  x3    <=  8 
   

   
   x₁, x₂, x₃ >= 0 .

   (a) [5] Show how complementary slackness can be used to prove that (2.5, 0, 0) is not an optimal solution.

   (b) [5] Show how complementary slackness can be used to prove that (2, 0, 1) is an optimal solution.

3. The Petersen graph:

   

   (a) [4] Analogous to what I did for the 120-cell, set up a linear programming problem for an upper bound for the maximum independent set order of a Petersen graph.

   The variables you should use (in this order) are: R, P0, P1, P2, B0, B1, B2, B3. The equations should state that:

   • The number of vertices is 10.
   • The number of pentagons is the total number that the Petersen graph has. Hint: the graph is vertex-symmetric so each vertex is in the same number of pentagons.
   • The number of reds matches up with the numbers you find in the pentagons.
   • The number of reds matches up with the numbers you find as neighbours of the blue vertices.
   
   (b) [4] Solve this using your program. What are the values for R, P0, P1, P2, B0, B1, B2, B3 at the optimal solution?
   (c) [2] Show an independent set of the Petersen graph that realizes the values obtained for your optimal solution (or explain why no such independent set can exist).

4. Consider the integer programming problem:
   Maximize 5 x₁ -2 x ₂
   subject to
   -x ₁ + x₂ <= 2.5
   x ₁ + x₂ <= 5.5
   x ₁ - x₂ <= 1.5
   x ₁, x₂ >= 0
   Solve this by the branch and bound algorithm. To make it easier for the TA to mark this question, please select the non-integer variable with smallest subscript at each step for the branching.
   (a) [10] Draw a flowchart indicating the subproblems you had to solve to find the optimal solution. When you do not have to continue with a subproblem, explain why on the flowchart.
   (b) [5] Hand in your program output for the subproblems you must solve to find the optimal solution.

5. Solve the problem from the previous question using Gomery's cutting plane technique.
   (a) [10] At each step where you computed a cutting plane, explain what you did to get it.
   (b) [5] Hand in the output for the problems you had to solve.

   BIG HINT: If you get something like this with integer coefficients:

   X2= 3.5 + 5 X4 - 1 X5
   
   Then break it up like this:
   
   X2=  3  + 6 X4 + 0 X5
     + 0.5 - 1 X4 - 1 X5
   
   and not like this:
   
   X2=  3  + 5 X4 - 1 X5
     + 0.5 - 0 X4 - 0 X5
   

   since the second approach won't get you anywhere.
6. Draw the feasible region for the initial relaxed problem for the previous two questions. On this picture, indicate with a black pen:
   • [2] The boundaries of the relaxed feasible region with the corners labelled with their x,y-coordinates.
   • [2] The optimal solution to the relaxed problem.
   Indicate with a blue pen:
   • [2] The corners of the feasible region for the integral solutions labelled with their x,y-coordinates.
   • [2] The extra integer constraints the separation algorithm considered.
   Indicate with a red pen:
   • [2] The cutting planes the cutting plane algorithm added.

7. [20] Print the attached transhipment problem worksheet. Solve the transhipment problem showing your work as done in class. Please use coloured pens so that it is easy to see what you have written. When computing the fair prices, start at vertex 1. The initial feasible solution should correspond to the tree with arcs (2,3), (1,3), (3,5) and (3,4). If you have a choice as to which edge enters, use the one with the lexicographically minimum choice of its endpoints.