Skip to main content
Bounty Ended with 50 reputation awarded by Louis Deaett
edited body; edited body
Source Link
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

Here is an Integer Linear Programming approach to this problem.

First, let's multiply given vectors by a suitable integer to make them all having integer components. Second, we notice that if certain rational coefficients deliver the minimum Hamming weight, then by scaling them, we can obtain integer coefficients delivering the same weight. Therefore, we can focus on the problem of finding an integer linear combination of integer vectors with the smallest nonzero number of nonzero components.

Let $v_1,\dots,v_m$ be given integer vectors. Let $c_i$ for $i\in\{1,\dots,m\}$ be integer variables corresponding to the coefficients in a linear combination. For each component $j\in\{1,\dots,n\}$, we further introduce two binary variables $p_j,q_j\in\{0,1\}$ and three inequalities: $$\sum_{i=1}^m v_{ij} c_i \geq p_j - Mq_j,$$ $$\sum_{j=1}^m v_{ij} c_i \leq -q_j + Mp_j,$$$$\sum_{i=1}^m v_{ij} c_i \leq -q_j + Mp_j,$$ $$p_j + q_j \leq 1,$$ where $M$ is a large positive constant (chosen empirically). The third inequality here restricts values to three possible cases: $(p_j,q_j)=(1,0)$ when the $j$-th component in the linear combination is positive; $(p_j,q_j)=(0,1)$ when the $j$-th component is negative; and $(p_j,q_j)=(0,0)$ when the $j$-th component is zero. Notice that the large value of $M$ when it comes with a nonzero coefficient makes the corresponding inequality silent (automatically satisfied).

Next, we exclude the zero linear combination by requiring $$\sum_{j=1}^n p_j + q_j \geq 1.$$

SinceFinally, since $\sum_{j=1}^n p_j + q_j$, in fact defines, equals the weight of the linear combination, our objective is $$\sum_{j=1}^n p_j + q_j\quad \longrightarrow\quad \min.$$$$\text{minimize}\quad \sum_{j=1}^n p_j + q_j.$$

Here is an Integer Linear Programming approach to this problem.

First, let's multiply given vectors by a suitable integer to make them all having integer components. Second, we notice that if certain rational coefficients deliver the minimum Hamming weight, then by scaling them, we can obtain integer coefficients delivering the same weight. Therefore, we can focus on the problem of finding an integer linear combination of integer vectors with the smallest nonzero number of nonzero components.

Let $v_1,\dots,v_m$ be given integer vectors. Let $c_i$ for $i\in\{1,\dots,m\}$ be integer variables corresponding to the coefficients in a linear combination. For each component $j\in\{1,\dots,n\}$, we further introduce two binary variables $p_j,q_j\in\{0,1\}$ and three inequalities: $$\sum_{i=1}^m v_{ij} c_i \geq p_j - Mq_j,$$ $$\sum_{j=1}^m v_{ij} c_i \leq -q_j + Mp_j,$$ $$p_j + q_j \leq 1,$$ where $M$ is a large positive constant (chosen empirically). The third inequality here restricts values to three possible cases: $(p_j,q_j)=(1,0)$ when the $j$-th component in the linear combination is positive; $(p_j,q_j)=(0,1)$ when the $j$-th component is negative; and $(p_j,q_j)=(0,0)$ when the $j$-th component is zero. Notice that the large value of $M$ when it comes with a nonzero coefficient makes the corresponding inequality silent (automatically satisfied).

Next, we exclude the zero linear combination by requiring $$\sum_{j=1}^n p_j + q_j \geq 1.$$

Since $\sum_{j=1}^n p_j + q_j$ in fact defines the weight of the linear combination, our objective is $$\sum_{j=1}^n p_j + q_j\quad \longrightarrow\quad \min.$$

Here is an Integer Linear Programming approach to this problem.

First, let's multiply given vectors by a suitable integer to make them all having integer components. Second, we notice that if certain rational coefficients deliver the minimum Hamming weight, then by scaling them, we can obtain integer coefficients delivering the same weight. Therefore, we can focus on the problem of finding an integer linear combination of integer vectors with the smallest nonzero number of nonzero components.

Let $v_1,\dots,v_m$ be given integer vectors. Let $c_i$ for $i\in\{1,\dots,m\}$ be integer variables corresponding to the coefficients in a linear combination. For each component $j\in\{1,\dots,n\}$, we further introduce two binary variables $p_j,q_j\in\{0,1\}$ and three inequalities: $$\sum_{i=1}^m v_{ij} c_i \geq p_j - Mq_j,$$ $$\sum_{i=1}^m v_{ij} c_i \leq -q_j + Mp_j,$$ $$p_j + q_j \leq 1,$$ where $M$ is a large positive constant (chosen empirically). The third inequality here restricts values to three possible cases: $(p_j,q_j)=(1,0)$ when the $j$-th component in the linear combination is positive; $(p_j,q_j)=(0,1)$ when the $j$-th component is negative; and $(p_j,q_j)=(0,0)$ when the $j$-th component is zero. Notice that the large value of $M$ when it comes with a nonzero coefficient makes the corresponding inequality silent (automatically satisfied).

Next, we exclude the zero linear combination by requiring $$\sum_{j=1}^n p_j + q_j \geq 1.$$

Finally, since $\sum_{j=1}^n p_j + q_j$, in fact, equals the weight of the linear combination, our objective is $$\text{minimize}\quad \sum_{j=1}^n p_j + q_j.$$

Source Link
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

Here is an Integer Linear Programming approach to this problem.

First, let's multiply given vectors by a suitable integer to make them all having integer components. Second, we notice that if certain rational coefficients deliver the minimum Hamming weight, then by scaling them, we can obtain integer coefficients delivering the same weight. Therefore, we can focus on the problem of finding an integer linear combination of integer vectors with the smallest nonzero number of nonzero components.

Let $v_1,\dots,v_m$ be given integer vectors. Let $c_i$ for $i\in\{1,\dots,m\}$ be integer variables corresponding to the coefficients in a linear combination. For each component $j\in\{1,\dots,n\}$, we further introduce two binary variables $p_j,q_j\in\{0,1\}$ and three inequalities: $$\sum_{i=1}^m v_{ij} c_i \geq p_j - Mq_j,$$ $$\sum_{j=1}^m v_{ij} c_i \leq -q_j + Mp_j,$$ $$p_j + q_j \leq 1,$$ where $M$ is a large positive constant (chosen empirically). The third inequality here restricts values to three possible cases: $(p_j,q_j)=(1,0)$ when the $j$-th component in the linear combination is positive; $(p_j,q_j)=(0,1)$ when the $j$-th component is negative; and $(p_j,q_j)=(0,0)$ when the $j$-th component is zero. Notice that the large value of $M$ when it comes with a nonzero coefficient makes the corresponding inequality silent (automatically satisfied).

Next, we exclude the zero linear combination by requiring $$\sum_{j=1}^n p_j + q_j \geq 1.$$

Since $\sum_{j=1}^n p_j + q_j$ in fact defines the weight of the linear combination, our objective is $$\sum_{j=1}^n p_j + q_j\quad \longrightarrow\quad \min.$$