1
$\begingroup$

Say, we're working with an LP that is primal degenerate (optimal solution is at a vertex but with multiple bases) and not dual degenerate (optimal solution is not at a face).

If we were to solve it with a simplex algorithm, we'd get a basic primal solution vector and a basic dual solution vector.

If we were to solve it with an interior point (barrier) algorithm, we'd get a "near-basic" primal solution vector (by near-basic, I mean very close to a vertex but still in the interior of the feasible region). What would the dual solution vector look like in this case? Will it be a "midface" solution?

My intuition is that it should be a midface solution since the dual of this LP will be dual degenerate, and solving this dual LP with the interior point algorithm will give us a midface solution. Is this a good way to think about it? I tested this by solving a two-variable LP example with CPLEX and it seems to confirm this, but I'm not sure if it will follow in higher dimensions.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I'm not sure what you mean by a "dual solution" for an interior (suboptimal) primal solution. If you mean the marginal affect on the primal solution for changes to the constraints, it would be all zeros (since small changes to any constraint would leave the interior solution feasible, with the same objective value). That said, I don't think this is a meaningful concept.

Improve this answer
$\endgroup$
2
  • $\begingroup$ By dual solution vector, I mean the dual values returned by CPLEX as referenced in the documentation for their barrier algorithm. $\endgroup$
    – Samarth
    Jun 1, 2022 at 16:25
  • $\begingroup$ Okay. The documentation says that it maintains strictly positive values for all dual variables, and the dual constraints are equalities, so the dual solution would be in the relative interior of the face defined by the equality constraints. $\endgroup$
    – prubin ♦
    Jun 1, 2022 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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