4

From the Integer Programming book by Conforti et al, I've sniped the image below. At the bottom of this image there is the remnants of a tableau, presumably from several iterations of the simplex algorithm. I cannot reproduce their numbers. It may just be that my simplex algorithm skills are poor.

However, I cannot reproduce the numbers using SCIP either. I get numbers that are close, but the signs and order don't quite match. Doing it by hand I cannot get fractional values on every slack since I don't go through that many iterations. Is there something wrong with my approach? What pivot rule are they using, or what elements did they pivot on to arrive those numbers?

Enter image description here

Peter Mortensen
  • 147
  • 7
Brannon
  • 900
  • 2
  • 12
  • 1
    "At the bottom of this image there is the remnants of a tableau" What is the meaning of "tableau" in this sentence? – Stef Dec 21 '22 at 11:20
  • @Stef https://en.wikipedia.org/wiki/Tableau "another term for a table of data" – user3067860 Dec 21 '22 at 17:02
  • @user3067860 That was my first thought, but there is no table in the screenshot provided. – Stef Dec 22 '22 at 08:11
  • @Stef Oh, I see what you mean--in this case, it means that even though the bottom section is equations they are written spaced out and aligned like a table. – user3067860 Dec 22 '22 at 16:48

1 Answers1

7

The dictionary is correct. You can check your work by using Robert Vanderbei's Simple Pivot Tool: enter image description here

The following sequence of pivots yields the same optimal dictionary:

Enter Leave
x3    w3
x2    w2
x1    w5
w2    w4

enter image description here

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • That's a nice tool (unless you put it into decimal mode, where it has terrible accuracy). Can I press you further for a sequence? E.g., when I click bottom right x3 followed by top x1, I get a valid solution that has a (3/4)x8, which isn't anywhere in the sample. Clicking on the 4th x1 instead -- the traditional min-quotient choice -- introduces the 1/6 factor. – Brannon Dec 21 '22 at 17:00
  • Thank you for adding the sequence. Is it using an obvious pivot rule, something I can see in the data? Is there a name/description for that pivot rule? Does it even follow a rule? – Brannon Dec 21 '22 at 17:50
  • The entering variable was chosen by Dantzig's rule (largest reduced price), and the leaving variable was chosen via the ratio test, together with knowledge of the target dictionary when there was a tie. – RobPratt Dec 21 '22 at 18:16