0
$\begingroup$

I guess I have a simple problem, but I can't find a fitting solution.

I have a certain amount periods $D$, and every period is described by the decision variable $X_d$. What I want to do is set a binary Variable $N_d$ to 1, if the value $X_d$ is not equal to $X_{d-1}$. So if the value $X$ changes between two periods, the binary variable should be $1$. If it stays the same, the binary variable should be $0$.

So far I'm struggeling with not being allowed to use the absolute value of the difference of $X_d$ and $X_{d-1}$ to keep the problem linear.

My first idea was: $$ |X_{d-1} - X_d| \times 0.01 \leq N_d \quad \textrm{for } d > 1 $$

I hope you can understand my problem and I would appreciate any help!

Best regards, Seba

$\endgroup$
4
  • $\begingroup$ Welcome to Math.SE. Take the opportunity to take the tour, if you haven't done it already. See also some tips on how to ask and on formatting help and write down equations using LaTeX / MathJax. $\endgroup$ Commented Jul 15, 2019 at 15:38
  • $\begingroup$ I've edited you question to add some mathematical formatting and corrected a few typos. Please check if they are OK, after my edit is accepted. $\endgroup$ Commented Jul 15, 2019 at 15:43
  • $\begingroup$ Are $X_d$ and $X_{d-1}$ binary variables? If not, what are their bounds? $\endgroup$ Commented Jul 15, 2019 at 17:32
  • $\begingroup$ Thank you Rob for your time! They are Integer and for both of them the bounds are 0 and 48 $\endgroup$ Commented Jul 15, 2019 at 18:37

2 Answers 2

Reset to default
3
$\begingroup$

The following formulation assumes that $X_d$ and $X_{d-1}$ are binary variables.

You can enforce the implication $X_d \not= X_{d-1} \implies N_d = 1$ by introducing these two linear constraints: \begin{align*} X_d - X_{d-1} &\le N_d \\ X_{d-1} - X_d &\le N_d \end{align*} You can enforce the implication $N_d = 1 \implies X_d \not= X_{d-1}$ by introducing these two linear constraints: \begin{align*} X_d + X_{d-1} &\le 2 - N_d \\ X_d + X_{d-1} &\ge N_d \end{align*}

Edit: The following formulation assumes that $X_d$ and $X_{d-1}$ are integer variables bounded by 0 and 48.

Introduce binary variables $N_d^1$, $N_d^2$, and $N_d^3$ and linear constraints: \begin{align} X_d - X_{d-1} &\ge -48 N_d^1 + N_d^3 \\ X_d - X_{d-1} &\le - N_d^1 + 48 N_d^3 \\ \sum_{i=1}^3 N_d^i &= 1 \\ N_d &= N_d^1 + N_d^3 \end{align}

To see that this works, consider the three cases $(N_d^1,N_d^2,N_d^3)=(1,0,0)$, $(0,1,0)$, and $(0,0,1)$.

As long as you impose an upper bound of 1 on $N_d$, you can omit $N_d^2$ and constraint (3).

$\endgroup$
0
$\begingroup$

What about $$ (X_{d-1} - X_d)^2 \ ? $$

I'm assuming that you're talking about linearity of coefficients, instead of linearity of measures.

$\endgroup$
1
  • $\begingroup$ Thank you Ertxiem. Is that possble, even if X is a decision variable? Isn't that a non convex problem then? $\endgroup$ Commented Jul 15, 2019 at 16: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.