4
$\begingroup$

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"?

$\endgroup$

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Just to be clear regarding the last observation, imposing finite bounding boxes on non-boxed variables enlarges the feasible set of the dual problem. After solving it, you may thus find dual infeasibilities with respect to the original problem which has to be resolved. This can be done either by switching to primal simplex (phase 2), or alternatively, via dual simplex (phase 1) followed by another round of dual simplex (phase 2) to reoptimize. $\endgroup$ Sep 23 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.