My student friends passed me a homework question for Operations Research. Since it involves Matrices, I was attracted to try Julia. At the end I was very happy with the experience. Julia is a great language to do matrix operations.

Question

Solve the following LP by using the Affine Scaling Approach of Interior Point Methods (IPM) with starting Try to solve the problem for at least 3 iterations.

Solution

Wikipedia explains the algorithm in a very mathematical way: https://en.wikipedia.org/wiki/Affine_scaling. I guess you need to be very familiar with linear programming to understand that. (I’m not)

I found this great resource about using Julia for Operations Research by Changhyun Kwon: https://juliabook.chkwon.net/book/interior

I understood the problem and the method (except for the math magic that somehow gives you the direction to move for each variable). I wasn’t sure how to get c and A matrices below. Luckily, I found the exact example with these matrices in a PDF(page 41) by chance. It became a perfect puzzle, with all the parts in front of me.

So, here is the solution:

using LinearAlgebra
 
beta=0.8
 
x0 = [10, 2, 7, 13]
 
x=x0
 
c = [-2, 1, 0, 0]
A = [1 -1 1 0 ;
     0 1 0 1 ]
b = [15, 15]
 
for i in 1:3
 
    local X = Diagonal(x)
    local p = inv(A*X^2*A')*A*X^2*c
    local r = c - A'*p
 
    global x = x - beta * X^2 * r / norm(X*r)
    println((round.(x; digits=2)))
end