Homework 4, due Mar 2
(really: because this is simple)

  • Experiment with the one-phase primal-dual method version of Vanderbei's simplex pivot tool.
    This is very clearly explained in the text in Chapter 7. The second row (all -1's) and the second column (all 1's) ARE CONSIDERED to be MULTIPLIED BY MU. Notice the allowable range on mu shown at the bottom of left. To make a valid pivot, the lower bound on mu must be reduced. Note that the terms involving mu in the top left entry in the dictionary (the objective value) are not shown, as they are not needed to make pivot choices and are eventually set to zero. Use the default values for rows, cols and seed, but change the number of problems to 5 instead of 10. Have the program submit your score to the grader (yangxi@cims.nyu.edu) as usual. You may exit and restart at any time. You may want to experiment by setting the number of problems to 1 or 2 first. If you have trouble, send me email or phone me any time.

  • What is the significance of the highlighted yellow box in this tool? Answer this in an email to the grader.

  • What happens in this algorithm if (a) the primal is infeasible, (b) the dual is infeasible, or (c) both are infeasible? Answer with an email to the grader.

    It may help to experiment with this version of the pivot tool which allows you to set your own data. This way you can enter the data for the example on p.106-108, by setting Rows to 3, Cols to 2 and using the Reset button in the tool, and then you can work through the example, following the book. As noted in class, there is a typo on p.107: in the last last line (x5) of the first dictionary, there should be a -x1.

    Sorry that the last class was not very well prepared. The next lecture will be much better: we will show using matrix notation that the primal and dual dictionaries are negative transposes of each other, and this will give us a clean, short proof the strong duality theorem. I was not able to find this in any book, but it turns out there is a nice way to do it.

    The next homework (now posted) will ask you to modify the Matlab program simplx.m to implement some of these simplex variants.

    Remember to subscribe to the class mailing list, by sending email to majordomo@cs.nyu.edu with the message body "subscribe g22_2730_001_sp98@cs.nyu.edu"