Randomized LP solver - GeomScale/gsoc20 GitHub Wiki

Overview

The project targets has two goals. 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.
This project is connected but still independent from randomized SDP solver project.

Related work

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.

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.

Details of your coding project

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.

Expected impact

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.

Mentors

  • 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, 2020).

  • 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.

Students, please contact the first and the third mentor after completing at least one of the tests below.

Tests

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 volesti and report performance benchmarks.
  • Hard: Try a prototype of simulating annealing algorithms for LP and report issues and difficulties.

Solutions of tests

Students, please post a link to your test results here.

  • EXAMPLE STUDENT 1 NAME, LINK TO GITHUB PROFILE, LINK TO TEST RESULTS.