Un método de optimización que elige variables de decisión enteras para maximizar o minimizar una función objetivo lineal sujeta a un conjunto finito de restricciones lineales de igualdad e inequidad.

Principio

La restricción de integridad limita las soluciones admisibles a un subconjunto discreto del politopo de la relajación lineal; las soluciones enteras óptimas se obtienen explorando ese conjunto discreto mediante ramificación, cortes o enumeración guiada por cotas lineales.

Demostración

Situación: Una planta asigna máquinas (0 o 1) para producir dos productos con limitaciones de capacidad y demanda. Reconocimiento: Las variables representan números enteros de máquinas y deben ser enteras. Acción: Formular el objetivo lineal de beneficio, las restricciones de capacidad lineales y resolver por branch-and-bound sobre la relajación LP. Consecuencia: El solucionador devuelve una asignación entera que maximiza el beneficio total respetando las restricciones.

Aplicación incorrecta

Tratar una PLNE como equivalente a resolver el programa lineal continuo y redondear el óptimo continuo. El error semántico es suponer que el redondeo asegura factibilidad e optimalidad enteras; el redondeo puede violar restricciones y producir soluciones inviables o subóptimas.

Consecuencia

La aplicación correcta genera planes implementables y cotas de optimalidad válidas; la incorrecta (redondeo ingenuo) puede conducir a horarios inviables, violación de restricciones, costes imprevistos o sobreestimación del objetivo alcanzable.

Inversión

Si las variables enteras interactúan no linealmente (productos de variables enteras) o se permiten decisiones fraccionarias con interpretación práctica (p. ej., asignaciones esperadas en problemas estocásticos), las suposiciones estándar de la PLNE dejan de aplicarse y se requieren formulaciones mixtas no lineales o estocásticas.

Límite

Claramente dentro: Problema de localización con variables binarias de apertura/cierre y restricciones lineales de capacidad. Caso límite: Variables de conteo grandes donde la relajación LP ofrece cotas ajustadas pero se necesitan cortes especializados. Claramente fuera: Optimización entera con objetivo o restricciones no lineales (no es PLNE).

Tensión semántica

Optimalidad ↔ Factibilidad computacional — imponer integridad da soluciones aplicables pero hace el problema computacionalmente más difícil que sus relajaciones continuas.

Síntesis

La PLNE diferencia la ejecutabilidad discreta de decisiones concretas del espacio convexo continuo; su uso eficaz equilibra la exactitud discreta con estrategias computacionales que explotan cotas LP, ramificación y cortes para controlar la complejidad combinatoria.