То ли Диофантовы уравнения, то ли что-то на них похожее

[st256]

Пусть есть система уравнений:

$ \left\{ \begin{array}{l} a_{11}x_1+a_{12}x_2+...a_{1N}x_N = y_1\\ a_{21}x_1+a_{22}x_2+...a_{2N}x_N = y_2\\ ................................\\ a_{M1}x_1+a_{M2}x_2+...a_{MN}x_N = y_M\\ \end{array} \right. $

числа $a_{ij}$ - любые.
числа $x_{i}$ - только целые.

Хочу найти такой набор ЦЕЛЫХ $x_{i}$, что сумма квадратов $y_{i}$ была минимальной.

[worm2]

Наверное, тут сумму квадратов $x_i$ нужно минимизировать ?

[st256]

worm2 в сообщении #319598 писал(а):

Наверное, тут сумму квадратов $x_i$ нужно минимизировать ?

Нет, именно сумму квадратов $y_i$. Только я немного неправильно сформулировал

$ \left\{ \begin{array}{l} a_{10}+a_{11}x_1+a_{12}x_2+...+a_{1N}x_N= y_1\\ a_{20}+a_{21}x_1+a_{22}x_1+...+a_{2N}x_N= y_2\\ ......................\\ a_{M0}+a_{M1}x_1+a_{M2}x_1+...+a_{MN}x_N= y_M \end{array} \right. $

а то при $x_i = 0$ все решается само собой.

Естественно $M \leqslant N$

[мат-ламер]

Это задача целочисленного квадратичного программирования (это не значит, что я умею её решать). Может Google что найдёт?