Skip to main content

How to set termination criteria for Master Problem?

Answered

Comments

1 comment

  • David Torres Sanchez
    Gurobi Staff Gurobi Staff

    Hi Ibrahim,

    These should be straightforward.

    1) Is there a way to set dynamic termination criteria for MP, e.g. solve MP optimally once in every 10 iterations?

    For example,

    # formulate Model: mp
    iteration = 0
    while iter_criteria:
    if iteration % 10 == 0:
    mp.Params.MIPGap = 0 # or default of 1e-4
    else:
    mp.Params.MIPGap = 0.1 # for example
    iteration += 1

    However, doing this will result in "inexact" cuts and you should check if you can make a claim about the optimality of the procedure (Zakeri et al. 2000).

     2) About MP size management: I know that I cannot remove any constraints in the callback. Could you provide any recommendations about how to remove some lazy cuts?

        - I tried storing the cuts and adding only when they improve the incumbent solution but the algorithm converges to a wrong optimal solution. 

    Have you tried to just add all lazy constraints? Gurobi will use the ones that help.
    You could also try adding each cut as a new constraint to the master problem iteratively instead of using a callback. This may bring some speedup as Gurobi will be able to apply presolve more effectively.

    To my limited understanding, after every subproblem you should always have a valid cut (optimality or feasibility cut, otherwise you should terminate).

    Cheers, 
    David

    ---

    Zakeri, G., Philpott, A.B. and Ryan, D.M., 2000. Inexact cuts in Benders decomposition. SIAM Journal on Optimization, 10(3), pp.643-657.

    1

Please sign in to leave a comment.