[BCP] Antw: pruning node after integral feasible solution is found ?

[Ted Ralphs]

Just to follow up, if a feasible solution is found by solving the LP
relaxation, then the upper and lower bounds should be equal and the node
should be fathomed. If it is not being fathomed, then my best guess is that
there are some numerical issues arising perhaps due to incompatible
tolerances. If you can either turn up the verbosity level or do some
debugging and find out why the upper and lower bounds are not actually
equal, that would be the first step in uncovering the problem. Feel free to
post any follow-ups here and we'll try to help you track down the problem.

Cheers,

Ted

On Tue, Dec 11, 2012 at 3:09 AM, Andrea Trautsamwieser <
andrea.trautsamwieser at boku.ac.at> wrote:

>  Dear Changhyeok,
>
> do you know the lower bound LB of your problem? Usually, the node is
> fathomed if the LB >= UB. Otherwise, the method
> "select_branching_candidates()" is looking for branching candidates and in
> case no variable is found reports the error you've got.
>
> For short, you can also fathom the node with
>
> BCP_DoNotBranch_Fathomed
>
> in your own "select_branching_candidates()" method.
>
> Hope this helps,
>
> Andrea
>
>
>
> >>> Changhyeok Lee <changhyeoklee at gmail.com> 11.12.2012 01:43 >>>
>
> Hello,
>
> I'm trying to solve an MILP using BCP package. Currently my problem has
> only core variable and constraints (no indexed cuts or variables to add).
>
> I'm using Clp solver and I have implemented the Gomory cuts using
> CglGomory library within "generate_cut_in_lp" and "cut_to_row" function.
>
> For my current test problem, the output log contains the following
> messages.
>
> LP: **** Processing NODE 0 on LEVEL 0 (from TM) ****
>
> ….
>
> LP: **** Processing NODE 1 on LEVEL 1 (dived) ****
>
> ….
>
> LP: **** Processing NODE 3 on LEVEL 2 (dived) ****
>
> In the first iteration of the last NODE 3, the Clp finds an integral
> solution and it prints the following output.
>
> LP: Default test_feasibility() executed.
> LP: Default test_full() executed.
> LP: Default pack_feasible_solution() executed.
> TM: Default unpack_feasible_solution() executed.
> TM: Solution found at 1.793 sec.
> TM 5.885: Sol from proc: 1 val: -3.320268 (prev best: infinity) tree
> size/procd: 5/2 cand list ins/size: 3/4
>
>
>
> Then, it continues the LP process and finally I see the following error
> message.
>
> LP: Default select_branching_candidates() executed.
> BM: Couldn't branch!
>
>
>
> Here is my question. How do we prune the node after I find an integral
> solution?
>
> My understanding is that in the branch and bound process, if we find an
> integral solution, then we just update the best incumbent solution and
> prune the node. However, it seems that my code continues to work on the
> node and even try to branch. Obviously, there's nothing to branch (all
> integral solution) and the BCP package generates the error message.
>
> Am I missing something? What do I need to do to have my BCP code to prune
> the integral node?
>
> Thank you in advance for your help!
>
> ----
> Changhyeok
>
>
>
>
> _______________________________________________
> BCP mailing list
> BCP at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/bcp
>
> _______________________________________________
> BCP mailing list
> BCP at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/bcp
>
>


-- 
Dr. Ted Ralphs
Associate Professor, Lehigh University
(610) 628-1280
ted 'at' lehigh 'dot' edu
coral.ie.lehigh.edu/~ted
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/bcp/attachments/20121211/ae8faece/attachment.html>