[Dip] Constraint Branching

[Ted Ralphs]

Hi Christian,

I'm not sure if Matt replied to you off list, but just to follow up.
Matt can correct me if I'm wrong, but I believe what is supported at
the moment for branching is to branch on a set of variables, assigning
arbitrary new upper and lower bounds to each, but you can only do
binary branching. I think the restriction that the branch be binary
would be fairly easy to relax if you need something more general.
Adding full-blown constraint branching would be a bit tougher. At the
moment, Dippy supports what I described above. To implement your own
branching, you Should create a derived DecompAlgo class (probably
derive from one of DecompAlgoXx) and override the chooseBranchSet
method. Hope this helps!

Cheers,

Ted

On Thu, Dec 1, 2011 at 10:12 AM, Christian Plum <chrplum at gmail.com> wrote:
> Thanks, this works as a charm!
>
> I've gotten a step further and i would like to do constraint branching /
> branch on sets of original variables. As I read it DIP per default does
> binary branching on the most fractional original variable, but dippy seems
> to support constraint branching, is it possible to use this functionality in
> DIP, without going through dippy?
>
> Brgds, Christian
>
> 2011/11/15 Matthew Galati <Matthew.Galati at sas.com>
>>
>> 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> 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>
>>>
>>> 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> 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
>>>> http://list.coin-or.org/mailman/listinfo/dip
>>>
>>>
>>
>> _______________________________________________
>> Dip mailing list
>> Dip at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/dip
>
>
>
> _______________________________________________
> Dip mailing list
> Dip at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/dip



-- 
Dr. Ted Ralphs
Associate Professor, Lehigh University
(610) 628-1280
ted 'at' lehigh 'dot' edu
coral.ie.lehigh.edu/~ted