Casi un programa lineal. ¿Cómo resolverlo de forma eficiente?

Question

¿Cómo se puede resolver este problema de optimización de forma eficiente? Desgraciadamente, se trata de una maximización en lugar de una minimización, lo que ha obstaculizado mis intentos de convertirlo en un LP.

$$ \mbox{maximize} \sum_i \mbox{max}_{j=1}^{k} \{ {\bf c_{ij}^T x}\} $$ $$\mbox{s.t.} \;{\bf A x} \le {\bf b}$$ $$ \mbox{and} \; {\bf x} \ge 0$$

$$ {\bf x} \in {R}^d$$ $$ {\bf c_{ij}} \in {R}^d \;\;\ \forall i, j$$ $$ A \in {R}^{n \times d} $$ $$ b \in {R}^n$$

Podemos suponer que las restricciones ${\bf A x} \le {\bf b}$ definen un poliedro compacto.

---

Una versión más sencilla del problema para que quede un poco más claro. (Aquí los cuatro ${\bf c_{ij}}$ son vectores d-dimensionales conocidos).

$$ \mbox{maximize} \;\; \{ \mbox{max}({\bf c_{11}^T x}, {\bf c_{12}^T x}) + \mbox{max}({\bf c_{21}^T x}, {\bf c_{22}^T x})\}$$ $$\mbox{s.t.} \;{\bf A x} \le {\bf b}$$ $$ \mbox{and} \; {\bf x} \ge 0$$

Answer 1

Esto no es posible (todavía o nunca). Demostraré que este problema es NP-completo reduciendo SAT en su problema.

Considere una instancia de SAT como una fórmula booleana bajo forma normal conjuntiva , utilizando $c$ cláusulas y $n$ diferentes variables ( $v_1$ , $v_2$ , , $v_n$ ). Haremos una instancia de su problema con el tamaño del vector $n+1$ y $1\le i \le c$ .

Primero dejemos $A$ sea la matriz identidad de tamaño $n+1$ y $b$ el vector con sólo $1$ . Por lo tanto, $Ax<b$ y $x>0$ implica que $x$ es un vector booleano (sólo $0$ s y $1$ s).

A continuación, considere la cláusula $i$ formado por una disyunción de $v$ variables. Sea $c_{ij}$ ( $1\le j\le v$ ) tal que :

• si el $j$ a variable utilizada en la cláusula $i$ es positivo e igual a $v_m$ , dejemos que $c_{ij}$ sea un vector con sólo $0$ excepto en la posición $m$ es igual a $1$ .
• si el $j$ a variable utilizada en la cláusula $i$ es negativo e igual a $\neg v_m$ , dejemos que $c_{ij}$ sea un vector con sólo $0$ excepto en la posición $m$ es igual a $-1$ y $1$ en posición $n+1$ .

Si trata de maximizar $m_i=\max_{j=1}^{v}c_{ij}^Tx$ , comentas que :

• puedes poner un $1$ en la posición $n+1$ en $x$ porque en $c_{ij}$ en la posición $n+1$ siempre tendrás $0$ o $1$ .
• necesita tener un $1$ en la posición correcta si $c_{ij}$ está vinculada a una variable positiva en la cláusula $i$ tener $c_{ij}^Tx=1$ , si no $c_{ij}^Tx=0$ .
• necesita tener un $0$ en la posición correcta si $c_{ij}$ está vinculada a una variable negativa en la cláusula $i$ tener $c_{ij}^Tx=1$ , si no $c_{ij}^Tx=0$ .

Por lo tanto, $m_i=1$ si y sólo si la cláusula $i$ se satisface con $x$ (teniendo en cuenta la $n$ primeras coordenadas de $x$ como valor verdadero/falso para la variable $v_1$ , , $v_n$ ).

Por tanto, la fórmula es satisfacible si el máximo de la instancia creada es igual a $c$ (el número de cláusulas satisfechas).

Por lo tanto, su problema es NP-duro, porque esta reducción es polinómica (cuadrática de hecho)

Es NP-completo, porque con el $x$ se puede calcular fácilmente el máximo (y verificar cualquier suposición al respecto).

---

Tenga en cuenta que puede rellenar con $c_{ij}=0$ Si necesita tener $1\le i\le k$ y $1\le j \le k$ con el mismo $k$ para ambos.

Answer 2

Tenemos que $\mathbf{c_{ij}^T\,x} $ es lineal en $\mathbf x$ así que $\max_j \mathbf{c_{ij}^T\,x} $ es convexo en $\mathbf x$ Por lo tanto $\sum_i \max_j\mathbf{c_{ij}^T\,x}$ también es convexo en $\mathbf x$ . Ahora se nos da que el conjunto $C=\{\mathbf x : \mathbf{Ax}\le \mathbf{b}\text{ and } \mathbf x \ge 0\}$ es un poliedro compacto, en particular es un conjunto convexo. Como estamos maximizando una función convexa en un conjunto convexo, sabemos que al menos uno de sus máximos debe estar en un punto extremo. Por lo tanto, para encontrar un máximo tenemos que evaluar la función objetivo en los vértices de $C$ que es un conjunto finito.