# Subgradient procedure for lagrangian relaxation of GAP

I'm trying to solve the general assignment problem by relaxing the capacity constraint and applying the subgradient procedure.

GAP (from here):

Relaxation (same source as above):

I am confused about the stopping condition for the subgradient method. The subgradient $$g_k$$ (step 2) never really approaches 0. I think this is because of the binary constraint on x.

I am calculating the subgradient as: $$g_{i} = \sum_j^na_{ij}x_{ij} - b_i$$

I am still able to calculate the correct result, however the method only terminates when it reaches the maximum number of iterations, but it converges to the correct result before this.

Am I misunderstanding how to calculate the subgradient? Is my problem different because the constraint I relaxed is an inequality constraint?

The behavior you are describing is very common in integer problems, at least in my experience. It seems strange to me to use $$\mathbf{g}_k = 0$$ as the only stopping criterion. Usually there's a combination of number of iterations, total computation time, gap between the bounds, etc.
Unless we obtain a $$u^k$$ for which $$Z_D(u^k)$$ equals the cost of a known feasible solution, there is no way of proving optimality in the subgradient method. To resolve this difficulty, the method is usually terminated upon reaching an arbitrary iteration limit.
• Well, just as an example, in this paper we terminate if (a) $(UB - LB)/LB < \epsilon$, (b) # iterations > $n_\max$, or (c) the constant in the numerator of the step size < $\beta_\min$ -- whichever comes first. We use $\epsilon=0.001$, $n_\max=1200$, and $\beta_\min=10^{-8}$. But if you look at just about any paper on Lagrangian relaxation for facility location, you'll find other (usually similar) examples. – LarrySnyder610 May 25 at 18:05