Integer Linear Least Squares

Question

Also muss ich ein x finden, das minimiert norm(A.dot(x) - y, 2) A ist eine Matrix und y ist ein Vektor.

Dies könnte leicht mit scipy.optimize.lsq_linear oder numpy.linalg.lstsq erreicht werden, aber ich brauche x ganze Zahlen. Im Allgemeinen ist "Integer-Programmierung" NP-vollständig. Ich habe Routines for solving the standard integer least squares problem gefunden, aber ich dachte, ich würde fragen, bevor ich es von Matlab konvertieren.

Gibt es eine etablierte Bibliothek, die Integer Linear Least Squares in Python lösen kann?

Answer 1

Sie könnten eine der Optimierungsbibliotheken verwenden, die für Python verfügbar sind, als mit (gemischter) Ganzzahlprogrammierung umgehen kann. Machen Sie eine Goggle Suche und Sie werden viele finden. Da Ihr Problem konvex ist, kann cvxpy als eine nette Schnittstelle zu vielen von ihnen verwendet werden. Hier ist ein Spielzeug Beispiel eine eingebaute in ganzzahligen Programmierung Solver (was nicht sehr effizient sein kann für große Probleme)

import numpy as np 
import cvxpy 

np.random.seed(123) # for reproducability 

# generate A and y 
m, n = 10, 10 
A = np.random.randn(m,n) 
y = np.random.randn(m) 

# declare the integer-valued optimization variable 
x = cvxpy.Int(n) 

# set up the L2-norm minimization problem 
obj = cvxpy.Minimize(cvxpy.norm(A * x - y, 2)) 
prob = cvxpy.Problem(obj) 

# solve the problem using an appropriate solver 
sol = prob.solve(solver = 'ECOS_BB') 

# the optimal value of x is 
print(x.value) 

[[-13.] 
[ -3.] 
[ 3.] 
[ 6.] 
[ 1.] 
[ -5.] 
[ -1.] 
[ -3.] 
[ -2.] 
[ -6.]] 

Answer 2

Ich habe mit einer ähnlichen Lösung zu lösen Summe kommen (| Ax-y |), das Sie in ein lineares ganzzahliges Programmierproblem umwandeln und mit PuLP lösen können.

Die Grundidee ist es, die Zielfunktionssumme (err (i)) unter den Randbedingungen zu minimieren:

Ax (i) - y (i) < = err (i) und Ax (i) - y (i)> = -err (i).

, die mit linearen Lösern kompatibel ist.