The improvement of serial dual Simplex algorithm

[tusiqi1]

Hello professor, I am an optimization solver researcher in a company, and my current responsibility is to optimize the serial dual simplex algorithm in HIGHS to achieve better performance in real-world applications. I have read some of Dr. huangfu's papers and yours.

At present, I have optimized the calculation process of PriceByColumn and some memory requests in "rebuild".

Dual simplex algorithm is a locally optimal iterative search between vertices in high dimensional space. Next, I want to implement multiple path search in the iterative process of dual simplex to extend the scope of the local optimal value
, and merge these search path results at appropriate time. The whole process is: branch search - merge - branch search and so on.

My idea above is obviously simple. But during my actual code changes, I found that the underlying data changes involved in this work were quite large.

If possible, I would be grateful if professor could give me some advice on my idea or other dual simplex optimization ideas before I proceed to the actual code implementation.

[jajhall]

This "branch search - merge - branch search" approach has been considered before by Maros and Mitra, but I don't think that it's worth trying in the context of the code complexity required. The bound on speed-up is the reduction in the number of iterations relative to vanilla dual simplex: not much given the overheads of merging and branching.

A much simpler concurrency approach - as taken by Gurobi (at least) - is to run different LP solution techniques concurrently until one has finished. This way you capture the few occasions when simplex out-performs barrier, and when primal simplex out-performs dual. I've got a prototype implementation of this for HiGHS. It's relatively easy to implement using by choosing the first to finish, but that's non-deterministic. LP solvers must be deterministic, and that requires a model of computation time to be used to decide which has finished first.

At present, I have optimized the calculation process of PriceByColumn and some memory requests in "rebuild".

I'm curious

• How have you improved the calculation process of PriceByColumn?
• What memory requests in "rebuild" have you optimized?

[tusiqi1]

The improvement of PriceByColumn is to divide the CSC data of matrix A into the same length, parallelize the calculation of each part, then merge the results, and finally traverse the array again to generate index. The details are mainly inspired by Algorithm 3 in Paper “https://arxiv.org/pdf/1503.05032.pdf”. In practice, priceByRow seems to take more time, but because it often deals with sparse row_ep, I didn't find a good way to improve it.

The improvement in "rebuild" is computeDual function in HEkk.cpp, dual_col and dual_row will repeat the memory request, I declared it in the .h file. I later found some improvement on larger, frequently rebuilt instances such as "http://plato.asu.edu/ftp/network.html" netlarge examples.

If professor think these two works is valuable, I hope you can cite this discussion so that I can prove my work to my boss.

My ultimate goal of optimizing the dual simplex is to improve the solving performance of the MIP problem. Due to some characteristics of the dual simplex on branch and cut, it may not be appropriate to choose multiple strategies to solve the LP problem in parallel.

[jajhall]

The improvement of PriceByColumn is to divide the CSC data of matrix A into the same length, parallelize the calculation of each part, then merge the results, and finally traverse the array again to generate index. The details are mainly inspired by Algorithm 3 in Paper “https://arxiv.org/pdf/1503.05032.pdf”. In practice, priceByRow seems to take more time, but because it often deals with sparse row_ep, I didn't find a good way to improve it.

The classical data parallel PriceByColumn may be useful for problems where the $\pi$ vector is not sparse, but don't look for linear speed-up, as the calculations are memory bound.

What do you mean by "in practice, priceByRow seems to take more time"? When $\pi$ vector is sparse, priceByRow is vastly more efficient than parallel PriceByColumn. Do you mean that priceByRow is used more (times) than PriceByColumn? If so, yes, I know.

The improvement in "rebuild" is computeDual function in HEkk.cpp, dual_col and dual_row will repeat the memory request, I declared it in the .h file. I later found some improvement on larger, frequently rebuilt instances such as "http://plato.asu.edu/ftp/network.html" netlarge examples.

I see, rather than create a new HVector instance twice in each call to HEkk::computeDual(), you're adding dual_col and dual_row as data members of HEkk class? Yes, maybe this is a marginal gain - but only in a method ( HEkk::computeDual()) that's called when rebuilding - which may be only once in hundreds or thousands of iterations. If it's valuable in "larger, frequently rebuilt instances such as "http://plato.asu.edu/ftp/network.html" netlarge examples." then that may be because (1) rebuild is too frequent and (2) because the $\pi$ vector is sparse, even when computing all the duals from scratch (with $c_B$ as the RHS rather than just $e_p$).

Do I think what you're doing is valuable? I can't say that it's going to make much difference to performance, as the HiGHS duial simplex solver is already very efficient, but ever little helps! I can credit you with trying and doing something sensible, that's for sure!

If you're looking at improving the performance of the dual simplex solver when solving MIPs, you're right in saying that trying to exploit parallelism is (even) less valuable than when solving an LP from scratch, since dual simplex in the MIP solver solves nodes in relatively few iterations, so the "start-up" overhead for parallelism is relatively high. Indeed, multiple threads when solving a MIP are better used in parallelising the MIP tree search.

[tusiqi1]

The explanation in "price" and "rebuild" is completely consistent with my thoughts and test results!

My job is to optimize the dual simplex algorithm and not directly optimize the MIP tree search. Pray that I can make some improvements on the dual simplex method.