Parameter tuning

[Fondry]

Hi Highs team,

First of all, congratulations on the work you are doing with this solver, i am sure it is not a easy task for an open source group.

I contacted you because right now I am working on a production scheduling optimization on my company and, for the solving time that we are aiming for (which is about 15 minutes if possible), the HIGHS solver is able to reach optimal or near optimal solutions for easy schedules, but when the schedules become more complex (longer optimization horizons, weeks with harder constraints to satisfy, etc.), the solver cannot get good solutions on the limited time we give it.

To deal with this problem, we are trying commercial solvers such as Gurobi and CPLEX. Those solvers have a dedicated tuning tool and in both cases, the tuning tools are improving the optimization results by using more heuristics (In gurobi, with Presolve=2 and Heuristics=0.5 https://docs.gurobi.com/projects/optimizer/en/12.0/concepts/parameters/groups.html#mip and in CPLEX by using the mip emphasis setting 5 https://www.ibm.com/docs/en/icos/22.1.2?topic=optimizer-emphasizing-feasibility-optimality ).

I am curious on what i can try to improve the HIGHS solver. I can program a script with Python and Optuna (https://optuna.readthedocs.io/en/stable/) to search for better parameters, but i have no idea on which ones to try.

Can you give me some hints on which parameters could affect the solver the most?

Thank you for your time and for the good effort you are doing!

[jajhall]

We've got no parameter tuning facility, but some users have found it valuable to modify mip_heuristic_effort.

[jajhall]

Thanks. I'm running the easy problem, and have already seen some odd behaviour

[jajhall]

HiGHS solved the easy problem to a gap of 0.01% in 18650s, and no amount of parameter tuning is going to get this near 15 minutes.

I solved it in 313s using a major commercial solver, so it's clearly a non-trivial problem.

Almost all the HiGHS solution time is spent in the tree search. This is currently serial, but work to exploit multi-threading is on-going.

So, thanks, it's a useful example for our development work

[Fondry]

Thank you for your insights!

For this problem we focus on getting the best possible integer solution and do not care about proving optimality. We have spotted a lot of times when a solver was able to get to the global optimum (or very close to it in monetary terms) but the gap was 2-0.5%. It then would spend a huge amount of time on lowering the gap to 0.

We will try the parameters you suggested and check if they can get better integer solutions on this limited time limit.

Thank you for the time, I am glad to read that these problems are useful!

[jajhall]

For this problem we focus on getting the best possible integer solution and do not care about proving optimality. We have spotted a lot of times when a solver was able to get to the global optimum (or very close to it in monetary terms) but the gap was 2-0.5%. It then would spend a huge amount of time on lowering the gap to 0.

Indeed, HiGHS got the gap down to 0.52% in 45s, with a solution value of 546466.465456 (within 0.2% of the optimal solution of 545215.010851) before completing all its work at the root node, but then took forever to close the gap.

Even the LP relaxation itself has an optimal objective value of 542552.22384

For the medium and hard instances, the LP relaxations are rather further from the optimal integer feasible objective value. Still, at the root node

• For the medium instance HiGHS gets 222825 (gap 6.5%) in 144s, so is within 3% of the optimal value of 216124
• For the hard instance HiGHS gets 283159 (gap 16.6%) in 91s.

For the hard instance, I doubt the optimal objective of 341701.305 that you quote. Using a major commercial solver (after 50774s!) the (dual, primal) bounds are (257022.462, 258905.288), a gap of 0.73%. Hence HiGHS at the root node is within no more than 10% of the optimal solution.

[Fondry]

Indeed, HiGHS got the gap down to 0.52% in 45s, with a solution value of 546466.465456 (within 0.2% of the optimal solution of 545215.010851) before completing all its work at the root node, but then took forever to close the gap.

Yes, most of the times with HIGHS we see results between the easy and the medium problem, a problem like the hard one doesn't happen that often. That is also why we wanted to focus on trying to get good integer feasible solutions (which in the commercial solvers seemed to come from modifying the heuristics parameters).

For the hard instance, I doubt the optimal objective of 341701.305 that you quote. Using a major commercial solver (after 50774s!) the (dual, primal) bounds are (257022.462, 258905.288), a gap of 0.73%. Hence HiGHS at the root node is within no more than 10% of the optimal solution.

You are right there, i think i copied the wrong number...