[BCP] Antw: pruning node after integral feasible solution is found ?
Changhyeok Lee
changhyeoklee2014 at u.northwestern.edu
Mon Dec 17 13:04:03 EST 2012
Finally, setting BCP_Granularity as 0.00001 resolved the issue.
Thank you for your help and suggestions.
Best,
Changhyeok
On Monday, December 17, 2012 at 10:29 AM, Changhyeok Lee wrote:
> I tried Valgrind to check any memory corruption, but it didn't give me any memory error.
>
> Actually, I found the cause of this weird behavior: the compiler. I was using Apple LLVM compiler 4.1 which is the default compiler of Xcode. It seems that this compiler has some bugs. I changed to another compiler that Xcode supports - GCC LLVM 4.2. When I use this gcc compiler, there was no such problem of accessing some garbage values from the correct reference variable.
>
> I still get "Couldn't branch!" message, but I'll check the LB/UB of my problem first.
>
> Thank you.
>
> --
> Changhyeok
>
>
>
> On Wednesday, December 12, 2012 at 12:04 PM, Ted Ralphs wrote:
>
> > Have you run your code through valgrind to make sure you don't have a bug that is corrupting the memory? I haven't thought in too much detail about what could be wrong in the way you have everything set up, but weird stuff like this is most often the result of memory corruption.
> >
> > Ted
> >
> > On Wed, Dec 12, 2012 at 11:55 AM, Changhyeok Lee <changhyeoklee2014 at u.northwestern.edu (mailto:changhyeoklee2014 at u.northwestern.edu)> wrote:
> > > By the way, my laptop is Macbook Pro with Intel Core 2 Duo processor (64bit) and the operating system is Mac OS X Lion (10.7.5). I'm using Xcode 4.5.2 for my IDE.
> > >
> > > I'm using BCP 1.3.4 package downloaded from Coin-OR website. I have compiled the BCP package following the pdf document in BAC example. I used additional '-arch -i386' flag for c++ compiler for 32-bit architecture.
> > >
> > > Thank you.
> > >
> > > Changhyeok
> > >
> > >
> > >
> > > On Wednesday, December 12, 2012 at 10:40 AM, Changhyeok Lee wrote:
> > >
> > > > Thank you very much for your suggestion.
> > > >
> > > > I tried to look at the lower bound of my problem, especially, 'lpres.objval()' or 'lp_result.objval()'. But, I came across very puzzling situation that I couldn't understand.
> > > >
> > > > I have 'MyBCP_lp' class that is derived from 'BCP_lp_user'. In this class, I overrode 'display_lp_solution' function to see the result of the most recent LP.
> > > >
> > > > However, there's something wrong with the object that is referred from 'const BCP_lp_result& lpres'. 'lp_result.objval()' is 2.122e-313 and 'lp_result.iternum()' is -1073049619 which is impossible. All the values in 'lp_result.x()' are not the correct solution.
> > > >
> > > > More interestingly, the object seems to be fine when its address is passed on to the original virtual function. I implemented my own 'display_lp_solution' function in the derived class in the following way.
> > > >
> > > > 1) display objective value
> > > > 2) display solution in the exact same way as the default 'display_lp_solution'
> > > > 3) call the default 'display_lp_solution' by passing all the parameters.
> > > >
> > > > Here is my code for your reference.
> > > >
> > > > void MyBCP_lp::display_lp_solution( const BCP_lp_result& lp_result,
> > > > const BCP_vec<BCP_var*>& vars,
> > > > const BCP_vec<BCP_cut*>& cuts,
> > > > const bool final_lp_solution) {
> > > >
> > > > // display objective value
> > > >
> > > > cout << "current obj: " << lp_result.objval() << endl;
> > > >
> > > > // display solution: the same code with the default BCP_lp_user::display_lp_solution
> > > > const double ietol = getLpProblemPointer()->param(BCP_lp_par::IntegerTolerance);
> > > > BCP_vec<int> coll;
> > > > const double * x = lp_result.x();
> > > > select_nonzeros(x, x+vars.size(), ietol, coll);
> > > > const int size = coll.size();
> > > > for (int i = 0; i < size; ++i) {
> > > > const int ind = coll[i];
> > > > vars[ind]->display(x[ind]);
> > > > }
> > > >
> > > >
> > > > // call the default 'display_lp_solution' function
> > > > BCP_lp_user::display_lp_solution(lp_result, vars, cuts, final_lp_solution);
> > > >
> > > >
> > > > }
> > > >
> > > > When I run this code, my 'display_lp_solution' function prints some random numbers for the solution x(), but the default 'display_lp_solution' function displays the correct solution!!!
> > > >
> > > > So, the reference variable in the derived class is referring to wrong address or object and all of the sudden the same reference variable refers to the correct object within the default function, which doesn't make sense to me. Are there any explanation for this kind of behavior?
> > > >
> > > > Thank you very much.
> > > >
> > > > Best,
> > > > Changhyeok
> > > >
> > > >
> > > >
> > > > On Tuesday, December 11, 2012 at 10:08 AM, Ted Ralphs wrote:
> > > >
> > > > > 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 (mailto:andrea.trautsamwieser at boku.ac.at) (mailto: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 (mailto:changhyeoklee at gmail.com) (mailto: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 (mailto:BCP at list.coin-or.org) (mailto:BCP at list.coin-or.org)
> > > > > > http://list.coin-or.org/mailman/listinfo/bcp
> > > > > >
> > > > > > _______________________________________________
> > > > > > BCP mailing list
> > > > > > BCP at list.coin-or.org (mailto:BCP at list.coin-or.org) (mailto:BCP at list.coin-or.org)
> > > > > > http://list.coin-or.org/mailman/listinfo/bcp
> > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > > --
> > > > > Dr. Ted Ralphs
> > > > > Associate Professor, Lehigh University
> > > > > (610) 628-1280 (tel:%28610%29%20628-1280)
> > > > > ted 'at' lehigh 'dot' edu
> > > > > coral.ie.lehigh.edu/~ted (http://coral.ie.lehigh.edu/~ted) (http://coral.ie.lehigh.edu/~ted)
> > > > >
> > > > > _______________________________________________
> > > > > BCP mailing list
> > > > > BCP at list.coin-or.org (mailto:BCP at list.coin-or.org) (mailto: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 (http://coral.ie.lehigh.edu/~ted)
>
More information about the BCP
mailing list