J'ai un programme linéaire entier (ILP) avec des variables destinées à représenter des valeurs booléennes. Les sont contraints d'être des entiers et de contenir 0 ou 1 ( ).x i 0 ≤ x i ≤ 1xixix_ixixix_i0≤xi≤10≤xi≤10 \le x_i \le 1 Je veux exprimer des opérations booléennes sur ces variables à valeur...
Il y a nnn bacs et mmm type de balles. La iii ième bin a des étiquettes a i , jai,ja_{i,j} pour 1 ≤ j ≤ m1≤j≤m1\leq j\leq m , c'est le nombre attendu de billes de type jjj . Vous commencez avec b jbjb_j boules de type jjj . Chaque boule de type jjj a un poids w jwjw_j et veut placer les boules dans...
Ainsi, comme on le sait, le problème de décision 0-1 d'ILP est NP-complet. Il est facile de montrer qu'il est en NP, et la réduction d'origine provenait de SAT; depuis lors, de nombreux autres problèmes NP-Complete se sont révélés avoir des formulations ILP (qui fonctionnent comme des réductions de...
Je me demande quel est l'algorithme le plus connu, en termes de notation Big- OOO , pour résoudre la programmation linéaire en nombres entiers? Je sais que le problème est NPNPNP complet, donc je ne m'attends à rien de polynomial. Et je sais qu'il y a beaucoup d'heuristiques et autres qui sont...
Si je comprends bien, le problème d'affectation est en P car l'algorithme hongrois peut le résoudre en temps polynomial - O (n 3 ). Je comprends également que le problème d'affectation est un problème de programmation linéaire entier , mais la page Wikipedia indique que c'est NP-Hard. Pour moi,...
Je veux exprimer la contrainte suivante, dans un programme linéaire entier: y= { 01si x = 0si x ≠ 0.y={0if x=01if x≠0.y = \begin{cases} 0 &\text{if } x=0\\ 1 &\text{if } x\ne 0. \end{cases} J'ai déjà les variables entières et on me promet que . Comment puis-je exprimer la contrainte ci-dessus,...
On me donne un ensemble A≜{1,…,k}A≜{1,…,k}A\triangleq\{1,\ldots,k\} , un entier s⩽ks⩽ks\leqslant k et des entiers non négatifs aijaija_{ij} . Mon problème est de trouver sss sous - ensembles disjoints SjSjS_j de {1,…,k}{1,…,k}\{1,\ldots,k\} tel que: ⋃sj=1Sj=A⋃j=1sSj=A\bigcup_{j=1}^s S_j=A ; et...
Étant donné un programme entier (binaire) de la forme:0,10,10,1 mins.t.f(x)Ax=bxi≥0xi∈{0,1}∀i∀iminf(x)s.t.Ax=bxi≥0∀ixi∈{0,1}∀i \begin{array}{lll} \text{min} & f(x) & \\ \text{s.t.} & A x = b \\ & x_i \ge 0 & \quad \forall i\\ & x_i \in \{0,1\} & \quad \forall i \end{array} Notez que la taille de...
En supposant est une variable booléenne dans un programme d'ILP (qui est , r ) et , sont délimités entier variables entre et . Je veux encoder la contrainte de haut niveau suivante:yyyy∈ Zy∈Zy \in Z0 < = y< = 10<=y<=10