Programação inteira - Integer programming

Um problema de programação inteira é uma otimização matemática ou programa de viabilidade no qual algumas ou todas as variáveis são restritas a serem números inteiros . Em muitos ambientes, o termo se refere à programação linear inteira (ILP), na qual a função objetivo e as restrições (além das restrições de número inteiro) são lineares .

A programação inteira é NP-completa . Em particular, o caso especial de programação linear inteira 0-1, em que as incógnitas são binárias e apenas as restrições devem ser satisfeitas, é um dos 21 problemas NP-completos de Karp .

Se algumas variáveis de decisão não forem discretas, o problema é conhecido como um problema de programação de número inteiro misto .

Formulário canônico e padrão para ILPs

Na programação linear inteira, a forma canônica é diferente da forma padrão . Um programa linear inteiro em forma canônica é expresso assim (observe que é o vetor que deve ser decidido): ${\ displaystyle \ mathbf {x}}$

{\ displaystyle {\ begin {alinhados} & {\ text {maximize}} && \ mathbf {c} ^ {\ mathrm {T}} \ mathbf {x} \\ & {\ text {subject to}} && A \ mathbf {x} \ leq \ mathbf {b}, \\ &&& \ mathbf {x} \ geq \ mathbf {0}, \\ & {\ text {and}} && \ mathbf {x} \ in \ mathbb {Z} ^ {n}, \ end {alinhado}}}

e um ILP na forma padrão é expresso como

{\ displaystyle {\ begin {alinhados} & {\ text {maximize}} && \ mathbf {c} ^ {\ mathrm {T}} \ mathbf {x} \\ & {\ text {subject to}} && A \ mathbf {x} + \ mathbf {s} = \ mathbf {b}, \\ &&& \ mathbf {s} \ geq \ mathbf {0}, \\ &&& \ mathbf {x} \ geq \ mathbf {0}, \\ & {\ text {and}} && \ mathbf {x} \ in \ mathbb {Z} ^ {n}, \ end {alinhado}}}

onde são vetores e é uma matriz, onde todas as entradas são inteiras. Tal como acontece com os programas lineares, os ILPs que não estão na forma padrão podem ser convertidos para a forma padrão , eliminando desigualdades, introduzindo variáveis de folga ( ) e substituindo as variáveis que não são restritas por sinal pela diferença de duas variáveis restritas por sinal ${\ displaystyle \ mathbf {c}, \ mathbf {b}}$ ${\ displaystyle A}$ ${\ displaystyle \ mathbf {s}}$

Exemplo

Polítopo IP com relaxamento LP

O gráfico à direita mostra o seguinte problema.

{\ displaystyle {\ begin {alinhado} \ max & {\ text {}} y \\ - x + y & \ leq 1 \\ 3x + 2y & \ leq 12 \\ 2x + 3y & \ leq 12 \\ x, y & \ geq 0 \\ x, y & \ in \ mathbb {Z} \ end {alinhado}}}

Os pontos inteiros viáveis são mostrados em vermelho, e as linhas tracejadas vermelhas indicam seu invólucro convexo, que é o menor poliedro convexo que contém todos esses pontos. As linhas azuis junto com os eixos coordenados definem o poliedro da relaxação LP, que é dada pelas desigualdades sem a restrição de integralidade. O objetivo da otimização é mover a linha pontilhada preta o máximo para cima enquanto ainda toca o poliedro. As soluções ótimas do problema dos inteiros são os pontos e que ambos têm um valor objetivo de 2. O ótimo único da relaxação é com valor objetivo de 2,8. Se a solução da relaxação for arredondada para os números inteiros mais próximos, isso não é viável para o ILP. ${\ displaystyle (1,2)}$ ${\ displaystyle (2,2)}$ ${\ displaystyle (1.8,2.8)}$

Prova de NP-dureza

A seguir está uma redução da cobertura mínima do vértice para a programação inteira que servirá como a prova da dureza NP.

Let ser um gráfico não direcionado. Defina um programa linear da seguinte forma: ${\ displaystyle G = (V, E)}$

