Topic
  • 3 replies
  • Latest Post - ‏2013-01-22T00:21:52Z by alvarolorca
alvarolorca
alvarolorca
21 Posts

Pinned topic Lazy constraint callbacks and Benders Decomposition with multiple subprblms

‏2013-01-18T22:25:38Z |
I have been trying to adapt the example file bendersatsp.py to solve a problem using Benders Decomposition with several subproblems. When registering callbacks I was trying to use:

lazyBendersBeta = [[]]*len(data.Generator)
for i in range(len(data.Generator)):
lazyBendersBeta[i] = [[]]*len(data.TimePeriod)
for t in range(len(data.TimePeriod)):
lazyBendersBeta[i][t] = cpx.register_callback(BendersLazyConsCallbackBeta)
lazyBendersBeta[i][t].i = i; lazyBendersBeta[i][t].t = t;
lazyBendersBeta[i][t].x = x; lazyBendersBeta[i][t].w = w; lazyBendersBeta[i][t].W = W; lazyBendersBeta[i][t].z = z;
lazyBendersBeta[i][t].workerLP = workerLP
lazyBendersBeta[i][t].data = data

Yet, I realized that the only callback that was actually registered was the last one, and I realized this is how it works, only one lazy constraint callback can be registered. So my question is, how do I apply callbacks when I have multiple subproblems?

I understand I could have one callback that successively searchs for cuts and adds all the ones that it finds (from solving all subproblems), but what if I want to add each cut immediately after it is found? (That is, what if I want to iteratively look at all subproblems, without collecting cuts before sending them to the master,but sending them one by one as they are found and each time one is found update the current master solution incorporating it?)

Thanks in advance,

Alvaro
Updated on 2013-01-22T00:21:52Z at 2013-01-22T00:21:52Z by alvarolorca
  • alvarolorca
    alvarolorca
    21 Posts

    Re: Lazy constraint callbacks and Benders Decomposition with multiple subprblms

    ‏2013-01-19T03:05:52Z  
    I found out how to do it, but please let me know if it is the "correct way". I register one lazy constraint, and within its class definition I cycle through different cut generation functions, in the following way:

    # Beta
    for i in range(len(data.Generator)):
    for t in range(len(data.TimePeriod)):
    if workerLP.BetaSeparate(i,t,solx,solw,solW,solz,x,w,W,z):
    self.add(constraint = workerLP.cutLhs, sense = "G", rhs = workerLP.cutRhs)
    return

    The "return" makes it add the cuts found immediately, to re-obtain the master decision variables and only after that look for other cuts.

    Alvaro
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Lazy constraint callbacks and Benders Decomposition with multiple subprblms

    ‏2013-01-21T07:35:04Z  
    I found out how to do it, but please let me know if it is the "correct way". I register one lazy constraint, and within its class definition I cycle through different cut generation functions, in the following way:

    # Beta
    for i in range(len(data.Generator)):
    for t in range(len(data.TimePeriod)):
    if workerLP.BetaSeparate(i,t,solx,solw,solW,solz,x,w,W,z):
    self.add(constraint = workerLP.cutLhs, sense = "G", rhs = workerLP.cutRhs)
    return

    The "return" makes it add the cuts found immediately, to re-obtain the master decision variables and only after that look for other cuts.

    Alvaro
    Yes, that is the correct way to do it.
    I think you may also want to run computational experiments without that "return" statement. Depending on your problem instance it may be beneficial to separate multiple cuts before returning to the master.
  • alvarolorca
    alvarolorca
    21 Posts

    Re: Lazy constraint callbacks and Benders Decomposition with multiple subprblms

    ‏2013-01-22T00:21:52Z  
    Yes, that is the correct way to do it.
    I think you may also want to run computational experiments without that "return" statement. Depending on your problem instance it may be beneficial to separate multiple cuts before returning to the master.
    Sounds great, thank you Daniel.