Abstract FR:

Ce travail s'interesse a la facon d'integrer les proprietes geometriques et arithmetiques a l'etude et a la resolution de programmes lineaires en nombres entiers. Se voulant autonome, il expose, dans la premiere partie, les differents problemes lineaires, leur complexite et les methodologies classiques pour les resoudre. La seconde partie concerne les apports originaux de cette these. Nous presentons une condition suffisante de realisabilite d'un probleme lineaire entier en termes d'epaisseur du polyedre associe. La finesse de ce polyedre semblant etre un critere de difficulte de resolution, nous nous sommes interesses a un changement de variables l'epaississant, conservant l'integrite et fournissant aisement des coupes. Nous avons ainsi utilise les particularites de la forme normale de hermite, pour elaborer des methodes de coupes et de separation evaluation, cette derniere methode fournissant des resultats prometteurs. Un autre axe de notre recherche est base sur le treillis des entiers. La plus grande part theorique de cette these consiste en l'etude des ensembles de minima locaux entiers d'une fonction convexe que nous caracterisons en terme de reseaux stochastiques. Nous presentons un algorithme, dit de poursuite, navigant sur le treillis des entiers en minimisant une fonction distance au polyedre, definie comme combinaison lineaire des distances aux faces. Nous proposons differentes strategies de choix des coefficients (aleatoires et deterministes) de cette combinaison lineaire, que nous comparons et classifions