Subgradient procedure for lagrangian relaxation of GAP

Question

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

Subgradient method (from here):

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?

Answer 1

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.

For a point of reference, in his excellent overview of Lagrangian relaxation for integer programming, Fisher says:

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.

In short, I think you are doing it right.