Finding a dual feasible basis for use with the dual simplex algorithm

Question

I have learnt that the dual simplex method requires reduced costs to be non-negative or else it cannot be used.

I wanted to know what could be done to find a dual feasible basis and came across this related (if not identical) question in the math stackexchange:

https://math.stackexchange.com/questions/3181411/how-to-find-initial-optimaldual-feasible-basis-which-may-not-be-primal-feasibl

I wasn't entirely convinced by the answer, which suggests there is no way forward. I thought there would be a way of creating a dual feasible basis - perhaps adding constraints to create the equivalent of the big M method, or two phase method in the dual space. But I cannot find anything suggesting this. If I ask a solver to use dual simplex to solve the problem posed in that linked question will it just say "no"?

Answer 1

First of all, off course there are dual phase 1 methods that find a dual feasible basis that is not necessarily primal feasible as a first step in a 2-phase dual simplex method. In Maros: "Computational Techniques of the Simplex Method" chapter 10.3 you find such a method described. An alternative is the Pan-Phase-1 described in Koberstein: "The dual simplex method, techniques for a fast and stable implementation" or together with other methods in Pan: "Linear Programming Computation" chapter 13.

Apart from the fact that these methods exist, it's important to consider another fact: In the general simplex method we can have the case that all variables are boxed, i.e. they have a lower and an upper bound. In that case, the trivial slack basis (all rows are basic, all variables are non-basic) is dual feasible because boxed variables can be flipped to the other bound to obtain feasibility based on the computed reduced cost. For these problems, a dual phase 1 is not needed if you are OK with starting from a slack basis. In practice, many instances have all variables boxed or presolve can find bounds for them.

Based on this observation, it is also possible to obtain a dual feasible basis by imposing artificial bounds on variables that don't have them and post-process variables that end up at these bounds at the end. Not sure if this approach is written down anywhere.