[Numpy-discussion] How can I constrain linear_least_squares to integer solutions?

[Charles R Harris]

On Nov 28, 2007 12:59 AM, Stefan van der Walt <stefan at sun.ac.za> wrote:

> On Tue, Nov 27, 2007 at 11:07:30PM -0700, Charles R Harris wrote:
> > This is not a trivial problem, as you can see by googling mixed integer
> least
> > squares (MILS). Much will depend on the nature of the parameters, the
> number of
> > variables you are using in the fit, and how exact the solution needs to
> be. One
> > approach would be to start by rounding the coefficients that must be
> integer
> > and improve the solution using annealing or genetic algorithms to jig
> the
> > integer coefficients while fitting the remainder in the usual least
> square way,
> > but that wouldn't have the elegance of some of the specific methods used
> for
> > this sort of problem. However, I don't know of a package in scipy that
> > implements those more sophisticated algorithms, perhaps someone else on
> this
> > list who knows more about these things than I can point you in the right
> > direction.
>
> Would this be a good candidate for a genetic algorithm?  I haven't
> used GA before, so I don't know the typical rate of convergence or its
> applicability to optimization problems.
>

It depends. Just to show the sort of problems involved, suppose you have 32
integer variables and are looking for the last bit of optimization. If the
floating point optimum is at (.5, .5, ...., .5) and the error is
symmetrical, then each vertex of the surrounding integer cube is a solution
and there are 2**32 of them. If the error isn't symmetrical, and chances are
that with that many variables it is very far from that, then you have to
search a larger region. That's a lot of points. The more sophisticated
algorithms try to eliminate whole regions of points and keep narrowing
things down, but even so the problem can easily get out of hand. If you just
need a good solution, a genetic algorithm is a good bet to find one without
too much hassle. I had a similar problem in designing a digital min/max FIR
filter where I needed 15 bit integer coefficients for hardware
implementation. There was a narrow high rejection band in the filter and
simply rounding the coefficients left spikes in the response through that
band. With a GA I was able to eliminate the spikes in about 30 minutes of
evolution using a python/Numeric program. In that case the performance of
annealing was quite dependent on choosing the right parameters for cooling
rate, etc., while the GA was quite robust and straight forward. There was no
guarantee the I ended up with the best solution, but what I got was good
enough.

Chuck
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20071128/68dd68ec/attachment.html>