-
Notifications
You must be signed in to change notification settings - Fork 5
Randomized LP solver and non convex optimization
The project targets has two directions. The first is a state-of-the-art implementation for solving LP, based on sampling and randomized tools. We are going to employ uniform and exponential sampling and various random walks to create a prototype implementation. In the sequel, the student has to make a list with all the open source LP solvers and to compare the run-times with our new solver.
The second direction considers sampling techniques in non-convex optimization. The goal is to verify experimentally (and obtain additional insight) that in s certain setting the computational complexity of sampling algorithms scales linearly with dimension of the model while the complexity of optimization scales exponentially.
For the randomized algorithm for LP, we will based on [B1] and [B2] using the current sampling routines of volesti or their modifications, but also employ new algorithmic techniques.
We note that one of the most efficient open-source LP-solve solvers to day is lp_solve, which is also used in volesti.
For non-convex optimization the paper of reference in our setting is [B3], but we should study [B4].
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.
[B3] Ma, Y. A., Chen, Y., Jin, C., Flammarion, N., & Jordan, M. I. (2019). Sampling can be faster than optimization. Proceedings of the National Academy of Sciences, 116(42), 20881-20885.
[B4] Cheng, Xiang. "The Interplay between Sampling and Optimization." PhD diss., UC Berkeley, 2020.
The project contains (a) two implementations of a randomized algorithms from [B1], [B2] for solving linear programs, (b) some heuristics' implementations to make those algorithms competitive in practice, (c) 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, and (d) implementation of the basic algorithms in [B3].
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 linear programs, that will be comparable and in many cases faster that existing and well known open source LP solvers. It will also provide efficient implementation for sampling in non-convex domains.
-
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 the first and the third mentor 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 using any of the random walks that are implemented in
volestiand 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.