## I'm stupid. How to cast in linear programming setting?

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

Styhn
Posts: 68
Joined: Fri Mar 02, 2007 10:10 am UTC
Contact:

### I'm stupid. How to cast in linear programming setting?

Either Matlab is trolling me or I'm having a massive brainfailure. Here's a homework question I'm trying to work out:

We have 100 dollars that want to invest in gold. There are four suppliers with prizes 1/2, 1, 1/7 and 1/4 dollar per gram of gold. We want to maximize the amount of gold. Formulate this as an LP and solve.

A straightforward question, whose purpose is do get us acquainted with LP software. I'm using SeDuMi (http://sedumi.ie.lehigh.edu/)and yalmip (http://users.isy.liu.se/johanl/yalmip/), along with this function:

Code: Select all

`function [opt,vecX]=standardLux(c,A,b) n = length(c); x = sdpvar(n,1); % %  F = set( A*x <= b ); F = F + set( x(:) >= 0 );%  obj = -c'*x;% %  diagnostics = solvesdp(F,obj,sdpsettings('showprogress',1,'solver','sedumi'))%  opt=double(obj); vecX=double(x); vecX(((abs(vecX)<1e-5))) = 0;end`

My input is as follows:

Code: Select all

`A =    0.5000    1.0000    0.1429    0.2500b =   100c =    -1    -1    -1    -1x=standardLux(A',b,c)`

The output of which is

Code: Select all

`+ Solver chosen : SeDuMi-1.1+ Processing objective h(x)+ Processing F(x)+ Calling SeDuMi-1.1SeDuMi 1.1R3 by AdvOL, 2006 and Jos F. Sturm, 1998-2003.Alg = 2: xz-corrector, theta = 0.250, beta = 0.500eqs m = 4, order n = 9, dim = 9, blocks = 1nnz(A) = 8 + 0, nnz(ADA) = 4, nnz(L) = 4 it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec  0 :            1.12E+003 0.000  1 : -5.52E-002 2.72E+001 0.000 0.0243 0.9900 0.9900   0.98  1  1  5.0E+000  2 : -1.85E-001 8.84E+000 0.000 0.3246 0.9000 0.9000  -0.60  1  1  1.6E+001  3 : -7.62E-001 4.23E-001 0.000 0.0478 0.9900 0.9900  -1.16  1  1  7.8E+001  4 : -1.75E+000 5.59E-005 0.126 0.0001 0.9999 0.9999  -1.01  1  1  Dual infeasible, primal improving direction found.iter seconds  |Ax|    [Ay]_+     |x|       |y|  4      0.0  7.1e-015  2.0e-021  5.0e+001  2.6e-023Detailed timing (sec)   Pre          IPM          Post0.000E+000    1.560E-002    0.000E+000    Max-norms: ||b||=1, ||c|| = 1,Cholesky |add|=0, |skip| = 0, ||L.L|| = 1.diagnostics =     yalmiptime: 0.0260    solvertime: 0.0140          info: 'Infeasible problem (SeDuMi-1.1)'       problem: 1        dimacs: [0.5773 0 0 0.5000 -0.5000 -0.5000]x =   -0.0189`

which is clearly not right. Could someone see where I went wrong? I apologize for the wall of code.

mfb
Posts: 947
Joined: Thu Jan 08, 2009 7:48 pm UTC

### Re: I'm stupid. How to cast in linear programming setting?

As the mathematical solution is obvious (buy 700 gram from the 1/7-supplier (, sell the 700 gram for ~40000 dollars, buy ~300kg of gold, repeat)) it looks like the interpretation of your code and output requires some knowledge about Matlab, I think this belongs to the coding section?
Agreed, moved. -phlip

Styhn
Posts: 68
Joined: Fri Mar 02, 2007 10:10 am UTC
Contact:

### Re: I'm stupid. How to cast in linear programming setting?

Thanks for moving, mods.

eta oin shrdlu
Posts: 450
Joined: Sat Jan 19, 2008 4:25 am UTC

### Re: I'm stupid. How to cast in linear programming setting?

I'm not familiar with these packages, but I see what I think are two problems with your code. First, you're calling

Code: Select all

`x=standardLux(A',b,c)`
but your function parameters are defined to be taken in a different order as

Code: Select all

`function [opt,vecX]=standardLux(c,A,b)`
which is undoubtedly confusing things a lot--the return value isn't even the right dimension. (You should be able to debug this in Matlab by either setting a breakpoint in the function or printing out the local variables' values so you can check that they are what you think they ought to be.) Second, solvesdp is trying to minimize obj, and you want to maximize sum(x)=[1 1 1 1]*x. You have tried to fix this twice, once by setting c=[-1 -1 -1 -1]' and then again by setting obj=-c'*x; I think these two signs will cancel out and give you the trivial minimum solution instead of the one you're looking for.

Styhn
Posts: 68
Joined: Fri Mar 02, 2007 10:10 am UTC
Contact:

### Re: I'm stupid. How to cast in linear programming setting?

Ah I see, thank you very much!