0
$\begingroup$

The LinearProgramming function solves a problem using the simplex method (by default). That means it internally selects a set of variables as basic (and the rest as nonbasic) to return the optimal solution (that is, it finds a basic feasible optimal solution). How do I retrieve this set? Please notice that this is not as simple as identifying nonzero variables in the solution, because there are so-called degenerate cases where some basic variables are zero. Also, (if it is not possible to directly retrieve the internally determined basis of LinearProgramming) please give a polynomial method. The immediately obvious 'trial-and-error' method is exponential.

PS: I saw another question on this site (Linear programming pivot), but that one focuses on how to calculate the values of the variables given a set of variables as basis. This is the inverse problem.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Mauri, could you expand on what problem you are trying to solve more generally? Also, perhaps you could give a solvable small system and the related code for people to play with. It is in your best interest to make it as easy as possible for people to get involved in your question: a minimal working example with running code is perhaps the best way. $\endgroup$
    – MarcoB
    Commented Apr 24, 2018 at 13:51
  • $\begingroup$ I'm using linear programming to find the sequential equilibria of a zero-sum two-player game using the method described in this paper. It involves solving P_epsilon to find the corresponding solution to P_delta by choosing the same set of basic variables. $\endgroup$
    – Mauri Ericson Sombowadile
    Commented Apr 24, 2018 at 14:57
  • $\begingroup$ "We simply run (...) LP solver on the program P_epsilon (...) The algorithm outputs (...) a partition of the variables into basic and non-basic ones, which enables us to find a symbolic description of the corresponding solution to P_delta as a polynomial in delta (...) and finally find the sequential equilibrium by setting delta = 0 in these symbolic expressions." $\endgroup$
    – Mauri Ericson Sombowadile
    Commented Apr 24, 2018 at 15:04
  • $\begingroup$ Also, see my essentially equivalent question (but probably elaborated more clearly). $\endgroup$
    – Mauri Ericson Sombowadile
    Commented Apr 24, 2018 at 15:08

1 Answer 1

Reset to default
3
$\begingroup$

It looks like you were lucky. I guess that the function Optimization`LinearProgramming`LinearProgrammingSimplex is the backend used in the simplex method and it is not a KernelFunction. So we can make the code visible with PrintDefinitions from the "GeneralUtilities"` package like this:

Needs["GeneralUtilities`"]
PrintDefinitions[Optimization`LinearProgramming`LinearProgrammingSimplex]

Follow the hyperlinks to the function Optimization`LPSimplexDump`linearprogsimplex and the calls it makes. The function where the magic happens seems to be Optimization`LPSimplexDump`SimplexAlgorithm. There is a variable called basics and I guess that it might contain the indices of the current basis vectors.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sorry, but I'm new to Mathematica... So does this mean that I can modify the LinearProgramming function so that it returns the basics variable? $\endgroup$
    – Mauri Ericson Sombowadile
    Commented Apr 24, 2018 at 15:24
  • $\begingroup$ Yes, it should be possible to copy the existing code and to manipulate it in order to write a customized version, e.g., one that also returns basics. But I have to admit that this might be a bit too hard for a beginner. Moreover, I am not sure if the methods above are really called by LinearProgramming. So quite a bit more reverse engineering would is necessary... $\endgroup$
    – Henrik Schumacher
    Commented Apr 24, 2018 at 15:37

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.