# Is the smallest objective value of a feasible solution to a dual problem an upper bound for the optimal solution of my primal problem?

Thereom: (Weak Duality)

For every primal feasible solution $$(x_1,...,x_n)$$ to the primal problem (P) and every dual feasible solution $$(y_1,...,y_n)$$ to the dual problem (D), it holds that:

$$\sum_{j=1}^n c_jx_j \leq \sum_i^m b_iy_i \tag{1}$$

So if I take an arbitrary feasible solution of P and one of D, then (1) holds. So that means, I could check for which feasible dual solution the objective value would be the smallest and thus find an upper bound for the optimal solution for P, right?

## 1 Answer

Yes, every dual feasible solution provides an upper bound on the primal objective value, and the smallest dual objective value provides the best such bound. The strong duality theorem states that equality is attained.