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

Improve this question
$\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
    Dec 21, 2022 at 11:20
  • $\begingroup$ @Stef en.wikipedia.org/wiki/Tableau "another term for a table of data" $\endgroup$
    – user3067860
    Dec 21, 2022 at 17:02
  • $\begingroup$ @user3067860 That was my first thought, but there is no table in the screenshot provided. $\endgroup$
    – Stef
    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$
    – user3067860
    Dec 22, 2022 at 16:48

1 Answer 1

Reset to default
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

Improve this answer
$\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
    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
    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
    Dec 21, 2022 at 18:16

Your Answer

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

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