Skip to Main content Skip to Navigation
Reports

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.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074844
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 4:33:36 PM
Last modification on : Thursday, February 11, 2021 - 2:50:07 PM
Long-term archiving on: : Sunday, April 4, 2010 - 9:43:14 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

186

Files downloads

171