Constraint in optimization problem

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

Answer 1

[Alan Weiss]

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

[Chris B]

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]

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]

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]

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]

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]

Hello Alan,

It is finally solved with another introduced variable as you said, with slight enhancements! Thanks again all for your time.

Answer 2

[Torsten]

x(i) + x(i+1) <= 1

Best wishes

Torsten.

[Chris B]

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!

Answer 3

[John D'Errico]

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

[Chris B]

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..