{\ displaystyle {\ begin {alinhado} \ min \ sum _ {v \ in V} y_ {v} \\ y_ {v} + y_ {u} & \ geq 1 && \ forall uv \ in E \\ y_ {v } & \ geq 0 && \ forall v \ in V \\ y_ {v} & \ in \ mathbb {Z} && \ forall v \ in V \ end {alinhado}}}

Dado que as restrições se limitam a 0 ou 1, qualquer solução viável para o programa inteiro é um subconjunto de vértices. A primeira restrição implica que pelo menos um ponto final de cada aresta está incluído neste subconjunto. Portanto, a solução descreve uma cobertura de vértices. Além disso, dada a cobertura de vértices C, pode ser definido como 1 para qualquer e como 0 para qualquer , dando-nos uma solução viável para o programa inteiro. Assim, podemos concluir que se minimizarmos a soma de também encontramos a cobertura mínima do vértice. ${\ displaystyle y_ {v}}$ ${\ displaystyle y_ {v}}$ ${\ displaystyle v \ in C}$ ${\ displaystyle v \ not \ in C}$ ${\ displaystyle y_ {v}}$

Variantes

A programação linear inteira mista ( MILP ) envolve problemas em que apenas algumas das variáveis ,, são restritas a inteiros, enquanto outras variáveis podem ser não inteiros. ${\ displaystyle x_ {i}}$

A programação linear zero-um (ou programação inteira binária ) envolve problemas nos quais as variáveis são restritas a 0 ou 1. Qualquer variável inteira limitada pode ser expressa como uma combinação de variáveis binárias. Por exemplo, dada uma variável inteira,, a variável pode ser expressa usando variáveis binárias: ${\ displaystyle 0 \ leq x \ leq U}$ ${\ displaystyle \ lfloor \ log _ {2} U \ rfloor +1}$

{\ displaystyle x = x_ {1} + 2x_ {2} + 4x_ {3} + \ cdots +2 ^ {\ lfloor \ log _ {2} U \ rfloor} x _ {\ lfloor \ log _ {2} U \ rfloor +1}.}

Formulários

Existem duas razões principais para usar variáveis inteiras ao modelar problemas como um programa linear:

As variáveis inteiras representam quantidades que só podem ser inteiras. Por exemplo, não é possível construir carros 3,7.
As variáveis inteiras representam decisões (por exemplo, se incluir uma borda em um gráfico ) e, portanto, devem assumir apenas o valor 0 ou 1.

Essas considerações ocorrem com frequência na prática e, portanto, a programação linear inteira pode ser usada em muitas áreas de aplicativos, algumas das quais são descritas resumidamente a seguir.

Planejamento de produção

A programação de número inteiro misto tem muitas aplicações em produções industriais, incluindo modelagem job-shop. Um exemplo importante acontece no planejamento da produção agrícola envolve a determinação do rendimento da produção para várias culturas que podem compartilhar recursos (por exemplo, terra, trabalho, capital, sementes, fertilizantes, etc.). Um possível objetivo é maximizar a produção total, sem exceder os recursos disponíveis. Em alguns casos, isso pode ser expresso em termos de um programa linear, mas as variáveis devem ser restringidas para serem inteiras.

Agendamento

Esses problemas envolvem a programação de serviços e veículos nas redes de transporte. Por exemplo, um problema pode envolver a atribuição de ônibus ou metrôs a rotas individuais para que um horário possa ser cumprido e também para equipá-los com motoristas. Aqui, as variáveis de decisão binárias indicam se um ônibus ou metrô é atribuído a uma rota e se um motorista é atribuído a um determinado trem ou metrô. A técnica de programação zero-um foi aplicada com sucesso para resolver um problema de seleção de projeto no qual os projetos são mutuamente exclusivos e / ou tecnologicamente interdependentes. É usado em um caso especial de programação de inteiros, em que todas as variáveis de decisão são inteiros. Ele pode assumir os valores como zero ou um.

Particionamento Territorial

O problema de repartição territorial ou distrital consiste em repartir uma região geográfica em distritos de forma a planear algumas operações tendo em consideração diferentes critérios ou constrangimentos. Alguns requisitos para este problema são: contiguidade, compactação, equilíbrio ou equidade, respeito aos limites naturais e homogeneidade socioeconômica. Algumas aplicações para este tipo de problema incluem: distrito político, distrito escolar, distrito de serviços de saúde e distrito de gestão de resíduos.

Redes de telecomunicações

O objetivo desses problemas é projetar uma rede de linhas a serem instaladas de forma que um conjunto predefinido de requisitos de comunicação seja atendido e o custo total da rede seja mínimo. Isso requer a otimização da topologia da rede juntamente com a configuração das capacidades das várias linhas. Em muitos casos, as capacidades são restritas a quantidades inteiras. Normalmente existem, dependendo da tecnologia usada, restrições adicionais que podem ser modeladas como desigualdades lineares com variáveis inteiras ou binárias.

Redes celulares

A tarefa de planejamento de frequência em redes móveis GSM envolve a distribuição de frequências disponíveis pelas antenas para que os usuários possam ser atendidos e a interferência entre as antenas seja minimizada. Este problema pode ser formulado como um programa linear inteiro no qual variáveis binárias indicam se uma frequência é atribuída a uma antena.

Outras aplicações

Algoritmos

A maneira ingênua de resolver um ILP é simplesmente remover a restrição de que x é inteiro, resolver o LP correspondente (chamado de relaxamento LP do ILP) e, em seguida, arredondar as entradas da solução para o relaxamento LP. Mas, não apenas esta solução pode não ser ótima, ela pode até mesmo não ser viável; ou seja, pode violar alguma restrição.

Usando unimodularidade total

