Bonjour à tous!
Je suis sur un système linéaire.
Il y a une dizaine d'équations et une centaine d'inconnues. Les coefficients sont des nombres entiers compris entre 1000 et 2000. Les seules valeurs autorisées pour les inconnues sont 0 et 1.
Comment résoudre un tel système? Ce type de problème est-il classique? Existe-t-il un logiciel adéquat?
J'ai essayé avec Maple, qui me donne très vite une représentation paramétrique des solutions (utilisant quelque chose comme 90 paramètres indépendants) mais je ne sais comment lui imposer , en un temps raisonnable, les seules valeurs 0 et 1 pour les inconnues.
Tout renseignement sera le bienvenu. Merci d'avance pour votre aide.
rogerd
salut
si les solutions ne peuvent être que 0 et 1 peut-être travailler un base 2 pour obtenir un nombre fini de solutions puis les essayer une par une ....
Bonjour carpediem,
ça fait quand même 2^100 solutions :/, ca met du temps de les essayer (même en faisaint 10000 vérifications/sec ca prends quelques années je crois)....
Moi j'irai plutôt voir du côté de l'optimisation discrète (méthode simplex etc...), dans mes souvenirs il y a des méthodes pour résoudre des systèmes d'équations avec contraintes sur les solutions (particulièrement lorsque ces dernières doivent faire partie d'un polygone intégral convexe, genre un hypercube ).
Bonjour et merci à Carpediem de se pencher sur mon problème.
J'ai 90 paramètres arbitraires pouvant prendre chacun 2 valeurs.
Je pense que l'essai un par un est impraticable.
Cela dit, Maple sait résoudre un système, à coefficients entiers, modulo un entier qu'on lui impose. Cela donne des résultats moins monstrueux que lorsque l'on considère les coefficients comme réels mais je tombe toujours sur une solution avec 90 paramètres dont je ne sais que faire.
Merci encore
Rebonsoir
Surb : je viens seulement de lire ton courrier. Pourrais-tu faire un effort de mémoire? (tes souvenirs sont alléchants!).Merci d'avance.
J'ai un peu relu ce qui concerne la méthode du simplexe ; je ne vois pas comment l'utiliser pour mon problème.
Bonjour,
Je n'ai (malheureusement) pas porté un grand intérêt à l'optimisation discrète (genre ca m'ennuie) du coup je peux te donner des documents sans pouvoir te garantir à 100% que ça répondra complètement à ta question.
Dans tous les cas va voir:
Ce qui t'intéresse c'est:
lecture notes -> Chapter 5: Integer programming
(va regarder dans les exercices aussi peut être que tu trouveras des trucs sympa (tout est avec corrigé )
C'est le mieux que je puisse faire
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :