[Dip] Master-only columns

[Matthew Galati]

You do not need to define the full compact model in the pricing problem if you write your own solveRelaxed function. Just the master needs to be defined in the compact space.

Examples of this in the examples dir are TSP, GAP and probably a few others.

I will look into the tickets when I get back from informs.

Sent from my iPhone

On Oct 18, 2011, at 5:17 AM, "Christian Plum" <chrplum at gmail.com<mailto:chrplum at gmail.com>> wrote:

Hi Matthew

Thanks, that works fine, though i run into https://projects.coin-or.org/Dip/ticket/64 on some of my instances, but this is alleviated by SolveMasterAsIP = 0 and I havent experienced 65.

I have another question I hope you can help me with:

In the compact formulation of my problem, theres a non-linear constraints, which at great expense in binary variables can be linearized. In the pricing problem (elementary shortest path with resource constraints), which I'll implement in "DecompApp::solveRelaxed" i can handle this non-linearity efficiently without additional use use binary vars. So my questions: Do I need to describe the "Full" compact model for the setModelRelax(model, m_appParam.ModelNameRelax) subproblem  or can this be a relaxed version ?

Hope that makes sense ;)

Brgds,

Christan



2011/10/7 Matthew Galati <matthew.galati at gmail.com<mailto:matthew.galati at gmail.com>>
Hi Christian,

The best way to handle master-only columns is explicitly. Unfortunately, I never got around to finish coding that up in the framework. It is on my longer-term ToDo List.

Currently, the way it works in DIP is by using dummy blocks for each master-only column. These are constructed relatively efficiently, so it is not as bad as it sounds. Although it does add a convexity constraint for each block - which can bog down the master problem if there are many master-only columns.

The MILPBlock application will create, identify and manage these for you. If you are building your own application, you have to let the framework know which columns are master-only by creating blocks (just like constraint blocks) and then flagging them as master only. I don't think I have a simple example of this written up. But, you can see how to do it in the MILPBlock application. See MILPBlock_DecompApp.cpp createModelMasterOnlys( ).


 for(vit = masterOnlyCols.begin(); vit != masterOnlyCols.end(); vit++){
      i = *vit;

      DecompConstraintSet * model = new DecompConstraintSet();
      model->m_masterOnly      = true;
      model->m_masterOnlyIndex = i;
      model->m_masterOnlyLB    = colLB[i];
      model->m_masterOnlyUB    = colUB[i];
      //0=cont, 1=integer
      model->m_masterOnlyIsInt =
         (integerVars && integerVars[i]) ? true : false;
//...
     setModelRelax(model,
                    "master_only" + UtilIntToStr(i), nBlocks);
     nBlocks++;
//...


Let me know if you have any questions.

Thanks,
Matt



On Fri, Oct 7, 2011 at 5:58 AM, Christian Plum <chrplum at gmail.com<mailto:chrplum at gmail.com>> wrote:
Hi,

Im working on price and cut model containing Master-only Columns, which are not appearing in any block. This is briefly mentioned in DecompAlgo.cpp Ln 134:

   //---
   //--- sanity check that the union of active columns in blocks
   //---   should cover all columns in core - if not, these are 'master-only'
   //---   columns which can be dealt with using either LD or the using the
   //---   ideas of Rob Pratt discussion (9/27/09), or defined explicitly
   //---   by user
   //---

Could this refer to creating a dummy block for these columns ? Or how is this best handled ?

Brgds, Christian



_______________________________________________
Dip mailing list
Dip at list.coin-or.org<mailto:Dip at list.coin-or.org>
http://list.coin-or.org/mailman/listinfo/dip


_______________________________________________
Dip mailing list
Dip at list.coin-or.org<mailto:Dip at list.coin-or.org>
http://list.coin-or.org/mailman/listinfo/dip
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/dip/attachments/20111115/e2a1480c/attachment.html>