Towards an Efficient Parallel Parametric Linear Programming Solver - IMAG Accéder directement au contenu
Thèse Année : 2019

Towards an Efficient Parallel Parametric Linear Programming Solver

Vers un solveur de programmation linéaire paramétrique parallèle efficace

Hang Yu
  • Fonction : Auteur

Résumé

VPL (Verified Polyhedra Library) is an abstract polyhedra domain using constraint-only description. All main operators boiled down to polyhedral projection, which can be computed using Fourier-Motzkin elimination. This method generates many redundant constraints which must be eliminated at a high cost. A novel algorithm was implemented in VPL for computing the polyhedral projection using parametric linear programming (PLP), which can replace Fourier-Motzkin elimination. This PLP solver can also be used for computing the join operator (convex hull). Our work focuses on improving the efficiency of the algorithm of PLP solver.In prior work, PLP was done in arbitrary precision rational arithmetic. In this work, we present an approach where most of the computations are performed in floating-point arithmetic, and then exact rational results are reconstructed. The result obtained from our approach is guaranteed to be sound. We also propose a workaround for a difficulty called degeneracy, which plagued previous attempts at using PLP for computations on polyhedra: in general the (parametric) linear programming problems are degenerated, resulting in redundant computations and duplicates in geometric descriptions.The algorithm of the PLP solver is intrinsically parallelable, however it was developed in VPL with OCaml, which does not well support parallelism programming. In our approach, which is implemented with C++, we proposed a task-based scheme for parallelizing it. Two parallel implementations have been realized using two different parallel mechanisms: Intel’s Thread Building Blocks (TBB) and OpenMP tasks.
VPL (Verified Polyhedra Library) est un domaine de polyhèdres abstraits utilisant une description uniquement par contrainte. Tous les opérateurs principaux se résumaient à une projection polyédrique pouvant être calculée à l'aide de l'élimination de Fourier-Motzkin. Cette méthode génère de nombreuses contraintes redondantes qui doivent être éliminées à un coût élevé. Un nouvel algorithme a été mis en œuvre dans VPL pour calculer la projection polyédrique à l'aide de la programmation linéaire paramétrique (PLP), qui peut remplacer l'élimination de Fourier-Motzkin. Ce solveur PLP peut également être utilisé pour calculer l’opérateur de jointure (coque convexe). Notre travail est axé sur l'amélioration de l'efficacité de l'algorithme du solveur PLP.Dans des travaux antérieurs, le PLP était effectué en arithmétique rationnelle de précision arbitraire. Dans ce travail, nous présentons une approche dans laquelle la plupart des calculs sont effectués en arithmétique en virgule flottante, puis les résultats rationnels exacts sont reconstruits. Le résultat obtenu grâce à notre approche est assuré d'être solide. Nous proposons également une solution de contournement à une difficulté appelée dégénérescence, qui entachait les tentatives précédentes d’utilisation de PLP pour les calculs sur polyèdres: en général, les problèmes de programmation linéaire (paramétrique) sont dégénérés, ce qui entraîne des calculs redondants et des doublons dans les descriptions géométriques.L'algorithme du solveur PLP est intrinsèquement parallèle, mais il a été développé en VPL avec OCaml, qui ne prend pas bien en charge la programmation en parallélisme. Dans notre approche, qui est implémentée avec C ++, nous avons proposé un schéma basé sur les tâches pour le paralléliser. Deux implémentations parallèles ont été réalisées en utilisant deux mécanismes parallèles différents: les blocs de construction de threads (TBB) d’Intel et les tâches OpenMP.
Fichier principal
Vignette du fichier
YU_2019_archivage.pdf (3.93 Mo) Télécharger le fichier
Origine : Version validée par le jury (STAR)
Loading...

Dates et versions

tel-02964528 , version 1 (12-10-2020)

Identifiants

  • HAL Id : tel-02964528 , version 1

Citer

Hang Yu. Towards an Efficient Parallel Parametric Linear Programming Solver. Computer Arithmetic. Université Grenoble Alpes, 2019. English. ⟨NNT : 2019GREAM081⟩. ⟨tel-02964528⟩
153 Consultations
183 Téléchargements

Partager

Gmail Facebook X LinkedIn More