Используя python, как я могу оптимизировать систему уравнений и получать решения только целого числа? [Дубликат]

Question

Используя python, как я могу оптимизировать систему уравнений и получать решения только целого числа? [Дубликат]

попробуйте это просто

var arr = [false,1,0,1,2,0,1,3,"a"];
arr.sort(function(a,b){if (a===0){return 1}});
document.body.innerHTML += JSON.stringify(arr);

5

python optimization integer linear-algebra least-squares

задан arshajii 16 December 2012 в 05:01

7 ответов

+1 к seberg, вот примерный пример, чтобы проиллюстрировать, что вы не должны отображать раунд: (Извините, это стиль matlab, но вы легко pythonize)

a =
     3     0
     0     3
     1     1
b = 
    2.71
   11.7
    0.5
x = a\b =
    0.5121
    3.5088
round(x) =
    1
    4
norm(a*round(x)-b) = 4.5193
norm(a*[0;4]-b) = 4.4367
norm(a*[1;3]-b) = 4.4299

1

ответ дан aka.nice 18 August 2018 в 23:46

Когда вы конвертируете в int, десятичная часть элементов усекается, поэтому округляется вниз.

a = np.array([[1,0], [0,1], [-1,1]])
b = np.array([1,1,0])

x = np.linalg.lstsq(a,b)[0]

Результат:

>>> x
array([ 1.,  1.])
>>> x[0]
0.99999999999999967
>>> x[1]
1.0000000000000002
>>> x.astype(int)
array([0, 1])
>>> map(int, x)
[0, 1]
>>> np.array([1.,1.]).astype(int) # works fine here
array([1, 1])

1

ответ дан Akavall 18 August 2018 в 23:46

1

Я понял, что это что-то вроде этого - так можно ли использовать вычисления только в целых числах, чтобы избежать этих неточностей поплавка? – arshajii 16 December 2012 в 05:19
2

Я думаю, что np.round должен это сделать. – Akavall 16 December 2012 в 05:20
3

Извините, но это работает, потому что точное решение для этого примера является целым. Нет причин, по которым округление / усечение даст вам лучшее целочисленное решение. – seberg 16 December 2012 в 13:29

Возможно, я не понимаю вашу проблему, но думаю, вам просто нужна комбинация round, а затем astype(int)?

Например:

a = np.array([[1,0], [0,1], [-1,1]])
b = np.array([1,1,0])

x = np.linalg.lstsq(a,b)[0]
print x.round().astype(int)

1

ответ дан Joe Kington 18 August 2018 в 23:46

1

Спасибо, это также помогает. Так что numpy не имеет функции специально для решения линейных систем только по целым числам? Я планировал использовать метод округления, подобный этому, в крайнем случае, но он не должен иметь особого значения. – arshajii 16 December 2012 в 05:34
2

@ A.R.S .: Вы хотите, чтобы линейная алгебра была решена с использованием целочисленной арифметики или вы хотите, чтобы результат был целым типом данных? Я не думаю, что первое возможно. Для последнего я считаю, что приведенные здесь предложения должны быть достаточными. – tiago 16 December 2012 в 12:15
3

Я согласен с tiango, из вопроса, который я бы сказал, это неверно, потому что округление не гарантирует найти лучшее целочисленное решение (если только оно не является целым), но с переопределенной системой, это кажется маловероятным. У примера, похоже, есть точное решение, хотя я допускаю. – seberg 16 December 2012 в 13:31
4

@ A.R.S. - Нет, насколько я знаю, numpy не имеет никакого способа решить систему уравнений, которая гарантировала бы получение целочисленного решения. Внутренне numpy - это просто вызов подпрограмм из LAPACK и т. Д., Поэтому функции, такие как lstsq, являются, по сути, плавающей точкой. Я думаю, что между ответом NPE, чтобы определить, существует ли решение, и предложение Себерга попробовать нелинейный решатель, вы можете, вероятно, собрать что-то вместе. Округленное или усеченное решение с плавающей точкой может дать хорошее исходное предположение для нелинейного решателя, если ничего другого. – Joe Kington 16 December 2012 в 17:34

