Questions about MIP
Guilherme Cardoso
First of all, congratulate you on the excellent work in python MIP.
In search of knowledge about linear and integer programming, we found Professor Túlio Toffolo's classes, where we were led to this open source project, having Professor Túlio and Professor Haroldo as authors.
I represent a team of 3 researchers (2 engineering, electrical and mechanical students, and a master in electrical engineering), and we raised some questions about the module:
How is the “best possible” value estimated? What does it mean if this value is a non integer and it keeps changing along the iterations of the optimization?
Is there a class of complex problems that can’t be solved using the Python MIP? Like the RCPSP/max-cal or MRCPSP (Variants of the Resource-constrained Project Scheduling Problem)
What is the stop criteria of the optimizer? In some cases, it converges to a value that doesn’t correspond to the “best possible” estimated, and in Other cases it Only converges When the “best possible” value changes and matches with the solution found.
What are the main hyperparameters of the optimizer that we should change to help in the solution of complex and large scaled problems?
Is there a different method to estimate the initial solution? Even in simple RCPSP cases and with the maximum iteration of the feasible pump method (100), it was not possible to found this solution in the initial stage of the optimizer.
In many cases, the solver seems to get stucked in a “local minumum”. Is there any strategy to avoid this situation and speed up the optimization process?
Luciano Rigolin de Almeida
--
You received this message because you are subscribed to the Google Groups "Python-MIP" group.
To unsubscribe from this group and stop receiving emails from it, send an email to python-mip+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/python-mip/8239f1bb-0dbf-4bb8-9b34-5bb3fe0e1da9n%40googlegroups.com.
Guilherme Cardoso
- How is the “best possible” value estimated? What does it mean if this value is a non integer and it keeps changing along the iterations of the optimization?
- What is the stop criteria of the optimizer? In some cases, it converges to a value that doesn’t correspond to the “best possible”, and in Other cases (like in the second image) it only converges when the “best possible” value changes and matches with the solution found (The optimal solution is 222).
- In many cases, the solver seems to get stucked in a “local minumum” (1e+50 for large problems). Am I doing anything wrong or there is any strategy to avoid this situation and speed up the optimization process?
Luciano Rigolin de Almeida
I think the best possible has to do with the values already found in the Branch and Cut trees. The best possible value found is the best value found so far. If it's a non-integer value, it will definitely be discarded.
Are you using a timeout? If not, try using it to see the solution that returns has the value of the last best possible.
As for the stopping criterion, if I understand Branch and Cut well, it is when there are no more nodes in the tree with non-integer solutions.
I have been using Gurobi solver instead of CBC. I found it faster. And Gurobi's outputs are different from CBC's, so I didn't realize about best possible. You can get an academic license from Gurobi.
Hi, Luciano.Maybe I didn't explain it correctly, I'll try to be more didactic.I am working with a Resource constrained Project Scheduling Problem (RCPSP), it’s a combinatorial optimization problem and that consists of finding a feasible scheduling for a set of n jobs subject to resource and precedence constraints. Each job has a processing time, a set of successors jobs and a required amount of different resources. Resources may be scarce but are renewable at each time period. Precedence constraints between jobs mean that no jobs may start before all its predecessors are completed. Using Python MIP with a binary formulation (Pritsker, 1969) was a success, with good results and a low processing time. However, my next step was to add a calendar of business days throught the duration of the tasks, for example, if a task has a processing time of 5 days and it starts on Wednesday it should end on Tuesday (because Saturday and Sunday are not business days), so now the task has a total duration of 7 days, and it changes the precedences and resources constrains.So I did a new formulation for this new problem, with the same binary approach but with some new features (Kreter, 2016). After that the processing time of the Python MIP has increased a lot, sometimes it seems impossible to get a result. Besides that I noticed some weird behaviour on Python MIP logs.
- How is the “best possible” value estimated? What does it mean if this value is a non integer and it keeps changing along the iterations of the optimization?
- What is the stop criteria of the optimizer? In some cases, it converges to a value that doesn’t correspond to the “best possible”, and in Other cases (like in the second image) it only converges when the “best possible” value changes and matches with the solution found (The optimal solution is 222).
- In many cases, the solver seems to get stucked in a “local minumum” (1e+50 for large problems). Am I doing anything wrong or there is any strategy to avoid this situation and speed up the optimization process?
Best regards,Guilherme Cardoso
Em quarta-feira, 21 de julho de 2021 às 06:16:22 UTC-3, luciano...@gmail.com escreveu:
To view this discussion on the web visit https://groups.google.com/d/msgid/python-mip/d8ad4a3f-1cf7-4d8c-9670-19c4e4ac8ab1n%40googlegroups.com.