How to solve this MILP-based regression model faster?

Hello,

I am trying to solve a MILP-based regression model as following.

Basically, I am training the B that can lead to good w with minimal cost loss (the first term in the objective), through solving the MILP model. What confuses me is that even though it only takes short time (about 10s) to achieve 0 of the cost loss term, it further takes much time (almost 800s) to handle the second norm-1 term. In other word, GUROBI puts a lot of effort into making B as sparse and small as possible.

Because the second norm-1 term aims to simplify the structure of B, so I understand it does need some time to do this. But could we improve the computational time through tuning the solver parameter?

I hope you could provide me some suggestions for impoving the computational performance. The mps file, LP file, and log are attached.

Best reagrds,
Xianbang

Log:

Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (mac64)
Thread count: 8 physical cores, 16 logical processors, using up to 16 threads
Optimize a model with 311800 rows, 133945 columns and 1414928 nonzeros
Model fingerprint: 0x7499d375
Variable types: 115513 continuous, 18432 integer (18432 binary)
Coefficient statistics:
Matrix range [1e-04, 1e+04]
Objective range [1e-05, 1e+05]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 2e+05]
Presolve removed 251513 rows and 87073 columns
Presolve time: 1.96s
Presolved: 60287 rows, 46872 columns, 343654 nonzeros
Variable types: 31624 continuous, 15248 integer (15248 binary)

Deterministic concurrent LP optimizer: primal and dual simplex
Showing first log only...


Root simplex log...

Iteration Objective Primal Inf. Dual Inf. Time
46189 1.2311176e+06 0.000000e+00 3.365542e+05 5s
Concurrent spin time: 0.00s

Solved with dual simplex

Root relaxation: objective 8.853941e+04, 75286 iterations, 5.55 seconds

Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time

0 0 88539.4055 0 365 - 88539.4055 - - 9s
H 0 0 222879.24131 88539.4055 60.3% - 10s
H 0 0 97899.329861 88539.4055 9.56% - 10s
0 0 88742.9496 0 413 97899.3299 88742.9496 9.35% - 13s
H 0 0 97870.274174 88742.9496 9.33% - 13s
0 0 88743.8306 0 419 97870.2742 88743.8306 9.33% - 14s
0 0 88816.2806 0 448 97870.2742 88816.2806 9.25% - 15s
0 0 88896.0320 0 444 97870.2742 88896.0320 9.17% - 16s
0 0 88896.0320 0 451 97870.2742 88896.0320 9.17% - 16s
0 0 88896.0320 0 448 97870.2742 88896.0320 9.17% - 16s
0 0 88896.0320 0 433 97870.2742 88896.0320 9.17% - 16s
0 0 88896.0320 0 448 97870.2742 88896.0320 9.17% - 16s
0 0 88896.0320 0 421 97870.2742 88896.0320 9.17% - 17s
0 0 88896.0320 0 433 97870.2742 88896.0320 9.17% - 18s
0 0 88896.0320 0 429 97870.2742 88896.0320 9.17% - 18s
0 0 88896.0320 0 432 97870.2742 88896.0320 9.17% - 18s
0 0 88896.0320 0 460 97870.2742 88896.0320 9.17% - 19s
0 0 88896.0320 0 467 97870.2742 88896.0320 9.17% - 19s
0 0 88896.0320 0 462 97870.2742 88896.0320 9.17% - 20s
0 0 88896.0320 0 459 97870.2742 88896.0320 9.17% - 21s
0 0 88896.0320 0 459 97870.2742 88896.0320 9.17% - 21s
0 0 88896.0320 0 461 97870.2742 88896.0320 9.17% - 21s
0 0 88896.0320 0 403 97870.2742 88896.0320 9.17% - 22s
H 0 0 93347.138450 88896.0320 4.77% - 31s
0 2 88896.0320 0 392 93347.1385 88896.0320 4.77% - 33s
15 24 89225.4295 4 400 93347.1385 89111.3735 4.54% 755 35s
H 31 40 93308.898611 89111.3735 4.50% 856 37s
73 84 89333.6740 9 401 93308.8986 89111.3735 4.50% 894 40s
155 173 90267.5961 17 373 93308.8986 89111.3735 4.50% 781 45s
H 172 181 93288.819695 89111.3735 4.48% 770 48s
H 173 181 93261.379496 89111.3735 4.45% 788 48s
H 174 181 93246.659040 89111.3735 4.43% 805 48s
H 175 181 93225.474528 89111.3735 4.41% 800 48s
H 177 181 93213.873774 89111.3735 4.40% 809 48s
200 238 90975.9721 23 393 93213.8738 89111.3735 4.40% 779 50s
H 310 332 93073.475144 89111.3735 4.26% 610 54s
331 361 91363.5106 35 375 93073.4751 89111.3735 4.26% 584 55s
475 508 91628.5642 40 391 93073.4751 89111.3735 4.26% 483 61s
607 660 91922.3869 44 366 93073.4751 89111.3735 4.26% 420 65s
851 877 92638.4594 54 310 93073.4751 89111.3735 4.26% 347 71s
1010 1030 92833.4087 59 302 93073.4751 89111.3735 4.26% 325 76s
1085 1051 cutoff 61 93073.4751 89193.9738 4.17% 315 80s
H 1087 1037 93013.258140 89193.9738 4.11% 315 80s
H 1104 1007 92920.284978 89193.9738 4.01% 310 80s
1283 1213 91645.0806 35 397 92920.2850 89193.9738 4.01% 294 86s
1461 1310 92363.3868 74 403 92920.2850 89213.6316 3.99% 279 103s
1463 1311 90973.6470 30 369 92920.2850 89213.6316 3.99% 279 111s
1466 1313 89942.2183 17 413 92920.2850 89213.6316 3.99% 278 115s
1469 1315 91530.4692 64 407 92920.2850 89213.6316 3.99% 277 120s
H 1471 1251 92900.516962 89213.6316 3.97% 277 123s
1473 1252 92248.3676 50 415 92900.5170 89213.6316 3.97% 277 125s
1476 1254 91372.1770 47 402 92900.5170 89213.6316 3.97% 276 131s
1478 1255 90965.3911 41 411 92900.5170 89213.6316 3.97% 276 138s
H 1479 1192 92808.046987 89213.6316 3.87% 275 147s
1481 1196 89213.6316 15 414 92808.0470 89213.6316 3.87% 319 171s
1483 1200 89213.6316 16 405 92808.0470 89213.6316 3.87% 320 178s
1487 1206 89213.6316 17 396 92808.0470 89213.6316 3.87% 320 183s
1495 1212 89265.6892 18 408 92808.0470 89213.6316 3.87% 322 185s
1527 1237 89360.5545 20 424 92808.0470 89296.6861 3.78% 321 191s
1567 1271 89514.4733 23 400 92808.0470 89338.0271 3.74% 327 195s
H 1606 1226 92806.540572 89338.0271 3.74% 327 197s
1657 1267 89890.1181 30 368 92806.5406 89338.0271 3.74% 325 200s
H 1672 1213 92791.047261 89338.0271 3.72% 325 210s
1760 1283 90070.1434 36 337 92791.0473 89338.0271 3.72% 321 215s
1872 1367 90190.2009 40 382 92791.0473 89338.0271 3.72% 319 220s
2029 1457 90446.8643 46 351 92791.0473 89338.0271 3.72% 311 226s
2149 1561 90716.0102 50 345 92791.0473 89338.0271 3.72% 311 230s
2431 1715 90966.1933 58 323 92791.0473 89338.0271 3.72% 298 236s
2481 1711 91206.6406 60 319 92791.0473 89338.0271 3.72% 297 241s
2589 1841 91125.8093 63 344 92791.0473 89338.0271 3.72% 291 245s
2864 1971 91494.3349 71 295 92791.0473 89338.0271 3.72% 285 250s
3015 2058 92052.4262 76 294 92791.0473 89338.0271 3.72% 283 256s
3229 2181 cutoff 84 92791.0473 89338.0271 3.72% 279 260s
3475 2348 89580.9602 22 373 92791.0473 89355.9553 3.70% 273 265s
3650 2436 90114.8540 26 369 92791.0473 89355.9553 3.70% 270 272s
3977 2578 92419.0551 34 395 92791.0473 89355.9553 3.70% 261 277s
4170 2651 90328.2167 37 398 92791.0473 89355.9553 3.70% 256 280s
4465 2810 90524.4779 46 408 92791.0473 89355.9553 3.70% 257 285s
4754 2960 91379.7218 68 390 92791.0473 89355.9553 3.70% 251 291s
5111 3230 92179.4683 97 303 92791.0473 89355.9553 3.70% 249 298s
5213 3416 92306.4744 105 293 92791.0473 89355.9553 3.70% 249 301s
5428 3526 92441.2203 124 265 92791.0473 89355.9553 3.70% 247 305s
5564 3590 92507.2677 143 212 92791.0473 89355.9553 3.70% 248 310s
H 5584 3574 92775.485660 89355.9553 3.69% 248 310s
5809 3862 infeasible 181 92775.4857 89367.0199 3.67% 249 319s
5994 4077 90059.8529 26 399 92775.4857 89428.8555 3.61% 248 323s
6276 4339 90291.2299 32 417 92775.4857 89428.8555 3.61% 243 328s
6569 4518 90896.0573 42 426 92775.4857 89428.8555 3.61% 240 333s
6784 4837 91597.5613 71 337 92775.4857 89428.8555 3.61% 239 338s
7128 5165 92283.2483 97 262 92775.4857 89428.8555 3.61% 234 344s
7534 5254 92529.6937 134 184 92775.4857 89428.8555 3.61% 226 346s
7646 5517 92730.7252 148 150 92775.4857 89431.7532 3.60% 224 351s
7976 5669 89840.8567 23 446 92775.4857 89465.9414 3.57% 223 356s
8159 5766 90335.4454 31 409 92775.4857 89465.9414 3.57% 223 362s
8283 6086 90645.1028 32 402 92775.4857 89465.9414 3.57% 223 368s
8636 6450 91207.3271 42 362 92775.4857 89465.9414 3.57% 223 374s
9031 6821 cutoff 53 92775.4857 89465.9414 3.57% 222 380s
9452 7159 91581.1189 70 285 92775.4857 89465.9414 3.57% 220 387s
9884 7431 91909.7556 79 267 92775.4857 89465.9414 3.57% 218 395s
10231 7862 92589.2663 101 234 92775.4857 89520.6687 3.51% 220 402s
10764 8406 cutoff 94 92775.4857 89532.7087 3.50% 217 410s
11445 8742 90182.1944 31 389 92775.4857 89534.3168 3.49% 211 417s
11823 9241 91010.5093 56 349 92775.4857 89534.3168 3.49% 214 425s
12352 9856 91789.0215 75 308 92775.4857 89534.3168 3.49% 212 433s
13049 10326 92133.6955 93 273 92775.4857 89534.3168 3.49% 206 441s
13597 10732 92570.2607 118 220 92775.4857 89561.3338 3.46% 206 450s
14068 11089 91658.0169 47 437 92775.4857 89573.8013 3.45% 208 458s
14504 11695 90069.8916 29 379 92775.4857 89573.8013 3.45% 211 470s
15254 11737 92198.1468 93 335 92775.4857 89573.8013 3.45% 210 483s
15319 12081 92533.0255 99 312 92775.4857 89584.0185 3.44% 210 492s
15764 12613 91509.2672 39 426 92775.4857 89587.3989 3.44% 213 502s
16429 13088 90328.0891 42 342 92775.4857 89599.9419 3.42% 214 514s
17138 13701 90100.6797 28 442 92775.4857 89611.3202 3.41% 214 525s
17752 14418 90968.2341 50 437 92775.4857 89611.3202 3.41% 212 537s
18571 14994 92411.0294 111 274 92775.4857 89611.4675 3.41% 209 550s
19241 15035 90548.5644 43 473 92775.4857 89611.4675 3.41% 208 563s
H19244 15010 92765.871399 89611.4675 3.40% 208 563s
H19245 15005 92764.404377 89611.4675 3.40% 209 563s
19284 15199 90641.9168 48 456 92764.4044 89611.4675 3.40% 209 575s
19493 16044 91208.3108 59 424 92764.4044 89611.4675 3.40% 210 589s
20393 16854 92410.5066 112 264 92764.4044 89617.2144 3.39% 208 603s
21354 17491 91136.7320 34 354 92764.4044 89629.2989 3.38% 205 618s
22186 18352 90487.6383 30 466 92764.4044 89638.4666 3.37% 205 632s
23210 19193 91709.7737 45 359 92764.4044 89649.5046 3.36% 203 647s
24246 19933 92272.1425 91 282 92764.4044 89659.2027 3.35% 201 661s
25172 20632 92599.1193 70 428 92764.4044 89668.9648 3.34% 200 674s
25971 21288 cutoff 84 92764.4044 89670.6283 3.34% 201 687s
26739 22035 90713.4047 44 365 92764.4044 89676.9167 3.33% 203 700s
27644 22836 91068.6182 58 363 92764.4044 89683.7394 3.32% 203 714s
28607 23643 90465.7238 33 429 92764.4044 89692.8543 3.31% 202 727s
Cutting planes:
Gomory: 3
Implied bound: 78
Projected implied bound: 29
MIR: 245
Flow cover: 201
Relax-and-lift: 28
Explored 29575 nodes (6044564 simplex iterations) in 900.16 seconds
Thread count was 16 (of 16 available processors)
Solution count 10: 92764.4 92765.9 92775.5 ... 93073.5
Time limit reached
Best objective 9.276440437681e+04, best bound 8.969669667980e+04, gap 3.3070%

