-
Notifications
You must be signed in to change notification settings - Fork 5
Counting linear extensions
The problem of counting the linear extensions of a given partial order consists in finding (counting) all the possible ways that we can extend the partial order to a total order that preserves the original partial order. It is an important problems with various applications in Artificial Intelligence and Machine Learning such, like for example in partial order plans [1] and in learning graphical model [2]. It is a well known #P-complete problem; the fastest known algorithms are based on dynamic programming and require exponential time and space [4, 5]. Nevertheless, if we only need an approximate counting attained with a probability of success, then the problem admits a polynomial-time solution for all posets using Markov chain Monte Carlo (MCMC) methods. During this project the student will implement new randomized methods to approximate the number of linear extensions based on volume approximation.
There are several MCMC schemes that have been proposed [3, 6]. The latter
improvements were based on rapidly mixing Markov chains in the set of linear
extensions [7]. In practice, approximate counting is feasible on partially
order sets up to a few hundred elements in a few hours [6]. It is well known
[8] that we can represent a partial order with a convex polyhedron, namely
order polytope. Furthermore, the number of linear extensions is equal to the
volume of the order polytope. However, there is no algorithm that counts
linear extensions through volume calculations of order polytopes.
However, there are a few practical algorithms for estimating the volume of a
convex polytope; volesti povides the most efficient implementations.
The goal of the project is to implement new approximation algorithms for counting linear extensions through volume approximation and an extensive empirical comparison included existing approximation methods. The aim is to exploit the structure of order polytopes to improve the existing implementations for approximate counting and to develop new efficient software implementations, based on volesti C++ library. In particular, the student will (a) implement a python and an R function to construct the order polytope given a partial ordered set, (b) write a new C++ class for the order polytope with optimized membership and boundary oracles, (c) optimize Billiard walk, Hit and Run and exact Hamiltonian Monte Carlo for the spherical Gaussian distribution, (d) will integrate the new optimized implementations into existing implementations of volume estimation algorithms and (e) perform extended empirical comparison of all approximation counting methods.
The impact of this project will be undoubted important in several applications in Artificial Intelligence and Machine Learning.
[1] Muise, C. and Beck, J. and McIlraith, S., Optimal Partial-Order Plan Relaxation via MaxSAT, Journal of Artificial Intelligence Research, 2016
[2] T. Niinimaki and P. Parviainen and M. Koivisto, Structure Discovery in Bayesian Networks by Sampling Partial Orders, Journal of Machine Learning Research, 2016
[3] Brightwell, G. and Winkler, P., Counting linear extensions, Order, 1991
[4] De Loof, K.; De Meyer, H.; and De Baets, B., Exploiting the lattice of ideals representation of a poset, Fundamenta Informaticae, 2006
[5] Kangas, K.; Hankala, T.; Niinimaki, T.; and Koivisto, M., Counting linear extensions of sparse posets, In Proceedings of the 25th International Joint Conference on Artificial Intelligence, 2016
[6] T. Talvitie and K. Kangas and T. Niinimaki and M. Koivisto, Counting Linear Extensions in Practice : MCMC versus Exponential Monte Carlo, Thirty-Second AAAI Conference on Artificial Intelligence, 2018
[7] Karzanov, A., and Khachiyan, L., 1. On the conductance of order Markov chains, Order, 1991
[8] Stanley, Richard P., Two Poset Polytopes, Discrete & Computational Geometry, 1986
[9] Matias von Bell, Benjamin Braun, Derek Hanely, Khrystyna Serhiyenko, Julianne Vega, Andrés R. Vindas-Meléndez, Martha Yip, Triangulations, order polytopes, and generalized snake posets, preprint, 2021.
-
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-2020) and the R-project (2017-2019).
-
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) and Geomscale (2020).
-
Matias Bender holds a PhD on algebraic algorithms and he is an expert computational algebra.
- Easy: Download, compile and run a simple volume estimation example with both C++ and R interfaces of volesti.
- Medium: Implement a C++ random generator of order polytopes.
- Hard: Write in your proposal how the implementation of Hit and Run can be optimized for an order polytope.