Inequações Lineares Válidas para Problemas de Custo Fixo

Muitos problemas na literatura de Pesquisa Operacional/Ciências da Gestão podem ser formulados com variáveis binárias e contínuas. No entanto, a otimização exata de tais modelos mistos binários continua sendo um desafio computacional. Neste artigo, propomos estudar problemas mistos de um ponto de vista matemático que é semelhante em espírito às pesquisas recentes sobre problemas puramente combinatórios que investigaram sistemas de definição de inequações lineares (ou facetas do poliedro subjacente). Pelo menos dois estudos numéricos validaram essa linha de pesquisa computacionalmente, e os avanços nas capacidades de resolução de problemas são consideráveis. Esperamos que ganhos semelhantes sejam possíveis para o problema misto binário. Mais precisamente, consideramos os programas mistos inteiros cuja região viável X é composta por (i) uma restrição aditiva simples nas variáveis contínuas x j, para j = 1, 2, …, n e (ii) restrições 0 ≤ x j ≤ m j y j definidas por variáveis binárias y j para j = 1, 2, …, n. Esse tipo de região viável surge em uma variedade de problemas mistos inteiros, e particularmente em problemas de rede com custos fixos nos arcos. Derivamos duas classes de inequações lineares definidoras de facetas do envoltório convexo de X e mostramos que a segunda dessas classes fornece uma descrição completa do envoltório convexo quando m j = m para todos os j. Também desenvolvemos métodos para detectar inequações violadas dessas classes, para que essas facetas possam ser usadas como planos de corte para fortalecer as formulações de certos problemas mistos inteiros.