LR_(GAP-2)_1.gms (3.11 KB)

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/lagrange-relax-tutorial-fisher.pdf and https://www.amazon.com/Fundamentals-Supply-Theory-Lawrence-Snyder/dp/0470521309 resources and have used https://www.gams.com/latest/gamslib_ml/libhtml/gamslib_gapmin.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:

- 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.

```
* 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))]);
```

- 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?

```
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;
```

- 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.

```
* U's are the Lagrangian multipliers
u(j) = max(0, u(j)+stepsize*gamma(j));
```

Best regards

Abbas