tag:blogger.com,1999:blog-593563533834706486.post3909832041697207145..comments2024-03-28T10:35:10.453-04:00Comments on Yet Another Math Programming Consultant: Model is infeasible or unboundedErwin Kalvelagenhttp://www.blogger.com/profile/09496091402502236997noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-593563533834706486.post-43301883614667881702012-05-03T12:19:37.109-04:002012-05-03T12:19:37.109-04:00Quick question:
"all variables in all practic...Quick question:<br />"all variables in all practical models should have finite bounds"<br /><br />Wouldn't this also compromise performance in some way (even if slightly)?<br /><br />I am 100% behind Erwin on this one, a better analysis is valid.Luis Pintohttps://www.blogger.com/profile/07642894986442544408noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-5355200498701547092012-04-23T06:37:26.703-04:002012-04-23T06:37:26.703-04:00Sure, dual infeasiblity only makes sense for the c...Sure, dual infeasiblity only makes sense for the continuous case, I was talking about LP.Bo Jensenhttps://www.blogger.com/profile/10533779186894174073noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-3556920074446983122012-04-23T05:33:22.880-04:002012-04-23T05:33:22.880-04:00Assume you solving a MIP (the case of Erwin). Now ...Assume you solving a MIP (the case of Erwin). Now assume that the initial relaxation is unbounded. What can you concluded then? All you can conclude is that the problem is unbounded or infeasible. You would have to do a phase 1 problem to make a different conclusion. Most users would not like that I think.<br /><br />So in my opinion there is a good reason why MIP codes report as they do. <br /><br />Talking about dual infeasibility only make sense in the continuous case. Please note that dual simplex usually would say dual infeasible and not unbounded because it does know whether the problem feasible or not.Erling D. Andersenhttps://www.blogger.com/profile/07306894197500659436noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-56384649550390796752012-04-20T10:53:55.452-04:002012-04-20T10:53:55.452-04:00I probably should add that, my previous comment no...I probably should add that, my previous comment notwithstanding, I do find the "infeasible or unbounded" message a PITA when helping other people with their models, since I typically have no intuition whether someone else's model is infeasible versus unbounded.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-74520341655151881762012-04-20T10:51:37.545-04:002012-04-20T10:51:37.545-04:00I've thumped the following drum before, but wh...I've thumped the following drum before, but what the heck, I'll do it again: all variables in all practical models should have finite bounds (and by "finite" I mean less than whatever huge value your solver equates with infinity). That way, the primal problem is never unbounded, so "infeasible or unbounded" will translate to "infeasible". If any primal variable hits an arbitrarily created bound, the modeler should look at whether the bound was chosen too tight or whether the model is trying to be unbounded (implying, to me, a defective formulation). <br /><br />Bo raises good points about what happens in presolve (as opposed to when you are staring at the equivalent of a terminal simplex tableau). To narrow down the result, you have to spend additional computational time, and it's not clear the user wants to spend that time. Personally, I would; but someone else might assume "infeasible or unbounded" means an error coding the model, and would be happy to stop there and start proof-reading the code.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-48852608905022140512012-04-20T02:08:51.600-04:002012-04-20T02:08:51.600-04:00@Bo: Well said. Then again, one could make rerunni...@Bo: Well said. Then again, one could make rerunning the modified version the 'standard behavior' and give power users the option to turn it off. Not sure which is better...still thinking which I like better for the Optimization.Framework.Larshttps://www.blogger.com/profile/08306102615208289852noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-54599117122881216462012-04-19T16:34:31.326-04:002012-04-19T16:34:31.326-04:00"Please don’t tell me “dual infeasible” is a ..."Please don’t tell me “dual infeasible” is a good return code."<br /><br />I did not say it was good, but I definitely think it's better. And it's not because developers want the easiest way out. <br /><br />"If you are working on a model you really want to know if the model is infeasible or unbounded" <br /><br />I agree, but in many situations there is no way around rerunning a modified version of the model to be sure. If you did that by default it would be time consuming for users not wanting this feature.Bo Jensenhttps://www.blogger.com/profile/10533779186894174073noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-18939660524604308222012-04-19T13:30:04.049-04:002012-04-19T13:30:04.049-04:00One of the reasons to not using a dual infeasible ...One of the reasons to not using a dual infeasible status is of course legacy, but also that many users don't know about duality and the farkas ray theory it leads to. Just like users want the SOLUTION and not the primal solution :-)Bo Jensenhttps://www.blogger.com/profile/10533779186894174073noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-40069249412124524442012-04-19T13:26:09.313-04:002012-04-19T13:26:09.313-04:00In my opinion it's because the optimizer shoul...In my opinion it's because the optimizer should not return "Unbounded". There should only be primal or dual infeasible return status, which is what we use in our software. The problem arise in situations where you don't know if the primal or dual feasible region is empty or not. For instance in presolve you can prove there exists no dual feasible solution, but to say it's unbounded you will need to make sure the primal feasible region is not empty.Bo Jensenhttps://www.blogger.com/profile/10533779186894174073noreply@blogger.com