tag:blogger.com,1999:blog-5246987755651065286.post8814181069037329644..comments2024-02-22T16:15:42.388-08:00Comments on cbloom rants: 10-20-10 - Discrete Math is the Bane of Computer Sciencecbloomhttp://www.blogger.com/profile/10714564834899413045noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-5246987755651065286.post-53707122128433920532010-10-24T09:07:05.870-07:002010-10-24T09:07:05.870-07:00Yeah .. I need to do some more reading.
BTW integ...Yeah .. I need to do some more reading.<br /><br />BTW integer linear feasability does come up in one important problem for us - rasterization. If you have a polygon and ask if any integer pixel centers fall inside it.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-69677813180269462902010-10-23T07:32:34.893-07:002010-10-23T07:32:34.893-07:00"I guess these types of problems are "in..."I guess these types of problems are "integer programming" (this particular case is integer linear programming since my example is linear, but sometimes we have to do it on nonlinear problems)"<br />It's a linear system but you didn't give your target function. ILP (like LP) only considers linear target functions which aren't very useful in this context. What you probably really want is Integer Least Squares.<br /><br />NP-hard doesn't mean much in this context. Basically all of the general integer optimization problems are, but that's for two reasons: (1) in general, finding even one viable point that satisfies the constraints is NP-hard and (2) there's degenerate configurations that essentially force you to look at all grid points. (1) is a non-issue in our case - our constraints just select and integer cube. (2) is a bit more subtle: the complexity in any kind of exact discrete optimization task starts to explode once your problem gets close to singular - e.g. consider a 3-dimensional "grid" with the basis vectors very similar to each other. The continuous version of that problem just is ill-conditioned and numerically tricky to solve. The discrete version has the added complication that even a tiny sphere around some grid point will contain a significant fraction of the whole grid, which of course royally screws you.<br /><br />That's the fundamentally hard cases where the complexity comes from. It's also cases we don't care about too much - essentially, if there's a really large number of points within a small neighborhood of your initial solution (presumably obtained from the continuous problem), there's little to gain from solving it to optimality.<br /><br />There's also <a href="http://www.systems.caltech.edu/EE/Faculty/babak/pubs/conferences/01006038.pdf" rel="nofollow">this paper</a>. In short, under conditions that are fairly similar to what you're trying to do, the actual observed runtime of one particular (relatively simple) ILS solver is polynomial.ryghttps://www.blogger.com/profile/03031635656201499907noreply@blogger.com