Modélisation de l'égalité dans un ILP

Question

Disons que nous avons des variables entières $ a in mathbb {z} ^ n $ et $ M in {0,1 } ^ {n Times L} $. Je suis promis $ a_i leq l $, pour une constante fixe $ L $. Je veux modéliser la contrainte $$ m_ {i, j} iff (a_i = j) $$Dans un programme linéaire entier. Quelle est la façon la plus efficace de le faire dans un ILP? En particulier, puis-je le faire sans contraintes Big-M et sans décomposer chaque entier dans sa représentation binaire?

Actuellement, je peux voir deux façons de modéliser ceci:

Option 1

Nous pouvons appliquer la méthode décrite dans la réponse ici à la contrainte $ M_ {i, j} iff (a_i-j = 0) $. Cela nécessite $1$ variable binaire supplémentaire ainsi que $4$ Contraintes "Big M" potentiellement importantes $ M_ {i, j} $, résultant ainsi en $ nl $ nouvelles variables binaires et 4 nl $ Nouvelles contraintes de B.

Option 2

Nous pouvons tomber en panne $ a_i $ dans ses bits en utilisant $ log L $ Variables binaires supplémentaires. Nous pouvons également calculer les ventilations binaires correspondantes pour chacun $ 0 leq j leq l $. Laisser $ bit ^ {(a)} _ {i, k} $ Soit le $ k $le peu de $ a_i $ et laisser $ bit_ {j, k} ^ * $ Soit le $ k $le peu de l'entier $ j $, pour que$$ a_i = sum_ {k = 0} ^ { log l} 2 ^ kbit ^ {(a)} _ {i, k}. $$

Nous avons maintenant la logique suivante:$$ m_ {i, j} iff ( forall k. 0 leq k leq log l implique bit ^ {(a)} _ {i, k} odot bit_ {j, k} ^ *) $$

Par conséquent

$$ m_ {i, j} = bigwedge_ {k = 0} ^ { log l} bit ^ {(a)} _ {i, k} odot bit_ {j, k} ^ *. $$

On peut utiliser ce post Pour nxor les paires de variables, stockant leurs résultats comme une autre variable $ z = {0,1 } ^ { log L} $. Nous pouvons et ceux-ci ensemble en utilisant les contraintes $$ m_ {i, j} ge sum z_i $$ $$ m_ {i, j} leq z_i ; ; ; forall i $$

Cela crée $ log L $ nouvelles variables et 1 contrainte pour représenter la ventilation binaire de $ a_i $. Nous avons alors $ log L $ XNOR Variables, chacune qui peut être représentée avec 4 contraintes. Nous pouvons enfin représenter $ M_ {i, j} $ avec $ log L + 1 $ plus de contraintes. Par conséquent, nous avons un total de 5 $ log L $ contraintes et 2 $ log L $ Nouvelles variables par $ M_ {i, j} $, nous donnant un total de 5 N $ log L $ nouvelles contraintes binaires et 2 $ log L $ Nouvelles variables binaires.

Y a-t-il une troisième option qui est meilleure que l'une ou l'autre de ces deux options?