Official comment

Simranjit Kaur

Gurobi Staff

December 06, 2024 00:33

This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.

Xianbang Chen

April 26, 2021 12:11

Hi, is it possible to upload a LP file? Seems only image is allowed.

Jaromił Najman

April 26, 2021 12:57
Edited

Yes, please have a look at Posting to the Community Forum.

Did you try Gurobi's parameter tuning tool?

April 26, 2021 13:00

Hi Jaromił,

I have attached the mps file on https://www.filemail.com/d/kluiopckxswcvir

Could you share any suggestions with me?

April 26, 2021 13:10

Thanks for this. I will adjust my way for posting a good question.

Not yet, but I just read this. Seems like if I spend enough time on runing it function, it is not difficut to get improvement. However, fine tuning is still required. Is that right?

April 26, 2021 13:37

Seems like if I spend enough time on runing it function, it is not difficut to get improvement. However, fine tuning is still required. Is that right?

If you let the tuning tool run for, e.g., 1-2 days, then it should be enough and it is very likely possible that no further fine tuning is required. If you have only a limited amount of time, then yes, fine tuning is still required.

April 26, 2021 13:39

BTW, I tried to use a MathJax rather than image to represent the model. But the Latex code for the model is somehow complicated. So I merely replace it with a clearer image. I hope this could improve the quality of this post.

