programação inteira

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

A programação inteira é NP-completa [ citação necessária ] . 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 problema de programação inteira mista . [1]

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

Na programação linear inteira, a forma canônica é distinta da forma padrão . Um programa linear inteiro na forma canônica é expresso assim (observe que é o vetor que deve ser decidido): [2]

e um ILP na forma padrão é expresso como

onde são vetores e é uma matriz. Assim como nos 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 variáveis ​​que não são restritas por sinal pela diferença de duas variáveis ​​com restrição de sinal.

Exemplo

Politopo IP com relaxamento LP

O gráfico à direita mostra o seguinte problema.

Os pontos inteiros factíveis são mostrados em vermelho, e as linhas tracejadas vermelhas indicam sua casca convexa, que é o menor poliedro convexo que contém todos esses pontos. As linhas azuis juntamente com os eixos coordenados definem o poliedro da relaxação LP, que é dado pelas desigualdades sem a restrição de integralidade. O objetivo da otimização é mover a linha tracejada preta para cima enquanto ainda toca o poliedro. As soluções ótimas do problema inteiro são os pontos e ambas têm um valor objetivo de 2. O único ótimo da relaxação é com valor objetivo de 2,8. Se a solução da relaxação for arredondada para os inteiros mais próximos, não é viável para o ILP.

Prova de dureza NP

A seguir, uma redução da cobertura mínima de vértices para programação inteira que servirá como prova de dureza NP.

Seja um grafo não direcionado. Defina um programa linear da seguinte forma:

Dado que as restrições 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 esteja incluído neste subconjunto. Portanto, a solução descreve uma cobertura de vértice. Além disso, dada alguma cobertura de vértice C, pode ser definido como 1 para qualquer um e como 0 para qualquer um , fornecendo assim 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 de vértices. [3]

variantes

A programação linear inteira mista ( MILP ) envolve problemas nos quais apenas algumas das variáveis, , são restritas a números inteiros, enquanto outras variáveis ​​podem ser não inteiros.

A programação linear zero-um (ou programação binária inteira ) 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 . [4] Por exemplo, dada uma variável inteira, , a variável pode ser expressa usando variáveis ​​binárias:

Formulários

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

  1. As variáveis ​​inteiras representam quantidades que só podem ser inteiras. Por exemplo, não é possível construir carros 3,7.
  2. As variáveis ​​inteiras representam decisões (por exemplo, incluir uma aresta 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 aplicação, algumas das quais são brevemente descritas abaixo.

Planejamento de produção

A programação de inteiro misto tem muitas aplicações em produções industriais, incluindo modelagem de job-shop. Um exemplo importante que ocorre 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, mão de obra, capital, sementes, fertilizantes, etc.). Um objetivo possível é 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 restritas para serem inteiras.

Agendamento

Esses problemas envolvem escalonamento de serviços e veículos em 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 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 trem ou metrô específico. A técnica de programação zero-um foi aplicada com sucesso para resolver um problema de seleção de projetos em que os projetos são mutuamente exclusivos e/ou tecnologicamente interdependentes. É usado em um caso especial de programação inteira, em que todas as variáveis ​​de decisão são inteiras. Pode assumir os valores como zero ou um.

partição territorial

O problema de compartimentação territorial ou compartimentação consiste em compartir 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 esse problema são: contiguidade, compacidade, 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 modo que um conjunto predefinido de requisitos de comunicação seja atendido e o custo total da rede seja mínimo. [5] Isso requer otimizar tanto a topologia da rede quanto 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 utilizada, 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 seja minimizada entre as antenas. [6] 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 então arredondar as entradas da solução para o relaxamento LP. Mas essa solução não só pode não ser ótima, como pode até não ser viável; ou seja, pode violar alguma restrição.

Usando unimodularidade total

Embora, em geral, a solução para o relaxamento de LP não seja garantida como integral, se o ILP tiver a forma tal que onde e tiver todas as entradas inteiras e for totalmente unimodular , toda solução viável básica será integral. Consequentemente, a solução retornada pelo algoritmo simplex é garantidamente integral. Para mostrar que toda solução viável básica é integral, seja uma solução viável básica arbitrária . Como é viável, sabemos que . Sejam os elementos correspondentes às colunas de base da solução básica . Por definição de base, existe alguma submatriz quadrada de com colunas linearmente independentes tais que .

Dado que as colunas de são linearmente independentes e são quadradas, são não singulares, e portanto por assunção, são unimodulares 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,

algoritmos exatos

