DPHPC Project
Dual simplex solver on GPU
Start
Sparse method for large-scale problems wikipedia
Try to run
-
Python: scipy simplex to read WARNING check the sparse algorithm specifically,
_linprog_rs.py
local copy -
Numerical Recipes: simplex algorithm walkthrough paper, and local version
-
Parallel search paths for simplex algorithm: howto parallelize local version
-
Linear Optimization with CUDA: simplex algorithm local version
-
github cuda-revised-simplex
-
github simplex-gpu
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 localchecker/gmp
(already hardcoded in makefile) -
make -j8 test TEST=testthetest
or any other file which contains a list of existing.mps.gz
s
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 ?