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

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

Moderators: phlip, Prelates, Moderators General

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

Postby Styhn » Tue Feb 28, 2012 9:42 pm UTC

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.2500

b =

   100

c =

    -1
    -1
    -1
    -1

x=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.1
SeDuMi 1.1R3 by AdvOL, 2006 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, theta = 0.250, beta = 0.500
eqs m = 4, order n = 9, dim = 9, blocks = 1
nnz(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-023

Detailed timing (sec)
   Pre          IPM          Post
0.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.
Styhn
 
Posts: 68
Joined: Fri Mar 02, 2007 10:10 am UTC

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

Postby mfb » Wed Feb 29, 2012 1:01 am UTC

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
mfb
 
Posts: 838
Joined: Thu Jan 08, 2009 7:48 pm UTC

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

Postby Styhn » Wed Feb 29, 2012 1:57 am UTC

Thanks for moving, mods.
Styhn
 
Posts: 68
Joined: Fri Mar 02, 2007 10:10 am UTC

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

Postby eta oin shrdlu » Wed Feb 29, 2012 9:20 pm UTC

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.
User avatar
eta oin shrdlu
 
Posts: 433
Joined: Sat Jan 19, 2008 4:25 am UTC

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

Postby Styhn » Sun Mar 04, 2012 12:38 pm UTC

Ah I see, thank you very much!
Styhn
 
Posts: 68
Joined: Fri Mar 02, 2007 10:10 am UTC


Return to Coding

Who is online

Users browsing this forum: No registered users and 6 guests