Integer programming formulation of the partition problem

Question

I have the following problem:

Consider the set of integers $\{1,2,3,4,5,6\}$ and $$\sum_{i=1}^6 s_i i,$$ where $s_1, s_2, \dots, s_6 \in \{1,-1\}$ are the signs that appear in front of each of these numbers. Present an integer programming model that minimizes $$\left| \,\sum_{i=1}^6 s_i i \,\right|$$

I created binary variables $b_1, b_2, \dots, b_6 \in \{0,1\}$ for this linear modeling.

$$\min U$$ subject t $$U \geq \sum_{i=1}^6 s_i i$$ $$U \geq -\sum_{i=1}^6 s_i i$$

$$s_i + 1 \leq M_1(1-b_i)$$ $$s_i - 1 \leq - M_1 + b_i$$

$$s_i = \{-1,+1\}$$ $$b_i = \{0,1\}$$ $M_1$ is big constant

My model is incorrect and I do not know how to solve

Answer 1

The constraint $s_i -1 \leq -M_1 + b_i$ must be removed.

Regardless of the values of $b_i$, it is making the problem infeasible as the upper bound is a very small number.

The constraint

$$s_i + 1 \leq M_1 (1-b_1)$$ means if $b_i = 1$,then we must have $s_i= -1$. If $b_i=0$, $s_i$ is free.

Hence you still need to include a constraint that says

if $b_1=0$, then we must have $s_i=1$.

$$-s_i\leq Mb_i$$

Remark:

In terms of the optimal value of the problem, since there are $3$ odd numbers, the optimal value will be at least $1$.

$$-1-2-3-4+5+6=1$$

Answer 2

You don't need big-M constraints for this purpose. $s_i=2b_i-1$ should suffice.