tag:blogger.com,1999:blog-593563533834706486.post2813140888417375799..comments2024-03-28T10:35:10.453-04:00Comments on Yet Another Math Programming Consultant: Difficult nodeErwin Kalvelagenhttp://www.blogger.com/profile/09496091402502236997noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-593563533834706486.post-79045398924813429732011-02-12T11:34:41.387-05:002011-02-12T11:34:41.387-05:00Would be a good question to cplex support forum, b...Would be a good question to cplex support forum, but most likely some cplex person will answer here soon, I am sure some of them follow your blog too :-)Bo Jensenhttps://www.blogger.com/profile/10533779186894174073noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-38691406085672235782011-02-12T09:30:40.925-05:002011-02-12T09:30:40.925-05:00Bo could be correct, but it would imply that CPLEX...Bo could be correct, but it would imply that CPLEX was computing LP bounds for different nodes during the node selection process. I think (and I stress "think" here) it switches to a node before solving the LP, in which case if it gets an LP value it doesn't like (or if the node is infeasible) it will prune the node and generate a line in the log.<br /><br />Another curiosity: This appears to be a maximization problem, but both problem node 488 and the subsequent (better behaved?) node 489 are listed with objective values higher than the "Best Node" value. Is a branch incumbent being used? The makeBranch command requires an estimate of the objective value for the new node; I've never looked into what happens if you underestimate the value in a max problem. (The lazy approach, which I always use, is to take the objective value of the parent node as the estimate, which if anything will overestimate in a max problem.) Other than that, my only guess would be that what's in the log is the objective value of the original (unpresolved) problem, whereas what CPLEX uses internally is the objective value of the presolved problem, and we're seeing the effects of massive rounding error or numerical stability problems.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-51151015989113072372011-02-12T03:32:35.711-05:002011-02-12T03:32:35.711-05:00I am also just guessing here, since the output is ...I am also just guessing here, since the output is a bit strange. So Paul could be right too. To me I does not look like cplex restart due to numerical issues, if that where the case you would see them raising markowitz tolerance in LU and other stuff. But as said I could be wrong. <br /><br />The dual norms can be updated by looking at the difference between the basis of the nodes you are switching from and to. One can do some tricks there, you can also see from :<br /><br />Reinitializing dual norms . . .<br />Computed 1 new norms.<br /><br />That it's not recomputed, which would be very time consuming. Switching nodes might need a refactorization, it depends on how you search the tree.<br /><br />Again I stress, I do not know the inside of cplex, so this is just guesses from my side.Bo Jensenhttps://www.blogger.com/profile/10533779186894174073noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-46184894815172523562011-02-11T18:48:41.699-05:002011-02-11T18:48:41.699-05:00Glad there is disagreement here: I am no longer as...Glad there is disagreement here: I am no longer ashamed that I am confused about Cplex's behavior here.Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-54137583569279088002011-02-11T18:41:30.059-05:002011-02-11T18:41:30.059-05:00I think I disagree with Bo here. I took this to m...I think I disagree with Bo here. I took this to mean that it was solving a single node LP (by dual simplex, I assume) and was struggling with numerical instability, forcing it to reinitialize dual norms (is that similar to refactoring a basis?). I think the repeat presolve parameter must also be on (can't recall if what the default for that is, but I think maybe "let CPLEX use it's own judgment").<br /><br />It would be interesting to know whether the numerical emphasis parameter would make a difference, but no guarantee you'd get the same search tree with the new parameter setting.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-21731037389456091762011-02-11T03:34:20.182-05:002011-02-11T03:34:20.182-05:00It looks to me it's solving several LP's a...It looks to me it's solving several LP's at this node, so I am quite sure it's doing more than branching. Also I do not think it's the actual solving of the LP's which is expensive. <br /><br />The message "Reinitializing dual norms" is just that CPLEX is trying to reuse dual norms between nodes in a cleaver way (my guess), otherwise it has to start with unit norms in many cases. So that's perfectly OK and should give you speed-up in many cases.Bo Jensenhttps://www.blogger.com/profile/10533779186894174073noreply@blogger.com