Decision Optimization

Expand all | Collapse all

Lagrangian Relaxation Example in Cplex

  • 1.  Lagrangian Relaxation Example in Cplex

    Posted Wed January 13, 2021 11:05 AM
    Edited by milena kafka Wed January 13, 2021 07:32 PM
    Hello everyone, 

    I am working on the Lagrangian relaxation nowadays.  I coded my problem as it is explained in the transportaion-location problem example found in the library of cplex. However, my lower bound does not improve that much. I initialize the multiplier with 0 as shown in the example. In the first iteration I get 0. And it goes down until -500 for the first ten iterations, then it climbs up and termintates at -50. ( I set the certain scale size(which is very small value like 0.000 Something) as the stopping criteria, the solution is terminated after 80 iterations) Btw, the optimal value of the same instance is 50. Especially, in the latest iterations, the improvement in the lower bound  is quite low , like 0,3; 0;05 between the succesive iterations. Like -49,005;-49, 674, -49,9 , finally it ends at -50, but the optimum value is 50 . Why does it happen ? What should I check? (I tried with different values for lag.multiplier but the behaviour is the same . 
    Thank you so much

    ------------------------------
    milena kafka
    ------------------------------


  • 2.  RE: Lagrangian Relaxation Example in Cplex

    Posted Fri January 15, 2021 02:37 PM
    It's hard to say much without knowing the problem formulation and the code. I would not be surprised if there is an issue with the updating of the multiplier(s), but that is just a guess.

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------



  • 3.  RE: Lagrangian Relaxation Example in Cplex

    Posted Fri January 22, 2021 12:12 PM
    Edited by milena kafka Fri January 22, 2021 12:26 PM
    Thank you so much Prof.Rubin, 

    I realized where the problem comes from after reviewing the code. Thank you so much for your guidance. For now, that problem has been solved but the gap between the lower bound and optimal solution is around (20%) when the stopping criteria is met  and I do not know how I can reduce this gap :(

    Thank you so much

    ------------------------------
    milena kafka
    ------------------------------



  • 4.  RE: Lagrangian Relaxation Example in Cplex

    Posted Fri January 22, 2021 01:36 PM
    Trust me, you are not the only person struggling to close the gap on a MIP problem. It is possible that tweaking some parameters (MIP emphasis, node presolve, cut generation) might help, but finding the right parameter combination is itself an NP-hard problem. One thing you might try is pausing the solver at some point before it hits the stopping criteria, switching MIP emphasis to 3 (improving the bound), and then resuming the solve.

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------