Существует метод, называемый block lanczos. Это может быть ваш ответ по конечному полю. Для этой конкретной проблемы есть решатели блоков lanczos.

0

ответ дан Metahominid 18 August 2018 в 23:46

Вы должны использовать специализированные решатели задач целого числа (обратите внимание, что целочисленные проблемы даже не решены). openopt - это пакет, который, например, должен обеспечивать хорошие обертки для целочисленной квадратичной оптимизации, например, вы делаете. Попытка использовать линейную алгебру просто не даст вам правильного решения, которое непосредственно.

Ваша проблема может быть записана как с квадратичной программой , но она является целым числом , поэтому для этого используйте openopt или какой-либо другой модуль. Так как это очень простой, безусловный, возможно, есть и другой подход. Но для начинающих это не простая проблема, поначалу она выглядит, и есть программы в openopt и т. Д., Готовые эффективно решить эту проблему.

6

ответ дан seberg 18 August 2018 в 23:46

Мне нужно было это сделать и в итоге портировал программу на PHP, написанную Кейтом Мэтьюсом, которую вы можете найти на http://www.numbertheory.org/php/php.html , в Python , Сначала я использовал массивы Numpy, но столкнулся с проблемами с целыми переполнениями, поэтому переключился на матрицы Sympy, которые используют произвольные прецизионные численные представления.

Код выпущен на GitHub в https://github.com/ tclose / Diophantine в соответствии с лицензией MIT, поэтому не стесняйтесь использовать его и дайте мне знать, если у вас возникнут проблемы (извините, что это не лучше документировано). Мастер-ветвь использует Sympy, но вы можете получить доступ к исходной реализации Numpy в ветке «numpy», которая, похоже, работает нормально для разумно разреженных систем.

Если вы в конечном итоге используете ее для научной публикации, пожалуйста, цитируйте Кит (и, возможно, добавить ссылку на репозиторий GitHub).

0

ответ дан Tom Close 18 August 2018 в 23:46

Другие вопросы по тегам:

python optimization integer linear-algebra least-squares

Похожие вопросы:

Я понял, что это что-то вроде этого - так можно ли использовать вычисления только в целых числах, чтобы избежать этих неточностей поплавка? — arshajii, 16 December 2012 в 05:19
Я думаю, что np.round должен это сделать. — Akavall, 16 December 2012 в 05:20
Извините, но это работает, потому что точное решение для этого примера является целым. Нет причин, по которым округление / усечение даст вам лучшее целочисленное решение. — seberg, 16 December 2012 в 13:29
Спасибо, это также помогает. Так что numpy не имеет функции специально для решения линейных систем только по целым числам? Я планировал использовать метод округления, подобный этому, в крайнем случае, но он не должен иметь особого значения. — arshajii, 16 December 2012 в 05:34
@ A.R.S .: Вы хотите, чтобы линейная алгебра была решена с использованием целочисленной арифметики или вы хотите, чтобы результат был целым типом данных? Я не думаю, что первое возможно. Для последнего я считаю, что приведенные здесь предложения должны быть достаточными. — tiago, 16 December 2012 в 12:15
Я согласен с tiango, из вопроса, который я бы сказал, это неверно, потому что округление не гарантирует найти лучшее целочисленное решение (если только оно не является целым), но с переопределенной системой, это кажется маловероятным. У примера, похоже, есть точное решение, хотя я допускаю. — seberg, 16 December 2012 в 13:31
@ A.R.S. - Нет, насколько я знаю, numpy не имеет никакого способа решить систему уравнений, которая гарантировала бы получение целочисленного решения. Внутренне numpy - это просто вызов подпрограмм из LAPACK и т. Д., Поэтому функции, такие как lstsq, являются, по сути, плавающей точкой. Я думаю, что между ответом NPE, чтобы определить, существует ли решение, и предложение Себерга попробовать нелинейный решатель, вы можете, вероятно, собрать что-то вместе. Округленное или усеченное решение с плавающей точкой может дать хорошее исходное предположение для нелинейного решателя, если ничего другого. — Joe Kington, 16 December 2012 в 17:34

score 4 · Accepted Answer

4

ответ дан NPE 18 August 2018 в 23:46