Lagrangian relaxation issue

Problems with modeling
Post Reply
abb.omidi
User
User
Posts: 39
Joined: 6 years ago

Lagrangian relaxation issue

Post by abb.omidi »

LR_(GAP-2)_1.gms
(3.11 KiB) Downloaded 155 times
Dear community team,

I am trying to solve a scheduling problem by using the Lagrangian relaxation method. As I am pretty new in this field have tried to start with a generalized assignment problem to understand how this method can work on the MILP's. Also, I have read https://my.ece.utah.edu/~kalla/phy_des/ ... fisher.pdf and https://www.amazon.com/Fundamentals-Sup ... 0470521309 resources and have used https://www.gams.com/latest/gamslib_ml/ ... apmin.html and http://www.amsterdamoptimization.com/pdf/lagrange.pdf examples.

Let's say, in both of the examples, it has been tried to relax the assignment constraint, but I have tried to relax the resource constraint. (I know that it does have a weaker linear relaxation, but I would like to test and run a different formulation). Please, see the attached file.

When the optimization is started, the problem is solved and the algorithm seems to work fine. Actually, it needs many iterations to be converged at a specific point. At the moment, I have adjusted the converging point at 0.01 and iterations at 100. The dual bound is being raised very slowly, but if you give enough time and more iterations (almost 500), the dual bouns would be very near to the original MIP solution. (~18). I was wondering if:

1) As the resource constraint is in the form `the less than or equal to` (<=) and based on what mentioned in the resources, we will need to relax the constraint in the objective function with a non-positive Lagrangian multiplier, but if we change the sign of the new term to the negative, the problem cannot be solved.

Code: Select all

* We relaxed the resource constraint as RHS-LHS. 
LR.. bound =e= sum((i,j), c(i,j)*x(i,j)) + sum(j, u(j)*[b(j)-sum(i,a(i,j)*x(i,j))]);
2) For the calculation of the norm in the stepsize expression, it seems to use the relaxed form of the constraint for invoking the required violations. Would you say please, is this a general rule or depends on the problem on hand?

Code: Select all

gamma(j) = b(j)-sum(i,a(i,j)*x.l(i,j));
norm = sum(j,sqr(gamma(j)));
stepsize = theta*(upperbound-bound.l)/norm;
3) What does the following expression mean? It, obviously, says that the multipliers should not be negative. I am a bit confused about its means and determining the sign of the multipliers.

Code: Select all

* U's are the Lagrangian multipliers
u(j) = max(0, u(j)+stepsize*gamma(j));
Best regards
Abbas
abb.omidi
User
User
Posts: 39
Joined: 6 years ago

Re: Lagrangian relaxation issue

Post by abb.omidi »

Dear community team,

If you need more details about the question I can elaborate more on this. Actually, I do not expect an exact answer and any useful insight would be appreciated.

Best regards
Abbas
Post Reply