Optimización entera y combinatoria

Una variable entera puede contar unidades: x∈Z y x≥0. Una binaria vale cero o uno y suele representar no elegir o elegir un objeto concreto. No es una probabilidad en este modelo determinista. Una restricción y un objetivo se comprueban usando ese significado desde el inicio.

Un modelo mixto combina decisiones continuas y enteras. La cantidad de líquido puede ser divisible mientras encender una instalación es sí/no. Retirar integridad da una relajación, que puede servir como cota, pero no autoriza a interpretar sus fracciones como decisiones del problema original.

Para objetos de pesos positivos wᵢ, valores no negativos vᵢ y capacidad W≥0, buscamos maximizar Σvᵢxᵢ con Σwᵢxᵢ≤W y xᵢ∈{0,1}. El peso consume capacidad y el valor es lo que queremos aumentar. El plan vacío está permitido salvo que añadamos otra condición.

El mayor valor individual no siempre produce la mejor combinación. Tampoco ordenar por valor/peso garantiza la mochila binaria: puede dejar un hueco que impida añadir otro objeto. Esa regla sí resuelve la versión clásica fraccionaria, donde podemos dividir objetos; intercambiar peso de menor proporción por peso disponible de mayor proporción no empeora su valor.

En un máximo, el óptimo relajado es una cota superior y un plan entero factible da una inferior. En un mínimo se invierten las direcciones. Si una solución óptima relajada ya es entera, también resuelve el problema entero.

Para certificar una cota de mochila podemos usar un precio λ≥0 por unidad de peso: Σvᵢxᵢ≤λW+Σmax(0, vᵢ−λwᵢ) para 0≤xᵢ≤1. Se obtiene separando λΣwᵢxᵢ y acotando cada término restante según su signo. Esto produce una desigualdad para todos los planes relajados, no solo una predicción optimista.

Una capacidad superior puede romperse al redondear hacia arriba. Una obligación mínima o una igualdad puede romperse al hacerlo hacia abajo. Incluso si el resultado es factible, otra combinación puede tener mejor objetivo. Un candidato redondeado se verifica desde cero contra el modelo original.

La distinción es entre redondear una cota válida con información de integridad y redondear una decisión coordenada a coordenada. Lo primero puede conservar un certificado; lo segundo es una heurística y no una prueba general.

Con n decisiones binarias independientes hay 2ⁿ combinaciones antes de filtrar restricciones: dos opciones en cada posición. Para n pequeño podemos comprobarlas todas, descartar las infactibles y comparar objetivos. Si añadimos condiciones como elegir exactamente dos, podemos enumerar directamente las selecciones que las cumplen.

Cada nueva variable binaria duplica la lista. De diez a veinte variables se pasa de 1024 a 1048576 combinaciones; la enumeración completa puede dejar de ser práctica. Esto no significa que toda familia combinatoria sea igual de difícil: estructura, representación y cotas pueden evitar gran parte del trabajo.

Con pesos enteros positivos y capacidad entera W≥0, V(i, w) es el mayor valor usando solo los primeros i objetos y capacidad como máximo w.

Si el objeto i cabe, comparamos V(i−1, w) con vᵢ+V(i−1, w−wᵢ); si no cabe, solo queda la primera opción. Usar i−1 en ambos casos evita reutilizarlo.

La tabla tiene (n+1)(W+1) celdas y un número constante de opciones por celda, aparte del coste aritmético de los valores; se resume como O(nW) para W≥1. Es pseudopolinómica: W escrito en binario necesita solo unas log₂W cifras, mientras la tabla depende de W. Una tabla unidimensional puede ahorrar memoria, pero el orden de actualización debe conservar la versión 0/1.

En un nodo resolvemos una relajación. Si es infactible, el nodo no contiene planes enteros. Si su solución óptima ya es entera, aporta un candidato y resuelve ese nodo. Si xⱼ=t es fraccionario, dividimos entre xⱼ≤⌊t⌋ y xⱼ≥⌈t⌉: todo entero del nodo pertenece a una de las dos ramas.

En maximización, una relajación con cota superior U≤B no puede mejorar el valor B de un plan entero conocido, así se poda. B debe venir de un plan realmente factible y U de una cota válida. Una aproximación optimista sin control no autoriza eliminar soluciones posibles.

Si el mejor plan entero de un máximo vale B y los nodos abiertos tienen cotas U₁,…, Uₖ, una cota global es max(B, U₁,…, Uₖ). No se suman: los nodos representan planes alternativos. Si todos se cierran o sus cotas quedan por debajo de B, el valor está certificado.

Con objetivo entero, una cota superior puede redondearse hacia abajo manteniendo validez.

Algunas formulaciones de redes tienen vértices integrales con datos adecuados y admiten un óptimo entero mediante su relajación. Eso no significa que todo punto factible o todo óptimo de esa relajación sea entero. Tampoco se extiende la propiedad a cualquier matriz de restricciones. Las tolerancias de un solucionador deben distinguirse de un certificado matemático exacto.