Would you please help me solve the following problem where $b_{ij}$ is my decision variable that must be determined and all other parameters are known.
$$\min \left(\sum_{i=1}^n b_i x_i\right)^2$$
such that
$$\sum_{i=1}^n b_i = k,\qquad b_i\in\{0,1\}$$
Please note that $n$ may be large, and I prefer an efficient approach (e.x. relaxing $b_i$ i.e., $0\leq b_i \leq 1$).
Edit: Confused max and min. Thx @ 900 sit-ups a day.
If $x_i$ are all of the same sign, then this is trivial since you can pick the smallest (in absolute value) $k$ elements of the array and you are done. If $x_i$ can be positive or negative, then one immediate idea that occurs to me is to use dynamic programming, since you have to now keep track of sums of elements in the array and make this sum as small as possible in absolute value.
Another approach is to replace the square in the objective with absolute value, and then use a dummy variable to obtain an integer linear program, which you can then solve using say branch and bound. This is unlikely to be efficient but considering the special structure that the problem has, a solver like CPLEX probably has all sorts of tricks built in to speed things up.
I suspect this probably has already been looked at in Machine Learning literature, since you are solving a convex objective over some cardinality constraints.