Topic
  • 2 replies
  • Latest Post - ‏2013-02-12T14:45:27Z by SystemAdmin
SystemAdmin
SystemAdmin
1883 Posts

Pinned topic Speeding up Column Generation

‏2013-02-06T07:04:03Z |
Hi,

I'm working on a column generation implementation in OPL, and would like to speed its performance up.

I have a master model and a number of subproblems (100 or so) that I solve in every iteration. These problems are almost identical from one iteration to the next (but each of the 100 subproblems are different), so my idea is that I should reuse these, by updating the changed values, instead of destroying and recreating the models.

In the master the only thing that changes is the addition of new variables (that I get from my subproblems).

The subproblems change even less, only a few dual values change so the effect is, some changed costs in the subproblems objective.

But how do i do this ? Currently I create and destroy the subproblems as:

subData.DualPiLow = masterOpl.DualPiLow;
subData.DualPiHigh = masterOpl.DualPiHigh;
subData.DualConvexity = masterOpl.DualConvexity;

...

var subOpl = new IloOplModel(subDef, subCplex);
subOpl.addDataSource(masterData);
subOpl.addDataSource(subData);
subOpl.generate();

...

if ( subCplex.solve() ) {
subOpl.postProcess();
}

...

subOpl.end();
Can I update the dual information of subData and call generate() again ? possibly first readding subdata ?

Looking forward for your comments!

Christian
Updated on 2013-02-12T14:45:27Z at 2013-02-12T14:45:27Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    1883 Posts

    Re: Speeding up Column Generation

    ‏2013-02-06T14:15:56Z  
    Hi Christian,

    I believe the answer is on the CPLEX help:
    http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/topic/ilog.odms.ide.help/refjsopl/html/IloObjective.html

    dvar int x in 0..200;
     
    minimize x;
    subject to
    {
    x>=10;
    }
     
    main
    {   
     thisOplModel.generate();
     thisOplModel.getObjective().setCoef(thisOplModel.x,3);  
     cplex.solve();
     writeln(cplex.getObjValue());
     if (cplex.getObjValue()!=30) fail(); 
    }
    
    Updated on 2014-03-26T05:51:02Z at 2014-03-26T05:51:02Z by iron-man
  • SystemAdmin
    SystemAdmin
    1883 Posts

    Re: Speeding up Column Generation

    ‏2013-02-12T14:45:27Z  
    Hi Christian,

    I believe the answer is on the CPLEX help:
    http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/topic/ilog.odms.ide.help/refjsopl/html/IloObjective.html

    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">dvar int x in 0..200; minimize x; subject to { x>=10; } main { thisOplModel.generate(); thisOplModel.getObjective().setCoef(thisOplModel.x,3); cplex.solve(); writeln(cplex.getObjValue()); if (cplex.getObjValue()!=30) fail(); } </pre>
    Hi Stephen,

    Thanks for your excellent answer, it works!
    Except I've used: subCplexArrays[j].setObjCoef( thisOplModel.x,3);
    instead, as my model is MIP and thus unlinear.

    Thanks, Chr
    Though I've run in to some other problems in extension of this, but I'll post seperately