Does highs have any plans to add model reduction techniques to linear programming?

[tusiqi1]

I‘m not sure the exact name of this technique, but it seems to be found in other commercial solvers.

In gurobi: https://support.gurobi.com/hc/en-us/community/posts/17441473898641-Crossover-LP-symmetric-solution

In xpress: https://community.fico.com/s/blog-post/a5Q80000000Drp2EAC/fico1299

[jajhall]

I've known of this technique for a long time, but it's time-consuming to implement and isn't valuable for a lot of LPs, so hasn't been done for HiGHS. I wouldn't say we'll never have it, but it won't happen soon.

Do you have LPs that would benefit from such reductions?

[tusiqi1]

I'm not sure how effective this technique really is on solving time. I found a good reduction in the following examples.

https://plato.asu.edu/ftp/lpfeas_logs/cop_results/a2864.cob
https://plato.asu.edu/ftp/lpfeas_logs/cop_results/cont1.cob
https://plato.asu.edu/ftp/lpfeas_logs/cop_results/cont11.cob

I guess if this technique is used to get "The folded problem" in the log.

[jajhall]

Yes, the symmetry reduction is also known as LP folding. It's also useful for QAP problems. Maybe it's useful for other combinatorial optimization problems. The 'cont' problems are very odd, and solving them well is only useful for benchmark performance, as anything like them is unlikely to be encountered in practice

[tusiqi1]

Thank you, Professor! I have another question.

Is there any related material available regarding the correlation between benchmarks and real-world problems (mathematical models)？

I feel that commercial solvers have been optimized for many common problems which cause a good perfoemence on benchmark, but I didn't even know what the problems were.

Analyzing lp files for benchmark individually was too slow.

[jajhall]

I know of no study comparing benchmark problems with regular practical problems. My understanding is that the benchmark LP problems are ones that have been discovered to be difficult to solve by companies and academics and proposed as benchmark problems. Tuning commercial solvers to perform well on benchmark problems has been known

[tusiqi1]

thanks!