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$
1
  • $\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, 2017 at 17:51

2 Answers 2

Reset to default
6
$\begingroup$

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

$\endgroup$
0
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$
2
  • $\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, 2017 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, 2017 at 19:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .