Français Anglais
Accueil Annuaire Plan du site
Accueil > Production scientifique > Résultat majeur
Production scientifique
Résultat majeur : A SIMPLEX-BASED EXTENSION OF FOURIER-MOTZKIN FOR SOLVING LINEAR INTEGER ARITHMETIC
A SIMPLEX-BASED EXTENSION OF FOURIER-MOTZKIN FOR SOLVING LINEAR INTEGER ARITHMETIC
05 juillet 2012

François Bobot, Sylvain Conchon, Evelyne Contejean, Mohamed Iguernelala, Assia Mahboubi, Alain Mebsout, and Guillaume Melquiond. IJCAR 2012
This paper describes a novel decision procedure for quantifier-free linear integer arithmetic. Standard techniques usually relax the initial problem to the rational domain and then proceed either by projection (e.g. Omega-Test) or by branching/cutting methods (branch-and-bound, branch-and-cut, Gomory cuts). Our approach tries to bridge the gap between the two techniques: it interleaves an exhaustive search for a model with bounds inference. These bounds are computed provided an oracle capable of finding constant positive linear combinations of affine forms. We also show how to design an efficient oracle based on the Simplex procedure. Our algorithm is proved sound, complete, and terminating and is implemented in the Alt-Ergo theorem prover. Experimental results are promising and show that our approach is competitive with state-of-the-art SMT solvers.



Activités de recherche
  ° Démonstration automatique

Equipe
  ° Toccata
  ° Vérification d'Algorithmes, Langages et Systèmes

Contact
  [aucun]
Résultats majeurs
COMPUTER‐AIDED BIOCHEMICAL PROGRAMMING OF SYNTHETIC MICROREACTORS AS DIAGNOSTIC DEVICES
27 avril 2018
Alexis Courbet, Patrick Amar, Francois Fages, Eric Renard, Franck Molina Mol Syst Biol. (2018) 14:

BEST PAPER AWARD: SELF-STABILIZING DISTRIBUTED STABLE MARRIAGE
05 novembre 2017
SSS 2017, M. Laveau, G. Manoussakis, J. Beauquier, T. Bernard, J. Burman, J. Cohen, and L. Pilard

BEST PAPER AWARD INTELLI 2017: A MODEL OF PULSATION FOR EVOLUTIVE FORMALIZING INCOMPLETE INTELLIGENT SYSTEMS
27 juillet 2017
authors: Marta Franova, Yves Kodratoff

INFORMATION-GEOMETRIC OPTIMIZATION ALGORITHMS: A UNIFYING PICTURE VIA INVARIANCE PRINCIPLES
02 mai 2017
Yann Ollivier, Ludovic Arnold, Anne Auger, Nikolaus Hansen - JMLR 18(18):1−65, 2017.

FORMAL MUTATION TESTING FOR CIRCUS
21 avril 2016
Alex Donizeti Betez Alberto, Ana Cavalcanti, Marie-Claude Gaudel, Adenilso Simao Journal of Infor