Quando a matriz não é totalmente unimodular, há uma variedade de algoritmos que podem ser usados ​​para resolver exatamente programas lineares inteiros. Uma classe de algoritmos são métodos de plano de corte que funcionam resolvendo o relaxamento de LP e, em seguida, adicionando restrições lineares que levam a solução a ser inteira sem excluir nenhum ponto viável inteiro.

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 antecipadamente 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 de LP podem ser usadas para fornecer uma estimativa de 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 múltiplas soluções ótimas.

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

Suponha que é uma matriz inteira m -por- n e é um vetor inteiro m -por-1. Focamos no problema de viabilidade, que é decidir se existe um vetor n por 1 satisfazendo .

Seja V o valor absoluto máximo dos coeficientes em e . Se n (o número de variáveis) for uma constante fixa, então o problema de viabilidade pode ser resolvido 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 . [11] O caso geral foi resolvido em 1983 por Hendrik Lenstra , combinando ideias de László Lovász e Peter van Emde Boas . [12]

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 n ), e a verificação da viabilidade de cada solução pode ser feita no tempo poly( m , log V ) . No caso geral, onde cada variável pode ser um 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 problema 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 de dimensão inferior. A complexidade do tempo de execução do algoritmo foi aprimorada em várias etapas:

  • O algoritmo original de Lenstra [12] tinha tempo de execução .
  • Kannan [13] apresentou um algoritmo aprimorado com tempo de execução . [14]
  • Frank e Tardos [15] apresentaram um algoritmo aprimorado com tempo de execução . [16] [17] : Prop.8 
  • Dadush [18] apresentou um algoritmo aprimorado com run-time .
  • Reis e Rothvoss [19] apresentaram um algoritmo aprimorado com run-time .

métodos heurísticos

Como a programação linear inteira é NP-difícil , muitas instâncias do problema são intratáveis ​​e, portanto, métodos heurísticos devem ser usados. Por exemplo, a pesquisa tabu pode ser usada para procurar soluções para ILPs. [20] Para usar a pesquisa tabu para resolver ILPs, os movimentos podem ser definidos como incrementar ou decrementar uma variável com restrição de número inteiro de uma solução viável, mantendo todas as outras variáveis ​​com restrição 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 previamente tentadas, enquanto a memória de médio prazo pode consistir em valores para as variáveis ​​inteiras restritas que resultaram em altos valores objetivos (assumindo que o ILP é um problema de maximização). Finalmente, a memória de longo prazo pode orientar a busca 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 de problemas, como a heurística k-opt para o problema do caixeiro-viajante. Uma desvantagem dos métodos heurísticos é que, se eles não conseguem 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 conseguiu encontrar uma. Além disso, geralmente é impossível quantificar o quão perto da solução ótima retornada por esses métodos está.

Programação inteira esparsa

Frequentemente, a matriz que define o programa inteiro é esparsa . Em particular, isso ocorre quando a matriz possui 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 tem uma linha onde ambas as colunas têm entradas diferentes de zero. Equivalentemente, os vértices correspondem a variáveis, e duas variáveis ​​formam uma aresta se compartilharem 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 . Seja a medida numérica de definida 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 [21] 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úmerode variáveis ​​é um parâmetro, aqui o número de variáveis ​​é uma parte variável da entrada.

Veja também

