Constraint in optimization problem

2015 3 19
3 个回答
回答已采纳
更新时间：2015 3 22
9 次查看（30 天）

0 个投票

Hello all,
I would like to kindly ask for your help, if you are familiar with optimization stuff...
Do you know how I can introduce a constraint in order to avoid having a vector solution without consecutive '1s' (either the number of '1' are two, or three etc)? (Let's say the vector is y and takes 6 binary values)
For example: vector1 = [1 0 1 0 0 0]
vector2 = [0 0 1 1 0 1]
vector3 = [1 0 0 0 1 0]
vector4 = [0 0 1 0 0 1]
are not valid solutions, but:
vector5 = [1 0 0 0 0 0]
vector6 = [0 0 1 1 1 0]
vector7 = [0 1 1 0 0 0]
vector8 = [0 0 1 0 0 0]
vector9 = [1 1 1 0 0 0]
are valid. I am really stuck with it!
Best regards, Chris

请先登录，再回答此问题。

 采纳的回答

Alan Weiss
Alan Weiss 2015-3-19

0 个投票

I am sorry, but I do not understand your constraint. Are "consecutive" in one vector? I see nothing wrong with vector1, vector3, or vector4 in terms of consecutive 1s. And vector6, vector7, and vector 9 seem to have consecutive 1s. So what is your constraint, in words or a formula?
Alan Weiss
MATLAB mathematical toolbox documentation

6 个评论
显示 4更早的评论 隐藏 4更早的评论

Chris B
Chris B 2015-3-19
Sorry for the misunderstanding, it is my fault that I didn't write it properly...
It would be an acceptable solution if I have two or three consecutive '1s', or just one, but without any other '1'... Any different solution should be undesirable.
For example, vector2 has two consecutive '1s', then a '0' and then again a '1'.. And we only want only one, or two, or three or more consecutive.
Alan Weiss
Alan Weiss 2015-3-19
If I understand you correctly, you are looking for a solution to have a single block of 1s, where a block is one or more consecutive 1s, but no more than one block is acceptable.
Also, you are using the intlinprog solver. That is another important problem detail.
Is this new understanding correct? If so, I will have to think whether I can come up with a constraint. Perhaps you will need to add some auxiliary variables, such as in this example, which may very well have the solution in it.
Alan Weiss
MATLAB mathematical toolbox documentation
Chris B
Chris B 2015-3-19
Yes, exactly what you said!
For example, if I set a factor 'a' that signifies the number of possible consecutive '1s', I accept as an answer a vector that has one or two or .. or 'a' AT MOST consecutive '1s'...
Thank you so much for your time!
Alan Weiss
Alan Weiss 2015-3-20
I believe that the link I gave you has the answer to your question. You need to introduce variables z(i,j) that are 1 when the vector(i,j) goes from 0 to 1, and z(i,j) = 0 otherwise. The example shows how to do this. Then make a constraint that in any row no more than one z(i,j) can be 1. The example in the link has a slightly more complex version of this constraint, so your problem fits easily.
Alan Weiss
MATLAB mathematical toolbox documentation
Chris B
Chris B 2015-3-20
Thank you for you answer!!! I think that in this way it solves everything, but it excludes the possibility of having [1 0 0 0 0 ... 0 0 0]...
Chris B
Chris B 2015-3-22
Hello Alan,
It is finally solved with another introduced variable as you said, with slight enhancements! Thanks again all for your time.

请先登录，再进行评论。

更多回答（2 个）

Torsten
Torsten 2015-3-19

0 个投票

x(i) + x(i+1) <= 1
Best wishes
Torsten.

1 个评论
显示 -1更早的评论 隐藏 -1更早的评论

Chris B
Chris B 2015-3-19
编辑：Chris B 2015-3-19
Thank you for your answer.
This one violates the case of having two consecutive '1s', that is something acceptable and it doesn't work for it!

请先登录，再进行评论。

John D'Errico
John D'Errico 2015-3-19
编辑：John D'Errico 2015-3-19

0 个投票

You don't say what optimization tool you are working with. But as long as your favorite optimizer (intlinprog maybe) can handle inequality constraints, then just specify
x(1) + x(2) <= 1
x(2) + x(3) <= 1
x(3) + x(4) <= 1
x(4) + x(5) <= 1
x(5) + x(6) <= 1

1 个评论
显示 -1更早的评论 隐藏 -1更早的评论

Chris B
Chris B 2015-3-19
Thank you for your reply as well.
Yes, I am using intlinprog as a solver... According to your specifications, [1 1 0 0 0 0] is not an acceptable solution, but it should be..
The thing is that I only want either one '1' in the vector solution, or if it is two, two consecutive '1s', if it is three, three consecutive '1s' etc..

请先登录，再进行评论。

类别

在 帮助中心 和 File Exchange 中查找有关 Systems of Nonlinear Equations 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by