_generate_auxiliary_problem(A, b, x0, tol)
Conceptually, this is done by stacking an identity matrix on the right of the original constraint matrix, adding artificial variables to correspond with each of these new columns, and generating a cost vector that is all zeros except for ones corresponding with each of the new variables.
A initial basic feasible solution is trivial: all variables are zero except for the artificial variables, which are set equal to the corresponding element of the right hand side :None:None:`b`.
Runnning the simplex method on this auxiliary problem drives all of the artificial variables - and thus the cost - to zero if the original problem is feasible. The original problem is declared infeasible otherwise.
Much of the complexity below is to improve efficiency by using singleton columns in the original problem where possible, thus generating artificial variables only as necessary, and using an initial 'guess' basic feasible solution.
Modifies original problem to create an auxiliary problem with a trivial initial basic feasible solution and an objective that minimizes infeasibility in the original problem.
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them