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$ Commented 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$ Commented 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$ Commented Jul 18, 2017 at 19:24

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.