Options for parameter tuning with HiGHS to make the MIP problem solve faster.

[hbshrestha]

Hello. I am solving an unit commitment economic dispatch problem (say scenario A) in power systems using HiGHS.
My problem size for Scenario A is as shown below. The mps file size is about 1.6 GB.

MIP  flextool has 5483776 rows; 2934600 cols; 9819975 nonzeros; 113880 integer variables (8760 binary)
Coefficient ranges:
  Matrix [1e-01, 3e+04]
  Cost   [4e-03, 9e+02]
  Bound  [3e-01, 9e+03]
  RHS    [1e+00, 6e+04]
Presolving model
1319682 rows, 1895871 cols, 4859343 nonzeros  12s
960661 rows, 1811940 cols, 4702858 nonzeros  31s

Solving MIP model with:
   960661 rows
   1811940 cols (8760 binary, 105120 integer, 113880 implied int., 1584180 continuous, 0 domain fixed)
   4702858 nonzeros

I am using v1.11.0 of the highs.exe file. My settings for highs.opt file is given below. I am using 0.5% of MIP gap as standard across all scenarios. I have set the threads to 2. (Previously, I had tested using 8 threads, but I had some issue #1670 during results extraction. So I set the threads to 2 as default)

write_solution_to_file=true
solution_file=flextool.sol
write_solution_style=2
mip_report_level=2
mip_heuristic_effort=0.5
mip_detect_symmetry=false
mip_rel_gap=0.005
threads=2
log_to_console=true

My current scenario A has been running for over 8 days as shown below. I thought my model was stuck, but after ~713000 seconds, the MIP gap reduced from 4.2% to 0.61%. I had run other scenarios, where one of the constraints (annual emissions budget) were ~1.5X and ~2X higher than Scenario A. Those two scenario runs were complete within one day itself.

I have three-fold questions:

1. Is it possible to understand from the log message why my MIP problem is taking too long to solve?
2. Is it possible to get an indication of how much time will HiGHS take to solve the problem (i.e., until the MIP gap goes <= 0.5%)?
3. What kind of parameters can I use with the HiGHS solver that can make the solve time faster besides relaxing the MIP gap? (We have used some scaling method in our own problem to narrow down the coefficient range as mentioned in Is MIP solver using IPM nowadays? #2537
   (We can try to share the problem file if that helps to answer these questions.)

I Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time

H 0 0 0 0.00% 77680.402243 81090.050779 4.20% 13767 4176 0 2325k 161369.0s
0 0 0 0.00% 77680.410423 81090.050779 4.20% 13913 4216 0 2905k 165564.6s

B 0 0 0 0.00% 77680.410423 78155.102297 0.61% 12511 3653 0 2905k 713302.9s
3775 786 0 0.00% 77680.489309 78155.102297 0.61% 12511 3653 0 4068k 713309.5s

HiGHS_ScenarioA.log

[Opt-Mucca]

@hbshrestha That is a monstrous MILP! Does HiGHS regularly solve instances of this size from your experience? Can you share the logs of the other instances that solved within a day? (I'm assuming that their relaxations were very close in value to the optimal solution or HiGHS never had to branch deeply)

1. HiGHS will print out something to the command line at the end of each dive or when one of the dual / primal bound updates. What you can interpret from the log is that HiGHS processed 3775 nodes in its first dive and just before the dive was terminated it found a solution from branching (the B in the log). Why did this take so long? The problem is simply large, and as you can see from the the time it took to process the root node, solving thousands of LPs of this size takes time (even if they are warm-started).
2. In general no. The Expl. column in the log (combined with the current time) tries to give a user some intuition on when the problem will terminate, but it's a very noisy signal. Gut feeling and experience from similar models are still useful tools.
3. I think changing mip_heuristic_effort and mip_rel_gap already covers most of what you can do from a tuning point of view. Exploring the formulation can always help, but for an instance this size I guess that's extremely difficult. We're working on interfacing the new interior point solver with the MILP code (should speed up the root LP by a fair bit), and there's some ongoing work for cutting planes that should help energy models, but both of those are still not released. Otherwise, you could try moving to v1.12 and see if some of the recent presolve improvements help. (I'd be extremely happy if you're comfortable sharing your model. It's always nice to have these instances for testing purposes and I can try looking into some stuff further when I have time)

[hbshrestha]

If I may, another query from my side would be - right now we have set the mip_heuristic_effort to 0.5.
If we increase it to 1, is there a certainty that the solve time will reduce or could it rather increase the solve time further?

[jkiviluo]

Yes, I think this could even be an issue for HiGHS if this holds water. It seems the presolver can convert integer variables to 'implied integer' in some circumstances, but cannot do the same if the variable happens to be binary. Even though binary is just a special case of integer.

I could try to replicate this in a small test case if you think it would be worth pursuing further.

And I am also interested to understand what exactly the presolver might be doing - if this is a solid feature, it can be very useful for multiple problems (and models).

[fwesselm]

There is no special handling for binary variables in the implied integer detection. There are two cases:

1. Primal case: An equation forces a continuous variable to an integral value.
2. Dual case (continuous variable only appears in inequality constraints): When treated as equality constraints, all inequality constraints force the continuous variable to an integral value, AND the continuous variable's bounds are both integral.

[jkiviluo]

Ok, thanks. I don't then see how HiGHS could really do anything about the startup problem I described above. So, it is starting to look like there is nothing here. The slower solve time for the scen A is just because it's a sufficiently harder problem for other reasons than the integer startup units (although of course their presence makes it a hard problem in the first place). However, I do have hard time pinpointing why it gets harder - I thought it could have been the two additional storage units compared to scen B (now altogether 10 storage units), but I took those out and it's still taking a lot longer to solve than scen B (still running...).

But just to make sure, how should I interpret these lines from the solver?

Solving MIP model with:
   286620 rows
   534235 cols (2688 binary, 32256 integer, 34944 implied int., 464347 continuous)
   1431738 nonzeros

I first thought that this means that those binary and integer variables had been converted to 'implied integer' (perhaps stupidly because it fit what I wanted to believe and the sums matched). However, now I think those lines should just be read literally: there are 2688 binary variables, 32256 integer variables, and 34944 implied integer variables. 34944 matches with the number of integer variables between INTORG and INTEND in the MPS file (and there are 13 integer units multiplied by 2688 timesteps = 34944).

So, where do those 34944 implied integer variables come from? Maybe it's the second case of the implied integer detection. It might detect v_startup_integer, which is continuous variable but lower bound to a change in v_online_integer, which is true integer. Or v_shutdown_integer. But apparently it does not detect both (because then it should be 2 x 34944 implied integer variables if it did). v_startup_integer and v_shutdown_integer both have integral upper and lower bounds, but I don't see how they would be forced to integral value between those integral bounds: you could start 1.5 units if the bounds were 0 and 2 - although the true integer from v_online_integer might then step into play.

[Opt-Mucca]

You should interpret those lines literally. Trying to match those numbers to the original problem without a proper mapping is not guaranteed to work.
An easy example of how a continuous variable gets upgraded to implied integer: x + y + z = 5, x, y \in {0, 1}, z \in R. You can infer that z \in {3, 4, 5}, and is therefore technically "integer", but was defined as continuous, and hence becomes implied integer. Maybe constraints like this aren't explicitly modelled, but after some intermediate presolve step and some variables are fixed / removed they can appear.