Re:GNU Linear Programming Kit
by analognoise on Sunday June 30, 2019 @01:38PM
(#20319377)
Would this be useful in solving the kinds of constraints found in ECAD layout?
[ Parent
| on HN ]
Re:GNU Linear Programming Kit
by 6thaccount2 on Sunday June 30, 2019 @01:54PM
(#20319456)
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.
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.
Re:GNU Linear Programming Kit
by 6thaccount2 on Sunday June 30, 2019 @04:56PM
(#20320463)
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.
Re:GNU Linear Programming Kit
by 6thaccount2 on Sunday June 30, 2019 @03:18PM
(#20319912)
Yea...if you're an OR/Applied Math guru, there is some magical stuff you can do.