April 26, 2021 13:43

Thanks for this. I will try this idea soon.

If the size of the problem is bigger, e.g., the solving time with default setting requires 3 hours instead of 3 mins, the "1-2 days" may be "1-2 weeks", is that possible?

April 26, 2021 13:55

Yes, the bigger the problem, the more time is required by the tuner. You might also be interested in our Most important parameters. For your problem MIPFocus=1 might work well. You should also think about the MIPGap you want to achieve. Are you really looking for the perfect solution or would a MIPGap of, e.g., 1% be already enough? You should also update to the latest version if possible.

April 26, 2021 14:02
Edited

Thanks for your suggestions!

You should also think about the MIPGap you want to achieve. Are you really looking for the perfect solution or would a MIPGap of, e.g., 1% be already enough?

Yes, I set the Gap as 3%, which is enough for my problem. Because I do not want the solver struggling in handle the regulation term for long time.

You should also update to the latest version if possible.

I am a user of MATLAB. If I update to the latest version, is it necessary to update my academic license? I cannot access to my school's network through VPN.

April 26, 2021 14:22

Since you are already using version 9.x.x, this means that your license is valid for all 9.x.x versions. There is no need to update your license unless it is expired.

April 26, 2021 14:24

Thank you very much. I love this community because of your remarkable works and suggestions.

How to solve this MILP-based regression model faster?

Comments

Didn't find what you were looking for?