Skip to content
Snippets Groups Projects
Felix Ludwig's avatar
fludwig authored
c6819efa
History

DPHPC Project

Dual simplex solver on GPU

Start

Sparse method for large-scale problems wikipedia

Try to run

Implementation

  • Python scipy sparse solver, read
  • use: cuSparse library

Ignore edge cases: focus on the solver

Edge cases like infinite solution, unfeasible...

Optimize

  • fuse cuda instructions together
  • tune: blocksize (caching behaviour: fine-tune foe euler env specifically)
  • read papers of other algorithms if enough time

Benchmark

well-known problems we should use as benchmarks

HOWTO:

  • cd miplib
    • cd scipoptsuite-8.0.4
    • mkdir build && cd build && cmake .. && make -j8 && make -j8 test
  • make checker, using the local checker/gmp (already hardcoded in makefile)
  • make -j8 test TEST=testthetest or any other file which contains a list of existing .mps.gzs

Smallest instances sorted by byte size

797 instances/miplib2017/revised-submissions/miplib2010_publically_available/instances/markshare_4_0.mps.gz
2179 instances/miplib2017/revised-submissions/miplib2010_publically_available/instances/markshare2.mps.gz
3872 instances/miplib2017/revised-submissions/miplib2010_publically_available/instances/enlight_hard.mps.gz
4005 instances/miplib2017/revised-submissions/miplib2010_publically_available/instances/pk1.mps.gz
5686 instances/miplib2017/revised-submissions/miplib2010_publically_available/instances/neos5.mps.gz
5884 instances/miplib2017/revised-submissions/Simon_Bowly/instances/gen-ip054.mps.gz
6320 instances/miplib2017/revised-submissions/miplib2010_publically_available/instances/neos859080.mps.gz
7077 instances/miplib2017/revised-submissions/miplib2010_timtab1/instances/timtab1.mps.gz
8706 instances/miplib2017/revised-submissions/Jeff_Linderoth2/instances/neos-3046615-murg.mps.gz

Most libraries already have a dual solver: use that if available!

HiGHS

HiGHS is a high performance linear programming algorithm. It uses revised simplex, interior point method and the sparsity of the problem.

It will replace the simplex, revised simplex and interior point method in scipy from 1.11 onwords.

Website: https://highs.dev/
Opensource code: https://github.com/ERGO-Code/HiGHS Scipy link: https://github.com/scipy/scipy/blob/main/scipy/optimize/_linprog_highs.py

Davinci

Ssh access, add these lines to .ssh/config

Host davinci
    Hostname davinci.inf.ethz.ch
    User "dphpc_simplex2_1"
    IdentityFile /home/felix/.ssh/id_rsa

and run ssh davinci.

Getting started and with GPUs.

Schedule

9 weeks total 1 week buffer

1st week 16-22 Oct

Research...

Simple implementation and benchmark baseline other implementations, understand python scipy, draft of pseudocode description of algorithm And check correctness between different implementations ?

2nd week 23-29 Oct

Get Pipeline up: read data from file, ..., print some garbage output like just the first guess.

Look at how to translate solver to Dual version, start writing CUDA...

3rd week 30 Oct-5 Nov

Design+CUDA+Testing

4th week 6-12 Nov

Design+CUDA+Testing

week 13-19 Nov

Design+CUDA+Testing

week 20-26 Nov

Presentation 22 Nov

in the übungsstunde

Explicit algorithm description

Something like pseudocode :

# A matrix
# c vector
A,c=load_problem_from_file()

return 0

Design+CUDA+Testing

week 27 Nov-03 Dec

Design+CUDA+Testing+Omtimizing

week 04-10 Dec

Design+CUDA+Testing+Omtimizing

week 11-17 Dec

finish: Design+CUDA+Testing+Omtimizing start: Documentation and final report (max 6 pages)

week 18-24 Dec

Documentation and final report (max 6 pages)

Write sequential implementation

O(n) solver exists ? O(n^2) normally ?

Benchmark

Write parallelized