interactive_simplex_method: Add static methods "random_element" to LPDictionary, InteractiveLPProblemStandardForm

[mkoeppe]

random_element is the standard method that Sage parents provide to produce a random element.

As the objects in interactive_simplex_method do not use the parent/element framework, we just make it a static method of the class.

The existing function random_dictionary is kept as an alias.

CC: @yuan-zhou @novoselt

Component: linear programming

Author: Matthias Koeppe

Branch/Commit: a6b7d5c

Reviewer: Yuan Zhou

Issue created by migration from https://trac.sagemath.org/ticket/31307

[mkoeppe]

Branch: u/mkoeppe/interactive_simplex_method__add_static_methods__random_element__to_lpdictionary__interactivelpproblemstandardform

[mkoeppe]

Commit: fff74c5

[mkoeppe]

New commits:

d5325e9	LPDictionary.random_element: Move random_dictionary here, leave alias behind
fff74c5	InteractiveLPProblemStandardForm.random_element: New

[yuan-zhou]

comment:3

patchbot fails?

[mkoeppe]

comment:4

Looks like this branch forgot to actually remove the original code.

[sagetrac-git]

Changed commit from fff74c5 to a07eca1

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

a07eca1

random_dictionary: Actually remove the old copy of this function

[yuan-zhou]

comment:6

I don't quite understand what the argument special_probability means (in both methods).

I thought that in order to meet the claimed probability, one has to scale the value special_probability using the other variables m,n and bound in

if special_probability < random():

[yuan-zhou]

comment:7

Does it make sense to include those optional arguments such as problem_type in the random_element generator?

[mkoeppe]

comment:8

Good idea.

[sagetrac-git]

Changed commit from a07eca1 to b6b39fc

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b6b39fc

InteractiveLPProblemStandardForm.random_element: Pass keywords to constructor

[mkoeppe]

comment:10

Replying to @yuan-zhou:

I don't quite understand what the argument special_probability means (in both methods).

I agree that it's not very clearly explained. The docstrings make the words "is allowed to be" and "potentially" do a lot of work here. As you can see in the code, with this probability it will allow negative lower bounds for the random b; and again (independently), with this probability it will allow positive upper bounds for the random c.

[yuan-zhou]

comment:11

Replying to @mkoeppe:

I agree that it's not very clearly explained. The docstrings make the words "is allowed to be" and "potentially" do a lot of work here. As you can see in the code, with this probability it will allow negative lower bounds for the random b; and again (independently), with this probability it will allow positive upper bounds for the random c.

Yes, I seem to understand the code, and I agree with this simple design of randomness.

The probability p*(1-1/2^m) of getting infeasible dictionary and the probability p+(1-p)/2^n of getting dual feasible dictionary are actually close to p when n,m are large. However, the probability of getting optimal dictionary is quite off. I guess it's the hidden meaning of "potentially" that I didn't understand.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

6e5d96c

InteractiveLPProblemStandardForm.random_element: Raise an error if is_primal=False is passed