migoox / genome-downsampler

Other
2 stars 0 forks source link

Express our problem as a linear programming problem #46

Closed migoox closed 5 months ago

migoox commented 5 months ago

Background:

We have successfully expressed 1-QMCP as a min cost circulation problem. This solution leads to push-relabel + cost-scaling algorithm implementation. The push-relabel + cost-scaling CUDA solution may be problematic, while there are papers on push-relabel algorithms that claim to speed up CPU solutions by 3-8 times (here), there is not many about the cost-scaling variant of the algorithm.

The cost-scaling seems to be compatible with the push-relabel CUDA solution, but it brings risks, since we don't now much about the performance.

To do

We would like to express 1-QMCP as a linear programming problem. It's important to find the direct solution, the solutions like this: 1-qmcp -> min cost max flow -> linear programming are not valid, since they increase complexity and probably slow down the algorithm, we need 1-qmcp -> linear programming.

The best place to start is here (2. Transformation of matrices with consecutive 1s)