[Coin-discuss] two phase algorithm with algo vars in BCP continued

[Laszlo Ladanyi]

Hello Juan Pablo and everyone else,

I try to reply to your comments in a single email.  

First of all, the 2 phase algorithm is tested, but barely... It just
doesn't come up that often. My comments on your questions are below,
but first a general comment. It seems that the multi-phase code
doesn't work properly at the moment. I'm certain that it can be
cleaned up reasonably quickly, it's just that I don't have time to
work on it now. If you are willing to dig into it, I'd be more than
happy to answer your questions, help you along the way and finally
incorporate the fixes into BCP.

Now the specific comments.

========================

> I am trying to use a two phase algorithm ( as described in the BCP manual )
> with BCP ( just B&P, no new cuts ), buy it seems to me that most of BCP
> features used to implement the 2 ph. algo. work only with indexed variables. 
> 

In general, there are lots of code related to indexed variables and
very little related to algo vars. The reason is simple: indexed vars
are well defined, they can be enumerated so all sort of data
structures and management code are written for them. On the other
hand, All BCP knows about algo vars is that they might exist. Thus in
the description of a search tree node algo vars are listed, but
nothing special is done about them. One particular example that you
have noticed as well is that just before the second phase variables
are priced out in the root. However, only index vars are
considered. The reason is that even if a single algo var does not
price out all BCP knows is that algo vars have to be checked
again. Hence in the leaves the same routine will be invoked to test
algo vars. So (unless every var prices out in the root) it doesn't
matter whether algo vars were priced out or not, BCP will invoke the
same routine. It's different for indexed vars, since the list of
remaining vars is propagated down to the leaves.

> Is this true?
> 
> I can try to elaborate on the features and how they seem not to
> apply for algo vars. I have been looking at the source code, but I
> still don't have a general picture of it, so I might be wrong
> 
> If it is true how can you implement a two phase algorithm using algo vars?
> 
> 
> Juan Pablo,
> 
> PS this seems to be true also for some fathoming features, like the 
> posibility of generating vars just before a node is fathomed

===============

>      It seems that problem with the 2 phase algorithm doesn't have anything
> to do with what I wrote on my last email. I just got confused with
> BCP_lp_node::indexed_pricing.get_status()  thinking that it
> only controled pricing status for index variables when it does for both
index
> and algo. vars.
> 

This is a problem with the current code. It is not completely clear
where the current status of a search tree node is stored. It can be
figured out, but it definitely needs to be cleaned up.

>      So lets see if I got the procedure for implementing the 2 phase ( or n
> phase for that mater )algorithm.
> 
>       - I should use BCP_tm_user::init_new_phase to tell BCP what to do with
> fathomable nodes in each phase. For example for a tipical II phases I should
> set BCP_DoNotGenerateColumns_Send for phase 0 and 
> BCP_GenerateColumns for phase 1.

That's right.

>         
>       - I am responsible for not generating columns on a particular phase (
> in the example phase 0 ) because pricing_status in BCP_tm_user::create_root
> should be set to something other than BCP_PriceNothing  for all phases
> 
>         And this works both for algo and index variables.

I *think* this is correct, too.

> 
>         I still have to try using the PriceInRootBeforePhase2 and
> TrimTreeBeforeNewPhase options.
> 
>      If the above is correct then the problem I had with two phases was that
> I got the following 
> 
> message just after starting phase 1:
> 
>         "Unexpected BCP_Msg_LpStatistics message in BCP_tm_process_message"
> 
>         It seems that BCP_tm_notify_about_new_phase(p) sends a
> BCP_Msg_NextPhaseStarts message to the 
> CP_lp which sends back to BCP_tm a BCP_Msg_LpStatistics message which trows 
> an exeption.
> 
>      Did I forget to some parameter or is this just an unexpected behaviour?

This is a bug. The TM should handle this properly.

> 
>         I still have some trouble with fathoming procedures specially when I
> don't have a good bound for a not totally priced LP, but I will look at it
in
> detail before posting.

==============================

> complementing my last email, there is also a problem with the call to
> BCP_tm_wrapup in BCP_tm_tasks_before_new_phase, but it seems to be directlly
> related to BCP_Msg_LpStatistics problem.
> 
> There doesn't seem to be no problem with TrimTreeBeforeNewPhase when using
> algo. vars, but PriceInRootBeforePhase2 is only for index variables
according
> to some warning messages. 
> 
> Is thera a simple way to so pricing of algo vars in the root node after
phase
> 1? It seems to me that you could just add the root node to the list of nodes
> to be processed on the next phase ( plus some bookeeping ) but you would
have
> to modify BCP's code. 

As I explained above, pricing algo vars in the root (while not
impossible) may gain very little, especially if the algorithm the user
has for generating the algo vars cannot take advantage of information
of the kind "no need to consider this sort of variables". Still, I'd
be very interested in trying out things.

Cheers,
--Laci