In its general form, an integer programming problem is NP-hard ( see here ). There are some efficient heuristic or approximate algorithm to solve this problem, but none guarantee an exact optimal solution.
In scipy you may implement a grid search over the integer coefficients and use, say, curve_fit
over the real parameters for the given integer coefficients. As for grid search. scipy has brute
function.
For example if y = a * x + b * x^2 + some-noise
where a
has to be integer this may work:
Generate some test data with
a = 5
andb = -1.5
:coef, n = [5, - 1.5], 50 xs = np.linspace(0, 10, n)[:,np.newaxis] xs = np.hstack([xs, xs**2]) noise = 2 * np.random.randn(n) ys = np.dot(xs, coef) + noise
A function which given the integer coefficients fits the real coefficient using
curve_fit
method:def optfloat(intcoef, xs, ys): from scipy.optimize import curve_fit def poly(xs, floatcoef): return np.dot(xs, [intcoef, floatcoef]) popt, pcov = curve_fit(poly, xs, ys) errsqr = np.linalg.norm(poly(xs, popt) - ys) return dict(errsqr=errsqr, floatcoef=popt)
A function which given the integer coefficients, uses the above function to optimize the float coefficient and returns the error:
def errfun(intcoef, *args): xs, ys = args return optfloat(intcoef, xs, ys)['errsqr']
Minimize
errfun
usingscipy.optimize.brute
to find optimal integer coefficient and calloptfloat
with the optimized integer coefficient to find the optimal real coefficient:from scipy.optimize import brute grid = [slice(1, 10, 1)] # grid search over 1, 2, ..., 9 # it is important to specify finish=None in below intcoef = brute(errfun, grid, args=(xs, ys,), finish=None) floatcoef = optfloat(intcoef, xs, ys)['floatcoef'][0]
Using this method I obtain [5.0, -1.50577]
for the optimal coefficients, which is exact for the integer coefficient, and close enough for the real coefficient.