4
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ "At the bottom of this image there is the remnants of a tableau" What is the meaning of "tableau" in this sentence? $\endgroup$
    – Stef
    Commented Dec 21, 2022 at 11:20
  • $\begingroup$ @Stef en.wikipedia.org/wiki/Tableau "another term for a table of data" $\endgroup$ Commented Dec 21, 2022 at 17:02
  • $\begingroup$ @user3067860 That was my first thought, but there is no table in the screenshot provided. $\endgroup$
    – Stef
    Commented Dec 22, 2022 at 8:11
  • $\begingroup$ @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. $\endgroup$ Commented Dec 22, 2022 at 16:48

1 Answer 1

7
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Brannon
    Commented Dec 21, 2022 at 17:00
  • $\begingroup$ 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? $\endgroup$
    – Brannon
    Commented Dec 21, 2022 at 17:50
  • $\begingroup$ 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. $\endgroup$
    – RobPratt
    Commented Dec 21, 2022 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.