Formulación de programación entera del problema de partición

Question

Tengo el siguiente problema:

Considere el conjunto de números enteros$\{1,2,3,4,5,6\}$ y$$\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|$ $

Creé las variables binarias$b_1, b_2, \dots, b_6 \in \{0,1\}$ para este modelado lineal.

$$\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$ es una gran constante

Mi modelo es incorrecto y no sé cómo resolverlo

Answer 1

No necesita restricciones de M grandes para este propósito. $s_i=2b_i-1$ debería ser suficiente.

Answer 2

La restricción $s_i -1 \leq -M_1 + b_i$ debe ser eliminado.

Independientemente de los valores de $b_i$, se está realizando el problema infactible como el límite superior es un número muy pequeño.

La restricción

$$s_i + 1 \leq M_1 (1-b_1)$$ significa que si $b_i = 1$,entonces tenemos que tener en $s_i= -1$. Si $b_i=0$, $s_i$ es gratis.

Por lo tanto, usted todavía necesita incluir una restricción que dice

si $b_1=0$, entonces tenemos que tener en $s_i=1$.

$$-s_i\leq Mb_i$$

Comentario:

En términos del valor óptimo del problema, ya que hay $3$ número impar, el valor óptimo será, al menos,$1$.

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