Considere el espacio dimensional , y deje que sea una restricción lineal de la forma , donde , y .{ 0 , 1 } n c a 1 x 1 + a 2 x 2 + a 3 x 3 + . . . + a n - 1 x n - 1 + a n x n ≥ k a i ∈ R x i ∈ { 0 , 1 } k ∈ R
Claramente, tiene el efecto de dividir en dos subconjuntos y . contiene todos y solo aquellos puntos que satisfacen , mientras que contiene todos y solo aquellos puntos que falsifican .{ 0 , 1 } n S c S ¬ c S c c S ¬ c c
Suponga que . Ahora, dejemos que sea un subconjunto de tal forma que se las siguientes tres declaraciones:O S c
- contiene exactamente puntos.
- Tales puntos son linealmente independientes.
- Tales puntos son aquellos a una distancia mínima del hiperplano representado por . Más precisamente, sea la distancia de un punto desde el hiperplano . Entonces, modo que satisfaga 1 y 2 es el caso de que . En otras palabras, es, entre todos los subconjuntos de satisfacen ambas condiciones 1 y 2, el que minimiza la suma de las distancias de sus puntos desde el hiperplano .c d ( x , c ) x ∈ { 0 , 1 } n c ∀ B ⊆ S c B ∑ x ∈ B d ( x , c ) ≥ ∑ x ∈ O d ( x , c ) O S c c
Preguntas
- Dado , ¿es posible calcular eficiente? O
- ¿Cuál es el algoritmo más conocido para calcularlo?
Ejemplo con
, .
Actualización 12/05/2012
Motivación
La motivación es que el uso de que debería ser posible determinar la óptima restricción c * , como debe ser el hiperplano definido por los n puntos en O .
La restricción óptima es la que conduce al politopo óptimo .
El politopo óptimo es aquel cuyos vértices son todos y solo los vértices enteros del politopo inicial (un vértice entero es un vértice cuyas coordenadas son todas enteras).
El proceso puede iterarse para cada restricción de una instancia 0-1 , cada vez que sustituya con su correspondiente restricción óptima . Al final, esto dará lugar a la óptima politopo P * de I . Entonces, dado que los vértices de P ∗ son todos y solo los vértices enteros del politopo inicial P de I ,se puede usarcualquier algoritmo para L P para calcular la solución entera óptima. Sé que ser capaz de calcular P ∗ de manera eficiente implicaría P = , sin embargo, la siguiente pregunta adicional sigue en pie:
Pregunta adicional
¿Hay algún trabajo previo en este sentido? ¿Alguien ya se investigó la tarea de calcular, dado un politopo , su correspondiente óptima politopo P * ? ¿Cuál es el algoritmo más conocido para hacer eso?
fuente
Respuestas:
Esto parece ser NP-difícil de hacer exactamente, por reducción de la suma del subconjunto. Supongamos que tenemos un procedimiento eficaz para calcular . Dados enteros positivos v 1 , ... , v n codificados en binario, deseamos probar si hay un subconjunto que sume a s . Preprocese arrojando cualquier número entero mayor que s .O v1, ... , vnorte s s
Llame al procedimiento para obtener un pequeño conjunto de puntos que satisfagan v 1 x 1 + ⋯ + v 1 x n ≤ s , satisfaciendo sus condiciones de minimidad (el preprocesamiento asegura | S c | ≥ n ). Este conjunto ciertamente contendrá un punto en el hiperplano v 1 x 1 + ⋯ + v 1 x n = s si hay uno.O v1X1+ ⋯ + v1Xnorte≤ s El | SCEl | ≥n v1X1+ ⋯ + v1Xnorte= s
fuente
Me parece que está tratando de llegar al casco convexo de la IP; en esencia, esto es lo que intentan lograr los algoritmos de corte. Aunque, desde el punto de vista lógico, estos métodos no funcionan bien en la práctica.
Existe toda la teoría sobre la generación de desigualdades válidas. Un buen punto de partida sería la teoría del libro de shrijver de la programación de enteros.
fuente