Expose random walk Cpp implementations in dingo

Overview

The project will expose to Python package dingo the following random walks for polytope sampling in volesti:

Random Directions Hit-and-Run
Coordinate Direction Hit-and-Run
Ball walk
Dikin Walk
John Walk
Vaidya Walk

The random walks are implemented in C++. The project will implement Python wrappers using the existing structure of dingo.

Related work

dingo is a python package that analyzes metabolic networks. It relies on high dimensional sampling with Markov Chain Monte Carlo (MCMC) methods and fast optimization methods to analyze the possible states of a metabolic network. It represents a metabolic network with a convex polytope, while the points in the interior of the polytope correspond to steady states of the network. By sampling, dingo, explores and statistically studies the flux space of the network. To perform MCMC sampling, dingo relies on the C++ library volesti. Currently, it provides MMCS algorithm which is based on Billiard Walk and on a multiphase rounding scheme.

Details of your coding project

The student will have to extend the C++ bindings and Python wrappers of the dingo to expose the random walks mentioned above.

Difficulty: Easy

Skills

Required: C++, Python, Basic applied math, and computational geometry background
Preferred: Experience with optimization or other mathematical software is a plus

Expected impact

The projects will provide efficient random walks to sample from a polytope in Python. This is an undoubtedly important contribution to the open-source and scientific community.

Mentors

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

Tests

Students, please do one or more of the following tests before contacting the mentors.

Easy: compile and run dingo. Use the documentation to sample from the flux space of e_coli.
Medium: Generate a random polytope in Python and use dingo to sample from it using MMCS.
Hard: Use all the random walks in volesti (C++ implementations) to sample from Birkhoff and skinny polytopes (use the C++ polytope generators in volesti) for dimension d <= 200 and report on the run-times (implement this test in C++).