[SCIP] Some insights about the Lagrangian relaxation

[Abbas Omidi]

Dear support team,

I hope you all be fine.
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)}.

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:

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?

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.
==================================================
* The output of the algorithm by dualizing the second constaint:
         dual_object    theta         norm                       step
          gap
iter1     337.000      2.000       1733184.000      -3.69263E-4
 0.470
iter2    -303.000      2.000       1733184.000       3.692626E-4       0.470
iter3     337.000      1.000       1733184.000      -1.84631E-4
 0.235
iter4      17.000       1.000       1733184.000        2.62377E-19
4.44089E-16
===================================================
Would you say please, are the above solutions correct?

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?

Best regards
Abbas
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20220213/f8e09710/attachment.html>