Topic
IC4NOTICE: developerWorks Community will be offline May 29-30, 2015 while we upgrade to the latest version of IBM Connections. For more information, read our upgrade FAQ.
2 replies Latest Post - ‏2013-02-12T14:45:27Z by SystemAdmin
SystemAdmin
SystemAdmin
1883 Posts
ACCEPTED ANSWER

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
    ACCEPTED ANSWER

    Re: Speeding up Column Generation

    ‏2013-02-06T14:15:56Z  in response to SystemAdmin
    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
      ACCEPTED ANSWER

      Re: Speeding up Column Generation

      ‏2013-02-12T14:45:27Z  in response to SystemAdmin
      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