scipy.optimize._linprog_rs:_generate_auxiliary_problem

Extended Summary

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 b.

Running 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.