Referências

  1. ^ "Programação Linear Inteira Mista (MILP): Formulação de Modelo" (PDF) . Acesso em 16 de abril de 2018 .
  2. ^ Papadimitriou, CH ; Steiglitz, K. (1998). Otimização combinatória: algoritmos e complexidade . Mineola, NY: Dover. ISBN 0486402584.
  3. ^ Erickson, J. (2015). "Redução de Programação Inteira" (PDF) . Arquivado do original (PDF) em 18 de maio de 2015.
  4. ^ Williams, HP (2009). Lógica e programação inteira . Série Internacional em Pesquisa Operacional e Ciência da Administração. Vol. 130. ISBN 978-0-387-92280-5.
  5. ^ Borndörfer, R.; Grötschel, M. (2012). "Projetando redes de telecomunicações por programação inteira" (PDF) .
  6. ^ Sharma, Deepak (2010). "Planejamento de Frequência".
  7. ^ Morais, Hugo; Kádár, Péter; FARIA, Pedro; Vale, Zita A.; Khodr, HM (2010-01-01). "Agendamento ideal de uma micro-rede renovável em uma área de carga isolada usando programação linear inteira mista". Energia Renovável . 35 (1): 151–156. doi : 10.1016/j.renene.2009.02.031. hdl : 10400.22/1585 . ISSN  0960-1481.
  8. ^ Omu, Akomeno; Choudhary, Ruchi; Boies, Adam (2013-10-01). "Otimização do sistema de recursos de energia distribuída usando programação linear inteira mista". Política Energética . 61 : 249–266. doi : 10.1016/j.enpol.2013.05.009. ISSN  0301-4215.
  9. ^ Schouwenaars, T.; Valenti, M.; Feron, E.; Como, J. (2005). "Resultados da implementação e dos testes de voo da orientação UAV baseada em MILP". Conferência Aeroespacial IEEE 2005 : 1–13. doi : 10.1109/AERO.2005.1559600. ISBN 0-7803-8870-4. S2CID  13447718.
  10. ^ Radmanesh, Mohammadreza; Kumar, Manish (2016-03-01). "Formação de voo de UAVs na presença de obstáculos em movimento usando programação linear inteira mista dinâmica rápida". Ciência e Tecnologia Aeroespacial . 50 : 149–160. doi : 10.1016/j.ast.2015.12.021 . ISSN  1270-9638.
  11. ^ Cachecol, Herbert E. (1981). "Conjuntos de produção com indivisibilidades, Parte I: Generalidades". Econometrica . 49 (1): 1–32. doi : 10.2307/1911124. ISSN  0012-9682. JSTOR  1911124.
  12. ^ ab Lenstra, HW (1983-11-01). "Programação inteira com um número fixo de variáveis". Matemática da Pesquisa Operacional . 8 (4): 538–548. CiteSeerX 10.1.1.431.5444 . doi : 10.1287/moor.8.4.538. ISSN  0364-765X. 
  13. ^ Kannan, Ravi (1987-08-01). "Teorema do corpo convexo de Minkowski e programação inteira". Matemática da Pesquisa Operacional . 12 (3): 415–440. doi : 10.1287/moor.12.3.415. ISSN  0364-765X.
  14. ^ Goemans, Michel X.; Rothvoss, Thomas (2020-11-07). "Polinomialidade para Bin Packing com um número constante de tipos de itens". Jornal da ACM . 67 (6): 38:1–38:21. doi : 10.1145/3421750 . hdl :1721.1/92865. ISSN  0004-5411. S2CID  227154747.
  15. ^ Frank, Andrés; Tardos, Éva (1987-03-01). "Uma aplicação de aproximação diofantina simultânea em otimização combinatória". Combinatória . 7 (1): 49–65. doi : 10.1007/BF02579200. ISSN  1439-6912. S2CID  45585308.
  16. ^ Bliem, Bernhard; Bredereck, Robert; Niedermeier, Rolf (2016-07-09). "Complexidade de alocação de recursos eficiente e sem inveja: poucos agentes, recursos ou níveis de utilidade". Anais da Vigésima Quinta Conferência Conjunta Internacional sobre Inteligência Artificial . IJCAI'16. Nova York, Nova York, EUA: AAAI Press: 102–108. ISBN 978-1-57735-770-4.
  17. ^ Bredereck, Robert; Kaczmarczyk, Andrzej; Knop, Dušan; Niedermeier, Rolf (2019-06-17). "Alocação Justa de Alta Multiplicidade: Lenstra Empowered by N-fold Integer Programming". Anais da Conferência ACM 2019 sobre Economia e Computação . CE '19. Phoenix, AZ, EUA: Association for Computing Machinery: 505–523. doi : 10.1145/3328526.3329649. ISBN 978-1-4503-6792-9. S2CID  195298520.
  18. ^ Dadush, Daniel (2012-06-14). "Programação inteira, algoritmos de rede e estimativa de volume determinística.
  19. Reis, Victor; Rothvoss, Thomas (2023-03-26). "A conjectura de planicidade do subespaço e a programação inteira mais rápida".
  20. ^ Glover, F. (1989). "Pesquisa Tabu-Parte II" . Jornal ORSA em Computação . 1 (3): 4–32. doi :10.1287/ijoc.2.1.4. S2CID  207225435.
  21. ^ Koutecký, Martin; Levin, Asaf; Onn, Shmuel (2018). "Um Algoritmo Fortemente Polinomial Parametrizado para Programas Inteiros Estruturados em Bloco". Michael Wagner: 14 páginas. arXiv : 1802.05859 . doi : 10.4230/LIPICS.ICALP.2018.85. S2CID  3336201. {{cite journal}}: Citar periódico requer |journal=( ajuda )

Leitura adicional

links externos

  • Um tutorial sobre programação inteira
  • Conferência Programação Inteira e Otimização Combinatória, IPCO
  • O Workshop de Otimização Combinatória Aussois