Analysis of standard and new algorithms for the integer ans linear constraint satisfaction problem

Abstract : The integer and linear constraint satisfaction problem, which consists in proving the emptiness of the set of integer points satisfying a set of linear constraints or the existence of a solution, is very frequent in the field of computer science (vectorization, code scheduling, etc.). Most methods proposed in the literature deal with various specific instances of this problem. In this paper, the problem is considered in its general form. Some standard methods are analyzed. Some new algorithms are proposed, either to simplify the problem, or to solve exactly (by cutting plane methods) the reduced for of the problem. A sequence of such algorithms is implemented in the automatic parallelizer available under PIAF, an interactive programming environment for FORTRAN. However, these algorithms could be applied to more difficult problems than the usual ones appearing in data dependence analysis.
Type de document :
Rapport
[Research Report] RR-1828, INRIA. 1992
Liste complète des métadonnées

https://hal.inria.fr/inria-00074844
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 16:33:36
Dernière modification le : vendredi 16 septembre 2016 - 15:19:38
Document(s) archivé(s) le : dimanche 4 avril 2010 - 21:43:14

Fichiers

Identifiants

  • HAL Id : inria-00074844, version 1

Collections

Citation

Jean-Claude Sogno. Analysis of standard and new algorithms for the integer ans linear constraint satisfaction problem. [Research Report] RR-1828, INRIA. 1992. 〈inria-00074844〉

Partager

Métriques

Consultations de la notice

166

Téléchargements de fichiers

123