Embora em geral a solução para relaxamento de LP não seja garantida como integral, se o ILP tem a forma em que onde e tem todas as entradas inteiras e é totalmente unimodular , então toda solução básica viável é integral. Conseqüentemente, a solução retornada pelo algoritmo simplex é garantidamente integral. Para mostrar que toda solução básica viável é integral, deixe ser uma solução viável básica arbitrária. Uma vez que é viável, sabemos disso . Let Ser os elementos correspondentes às colunas de base para a solução básica . Por definição de uma base, existe alguma submatriz quadrada de com colunas linearmente independentes, tal que . ${\ displaystyle \ max \ mathbf {c} ^ {\ mathrm {T}} \ mathbf {x}}$ ${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$ ${\ displaystyle A}$ ${\ displaystyle \ mathbf {b}}$ ${\ displaystyle A}$ ${\ displaystyle \ mathbf {x}}$ ${\ displaystyle \ mathbf {x}}$ ${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$ ${\ displaystyle \ mathbf {x} _ {0} = [x_ {n_ {1}}, x_ {n_ {2}}, \ cdots, x_ {n_ {j}}]}$ ${\ displaystyle \ mathbf {x}}$ ${\ displaystyle B}$ ${\ displaystyle A}$ ${\ displaystyle B \ mathbf {x} _ {0} = \ mathbf {b}}$

Uma vez que as colunas de são linearmente independentes e quadradas, é não singular e, portanto, por suposição, é unimodular e assim . Além disso, como não é singular, é invertível e, portanto . Por definição ,. Aqui denota o adjunto de e é integral porque é integral. Portanto, ${\ displaystyle B}$ ${\ displaystyle B}$ ${\ displaystyle B}$ ${\ displaystyle B}$ ${\ displaystyle \ det (B) = \ pm 1}$ ${\ displaystyle B}$ ${\ displaystyle \ mathbf {x} _ {0} = B ^ {- 1} \ mathbf {b}}$ ${\ displaystyle B ^ {- 1} = {\ frac {B ^ {adj}} {\ det (B)}} = \ pm B ^ {adj}}$ ${\ displaystyle B ^ {adj}}$ ${\ displaystyle B}$ ${\ displaystyle B}$

{\ displaystyle {\ begin {alinhados} & \ Rightarrow B ^ {- 1} = \ pm B ^ {adj} {\ text {é integral.}} \\ & \ Rightarrow x_ {0} = B ^ {- 1 } b {\ text {é integral.}} \\ & \ Rightarrow {\ text {Cada solução básica viável é integral.}} \ end {alinhado}}}

Assim, se a matriz de um ILP for totalmente unimodular, ao invés de usar um algoritmo ILP, o método simplex pode ser usado para resolver o relaxamento LP e a solução será inteira. ${\ displaystyle A}$

Algoritmos exatos

Quando a matriz não é totalmente unimodular, há uma variedade de algoritmos que podem ser usados para resolver programas lineares inteiros com exatidão. Uma classe de algoritmos são métodos de plano de corte que funcionam resolvendo a relaxação LP e, em seguida, adicionando restrições lineares que conduzem a solução a ser inteira sem excluir quaisquer pontos inteiros viáveis. ${\ displaystyle A}$

Outra classe de algoritmos são variantes do método branch and bound . Por exemplo, o método de ramificação e corte que combina os métodos de ramificação e limite e plano de corte. Os algoritmos de ramificação e limite têm várias vantagens sobre os algoritmos que usam apenas planos de corte. Uma vantagem é que os algoritmos podem ser encerrados precocemente e, desde que pelo menos uma solução integral tenha sido encontrada, uma solução viável, embora não necessariamente ótima, pode ser retornada. Além disso, as soluções dos relaxamentos LP podem ser usadas para fornecer uma estimativa do pior caso de quão longe da otimização está a solução retornada. Finalmente, os métodos branch e bound podem ser usados para retornar várias soluções ótimas.

Algoritmos exatos para um pequeno número de variáveis

Suponhamos que é um m -by- n matriz de número inteiro e é um m vector inteiro -by-1. Nós nos concentramos no problema de viabilidade, que é decidir se existe um vetor n -por-1 que satisfaça . ${\ displaystyle A}$ ${\ displaystyle \ mathbf {b}}$ ${\ displaystyle \ mathbf {x}}$ ${\ displaystyle A \ mathbf {x} \ leq \ mathbf {b}}$

Seja V o valor absoluto máximo dos coeficientes em e . Se n (o número de variáveis) é uma constante fixa, então o problema pode ser resolvido de viabilidade em tempo polinomial em m e log V . Isso é trivial para o caso n = 1. O caso n = 2 foi resolvido em 1981 por Herbert Scarf . O caso geral foi resolvido em 1983 por Hendrik Lenstra , combinando ideias de Laszlo Lovasz e Peter van Emde Boas . ${\ displaystyle A}$ ${\ displaystyle \ mathbf {b}}$

No caso especial de 0-1 ILP, o algoritmo de Lenstra é equivalente à enumeração completa: o número de todas as soluções possíveis é fixo (2 ⁿ ), e a verificação da viabilidade de cada solução pode ser feita em tempo poli ( m , log V ) . No caso geral, onde cada variável pode ser um número inteiro arbitrário, a enumeração completa é impossível. Aqui, o algoritmo de Lenstra usa ideias da geometria dos números . Ele transforma o problema original em um equivalente com a seguinte propriedade: ou a existência de uma solução é óbvia, ou o valor de (a n- ésima variável) pertence a um intervalo cujo comprimento é limitado por uma função de n . No último caso, o problema é reduzido a um número limitado de problemas dimensionais inferiores. ${\ displaystyle \ mathbf {x}}$ ${\ displaystyle x_ {n}}$

O algoritmo de Lenstra implica que ILP é solucionável em tempo polinomial também no caso dual, em que n varia, mas m (o número de restrições) é constante.

O algoritmo de Lenstra foi posteriormente aprimorado por Kannan e Frank e Tardos. O tempo de execução aprimorado é , onde está o número de bits de entrada, que está dentro . ${\ displaystyle n ^ {2.5n} \ cdot \ ell}$ ${\ displaystyle \ ell}$ ${\ displaystyle {\ text {poly}} (m, \ log {V})}$

Métodos heurísticos

Como a programação linear inteira é NP-difícil , muitas instâncias do problema são intratáveis e, portanto, os métodos heurísticos devem ser usados em seu lugar. Por exemplo, a pesquisa tabu pode ser usada para pesquisar soluções para ILPs. Para usar a pesquisa tabu para resolver ILPs, os movimentos podem ser definidos como incrementar ou decrementar uma variável restrita de número inteiro de uma solução viável, mantendo todas as outras variáveis restritas de número inteiro constantes. As variáveis irrestritas são então resolvidas. A memória de curto prazo pode consistir em soluções experimentadas anteriormente, enquanto a memória de médio prazo pode consistir em valores para as variáveis inteiras restritas que resultaram em valores objetivos elevados (assumindo que o ILP é um problema de maximização). Finalmente, a memória de longo prazo pode orientar a pesquisa para valores inteiros que não foram tentados anteriormente.

Outros métodos heurísticos que podem ser aplicados a ILPs incluem

Há também uma variedade de outras heurísticas específicas para o problema, como a heurística k-opt para o problema do caixeiro viajante. Uma desvantagem dos métodos heurísticos é que, se eles falham em encontrar uma solução, não pode ser determinado se é porque não há solução viável ou se o algoritmo simplesmente não foi capaz de encontrar uma. Além disso, geralmente é impossível quantificar o quão perto do ótimo está uma solução retornada por esses métodos.

Programação de número inteiro esparso

Freqüentemente, a matriz que define o programa de inteiros é esparsa . Em particular, isso ocorre quando a matriz tem uma estrutura de bloco, que é o caso em muitas aplicações. A dispersão da matriz pode ser medida da seguinte forma. O gráfico de tem vértices correspondentes às colunas de , e duas colunas formam uma aresta se tiver uma linha onde ambas as colunas têm entradas diferentes de zero. De forma equivalente, os vértices correspondem a variáveis, e duas variáveis formam uma aresta se compartilham uma desigualdade. A medida de esparsidade de é o mínimo entre a profundidade da árvore do gráfico de e a profundidade da árvore do gráfico da transposta de . Let Ser a medida numérica de definido como o valor absoluto máximo de qualquer entrada de . Let Ser o número de variáveis do programa inteiro. Em seguida, foi mostrado em 2018 que a programação inteira pode ser resolvida em tempo tratável fortemente polinomial e de parâmetro fixo parametrizado por e . Ou seja, para alguma função computável e alguma constante , a programação inteira pode ser resolvida no tempo . Em particular, o tempo é independente do lado direito e da função objetivo . Além disso, em contraste com o resultado clássico de Lenstra, onde o número de variáveis é um parâmetro, aqui o número de variáveis é uma parte variável da entrada. ${\ displaystyle A}$ ${\ displaystyle A}$ ${\ displaystyle A}$ ${\ displaystyle A}$ ${\ displaystyle d}$ ${\ displaystyle A}$ ${\ displaystyle A}$ ${\ displaystyle A}$ ${\ displaystyle a}$ ${\ displaystyle A}$ ${\ displaystyle A}$ ${\ displaystyle n}$ ${\ displaystyle a}$ ${\ displaystyle d}$ ${\ displaystyle f}$ ${\ displaystyle k}$ ${\ displaystyle f (a, d) n ^ {k}}$ ${\ displaystyle b}$ ${\ displaystyle c}$ ${\ displaystyle n}$ ${\ displaystyle n}$

Veja também

Mínimos quadrados restritos

Referências

Leitura adicional

George L. Nemhauser ; Laurence A. Wolsey (1988). Otimização inteira e combinatória . Wiley. ISBN 978-0-471-82819-8.
Alexander Schrijver (1998). Teoria da programação linear e inteira . John Wiley and Sons. ISBN 978-0-471-98232-6.
Laurence A. Wolsey (1998). Programação inteira . Wiley. ISBN 978-0-471-28366-9.
Dimitris Bertsimas; Robert Weismantel (2005). Otimização sobre inteiros . Idéias dinâmicas. ISBN 978-0-9759146-2-5.
John K. Karlof (2006). Programação inteira: teoria e prática . CRC Press. ISBN 978-0-8493-1914-3.
H. Paul Williams (2009). Programação lógica e inteira . Springer. ISBN 978-0-387-92279-9.
Michael Jünger; Thomas M. Liebling; Denis Naddef; George Nemhauser ; William R. Pulleyblank ; Gerhard Reinelt; Giovanni Rinaldi; Laurence A. Wolsey, eds. (2009). 50 anos de programação inteira 1958-2008: dos primeiros anos ao estado da arte . Springer. ISBN 978-3-540-68274-5.
Der-San Chen; Robert G. Batson; Yu Dang (2010). Programação Inteira Aplicada: Modelagem e Solução . John Wiley and Sons. ISBN 978-0-470-37306-4.
Gerard Sierksma; Yori Zwols (2015). Otimização Linear e Integer: Teoria e Prática . CRC Press. ISBN 978-1-498-71016-9.

Languages

In other projects