IP solvers

[alanctprado]

So far, we have only experimented with LP Solve. We should come up with other IP solvers in order to check the performance differences.

Possible solvers should be listed as comments below.

[alanctprado]

1) Gurobi

[alanctprado]

2. OR-Tools

[alanctprado]

3. HiGHS

[alanctprado]

4. coin-or

[alanctprado]

5. GLPK

[alanctprado]

1. Gurobi

sh run_case.sh medium-set 15 --ipsolver="lpsolve" 7.91s user 0.04s system 99% cpu 7.966 total sh run_case.sh medium-set 15 --ipsolver="gurobi" 0.67s user 0.08s system 111% cpu 0.665 total

[alanctprado]

1. Gurobi

sh run_case.sh medium-set 30 --ipsolver="lpsolve" 398.04s user 0.33s system 99% cpu 6:40.16 total sh run_case.sh medium-set 30 --ipsolver="gurobi" 4.39s user 0.28s system 100% cpu 4.663 total

[alanctprado]

1. Gurobi

I think it is pretty clear from a few tests that Gurobi scales drastically better than LPSolve. Nevertheless, it is quite bad for instances with 500 vertices and over (which basically all instances from the exact-set have). The bottleneck is definitely the $N^3$ transitivity constraints. But i think that these tests pave the way forward:

1. We should test open-source MIP solvers to find one that has a performance that is somehow similar to Gurobi's.
2. If we are going to use IP in the exact track, we could use a better formulation of the problem (if one exists). But this holds as a possibility.
3. It is definitely worth it to consider some heuristic which reduces the number of cardinality constraints for a submission on the Heuristic track. I believe me and @MvKaio can get this done by this week. BTW, I have tested Gurobi's performance on the relaxed problem - without integer constraints - and it finds the optimum in all cases of the tiny and medium sets (the ones that run without crashing my computer's memory for the latter xD)

[luishgh]

I'll work on testing OR-Tools @alanctprado.

[luishgh]

Closed by #26