Hacker News Reader

Comment by analognoise | Hacker News Reader

Would this be useful in solving the kinds of constraints found in ECAD layout?

Can the problem be formulated in a linear way? When doing optimization you have a function that you are trying to minimize like the cost of dispatching power plants. If there is no exponents or trig functions (and whatever else that could make it non-linear) you can solve the problem while adding constraints.

GLPK can also do mixed-integer linear programming where some variables are integers like (0,1).

If you need to optimize something that is nonlinear, that requires something else I think, but read the doc.

There is nearly no end of triple tricky clever ways to take a particular optimization problem, exploit its special structure, and have linear programming still be the main part of the solution.

Yea...if you're an OR/Applied Math guru, there is some magical stuff you can do.

Bonus if you can use Subspace-BB (Barzilai-Borwein) on what is left after activating your constraints. That stuff is magical. Also because you can throw it at linear systems that are actually FFT-based time/space variant convolutions or similar things where you never, ever want so much as touch the sparse matrix of that linear system.

Y not touch the sparse matrix of that system?

Because that'd be equivalent to computing the convolution explicitly. The whole approach is based on tricking Overlapp-Add to support compactly supported interpolation kernels between representative convolution kernels. Easiest would be bilinear interpolation between between the surrounding representative kernels, which mostly translated to using the bilinear weights before using the fft convolution, and deferring the summation of the interpolation to be fused with the addition done due to overlap-add.

Unlikely. Most interesting problems in ECAD are non-linear.

Reply on news.ycombinator.com