Linear programming counter variable

Question

I have a binary variable X_i and an integer variable Y_i

I want to use Y as a counter in such a way that Y_i is reset to 0 every time X_i = 1

Is it possible to find constraints that would allow me to do it ?

Here is an example :

X : 001011001

Y : 120100120

edit :

Here are the constraints I find, using a linearization of

y(i) = (y(i-1)+1)*(1-x(i))

:

y[1] == (1-x[1])
    for i in 2:N
        y[i] <= 10000*(1-x[i])
        y[i] <= y[i-1] + 1
        y[i] >= y[i-1] + 1 - 10000*x[i]

And here are some results I get

x : 0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,1,1,1
y : 1,2,3,4,5,6,7,8,0,1,2,3,0,1,0,0,0,-9999

or

x : 0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,1,1
y : 1,2,3,4,5,6,7,8,9,0,-9999,-19998,-29997,-39996,-49995,-49994,-59993,-69992

What am I doing wrong ?

A LP/MIP is a static problem. If you want something dynamic you have to discretize your time. That means here: you will have one X-var and one Y-var for each time tick. Then it's just a problem of formulating boolean logic (implication + or). — sascha
– sascha, Commented Nov 28, 2017 at 17:09
Yes, that's actually what I have (ILP), I thought it was called the same, my mistake. So from there, any tips on how I can formulate the problem ? — user3548298
– user3548298, Commented Nov 28, 2017 at 17:27
I already did. Look up indicator-constraints or logical-constraints in MIP for common formulations and try something. And start by creating propositional-logic which solves this task, then think about linearization of this. — sascha
– sascha, Commented Nov 28, 2017 at 17:28

Erwin Kalvelagen · Accepted Answer · 2017-11-29 06:21:33Z

1

You can express this as:

 y(i) = (y(i-1)+1)*(1-x(i))

This can be linearized (link) or handled by indicator constraints.

answered Nov 29, 2017 at 6:21

Erwin Kalvelagen

16.9k3 gold badges18 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

user3548298 Over a year ago

Here are the constraints I find, using your method y[1] == (1-x[1]) for i in 2:N y[i] <= 10000*(1-x[i]) y[i] <= y[i-1] + 1 y[i] >= y[i,j-1] + 1 - 10000*x[i] Here is the result I get x : 0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,1,1,1 y : 1,2,3,4,5,6,7,8,0,1,2,3,0,1,0,0,0,-9999 What am I doing wrong ? (edit : how do I write code and carriage return when replying here ? The formatting is awful)

Erwin Kalvelagen Over a year ago

Check your code: y[i] >= y[i,j-1] + 1 - 10000*x[i]. y[i,j-1] looks strange. Also add y[i]>=0.

user3548298 Over a year ago

It's because in my project I use multiple rows, don't mind the j, it should have been y[i-1]

user3548298 Over a year ago

It works perfectly with the y[i] >= 0 condition ! Thanks ! I also witnessed the issue that is mentionned when M is too high. Awesome. What I'm kind of wondering now is : isn't this notation too heavy ? Is there a way to decrease the number of conditions or is this something I'm forced to deal with ?

Erwin Kalvelagen Over a year ago

As said earlier, you can use indicator constraints.

Collectives™ on Stack Overflow

Linear programming counter variable

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related