Dado $\vec{a}, \vec{b} \in \mathbb{Z}^d$ y un sistema de dos ecuaciones: $$ \begin{cases} \langle \vec{a}, \vec{x} \rangle = 0 \\ \langle \vec{b}, 1-\vec{x} \rangle = 0 \end{cases} $$ donde $\vec{x} \in \{0, 1\}^d$ . Aquí $\langle,\rangle$ se refiere al producto interior y $1-\vec{x}$ se refiere a todo 1 vector menos $\vec{x}$ .
¿Cómo puedo verificar que dicho sistema existe una solución para $\vec{x}$ ?
Si hay soluciones, ¿cómo puedo enumerarlas todas?
Para los pequeños $d$ por supuesto, puede enumerar todos los $x\in \lbrace 0,1 \rbrace^d$ y probarlos todos en el sistema de ecuaciones.
De forma más general, para determinar si existe una solución se puede tratar el problema como un programa entero binario con una función objetivo trivial (minimizar 0 sujeto a sus dos ecuaciones) y resolverlo con cualquier solucionador de PIM. Una forma (que lleva mucho tiempo) de enumerar todas las soluciones es resolver el modelo MIP, añadir una restricción que prohíba la solución que se obtuvo (y sólo esa solución), y repetir. Para eliminar una solución $x=\hat{x}$ se añade la restricción $$\sum_{i:\hat{x}_i=0} x_i + \sum_{j:\hat{x}_j=1} (1-x_j) \ge 1.$$
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
