There are quite a few modeling tools available for Python: Pyomo, PuLP, and most commercial LP/MIP solvers come with some Python modeling layer.
This is what caught my eye when reading about Python-MIP:
- The name is rather unimaginative.
- Looks like the authors are from Brazil.
- Supported solvers are CBC and Gurobi.
- The Python-MIP is compatible with the just-in-time compiler PyPy, which can lead to substantial performance improvements.
- It is claimed that with PyPy jit, python-MIP can be 25 times as fast than the Gurobi modeling tool.
- There are some interesting facilities supported by Python-MIP:
- Cuts can be provided using a call-back mechanism
- Support for MIPSTART (initial integer solution)
- Solution pool
Interesting question
Related to Python-MIP, in [3] an interesting question came up. The value of an integer variable is often slightly non-integer. E.g. something like 0.0000011625. This is the result of the integer feasibility tolerance that a solver applies.
Background: during the MIP search quite a lot of integer variables are automatically (or by accident) integer valued. To exploit this, and not wasting time branching on these variables, a MIP solver wants to consider variables that are close to being integer as integer. Basically, skipping these variables when branching.
In the discussion [3] the remark is made:
Is rounding integer solutions automatically a good idea? No MIP solver or modeling system is doing this AFAIK The exceptions are modeling tools mainly targeting Constraint Programming solvers. Here are some arguments against this rounding strategy.
Rounding integer solutions can lead to larger infeasibilities. With some aggressive presolve/scaling these infeasibilities can sometimes be large after postsolve/unscaling. Also: some equations may have long summations of binary variables. This would accumulate a lot of rounding errors. And then there are these big-M constraints....
It also means that using the steps:
solve
fix solution (or fix integers) to optimal solution
solve
may lead to "feasible" for the first solve, but "infeasible" for the second solve. E.g. when we want duals for the fixed LP we use this "fix integers" step.
Safer would be to tighten the integer feasibility tolerance. Cplex even allows epint=0 (epint is Cplex's integer feasibility tolerance). Of course tightening the integer feasibility tolerance will likely lead to longer solution times.
Indeed, modeling systems and solvers currently handle this by offloading the problem to the user. The solver is probably the right place to deal with this. Not sure developers are eager to work on this. Taking responsibility by simple-minded rounding may be asking for more problems than it solves.
On the other hand, these slightly fractional values certainly cause confusion. Especially for beginners in MIP modeling. This is the main argument in favor of automatic rounding.
So the question remains: is rounding integer variables a good idea?
So the question remains: is rounding integer variables a good idea?
It isn't, for exactly the reason you mentioned. The user can get the solution cleaned up if it is necessary, typically when binaries are used in bigM constraints. I'd even argue that if the optimal solution turns out to be slightly fractional (tolerance), and rounding it leads to infeasibility or a significant change in the objective value, then the model is malformed, and doesn't really convey what the modeler had intended.
ReplyDelete