onur (./11) :
A*X <= B, si A est une matrice totalement unimodulaire, tu n'as pas besoin de forcer les xi à entier (et ca resoudra en temps polynomial)

Elle ne l'est pas

et mettre le problème sous cette forme revient à utiliser un programme externe pour résoudre le problème (genre glpk, lp_solve ou cplex qui est le meilleur même s'il coûte la peau des fesses)