1
$\begingroup$

Let $X=\{-1,1\}^n$ for a given natural number $n$ and $(w_0,w_2,\cdots,w_n)\in R_+^{n+1}$. Find $$\min_{(x_1,x_2,\cdots,x_n)\in X}\bigg|w_0+\sum_iw_ix_i\bigg|.$$

We can turn this into the following binary linear programming problem. \begin{align} \min_{{(x_1,\,x_2,\,\cdots,\,x_n)\in X}\atop{d}}&\ d \\ w_0+\sum_iw_ix_i&\le d \\ -(w_0+\sum_iw_ix_i)&\le d \\ \end{align} or \begin{align} \min_{{(x_1,\,x_2,\,\cdots,\,x_n)\in X}\atop{s,\,t}}&\ s+t \\ w_0+\sum_iw_ix_i&=s-t \\ s&\ge 0 \\ t&\ge 0 \end{align}

Is there a faster and general solution?

$\endgroup$
  • 1
    $\begingroup$ You are mixing two methods to reformulate absolute values. You can get rid of $d$ and define the objective as $s+t$. As subset sum is a special case of your problem, I would not expect any fast solution method. $\endgroup$ – LinAlg Feb 7 '17 at 8:21
  • $\begingroup$ @LinAlg: You are right. I have edited the question. Is there a fast dynamic programming algorithm to solve this problem? $\endgroup$ – Hans Feb 7 '17 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.