search

google / or-tools

Google's Operations Research tools:
https://developers.google.com/optimization/
Apache License 2.0
11k stars 2.11k forks source link

MIP: Setting a lower bound on a maximization problem gives me a better "optimal" solution #1175

Closed Jcortesconde closed 5 years ago

Jcortesconde commented 5 years ago

Hello, I have a weird issue. I have a maximization problem and whenever I run it with the basic restrictions it gives me an optimal awnser. Where the optimal is to set all the variables im maximizing to 0. which is weird, cause I know for a fact you can go higher than that. So I decided to make a lower bound and force the variables to be higher than 0, after a few seconds a new optimal answer is once again found, this time is close to the lower bound, a little bit higher. But I know for a fact that I can go even higher, and so I set an even higher lower bound, the solver found another optimal solution and I keep going.

I can't understand why a maximization problem would do such a thing. If need be I can show some code, in worst case scenario I could give the full folder so it could be run (excel and python files)

Im using cbc solver and python btw. Please any help or insight would be appreciated as I been fighting this bug for a couple of days, hopefully it is a bug on my coding.

PD: I cant seem to make the Markdown math symbols to work, so I'll add the problem later.

Jcortesconde commented 5 years ago

Horrible md formatting by github, however it can be seen okey with other md readers, I use jupyter notebook (a little bit overkill).
When i Get home ill try to do the pdf version. Here is the code that im using to run the solver... well the important bits, the functions I call are already validated. Thanks

lperron commented 5 years ago

I would not trust cbc. Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le ven. 5 avr. 2019 à 21:13, Jcortesconde notifications@github.com a écrit :

Horrible md formatting by github https://gist.github.com/Jcortesconde/8538fddbbaea99e698900a78de90fd2c, however it can be seen okey with other md readers, I use jupyter notebook (a little bit overkill). When i Get home ill try to do the pdf version. Here https://pastebin.com/YRHv1PH0 is the code that im using to run the solver... well the important bits, the functions I call are already validated. Thanks

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/1175#issuecomment-480391111, or mute the thread https://github.com/notifications/unsubscribe-auth/AKj17SdBGm0Rowyj1Dg-zFOYbXtln9IWks5vd6BjgaJpZM4cfd0M .

Jcortesconde commented 5 years ago

Is there any free solvers you recommend using? and whats the problem with cbc if you don't mind explaining?

lperron commented 5 years ago

CBC can be false. Super optimal, stop search too early.

You can use the CP-SAT solver as your problem is purely integral. The API is close.

Create a CpModel first.

IntVar -> NewIntVar Solver.Sum([...]) -> sum(...)

The create the solver and solve.

See https://github.com/google/or-tools/blob/stable/ortools/sat/doc/integer_arithmetic.md#python-code Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le ven. 5 avr. 2019 à 23:58, Jcortesconde notifications@github.com a écrit :

Is there any free solvers you recommend using? and whats the problem with cbc if you don't mind explaining?

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/1175#issuecomment-480435145, or mute the thread https://github.com/notifications/unsubscribe-auth/AKj17QufFZ302EWI_y7gHWKNOMkqwmDMks5vd8cVgaJpZM4cfd0M .

Jcortesconde commented 5 years ago

Okey, for now I will migrate everything to CP-SAT. But I would like to try and help in solving this issue via the use of CBC or any other solver... As it would be bad for someone who would trust in the tool. So if anyone wants a hand I can provide with whatever they need. Thanks for the help.

lperron commented 5 years ago

You can send the model to ted ralphs, CBC maintainer. Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le lun. 8 avr. 2019 à 14:21, Jcortesconde notifications@github.com a écrit :

Okey, for now I will migrate everything to CP-SAT. But I would like to try and help in solving this issue via the use of CBC or any other solver... As it would be bad for someone who would trust in the tool. So if anyone wants a hand I can provide with whatever they need. Thanks for the help.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/1175#issuecomment-480808558, or mute the thread https://github.com/notifications/unsubscribe-auth/AKj17bOfKgJXwAH8RbabOD5EnJrFxg4Yks5vezQ2gaJpZM4cfd0M .

Jcortesconde commented 5 years ago

I'll Contact him right away... well, whenever I have time to be useful.

So I have migrated part of the problem to CP-SAT, but I seem to encounter the same issue... Even though I maximize production it makes me produce almost nothing. I know it can be done, as there are no restrictions besides one.

I found something weird (maybe its not). So i have a restriction that goes produced + inventory > demand. Where produced and demand are variables that have to be found by the solver, and invetory is a fixed number. However if I dont create a newIntVar(1,1,"dummy") I have the following error: TypeError: Not supported: CpModel.Add(True)

It seems I bypassed that error creating that dummy "variable". But I still havent maximize demand produced. Any clues? Thanks

lperron commented 5 years ago

I have no context for the dummy variable. Where does it appear ? Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le lun. 8 avr. 2019 à 19:55, Jcortesconde notifications@github.com a écrit :

I'll Contact him right away... well, whenever I have time to be useful.

So I have migrated part of the problem to CP-SAT, but I seem to encounter the same issue... Even though I maximize production it makes me produce almost nothing. I know it can't be done, as there are no restrictions besides one.

I found something weird (maybe its not). So i have a restriction that goes produced + inventory > demand. Where produced and demand are variables that have to be found by the solver, and invetory is a fixed number. However if I dont create a newIntVar(1,1,"dummy") I have the following error: TypeError: Not supported: CpModel.Add(True)

It seems I bypassed that error creating that dummy "variable". But I still havent maximize demand produced. Any clues? Thanks

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/1175#issuecomment-480937590, or mute the thread https://github.com/notifications/unsubscribe-auth/AKj17Ulec5KmQjdJ1kAJ7qSOBa0-PVdaks5ve4KngaJpZM4cfd0M .

Jcortesconde commented 5 years ago

I have two sets of variables, The amount I will produced of a certain item and The amount that will be demanded. But I also have an initial inventory. I want to maximize the amount to be demanded, however the real output is what to produced each month. Lets say we have only one product. Sow we have a restriction that is for every time t: produced(t) + inventory > demand(t) and we want to solve: Max(demand(t))

If I dont link inventory with a IntVar I got the error described before. My solution was to have a new variable, which is set to 1, thats why I call it dummy. and the restriction goes like produced(t) + dummy*inventory > demand(t)

However I don't think that is why I am not maximizing demand.

lperron commented 5 years ago

It means you are creating an expression that does not contain any IntVar or BoolVar. This one will be interpreted by python into True or False.

This will be accepted by the solver, but most likely there is an error in your code.