1
$\begingroup$

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

GAP (from here):

enter image description here

Relaxation (same source as above):

enter image description here

Subgradient method (from here):

enter image description 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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your answer. Do you have any references on other stopping criteria that I could apply? $\endgroup$ – beenjaminnn May 25 at 17:27
  • 1
    $\begingroup$ 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. $\endgroup$ – LarrySnyder610 May 25 at 18:05
  • $\begingroup$ By the way, about the "constant in numerator of step size": They don't include this in the paper you linked to, but it's common to. The idea is to reduce the step size if you're not making enough progress. Again, see the paper by Fisher. $\endgroup$ – LarrySnyder610 May 25 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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