-
Notifications
You must be signed in to change notification settings - Fork 3
Randomized LP solver
The projects targets in a state-of-the-art implementation for solving LP, based on sampling and randomized tools. As we can sample points independently, this approach could have an efficient parallel implementation.
This project is connected but still independent from randomized SDP solver project.
For the randomized algorithm for LP, we will based on [B1] and [B2] using the current sampling routines of volesti but also implementing new ones.
One of the most efficient open-source LP-solve solvers to day is lp_solve
References:
[B1] Dabbene, Fabrizio, Pavel S. Shcherbakov, and Boris T. Polyak. A randomized cutting plane method with probabilistic geometric convergence SIAM Journal on Optimization 20.6 (2010): 3185-3207.
[B2] Adam Tauman Kalai, Santosh Vempala Simulated Annealing for Convex Optimization Mathematics of Operations Research Vol. 31, No. 2, 2006.
The project contains two implementations of a randomized algorithms from [B1], [B2] for solving linear programs.
Comparison with existing open-source LP solvers like lp_solve. The student should study the availability and performance of current open-source LP solvers. The following links 1, 2 are good starting points.
The code will be in C++ with R interfaces using Rcpp, following volesti structure. Basic documentation for the R version is required.
The projects will provide GeomScale with state-of-the-art randomized solver for semi-definite programming, that will comparable and in many case faster that traditional LP solvers.
-
Vissarion Fisikopoulos <vissarion.fisikopoulos at gmail.com> is an international expert in mathematical software, computational geometry and optimization, and has previous GSOC mentoring experience with Boost C++ libraries (2016-2017) and the R-project (2017).
-
Fabrice Rouillier <fabrice.rouillier at inria.fr> is an expert in computational algebra, geometry, and mathematical software. He has contributed to the implementation of several state-of-the-art software tools for computing with intervals and polynomials.
-
Elias Tsigaridas <elias.tsigaridas at inria.fr> is an expert in computational nonlinear algebra and geometry with experience in mathematical software. He has contributed to the implementation, in C and C++, of several solving algorithms for various open source computer algebra libraries and has previous GSOC mentoring experience with the R-project (2019).
Students, please contact both mentors below after completing at least one of the tests below.
Students, please do one or more of the following tests before contacting the mentors above.
- Easy: compile and run VolEsti. Use the R extension to visualize sampling in a polytope.
- Medium: Implement randomized cutting plane method for LP and report performance benchmarks.
- Hard: Try a prototype of simulating annealing algorithms for LP and report issues and difficulties.
Students, please post a link to your test results here.
- EXAMPLE STUDENT 1 NAME, LINK TO GITHUB PROFILE, LINK TO TEST RESULTS.
Name:Rohit Email:[email protected] GitHub:https://github.com/phoenixrao885/gsoc-monte-carlo-solutions Test done :monte carlo integration -Easy,Medium,Hard,Bonus
Name: Prajwal Bagal Email: [email protected] Github: https://github.com/Prajwalbagal/GeomScaleTest
Name:Abhishek Agrawal Email:[email protected] GitHub:Easy-task: https://github.com/abhishek8764/Monte-Carlo-Integration
Name: Divesh Kuamar Email: [email protected] Task-Link(Easy Randomized LP solver): https://github.com/diveshkr-code/Geomscale_Gsoc2020`
Name: Deifilia To Email: [email protected] Task-link: (Easy and Medium of Apothesis): https://github.com/DeifiliaTo/Apothesis_gsoc
Name: Soumyajit Chakraborty Email: [email protected] Task-Link(Easy Task of Apothesis): https://github.com/soumyajit1729/Apothesis
Name: Soumyajit Chakraborty Email: [email protected] Task-Link(Medium Task of Apothesis): https://github.com/soumyajit1729/Apothesis
Name: Soumyajit Chakraborty Email: [email protected] Task-Link(Hard Task of Apothesis): https://docs.google.com/presentation/d/1mX4UA3x8cs6--aCZ_cN2ZNB6jr3eC7P5sbiEB92YEC0/edit?usp=sharing
Name:Abhishek Agrawal Email:[email protected] GitHub:Medium-task: https://github.com/abhishek8764/Monte-Carlo-Integration
Name: Alexandros Manochis, Email: [email protected], Github: https://github.com/AlexManochis/volume_approximation/tree/gsoc20, Project: A comparative study of uniform high dimensional samplers, Tests completed: Easy, Medium, Hard
Name: Sunit Gautam Email: [email protected], [email protected] GitHub: https://github.com/gsunit/Monte-Carlo-Intergration Tasks completed: Monte Carlo integration - Easy, Medium, Hard
Name: Vaibhav Thakkar
Email: [email protected]
GitHub: https://github.com/vaithak/GeomScale_LP
Tasks completed: Randomized LP - Easy, Medium, Hard
Name: Sharat Bhat Email: [email protected] Github: https://github.com/Sharat-Bhat Tasks: https://github.com/Sharat-Bhat/GSoC_volesti
Name: Kunal Katiyar Email: [email protected] GitHub: https://github.com/KunalKatiyar/GSoC_RandLP
Name: Reyan Ahmed Email: [email protected] GitHub: https://github.com/abureyanahmed/VolEsti_test
Name:Abhishek Agrawal Email:[email protected] GitHub:Easy-task: https://github.com/abhishek8764/A-comparative-study-of-uniform-high-dimensional-samplers
Name: Sushovan Haldar Email: [email protected] Github: Easy task of using volesti : https://github.com/SushovanHaldar/geomscalecodes
Name: Anastasios Sourpis Email: [email protected] Github: Apothesis : https://github.com/pithonas/Apothesis
Name: Daniel Pozo Email: [email protected] GitHub: https://github.com/danipozo/uld-test-solutions
Name: Iasonas Nikolaou Email: [email protected] GitHub: (Easy and medium task, randomized LP) https://github.com/jasonNikolaou/GeomScale_gsoc
Name: Fernando Martin Email: fdmartin92 (at) gmail (dot) com GitHub: https://github.com/fmartin92/GeomScale_MonteCarlo (All tasks corresponding to the Monte Carlo integration proposal)
Name: Marios Papachristou Email: papachristoumarios [at) gmail (dot] com GitHub: https://github.com/papachristoumarios/geomscales-challenge (All challenges for ULD)
Name: Eugenio Borghini Email: [email protected] GitHub: https://github.com/eugenusb/GeomScale_LP (Easy and medium test projects for the randomized LP solver)
Name: Muhammad Ali Nayeem Email: [email protected] GitHub: https://github.com/ali-nayeem Test: https://github.com/ali-nayeem/gsoc2020_rand_LP_solver
Name: Bychkov Andrey Email: [email protected] GitHub: https://github.com/AndreyBychkov Test: https://github.com/AndreyBychkov/LIPA (Hard for Optimization and SOS)
Name: Yuan Yuan Email: [email protected] Github:https://github.com/yzy0014 Test:https://github.com/yzy0014/GeomScale Test demo:https://rpubs.com/yzy0014/584976, https://rpubs.com/yzy0014/585064 (High dimensional sampling with applications to structural biology)
Name: Haris Zafeiropoulos Email: [email protected] Github:https://github.com/hariszaf/ Test:https://hariszaf.github.io/gsoc2020/
Name: Mokhwa Lee
Email: [email protected] OR [email protected]
Github: https://github.com/Mokhwalee
Test: https://github.com/Mokhwalee/Exercise-Gsos
( Monte Carlo - Easy, Medium, Hard, Bonus )
Name: Antonis Skarlatos
Email: [email protected]
Github: https://github.com/Hepic/
Test: https://github.com/Hepic/Monte-Carlo-integration
(Monte-Carlo-integration: easy/medium/hard/bonus Languages used: R/C++)
Name: Konstantinos Emmanouilidis
Email: [email protected]
Github: https://github.com/emmanouilidisk
Test: https://github.com/emmanouilidisk/GeomScale_challenges
(Challenges for Randomised LP Solver)
Name: Imrane Belhadia Email: [email protected] Github:https://github.com/ImraneBELH Test: https://github.com/ImraneBELH/gsocEvaluation-MonteCarlo.git (Monte Carlo)
Name: Repouskos Panagiotis Email: [email protected] Github: https://github.com/panagiotisrep/volume_approximation/tree/Optimization , https://github.com/panagiotisrep/volume_approximation/tree/SDP-cutting-plane Test: Randomized SDP solver (medium, hard)
Name: Mohammad Taufeeque
Email: [email protected]
Github: https://github.com/taufeeque9
Test: https://github.com/taufeeque9/GSoC_Randomized_SDP_Solver_Test
(Easy and hard task for Randomized SDP Solver)
Name: Bento Natura
Email: [email protected]
Github: https://github.com/platformconclude/volume_approximation/tree/spectra_sampling
Test: Randomized SDP solver (medium)
Github: https://github.com/platformconclude/simple_LP_IPM
Test: Interior point method for linear programming (IPM)
Name: Ritwik Chakraborty
Email: [email protected]
Github: https://github.com/ritwikchakraborty123
Test: :A comparative study of uniform high-dimensional samplers (medium)