5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What do you mean by "the following mathematical expression: S1 1 s2 2 s3 3 s4 4 s5 5 s6 6" ?? And please see this link to reformat your post into proper math rendering: math.meta.stackexchange.com/questions/5020/… $\endgroup$ – hausdork Jul 18 '17 at 17:51
6
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ I don't think the constraint $-s_i \le Mb_i$ is what you had in mind. for $b_i=0$, it just requires $s_i\ge 0$, which is insufficient unless the domain $s\in\{-1,1\}$ is enforced somewhere else in the model. $\endgroup$ – prubin Jul 18 '17 at 19:23
  • 1
    $\begingroup$ @prubin of course, she has to keep those constraint. thanks for bringing this up. the intention is to help her replace a wrong constraint. I think too complicated that I just look at big M method. $\endgroup$ – Siong Thye Goh Jul 18 '17 at 19:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.