# What happens to the dual and primal feasibility when a constraint is removed after finding an optimal solution?

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.

• 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. Commented Dec 16, 2022 at 13:06
• 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? Commented Dec 16, 2022 at 13:16

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

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:

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.

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

• I don’t mean redundant constraints. Commented Dec 16, 2022 at 19:29
• @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. Commented Dec 16, 2022 at 19:49