3

I'm trying to formulate a constraint for an optimization problem that forces the solution (a combination of products, represented by binary numbers to signify if they got picked or not) to have a certain property in order.

So let's say products 1, 2 and 5 got selected, that solution is represented by [1, 1, 0, 0, 1]. These products have another property (location) that has to be in order. A Python function for checking would be:

def products_in_order(products_selected):
    locations = [p.location for p in products_selected]
    # locations = [80, 79, 81] (for instance) 
    return max(locations) - min(locations) <= 2

(This works because they're never in the same location)

However, it gets harder. The maximum location is 99, wrapping around: so [98, 99, 0] is a valid solution as well.

There are always exactly three products selected.

Thanks for any help you can give, I've been struggling with this for quite some time. Right now I'm enumerating all possible configurations, resulting in 100 constraints (which makes things sloooow).

JR

Improve this question

2 Answers 2

Reset to default
1

I ended up solving this problem with a meta solution, that a friend of mine came up with.

Since choosing the product with position X infers the other allowed choices (namely X+1 and X+2) it makes sense to optimize on groups of products, not on individual products. I've built this and it works beautifully.

Thanks for the responses!

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

1 Comment

It's been a few years, but is it possible to elaborate a bit more the solution? It seems to be independent of the originally asked question, is this why you call it "meta"?
0

The condition you are looking for is

return abs( mod( max(locations) - min(locations) +50,100)-50) <=2

or in a general form:

abs(mod( distance + range/2,range)-range/2)

This gives the minimum distance in a circular space. It is commonly used to compute the angular distance of 2 given points in a circle, where range is 2*pi and distance is angle2-angle1

Improve this answer

8 Comments

@ayhan the constrain he talks about is neither linear. You can linearize it by writing it 100 times I guess....
Awesome, thank you very much! I'll investigate and accept in the coming day or two.
These specific functions (abs, mod, min, max) are not linear indeed. I have no way of presenting this to a MIP Solver. I ended up solving this with a meta solution that a friend of mine came up with. I'll post it for completion.
Please do. I knew they are not linear, was just giving my two cents! Glad you solved it.
@J.Schmidt that is what non-linear means yes. abs and mod are non-linear and thus the equation is non-linear: en.wikipedia.org/wiki/Nonlinear_system . The amount of looping is irrelevant.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.