Resolución de un sistema de ecuaciones con variables booleanas en $\mathbb{Z}_3$

Question

Tengo un problema que se reduce a un sistema de $2n+1$ igualdades en $4n$ variables todas en $\mathbb{Z}_3$ donde las variables están limitadas a estar en $\{0,1\}$ , es decir ,

$$x_1 + x_2 + ... + x_k \equiv a\ (\mathrm{mod}\ 3)$$

$$x_2 + x_3 + ... + x_l \equiv b\ (\mathrm{mod}\ 3)$$

$$\cdots$$

$$x_m + ... + x_{4n} \equiv c\ (\mathrm{mod}\ 3)$$

El lado derecho ( $a$ , $b$ , $c$ , $\ldots$ ) es conocido, pero no necesariamente en $\{0,1\}$ pero en $\{0,1,2\}$ .

No he encontrado una forma mejor de resolver esto que un enfoque de fuerza bruta en las variables libres, porque haciendo la eliminación gaussiana, puedo obtener un sistema triangular superior, pero eso sólo me daría una solución si mis variables estuvieran en $\{0,1,2\}$ .

Así que mi pregunta es si hay una forma más eficiente, en tiempo polinómico, de resolver este sistema que pueda haber pasado por alto. Si no es así, ¿hay algún resultado de complejidad que demuestre que este problema es difícil en el caso general?

Answer 1

Si lo he entendido bien, quieres encontrar una solución al sistema :

$$Ax = b$$

Dónde $A$ es una matriz binaria, $x = (x_1, x_2, ... , x_n)^T$ un vector de variables, y $b = (b_1, b_2, ..., b_m)$ un vector del lado derecho, con $b_i \in \{0, 1, 2\} \; \forall i \in \{1, ..., m\}$ .

Si es así, quiere resolver un programa de números enteros.

Por desgracia, programas enteros son NP-Completas en general, y su caso especial incluye la set-partitioning que también es NP-completo.

Cómo solucionarlo

Porque los programas enteros tienen un montón de las aplicaciones de la vida real, se han ideado algoritmos y programas informáticos especializados para resolverlas. Según mi experiencia, resolver un problema con menos de 1000 variables debería llevar menos de un segundo, pero realmente depende del problema... Los solucionadores que ofrecen un mayor rendimiento son probablemente cplex o gurobi (no son gratuitos, pero creo que ofrecen una versión gratuita para estudiantes). También hay solucionadores de código abierto como GLPK y lp_solve . Si tienes un problema relativamente pequeño (tal vez menos de 100 variables), puedes incluso utilizar el solucionador de Excel, aunque realmente no es el mejor.

En cualquier caso, usted no quiere codificarla usted mismo. Estos programas tienen décadas de mejoras en ellos y por eso funcionan bien.

Cómo funciona el algoritmo

Todo solucionador comercial resuelve el problema mediante _rama y límite_ .

Un algoritmo branch-and-bound consiste en una enumeración sistemática de soluciones candidatas mediante la búsqueda en el espacio de estados: el conjunto de soluciones candidatas se considera que forma un árbol rooteado con el conjunto completo en la raíz. El algoritmo explora las ramas de este árbol, que representan subconjuntos del conjunto de soluciones. Antes de enumerar las Antes de enumerar las soluciones candidatas de una rama, la rama se comprueba con los límites superiores y los límites inferiores estimados de la solución óptima, y se descarta si no puede producir una solución mejor que la mejor encontrada hasta el momento por el algoritmo.

Su problema es un problema de viabilidad y no de optimización, por lo que no es necesario calcular los límites. Sin embargo, el algoritmo tiene que comprobar si la rama actual es inviable. Esto se suele hacer resolviendo una relajación lineal del problema (aceptando soluciones con variables fraccionarias).

Los solucionadores comerciales también utilizan muchos trucos de reducción para acelerar el algoritmo. Por desgracia, ¡muchos de esos trucos son secretos!