Memory allocation in facet redundancy removal in dingo

Overview

This project will improve the memory allocation in the main routine for facet redundancy removal in GeomScale's Python package dingo. The project is expected to highly improve the run-time of the preprocessing of a metabolic network with dingo. Thus, that will be an important contribution that will allow for preprocessing of large metabolic networks in Systems Biology.

Related work

A convex polytope is given as a set of linear inequalities, and the feasible space is the intersection of the corresponding half-spaces. However, some of the inequalities could be redundant. That is if we remove them the feasible space does not change. The package dingo represents a metabolic network with a convex polytope. Typically, there are a few linear inequalities that are redundant. dingo also provides one implementation that solves a sequence of linear programs to find those inequalities and to remove them. However, the implementation is not efficient as it does not allocate the memory efficiently when building the objects that represent the linear programs. dingo uses the Python interface of gurobi to solve those linear programs.

Details of your coding project

The student will have to improve the memory allocation in the existing Python implementation of dingo which removes the redundant facets of a polytope. She/he will have to provide experimental evidence that the new implementation is more efficient.

Difficulty: Easy

Skills

Required: Python, Linear programming theory, Basic computational geometry background
Preferred: Experience with mathematical software is a plus

Expected impact

The projects will drastically improve the preprocessing routines of dingo package.

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: Compare the run-time of the preprocessing of dingo with that of PolyRound python package.
Hard: Write in your proposal the pipeline of the procedure that finds and removes the redundant facets and is implemented in both dingo and PolyRound packages