Which algorithm for this type of problem?

Hi!

I would like to solve a problem, where I have run many optimization problems by using a loop. That problem has already been solved by another person, however the results that I get in each step of the loop are very different from the result of the other person who solved this problem. That is why, I would like to make sure that Matlab uses the best algorithm available for this type of problem.

The problem:

A =

      174726      187180          -1
      196094      171660          -1
       87100      110042          -1
      182625      157808          -1
      188196      233574          -1

b =

    91832600
   165805408
    51750400
   113998496
   158685200

f =

     -110429     -120153           1

problem: min f^T*x

st Ax<=b, x>=0

--------------------

My code:

options=optimset('display','off');

[x,fval,exitflag,output]=linprog(f,A,b,[],[],zeros(1,3),[],[],options);

As previously mentioned, I have to run this code a number of times by using a loop. In each step only the two first elements of f change - otherwise the problem is exactly the same.

So, by not changing the algorithm Matlab uses "interior point" by default. I have tried to change something (largescale on/off, simplex, actice-set). But sometimes even though I change it in optimset it does not give me any error, and I can see in the output that the algorithm is stille the same. My question is, which algorithm is best for this type of problem and how do I tell Matlab to use it?

Thank you very much for your time and consideration!

Alex

[Matt J]

Why do you think it matter which one you use? Your tests show that all the different alternatives are giving you the correct result.

Answer 1

[Matt J]

If you add upper bounds to your problem, you can compute the vertices of the feasible region using LCON2VERT (Available Here). Then you can simply evaluate f.'*V(i,:) for all the different vertices V(i,:) and all different f and find the minimum.

>> A,b

A =

        174726      187180          -1
        196094      171660          -1
         87100      110042          -1
        182625      157808          -1
        188196      233574          -1
            -1           0           0
             0          -1           0
             0           0          -1
             1           0           0
             0           1           0
             0           0           1

b =

      91832600
     165805408
      51750400
     113998496
     158685200
             0
             0
             0
      10000000
      10000000
      10000000

 >> V=lcon2vert(A,b);
 >> [~,i]=min(V*f(:)); x=V(i,:)

x =

    143.2383  356.9032         0