Questions about MIP

[CardosoGuiVi]

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?

[sebheger]

@CardosoGuiVi

Maybe your questions have been already answered, but first of all, I just want to make some clarifications.

The python-MIP package is not a solver itself. It provides an API with methods and parameters to model linear and integer programs (or mixed ones) in python language and lets them be solved by either the open-source CBC solver (https://github.com/coin-or/Cbc) or the commercial gurobi solver (www.gurobi.com), both written in C programming language.

And CBC in comparison to gurobi has in many general cases a slower runtime on larger/complex models - but CBC is free to use. Also, many of your questions relate to tuning the parameters of the solving algorithm. There is a lot of material with free access on the web. Just google for performance tuning mixed integer programs. A lot of the things there could be applied to any MI(L)P branch-and-cut solver, like e.g. CBC or gurobi are.