[R] Solving an optimization problem: selecting an "optimal" subset

[Erwin Kalvelagen]

Dimitri Shvorob <dimitri.shvorob <at> gmail.com> writes:

> 
> 
> Thank you very much, Erwin. If I may ask some follow-up questions
> 1. GAMS <> R, ad it's just not entirely clear how to move the soltion to R.
> (At most trivial, how do I "bring in" the subsettable vector into the
> solver?")
> 2. "The quadratic objective can be replaced by a linear one by minimizing
> the absolute deviation".
>     Minimizing absolute deviation is not, as far as I can see, a linear
> problem... ??
>     What magic is happening in these lines?
>     positive variable d1,d2; 
>     e3.. d1-d2 =e= s-target; 
>     obj.. z =e= d1+d2; 
> 

1. First of all, I don't want to tell you to use GAMS. I just find GAMS easier 
to use than Rcplex to quickly develop models, so for this experiment it was for 
the right tool. Having said this, it is possible call GAMS from R. E.g. by 
something like:

> "runmip" <- function(v,k,target)
+ {
+     write.csv(v,file="gamsdata.csv")
+     cmd = paste("c:/\"program files\"/gams23.3/gams.exe",
+             "selectmip.gms","lo=2",
+             "--n",length(v),
+             "--k",k,
+             "--target",target)
+     system(cmd)
+     read.csv("solution.csv",header=FALSE)$V1
+ 
+     
+ }
> v=runif(200,-100,100)
> system.time(solution<-runmip(v,40,3.1415))
   user  system elapsed 
   0.01    0.00   11.02 
> solution
  [1] 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 1
 [54] 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
[107] 0 1 1 1 1 1 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 0 1 1 0 
1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0
[160] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 0 0
> sum(solution)
[1] 40
>


2. Any free variable x can be written as the sum of two non-negative variables. 
I.e. x=d1-d1, d1>=0, d2>=0. The absolute value is d1+d2 provided that only one 
of d1,d2 is non-zero. In theory this can be formulated as a nonlinear 
constraint: d1*d2=0 but in this case we don't need it because as we are 
minimizing d1+d2 this condition holds automatically in the optimal solution. 
Examples:
x=10: d1=10,d2=0 => abs(x)=d1+d2=10
x=-2: d1=0,d2=2 => abs(x)=d1+d2=2

----------------------------------------------------------------
Erwin Kalvelagen
Amsterdam Optimization Modeling Group
erwin at amsterdamoptimization.com
http://amsterdamoptimization.com