HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 4:33:36 PM
Last modification on : Friday, February 4, 2022 - 3:19:43 AM
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

92

Files downloads

95