[R] Help with optimization problem

[Berend Hasselman]

Jorge,

First of all, I really do think that questions such as these should be posted directly to R-help.
More people will then see it with a greater chance of getting useful replies.
I am subscribed to R-help so will see posts.

I have cc'ed  this reply to R-help so that you may get more answers than I can give you.

I know absolutely nothing about transportation problems. 
For comments see inline.

On 27-11-2012, at 00:24, Jorge I Velez wrote:

> Dear Dr. Hasselman,
> 
> Please receive my apologies in advance for contacting you directly, but I have seen your replies in R-help and just thought that, perhaps, you could give me a hand. I am facing an optimization problem and unfortunately can not find a way to get around.  I will try to explain myself as good as I can.
> 
> Let us consider an optimization problem in which it is of interest to distribute resources from 2 to 3 points. The costs associated are as follows:
> 
>            Destination
> From      1    2     3     Total 
>  1           1    3     4      300
>   2          3    2     3      200
> Total    150  250  100     500
> 
> If X_i (i = 1, 2, ..., 6) is the cost of shipping X units from/to the ith combination (i.e., i = 1 means from shipping from point 1 to destination 1; i = 2 from point 1 to destination 2 and so on), the formulation in R would be as follows:
> 

This description  is confusing. So x4 means shipping from point to destination 4 (you only have 3 destinations)?

> require(lpSolve)
> f <- matrix(c(1, 3, 4, 3, 2, 3), ncol = 3, byrow = TRUE)
> row.rhs <- c(300, 200)
> col.rhs <- c(150, 250, 100)
> row.signs <- rep("==", length(row.rhs))
> col.signs <- rep("==", length(col.rhs))
> D <- lp.transport(f, "min", row.signs, row.rhs, col.signs, col.rhs)
> D$solution
> 
> So far so good until this point.  However, in addition to spend *all* the resources as above, in my application I would like to set up a couple of more constraints as follows.
> 
> # row and column constraints
> x1 + x2 + x3                         == 300    # row 1
>                      x4 + x5 + x6    == 200    # row 2
> x1              + x4                   == 150    # col 1
>      x2                 + x5           == 250    # col 2
>           x3                   + x6    == 100    # col 3
> x1 + x2 + x3 + x4 + x5 + x6  == 500    # all available
> 

But these constraints are already satisfied in the solution.

> Now, if w is a vector representing some constants (the length of w is the number of destinations from which we ship stuff), I would like to include the following three constraints, where r is fixed and known:
> 

I don't understand "the number of destinations from which we ship stuff".
Shouldn't "from" be "to"?


> w1*x1           + w2*x4                   == r    # col 1
>        w1*x2             + w2*x5          == r    # col 2
>              w3*x3               + w6*x6  == r    # col 3
> 

vector w is length 6 but you only have three destinations (from the initial description)
I don't understand what you are doing here.

> Another constraint that I would like to impose is that, by column, the number of X_i's greater than zero should be at least two.  Furthermore, the maximization function should not be the coefficients in the f matrix, but the standard deviation of g = c(l1, l2, l3) where
> 
> l1 = w1*x1 + w2*x4
> l2 = w1*x2 + w2*x5 
> l3 = w3*x3 + w6*x6 
> 

How does this relate to your previous formula?

> In my application I have up to 100 columns and 50 rows and I am able to include all the constraints but not the number of zeros neither the new function to optimize. Could you please give some advice me on how to do both?  I have been reading a bit on quadratic programing as the function to optimize is the standard deviation, but I do not really know how to set up the constraints, let alone the complete problem. 
> 

From this description I gather that you want to optimize (minimize?) the standard deviations, perhaps a weighted sum?

> Thank you very much in advance for any help you can provide me.
> 

There is far too much unclear about your problem to give any sensible advice, assuming that I have any.

Berend