tag:blogger.com,1999:blog-8781383461061929571.post7270001161604642795..comments2024-03-14T09:08:19.035-04:00Comments on OR in an OB World: Finding a "Core Point"Paul A. Rubinhttp://www.blogger.com/profile/05801891157261357482noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-8781383461061929571.post-4844084985582065982018-01-18T17:31:39.335-05:002018-01-18T17:31:39.335-05:00Fair enough. That particular situation results in ...Fair enough. That particular situation results in an integer hull with no relative interior, so I suspect that a point in the relative interior of the LP hull is the best you're likely to do. I think the real question, though, is whether you're likely to get a valid "core point" with problems "in the wild", rather than with edge cases.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-25452448886748619772018-01-18T16:47:32.783-05:002018-01-18T16:47:32.783-05:00It’s easy to come up with problems whose integer h...It’s easy to come up with problems whose integer hull is a single point, but a very large and rich LP hull.Petterhttps://www.blogger.com/profile/10458441676290777808noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-45002223454030284942018-01-18T16:15:16.562-05:002018-01-18T16:15:16.562-05:00Is there a particular reason you think it is not l...Is there a particular reason you think it is not likely, at least with the starting solution (or maybe an intermediate solution) of an interior point method? The final solution (before cross-over) is likely to be near the boundary.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-84119444565256626992018-01-18T07:04:53.025-05:002018-01-18T07:04:53.025-05:00> but is more likely than not inside the relati...> but is more likely than not inside the relative interior<br /><br />I don’t think that is true at all. Of course, there may be classes of (easy) problem for which it is true.Petterhttps://www.blogger.com/profile/10458441676290777808noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-72232624931309736072018-01-17T20:12:38.974-05:002018-01-17T20:12:38.974-05:00I'd just set the objective function to 0.
Depe...I'd just set the objective function to 0.<br />Depending on the type of IPM it may not provide a feasible solution until the very end.pihttps://www.blogger.com/profile/00954503509976411806noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-51729408742299102832018-01-17T19:07:19.410-05:002018-01-17T19:07:19.410-05:00Interesting idea. I don't normally use interio...Interesting idea. I don't normally use interior-point solvers, and to be honest I don't know off-hand how they get started. You wouldn't really need to _solve_ the LP relaxation with an IP solver: the first feasible point would be in the relative interior (of the LP hull). You definitely would not want to go so far as to invoke crossover, but pretty much any feasible solution short of crossover might be a candidate.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-32280303057271945322018-01-17T19:01:35.139-05:002018-01-17T19:01:35.139-05:00How about solving the LP relaxation with an interi...How about solving the LP relaxation with an interior-point method? I know this can be outside of the integer hull, but is more likely than not inside the relative interior. pihttps://www.blogger.com/profile/00954503509976411806noreply@blogger.com