Binary variables in time series: integer linear programming
up vote
0
down vote
favorite
I'm working on a problem and I can't seem to find an easy solution to it. It's about an optimization problem, concerning a time series.
I have a binary variable $alpha_t$ for $t in [0, 24[$. I also have an extra constraint, which states that $$sum_{t=0}^{23} alpha_t geq 14.$$ The problem is that I want to add an extra constraint that if a certain $alpha_t = 1$, then either $$alpha_{t-1} = alpha_{t+1} = 1$$ or $$alpha_{t-1} = alpha_{t-2} = 1$$ or $$alpha_{t+1} = alpha_{t+2} = 1, $$ i.e. at least 3 consecutive times $alpha$ needs to be 1. It can be 4 times, it can be 5, but it has to be at least 3 times.
The most intuitive idea is probably this:
$$alpha_t = 1 Rightarrow alpha_t + alpha_{t+1} + alpha_{t + 2} = 3,$$ but from a certain $t$, this will result that all $alpha_t = 1$.
I also tried big M constraints, but for larger consecutive times ( $geq 3)$, this becomes almost impossible to write down/implement.
linear-programming binary integer-programming time-series constraints
asked Nov 22 at 10:31
Riley
623414
add a comment |
up vote
0
down vote
favorite
I'm working on a problem and I can't seem to find an easy solution to it. It's about an optimization problem, concerning a time series.
I have a binary variable $alpha_t$ for $t in [0, 24[$. I also have an extra constraint, which states that $$sum_{t=0}^{23} alpha_t geq 14.$$ The problem is that I want to add an extra constraint that if a certain $alpha_t = 1$, then either $$alpha_{t-1} = alpha_{t+1} = 1$$ or $$alpha_{t-1} = alpha_{t-2} = 1$$ or $$alpha_{t+1} = alpha_{t+2} = 1, $$ i.e. at least 3 consecutive times $alpha$ needs to be 1. It can be 4 times, it can be 5, but it has to be at least 3 times.
The most intuitive idea is probably this:
$$alpha_t = 1 Rightarrow alpha_t + alpha_{t+1} + alpha_{t + 2} = 3,$$ but from a certain $t$, this will result that all $alpha_t = 1$.
I also tried big M constraints, but for larger consecutive times ( $geq 3)$, this becomes almost impossible to write down/implement.
linear-programming binary integer-programming time-series constraints
asked Nov 22 at 10:31
Riley
623414
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I'm working on a problem and I can't seem to find an easy solution to it. It's about an optimization problem, concerning a time series.
I have a binary variable $alpha_t$ for $t in [0, 24[$. I also have an extra constraint, which states that $$sum_{t=0}^{23} alpha_t geq 14.$$ The problem is that I want to add an extra constraint that if a certain $alpha_t = 1$, then either $$alpha_{t-1} = alpha_{t+1} = 1$$ or $$alpha_{t-1} = alpha_{t-2} = 1$$ or $$alpha_{t+1} = alpha_{t+2} = 1, $$ i.e. at least 3 consecutive times $alpha$ needs to be 1. It can be 4 times, it can be 5, but it has to be at least 3 times.
The most intuitive idea is probably this:
$$alpha_t = 1 Rightarrow alpha_t + alpha_{t+1} + alpha_{t + 2} = 3,$$ but from a certain $t$, this will result that all $alpha_t = 1$.
I also tried big M constraints, but for larger consecutive times ( $geq 3)$, this becomes almost impossible to write down/implement.
linear-programming binary integer-programming time-series constraints
asked Nov 22 at 10:31
Riley
623414
I'm working on a problem and I can't seem to find an easy solution to it. It's about an optimization problem, concerning a time series.
I have a binary variable $alpha_t$ for $t in [0, 24[$. I also have an extra constraint, which states that $$sum_{t=0}^{23} alpha_t geq 14.$$ The problem is that I want to add an extra constraint that if a certain $alpha_t = 1$, then either $$alpha_{t-1} = alpha_{t+1} = 1$$ or $$alpha_{t-1} = alpha_{t-2} = 1$$ or $$alpha_{t+1} = alpha_{t+2} = 1, $$ i.e. at least 3 consecutive times $alpha$ needs to be 1. It can be 4 times, it can be 5, but it has to be at least 3 times.
The most intuitive idea is probably this:
$$alpha_t = 1 Rightarrow alpha_t + alpha_{t+1} + alpha_{t + 2} = 3,$$ but from a certain $t$, this will result that all $alpha_t = 1$.
I also tried big M constraints, but for larger consecutive times ( $geq 3)$, this becomes almost impossible to write down/implement.
linear-programming binary integer-programming time-series constraints
linear-programming binary integer-programming time-series constraints
asked Nov 22 at 10:31
Riley
623414
asked Nov 22 at 10:31
Riley
623414
edited Dec 7 at 12:53
asked Nov 22 at 10:31
Riley
623414
asked Nov 22 at 10:31
Riley
623414
asked Nov 22 at 10:31
Riley
623414
623414
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
up vote
3
down vote
accepted
One simple way to enforce a run length of at least three, is to forbid patterns 010 and 0110. This can be modeled as:
$$ -x_t + x_{t+1} - x_{t+2} le 0 $$
and
$$ -x_t + x_{t+1} + x_{t+2} - x_{t+3} le 1 $$
A little bit of thought is needed to decide what to do at the borders, especially the first time period.
answered Nov 29 at 21:04
Erwin Kalvelagen
3,0442511
I thought about that too, but what about patterns like 110, 101, 011, etc? I want to generalize the method and I feel like this would get way out of hand way too soon for larger consecutive times.
– Riley
Dec 10 at 9:52
I don't think you fully understand what I suggested. You really only need to worry about 010 and 0110. (With some more thought needed near the boundaries of the planning period)
– Erwin Kalvelagen
Dec 10 at 10:10
that indeed seemed to be the case. Smart observation regarding the patterns!
– Riley
Dec 10 at 14:52
Not so smart. This is a fairly standard and often used approach. Most modelers are well aware of this.
– Erwin Kalvelagen
Dec 10 at 19:53
Apologies, novice modeler here. Small follow-up question: is there then also a way to formulate the constraint, that if one $x_t=1$ in an interval $[a, b]$, then all $x_t$ in $[a, b] $ have to be equal to 1? (Without using Big-$M$ constraints?)
– Riley
Dec 11 at 13:38
|
show 4 more comments
up vote
1
down vote
One method is to let $x_t$ denote the starting indices and $y_t$ denote the ending indices of the sequences of ones. For example, if $x=(0,1,0,0,0,1,0)$ and $y=(0,0,0,1,0,0,1)$, the sequence is $alpha=(0,1,1,1,0,1,1)$. You get the following constraints:
number of starting indices equals number of ending indices:
$$sum_t x_t = sum_t y_t$$cannot end a sequence unless it was started at least 3 periods prior:
$$y_i leq sum_{t=1}^{i-2}x_t-y_t quad forall i$$cannot start a new sequence before the previous one is closed:
$$x_i leq 1- sum_{t=1}^{i-1}(x_t-y_t) quad forall i$$relating $alpha$ to $x,y$:
$$alpha_i = sum_{t=1}^{i}x_t - sum_{t=1}^{i-1}y_t quad forall i$$
answered Nov 26 at 17:22
LinAlg
7,9361521
I think there's an error in your reasoning: when I implement this, I get only one $x_t = 1$, which results in some $alpha = (0, 0, ldots, 0, 1, 1, ldots , 1)$. In every case I tried (also by forcing some values of variables), it's as if there's a value of 1 in $alpha$, so must be everything else after that.
– Riley
Dec 7 at 13:28
@Riley you are right, I have corrected the errors.
– LinAlg
Dec 7 at 14:28
Unless I'm mistaken, this doesn't necessarily guarantee consecutiveness. Formulation nr 2 doesn't rule out the possibility of a 'zero gap'. Example: $alpha = (1,1,1,0,1), x=(1,0,0,0,1), y=(0,0,1,0,1)$
– Riley
Dec 10 at 13:07
@Riley the second constraint includes $y_5 leq x_1+x_2+x_3 - y_1 - y_2 - y_3$, which in your example is $y_5 leq 0$, so $y_5=1$ is infeasible
– LinAlg
Dec 10 at 15:40
add a comment |
up vote
0
down vote
I think I've got it:
use the reasoning in this post Integer linear programming constraint for maximum number of consecutive ones in a binary sequence.
Here, we have to look at the $alpha_t$ as zero's instead of ones. At this point, you can impose a maximum of consecutive zero's.
If the variable however has a value of one, then you can use big M constraints to set the sum of the next 3, equal to 3.
answered Nov 22 at 11:13
Riley
623414
You want to impose a minimum number of consecutive ones, so that reasoning does not apply. Using big-M is not necessary, see my other answer.
– LinAlg
Nov 26 at 17:26
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3008969%2fbinary-variables-in-time-series-integer-linear-programming%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
One simple way to enforce a run length of at least three, is to forbid patterns 010 and 0110. This can be modeled as:
$$ -x_t + x_{t+1} - x_{t+2} le 0 $$
and
$$ -x_t + x_{t+1} + x_{t+2} - x_{t+3} le 1 $$
A little bit of thought is needed to decide what to do at the borders, especially the first time period.
answered Nov 29 at 21:04
Erwin Kalvelagen
3,0442511
I thought about that too, but what about patterns like 110, 101, 011, etc? I want to generalize the method and I feel like this would get way out of hand way too soon for larger consecutive times.
– Riley
Dec 10 at 9:52
I don't think you fully understand what I suggested. You really only need to worry about 010 and 0110. (With some more thought needed near the boundaries of the planning period)
– Erwin Kalvelagen
Dec 10 at 10:10
that indeed seemed to be the case. Smart observation regarding the patterns!
– Riley
Dec 10 at 14:52
Not so smart. This is a fairly standard and often used approach. Most modelers are well aware of this.
– Erwin Kalvelagen
Dec 10 at 19:53
Apologies, novice modeler here. Small follow-up question: is there then also a way to formulate the constraint, that if one $x_t=1$ in an interval $[a, b]$, then all $x_t$ in $[a, b] $ have to be equal to 1? (Without using Big-$M$ constraints?)
– Riley
Dec 11 at 13:38
|
show 4 more comments
up vote
3
down vote
accepted
One simple way to enforce a run length of at least three, is to forbid patterns 010 and 0110. This can be modeled as:
$$ -x_t + x_{t+1} - x_{t+2} le 0 $$
and
$$ -x_t + x_{t+1} + x_{t+2} - x_{t+3} le 1 $$
A little bit of thought is needed to decide what to do at the borders, especially the first time period.
answered Nov 29 at 21:04
Erwin Kalvelagen
3,0442511
I thought about that too, but what about patterns like 110, 101, 011, etc? I want to generalize the method and I feel like this would get way out of hand way too soon for larger consecutive times.
– Riley
Dec 10 at 9:52
I don't think you fully understand what I suggested. You really only need to worry about 010 and 0110. (With some more thought needed near the boundaries of the planning period)
– Erwin Kalvelagen
Dec 10 at 10:10
that indeed seemed to be the case. Smart observation regarding the patterns!
– Riley
Dec 10 at 14:52
Not so smart. This is a fairly standard and often used approach. Most modelers are well aware of this.
– Erwin Kalvelagen
Dec 10 at 19:53
Apologies, novice modeler here. Small follow-up question: is there then also a way to formulate the constraint, that if one $x_t=1$ in an interval $[a, b]$, then all $x_t$ in $[a, b] $ have to be equal to 1? (Without using Big-$M$ constraints?)
– Riley
Dec 11 at 13:38
|
show 4 more comments
up vote
3
down vote
accepted
up vote
3
down vote
accepted
One simple way to enforce a run length of at least three, is to forbid patterns 010 and 0110. This can be modeled as:
$$ -x_t + x_{t+1} - x_{t+2} le 0 $$
and
$$ -x_t + x_{t+1} + x_{t+2} - x_{t+3} le 1 $$
A little bit of thought is needed to decide what to do at the borders, especially the first time period.
answered Nov 29 at 21:04
Erwin Kalvelagen
3,0442511
One simple way to enforce a run length of at least three, is to forbid patterns 010 and 0110. This can be modeled as:
$$ -x_t + x_{t+1} - x_{t+2} le 0 $$
and
$$ -x_t + x_{t+1} + x_{t+2} - x_{t+3} le 1 $$
A little bit of thought is needed to decide what to do at the borders, especially the first time period.
answered Nov 29 at 21:04
Erwin Kalvelagen
3,0442511
edited Dec 6 at 0:05
answered Nov 29 at 21:04
Erwin Kalvelagen
3,0442511
answered Nov 29 at 21:04
Erwin Kalvelagen
3,0442511
answered Nov 29 at 21:04
Erwin Kalvelagen
3,0442511
3,0442511
I thought about that too, but what about patterns like 110, 101, 011, etc? I want to generalize the method and I feel like this would get way out of hand way too soon for larger consecutive times.
– Riley
Dec 10 at 9:52
I don't think you fully understand what I suggested. You really only need to worry about 010 and 0110. (With some more thought needed near the boundaries of the planning period)
– Erwin Kalvelagen
Dec 10 at 10:10
that indeed seemed to be the case. Smart observation regarding the patterns!
– Riley
Dec 10 at 14:52
Not so smart. This is a fairly standard and often used approach. Most modelers are well aware of this.
– Erwin Kalvelagen
Dec 10 at 19:53
Apologies, novice modeler here. Small follow-up question: is there then also a way to formulate the constraint, that if one $x_t=1$ in an interval $[a, b]$, then all $x_t$ in $[a, b] $ have to be equal to 1? (Without using Big-$M$ constraints?)
– Riley
Dec 11 at 13:38
|
show 4 more comments
I thought about that too, but what about patterns like 110, 101, 011, etc? I want to generalize the method and I feel like this would get way out of hand way too soon for larger consecutive times.
– Riley
Dec 10 at 9:52
I don't think you fully understand what I suggested. You really only need to worry about 010 and 0110. (With some more thought needed near the boundaries of the planning period)
– Erwin Kalvelagen
Dec 10 at 10:10
that indeed seemed to be the case. Smart observation regarding the patterns!
– Riley
Dec 10 at 14:52
Not so smart. This is a fairly standard and often used approach. Most modelers are well aware of this.
– Erwin Kalvelagen
Dec 10 at 19:53
Apologies, novice modeler here. Small follow-up question: is there then also a way to formulate the constraint, that if one $x_t=1$ in an interval $[a, b]$, then all $x_t$ in $[a, b] $ have to be equal to 1? (Without using Big-$M$ constraints?)
– Riley
Dec 11 at 13:38
I thought about that too, but what about patterns like 110, 101, 011, etc? I want to generalize the method and I feel like this would get way out of hand way too soon for larger consecutive times.
– Riley
Dec 10 at 9:52
I thought about that too, but what about patterns like 110, 101, 011, etc? I want to generalize the method and I feel like this would get way out of hand way too soon for larger consecutive times.
– Riley
Dec 10 at 9:52
I don't think you fully understand what I suggested. You really only need to worry about 010 and 0110. (With some more thought needed near the boundaries of the planning period)
– Erwin Kalvelagen
Dec 10 at 10:10
I don't think you fully understand what I suggested. You really only need to worry about 010 and 0110. (With some more thought needed near the boundaries of the planning period)
– Erwin Kalvelagen
Dec 10 at 10:10
that indeed seemed to be the case. Smart observation regarding the patterns!
– Riley
Dec 10 at 14:52
that indeed seemed to be the case. Smart observation regarding the patterns!
– Riley
Dec 10 at 14:52
Not so smart. This is a fairly standard and often used approach. Most modelers are well aware of this.
– Erwin Kalvelagen
Dec 10 at 19:53
Not so smart. This is a fairly standard and often used approach. Most modelers are well aware of this.
– Erwin Kalvelagen
Dec 10 at 19:53
Apologies, novice modeler here. Small follow-up question: is there then also a way to formulate the constraint, that if one $x_t=1$ in an interval $[a, b]$, then all $x_t$ in $[a, b] $ have to be equal to 1? (Without using Big-$M$ constraints?)
– Riley
Dec 11 at 13:38
Apologies, novice modeler here. Small follow-up question: is there then also a way to formulate the constraint, that if one $x_t=1$ in an interval $[a, b]$, then all $x_t$ in $[a, b] $ have to be equal to 1? (Without using Big-$M$ constraints?)
– Riley
Dec 11 at 13:38
|
show 4 more comments
up vote
1
down vote
One method is to let $x_t$ denote the starting indices and $y_t$ denote the ending indices of the sequences of ones. For example, if $x=(0,1,0,0,0,1,0)$ and $y=(0,0,0,1,0,0,1)$, the sequence is $alpha=(0,1,1,1,0,1,1)$. You get the following constraints:
number of starting indices equals number of ending indices:
$$sum_t x_t = sum_t y_t$$cannot end a sequence unless it was started at least 3 periods prior:
$$y_i leq sum_{t=1}^{i-2}x_t-y_t quad forall i$$cannot start a new sequence before the previous one is closed:
$$x_i leq 1- sum_{t=1}^{i-1}(x_t-y_t) quad forall i$$relating $alpha$ to $x,y$:
$$alpha_i = sum_{t=1}^{i}x_t - sum_{t=1}^{i-1}y_t quad forall i$$
answered Nov 26 at 17:22
LinAlg
7,9361521
I think there's an error in your reasoning: when I implement this, I get only one $x_t = 1$, which results in some $alpha = (0, 0, ldots, 0, 1, 1, ldots , 1)$. In every case I tried (also by forcing some values of variables), it's as if there's a value of 1 in $alpha$, so must be everything else after that.
– Riley
Dec 7 at 13:28
@Riley you are right, I have corrected the errors.
– LinAlg
Dec 7 at 14:28
Unless I'm mistaken, this doesn't necessarily guarantee consecutiveness. Formulation nr 2 doesn't rule out the possibility of a 'zero gap'. Example: $alpha = (1,1,1,0,1), x=(1,0,0,0,1), y=(0,0,1,0,1)$
– Riley
Dec 10 at 13:07
@Riley the second constraint includes $y_5 leq x_1+x_2+x_3 - y_1 - y_2 - y_3$, which in your example is $y_5 leq 0$, so $y_5=1$ is infeasible
– LinAlg
Dec 10 at 15:40
add a comment |
up vote
1
down vote
One method is to let $x_t$ denote the starting indices and $y_t$ denote the ending indices of the sequences of ones. For example, if $x=(0,1,0,0,0,1,0)$ and $y=(0,0,0,1,0,0,1)$, the sequence is $alpha=(0,1,1,1,0,1,1)$. You get the following constraints:
number of starting indices equals number of ending indices:
$$sum_t x_t = sum_t y_t$$cannot end a sequence unless it was started at least 3 periods prior:
$$y_i leq sum_{t=1}^{i-2}x_t-y_t quad forall i$$cannot start a new sequence before the previous one is closed:
$$x_i leq 1- sum_{t=1}^{i-1}(x_t-y_t) quad forall i$$relating $alpha$ to $x,y$:
$$alpha_i = sum_{t=1}^{i}x_t - sum_{t=1}^{i-1}y_t quad forall i$$
answered Nov 26 at 17:22
LinAlg
7,9361521
I think there's an error in your reasoning: when I implement this, I get only one $x_t = 1$, which results in some $alpha = (0, 0, ldots, 0, 1, 1, ldots , 1)$. In every case I tried (also by forcing some values of variables), it's as if there's a value of 1 in $alpha$, so must be everything else after that.
– Riley
Dec 7 at 13:28
@Riley you are right, I have corrected the errors.
– LinAlg
Dec 7 at 14:28
Unless I'm mistaken, this doesn't necessarily guarantee consecutiveness. Formulation nr 2 doesn't rule out the possibility of a 'zero gap'. Example: $alpha = (1,1,1,0,1), x=(1,0,0,0,1), y=(0,0,1,0,1)$
– Riley
Dec 10 at 13:07
@Riley the second constraint includes $y_5 leq x_1+x_2+x_3 - y_1 - y_2 - y_3$, which in your example is $y_5 leq 0$, so $y_5=1$ is infeasible
– LinAlg
Dec 10 at 15:40
add a comment |
up vote
1
down vote
up vote
1
down vote
One method is to let $x_t$ denote the starting indices and $y_t$ denote the ending indices of the sequences of ones. For example, if $x=(0,1,0,0,0,1,0)$ and $y=(0,0,0,1,0,0,1)$, the sequence is $alpha=(0,1,1,1,0,1,1)$. You get the following constraints:
number of starting indices equals number of ending indices:
$$sum_t x_t = sum_t y_t$$cannot end a sequence unless it was started at least 3 periods prior:
$$y_i leq sum_{t=1}^{i-2}x_t-y_t quad forall i$$cannot start a new sequence before the previous one is closed:
$$x_i leq 1- sum_{t=1}^{i-1}(x_t-y_t) quad forall i$$relating $alpha$ to $x,y$:
$$alpha_i = sum_{t=1}^{i}x_t - sum_{t=1}^{i-1}y_t quad forall i$$
answered Nov 26 at 17:22
LinAlg
7,9361521
One method is to let $x_t$ denote the starting indices and $y_t$ denote the ending indices of the sequences of ones. For example, if $x=(0,1,0,0,0,1,0)$ and $y=(0,0,0,1,0,0,1)$, the sequence is $alpha=(0,1,1,1,0,1,1)$. You get the following constraints:
number of starting indices equals number of ending indices:
$$sum_t x_t = sum_t y_t$$cannot end a sequence unless it was started at least 3 periods prior:
$$y_i leq sum_{t=1}^{i-2}x_t-y_t quad forall i$$cannot start a new sequence before the previous one is closed:
$$x_i leq 1- sum_{t=1}^{i-1}(x_t-y_t) quad forall i$$relating $alpha$ to $x,y$:
$$alpha_i = sum_{t=1}^{i}x_t - sum_{t=1}^{i-1}y_t quad forall i$$
answered Nov 26 at 17:22
LinAlg
7,9361521
edited Dec 7 at 14:28
answered Nov 26 at 17:22
LinAlg
7,9361521
answered Nov 26 at 17:22
LinAlg
7,9361521
answered Nov 26 at 17:22
LinAlg
7,9361521
7,9361521
I think there's an error in your reasoning: when I implement this, I get only one $x_t = 1$, which results in some $alpha = (0, 0, ldots, 0, 1, 1, ldots , 1)$. In every case I tried (also by forcing some values of variables), it's as if there's a value of 1 in $alpha$, so must be everything else after that.
– Riley
Dec 7 at 13:28
@Riley you are right, I have corrected the errors.
– LinAlg
Dec 7 at 14:28
Unless I'm mistaken, this doesn't necessarily guarantee consecutiveness. Formulation nr 2 doesn't rule out the possibility of a 'zero gap'. Example: $alpha = (1,1,1,0,1), x=(1,0,0,0,1), y=(0,0,1,0,1)$
– Riley
Dec 10 at 13:07
@Riley the second constraint includes $y_5 leq x_1+x_2+x_3 - y_1 - y_2 - y_3$, which in your example is $y_5 leq 0$, so $y_5=1$ is infeasible
– LinAlg
Dec 10 at 15:40
add a comment |
I think there's an error in your reasoning: when I implement this, I get only one $x_t = 1$, which results in some $alpha = (0, 0, ldots, 0, 1, 1, ldots , 1)$. In every case I tried (also by forcing some values of variables), it's as if there's a value of 1 in $alpha$, so must be everything else after that.
– Riley
Dec 7 at 13:28
@Riley you are right, I have corrected the errors.
– LinAlg
Dec 7 at 14:28
Unless I'm mistaken, this doesn't necessarily guarantee consecutiveness. Formulation nr 2 doesn't rule out the possibility of a 'zero gap'. Example: $alpha = (1,1,1,0,1), x=(1,0,0,0,1), y=(0,0,1,0,1)$
– Riley
Dec 10 at 13:07
@Riley the second constraint includes $y_5 leq x_1+x_2+x_3 - y_1 - y_2 - y_3$, which in your example is $y_5 leq 0$, so $y_5=1$ is infeasible
– LinAlg
Dec 10 at 15:40
I think there's an error in your reasoning: when I implement this, I get only one $x_t = 1$, which results in some $alpha = (0, 0, ldots, 0, 1, 1, ldots , 1)$. In every case I tried (also by forcing some values of variables), it's as if there's a value of 1 in $alpha$, so must be everything else after that.
– Riley
Dec 7 at 13:28
I think there's an error in your reasoning: when I implement this, I get only one $x_t = 1$, which results in some $alpha = (0, 0, ldots, 0, 1, 1, ldots , 1)$. In every case I tried (also by forcing some values of variables), it's as if there's a value of 1 in $alpha$, so must be everything else after that.
– Riley
Dec 7 at 13:28
@Riley you are right, I have corrected the errors.
– LinAlg
Dec 7 at 14:28
@Riley you are right, I have corrected the errors.
– LinAlg
Dec 7 at 14:28
Unless I'm mistaken, this doesn't necessarily guarantee consecutiveness. Formulation nr 2 doesn't rule out the possibility of a 'zero gap'. Example: $alpha = (1,1,1,0,1), x=(1,0,0,0,1), y=(0,0,1,0,1)$
– Riley
Dec 10 at 13:07
Unless I'm mistaken, this doesn't necessarily guarantee consecutiveness. Formulation nr 2 doesn't rule out the possibility of a 'zero gap'. Example: $alpha = (1,1,1,0,1), x=(1,0,0,0,1), y=(0,0,1,0,1)$
– Riley
Dec 10 at 13:07
@Riley the second constraint includes $y_5 leq x_1+x_2+x_3 - y_1 - y_2 - y_3$, which in your example is $y_5 leq 0$, so $y_5=1$ is infeasible
– LinAlg
Dec 10 at 15:40
@Riley the second constraint includes $y_5 leq x_1+x_2+x_3 - y_1 - y_2 - y_3$, which in your example is $y_5 leq 0$, so $y_5=1$ is infeasible
– LinAlg
Dec 10 at 15:40
add a comment |
up vote
0
down vote
I think I've got it:
use the reasoning in this post Integer linear programming constraint for maximum number of consecutive ones in a binary sequence.
Here, we have to look at the $alpha_t$ as zero's instead of ones. At this point, you can impose a maximum of consecutive zero's.
If the variable however has a value of one, then you can use big M constraints to set the sum of the next 3, equal to 3.
answered Nov 22 at 11:13
Riley
623414
You want to impose a minimum number of consecutive ones, so that reasoning does not apply. Using big-M is not necessary, see my other answer.
– LinAlg
Nov 26 at 17:26
add a comment |
up vote
0
down vote
I think I've got it:
use the reasoning in this post Integer linear programming constraint for maximum number of consecutive ones in a binary sequence.
Here, we have to look at the $alpha_t$ as zero's instead of ones. At this point, you can impose a maximum of consecutive zero's.
If the variable however has a value of one, then you can use big M constraints to set the sum of the next 3, equal to 3.
answered Nov 22 at 11:13
Riley
623414
You want to impose a minimum number of consecutive ones, so that reasoning does not apply. Using big-M is not necessary, see my other answer.
– LinAlg
Nov 26 at 17:26
add a comment |
up vote
0
down vote
up vote
0
down vote
I think I've got it:
use the reasoning in this post Integer linear programming constraint for maximum number of consecutive ones in a binary sequence.
Here, we have to look at the $alpha_t$ as zero's instead of ones. At this point, you can impose a maximum of consecutive zero's.
If the variable however has a value of one, then you can use big M constraints to set the sum of the next 3, equal to 3.
answered Nov 22 at 11:13
Riley
623414
I think I've got it:
use the reasoning in this post Integer linear programming constraint for maximum number of consecutive ones in a binary sequence.
Here, we have to look at the $alpha_t$ as zero's instead of ones. At this point, you can impose a maximum of consecutive zero's.
If the variable however has a value of one, then you can use big M constraints to set the sum of the next 3, equal to 3.
answered Nov 22 at 11:13
Riley
623414
answered Nov 22 at 11:13
Riley
623414
answered Nov 22 at 11:13
Riley
623414
answered Nov 22 at 11:13
Riley
623414
623414
You want to impose a minimum number of consecutive ones, so that reasoning does not apply. Using big-M is not necessary, see my other answer.
– LinAlg
Nov 26 at 17:26
add a comment |
You want to impose a minimum number of consecutive ones, so that reasoning does not apply. Using big-M is not necessary, see my other answer.
– LinAlg
Nov 26 at 17:26
You want to impose a minimum number of consecutive ones, so that reasoning does not apply. Using big-M is not necessary, see my other answer.
– LinAlg
Nov 26 at 17:26
You want to impose a minimum number of consecutive ones, so that reasoning does not apply. Using big-M is not necessary, see my other answer.
– LinAlg
Nov 26 at 17:26
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3008969%2fbinary-variables-in-time-series-integer-linear-programming%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
