4
$\begingroup$

Assuming I had solved the a problem to optimality, I want to remove a constraint.

What happens to primal feasibility? What happens to dual feasibility?

How to solve this new problem efficiently?

My understanding is that the primal feasibility is maintained and I can solve the new problem using primal simplex very fast.

Assumption is that the original is solved to optimal it’s using dual simplex.

Improve this question
$\endgroup$
2
  • $\begingroup$ That is true in exact arithmetic. In finite precision floating point arithmetic, if the "numerics"of the problem are bad, it is possible the the optimal solution gets declared infeasible after removing a constraint; ll the more likely to happen when presolve is turned on (not turned off). Yes, that kind of stuff happens in real world problems ... a lot. $\endgroup$
    – Mark L. Stone
    Commented Dec 16, 2022 at 13:06
  • $\begingroup$ Sorry I am just wondering algebraically. For instance, when we add a constraint to an optimal solution, we can typically reuse the dual basis and the problem can be solved using the dual simplex algorithm. But what can be done when a constraint is removed? And mathematically what happens to dual feasibility? $\endgroup$
    – Morpheus
    Commented Dec 16, 2022 at 13:16

2 Answers 2

Reset to default
4
$\begingroup$

Since the primal problem was feasible before you removed the constraint, it remains feasible. Any feasible solution to the original problem obviously satisfies all the remaining constraints.

Dual feasibility is tied to primal boundedness. Since the original primal problem had an optimal solution, so did the original dual problem (strong duality). If removing one primal constraint makes the primal problem unbounded, the dual becomes infeasible (weak duality). If the primal remains bounded, and thus still has an optimal solution, the dual remains feasible (and has an optimal solution -- strong duality again).

Improve this answer
$\endgroup$
1
$\begingroup$

I assume that you meant by removed constraints is something like redundant constraints, otherwise, by that, the feasibility space of the primal is totally changing.

Based on the duality theorem, the feasibility of the primal is the optimality of the dual, and the optimality of the primal is the feasibility of the dual. Also, the constraints in the primal are already converted to the corresponding dual variables. Now, let's show what's happened to the primal and dual with the redundant constraints.

\begin{array}{l} \text{Maximize} & Z = 3x_1 + 2x_2\\ \text{subject to:}& \\ &x_1 + x_2 \leq 9\\ &3x_1 + x_2 \leq 18\\ &x_1 \leq 7\\ &x_2 \leq 6\\ &x_1,x_2\geq 0, \end{array}

The feasible space of the problem is as follows:

enter image description here

as you can see the last two constraints are redundant and can be omitted without changing the problem's feasible space and the optimal solution.

Now, consider the dual form of the original primal:

\begin{array}{l} \text{Minimize} & W = 9y_1 + 18y_2 + 7y_3 + 6y_4\\ \text{subject to:}& \\ &y_1 + 3y_2 + y_3 \geq 3\\ &y_1 + y_2 + y_4 \geq 2\\ &y_1,y_2,y_3,y_4\geq 0, \end{array}

By omitting the primal last two constraints, one can see the variables $y_3$ and $y_4$ would be removed from the dual without changing the solution space and also optimal value.

enter image description here

Actually, this is a tiny problem and I am really not sure if may it be a general rule or not.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I don’t mean redundant constraints. $\endgroup$
    – Morpheus
    Commented Dec 16, 2022 at 19:29
  • $\begingroup$ @Morpheus, as far as I know, by removing the non-redundant constraints from the primal, its feasible space has totally changed, and actually, it becomes another problem with another dual form. In this case, I really like to know how it can be treated as an original one. $\endgroup$
    – A.Omidi
    Commented Dec 16, 2022 at 19:49

Your Answer

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

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