Homework 3, due Feb 24
(really: because of the holiday Monday, I expect this homework to be done on time):

Exercises 2.13 and 2.14 on p.24 of the text.

Exercises 3.5 and 3.6 on p.40 of the text.

Exercises 4.4 and 4.5 on p.48 of the text.

Experiment with 3 more versions of Vanderbei's simplex pivot tool, as follows. These refer to chapters 2, 3 and 4 in the text respectively, which you should of course read carefully.

Phase I/Phase II: Artificial Variable x0

The objective has two rows now: the first one is for Phase II and the second one is the artificial variable objective in the auxiliary problem for Phase I. You must click on the appropriate row of the artificial variable column x0 to make the first pivot, generating a feasible dictionary for the auxiliary problem, eliminating all the purple colors in the left column and generating yellow colors in the second row, highlighting the possible entering variables for the auxiliary problem. If the original problem is infeasible, you should be able to reduce x0 to zero and make the yellow colors all disappear, and then continue with Phase II as usual.

Using the Lexicographic Rule to handle Degeneracy

Here e1,e2,e3,e4 are the epsilons explained in Chapter 3. In order to figure out which variables leave the basis, you need to remember that the epsilons are part of the current basic variable values and that e1 >> e2 >> e3 >> e4.

The Klee-Minty example showing the Simplex Method can take Exponential time

Here b1,b2,b3,b4 are again components of the objective function (text p.44), but this time they are really part of the problem and not perturbations to it. As in the previous case, in order to figure out the leaving variables, you need to remember the ordering; this time b1 << b2 << b3 << b4. The coefficients used are powers of 10 in the book and powers of 2 in the tool.

In all cases, use the default values for rows, cols and seed (which initializes the random number generator), but change the number of problems to 5 instead of 10 (there is only 1 in the Klee-Minty case). First experiment with the tools, listing your own email address so the automatic grading program sends you the results and you can make sure the system is working properly. Remember that nothing will get sent unless you press Submit, and you cannot do that until you have completed all the problems. 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.

When everything is working properly, arrange for the scores to be sent to the grader (yangxi@cims.nyu.edu). However, if, as some students have reported, you cannot get the program to send the grades to you or the grader, don't worry about it. We'll take care of it later.

Added 2/18/98:
Important: it turns out that you cannot use Pine to read the email which is sent by the grading program. You must use Mail or Elm to read it. Sorry about the confusion!

For question 3.5 on p.40, assume that the initial dictionary is not degenerate.

Please 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"