Solving an optimization problem: selecting an "optimal" subset

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

A 40-element subset proves too much :(

Error: cannot allocate vector of size 554.1 Mb

Thanks, Bart!

I could solve a problem with n=200, k=40 with Cplex's MIQP solver in less than a 
minute, but that may depend heavily on the data. The model I used looks like:

 min (s-target)^2
 s = sum(i,p[i]*x[i])
 sum(i,x[i]) = k
 x[i] in {0,1}

One can replace the quadratic object by a linear one by minimizing the absolute 
deviation. That leads to a MIP model:

 min d1+d2
 s = sum(i,p[i]*x[i])
 sum(i,x[i]) = k
 d1-d2 = s-target
 d1,d2>=0  
 x[i] in {0,1}

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