<div dir="ltr">Dear support team,<div><br></div><div>I hope you all be fine. </div><div>I am working on the Lagrangian relaxation algorithm to solve a scheduling problem. And I need some of the insights about the subgradient optimization for updating the multipliers. Let's say, as I would like to understand this algorithm mechanism, I have tried to implement an instance on the generalized assignment problem, as it is frequently studied in the literature. In short, it works very well for all of the instances I have tested. Nowadays, I am struggling to implement this method on the variant of the multi-dimensional bin-packing problem, but first, I want to do it on the standard BPP as, {min y | x = 1, x <= y, ax <= b; x, y in (0,1)}. </div><div><br></div><div>Without changing the SCIP parameters, the original problem can be solved in around 130 secs. After dualizing the assignment constraints (sum(bin,x(item, bin) = 1, forall item) and by using the subgradient method, the problem can be solved in less than 20 secs and stopped in the pre-defined tolerance. For the first step, it is very good and the reported lower bound is around 12. (the optimal solution of the original MIP problem is 17). What I have tried to understand is that:</div><div><br></div><div>1) Is there any way to know which one of the constraints has to be dualized to speed up the convergence of the SB method?</div><div><br></div><div>2) I have worked on dualizing the second constraint. I set the multiplier's initial value on the capacity constraint marginal value in the original problem, but as it corresponds to the upper bound of the constraint, the capacity of each bin, it could not produce a reasonable lower bound.  Also, I set a random number to pre-define the multipliers, but the result is very strange. </div><div>==================================================</div><div>* The output of the algorithm by dualizing the second constaint:</div><div>         dual_object    theta         norm                       step                gap<br>iter1     337.000      2.000       1733184.000      -3.69263E-4         0.470<br>iter2    -303.000      2.000       1733184.000       3.692626E-4       0.470<br>iter3     337.000      1.000       1733184.000      -1.84631E-4         0.235<br>iter4      17.000       1.000       1733184.000        2.62377E-19      4.44089E-16<br></div><div>===================================================</div><div>Would you say please, are the above solutions correct?</div><div><br></div><div>3) As the Lagrangian method in many cases cannot produce a primal (feasible) solution, we will have to check the final solution (related to the maximized LR bound as the original problem is minimization) and try to reproduce a feasible solution based on. Unfortunately, in the case of BPP, the achieved solution by dualizing the first constraint is far quite from the optimal solution. I was wondering if, is there any way to repair the infeasible solution inside the SB algorithm iterations to invoke a feasible solution?</div><div><br></div><div>Best regards</div><div>Abbas</div></div>