# Extremely short Matlab LP solvers

This one by Borja Peleato is based on ADMM, does not require any particular initialization, and uses just 49 characters. (Yes, that is indeed ridiculously short.)

```for i=1:99,z=max(z-x,x-c);x=z+pinv(A)*(b-A*z);end
```

## 69 characters: More stable than the original version

Zhonghao Zhang, a student of Chee Wei Tan, emailed me in November 2010 with this solver:

```for i=1:50,X=diag(x);F=X*null(A*X);d=F*F'*c;x=x-d/max(X\abs(d))/2;end
```

It is a mere 69 characters (though uses the higher-level function ‘null’), and seems more stable than my solver.

## 75 characters: The original version

This is Dikin's method for minimizing , subject to and . Start with x at a feasible point.

```for i=1:50,p=diag(x)^2;r=p*(c-A'*(A*p*A'\A*p*c));x=x-r*min(x./abs(r))/2;end
```
Example: Matlab LP generation and solution
```A = randn(100, 300);
x0 = rand(300, 1);
b = A*x0;
c = rand(300, 1);
x = x0;
for i=1:50,p=diag(x)^2;r=p*(c-A'*(A*p*A'\A*p*c));x=x-r*min(x./abs(r))/2;end
```

Astonishingly, this particular solver continues to get smaller and smaller, with the latest reduction placed here in March 2010 (down from 80 characters). Thanks to Yang Wang and Richard Brown for suggesting improvements. Let me know if you can reduce it further!