Programação inteira

Um problema de programação inteira é um programa de otimização ou viabilidade matemática no qual algumas ou todas as variáveis ​​são restritas a serem inteiras . Em muitos cenários, 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 . Em particular, o caso especial da 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 . [1]

Se algumas variáveis ​​de decisão não forem discretas, o problema é conhecido como um problema de programação inteira mista . [2]

Forma canônica 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 (note que é o vetor que deve ser decidido): [3]

e um ILP na forma padrão é expresso como

onde são vetores e é uma matriz. Assim como em programas lineares, ILPs que não estão na forma padrão podem ser convertidos para a forma padrão eliminando desigualdades, introduzindo variáveis ​​slack ( ) e substituindo variáveis ​​que não são restritas por sinal pela diferença de duas variáveis ​​restritas por sinal.

Exemplo

Politopo IP com relaxamento LP

O gráfico à direita mostra o seguinte problema.

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

Prova de dureza NP

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

Seja um grafo não direcionado. Defina um programa linear como segue:

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 está incluído neste subconjunto. Portanto, a solução descreve uma cobertura de vértice. Adicionalmente, dada alguma cobertura de vértice C, pode ser definida como 1 para qualquer e como 0 para qualquer, dando-nos assim uma solução viável para o programa inteiro. Assim, podemos concluir que se minimizarmos a soma de também encontramos a cobertura de vértice mínima. [4]

Variantes

A programação linear mista-inteira ( MILP ) envolve problemas nos quais apenas algumas das variáveis, , são limitadas a serem inteiras, enquanto outras variáveis ​​podem ser não inteiras.

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 . [5] Por exemplo, dada uma variável inteira, , a variável pode ser expressa usando variáveis ​​binárias:

Aplicações

Há 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 3,7 carros.
  2. As variáveis ​​inteiras representam decisões (por exemplo, se deve incluir uma aresta em um gráfico ) e, portanto, devem assumir apenas o valor 0 ou 1.

Essas considerações ocorrem frequentemente 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 inteira mista tem muitas aplicações em produções industriais, incluindo modelagem job-shop. Um exemplo importante acontece no planejamento da produção agrícola e 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 programação 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 cronograma possa ser cumprido e também para equipá-los com motoristas. Aqui, 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 projeto no qual os projetos são mutuamente exclusivos e/ou tecnologicamente interdependentes. Ela é usada em um caso especial de programação inteira, no qual todas as variáveis ​​de decisão são inteiras. A variável pode assumir apenas os valores zero ou um.

Partilha territorial

Problemas de partição territorial ou distritalização consistem em dividir uma região geográfica em distritos para planejar algumas operações, considerando diferentes critérios ou restrições. Alguns requisitos para esse problema são: contiguidade, compacidade, equilíbrio ou equidade, respeito a limites naturais e homogeneidade socioeconômica. Algumas aplicações para esse tipo de problema incluem: distritalização política, distritalização escolar, distritalização de serviços de saúde e distritalização de gerenciamento de resíduos.

Redes de telecomunicações

O objetivo desses problemas é projetar uma rede de linhas para instalar de modo que um conjunto predefinido de requisitos de comunicação seja atendido e o custo total da rede seja mínimo. [6] Isso requer a otimização da topologia da rede junto com a configuração das capacidades das várias linhas. Em muitos casos, as capacidades são restritas a quantidades inteiras. Normalmente, há, 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 seja minimizada entre as antenas. [7] 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 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 nem ser viável; isto é, pode violar alguma restrição.

Usando unimodularidade total

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

Como as colunas de são linearmente independentes e é quadrado, é não singular e, portanto, por suposição, é unimodular e, portanto , . Além disso, como é não singular, é invertível e, portanto , . Por definição, . Aqui denota o adjunto de e é integral porque é integral. Portanto, Assim, se a matriz de um ILP for totalmente unimodular, em vez de usar um algoritmo ILP, o método simplex pode ser usado para resolver o relaxamento LP e a solução será inteira.

Algoritmos exatos

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

Outra classe de algoritmos são variantes do método branch and bound . Por exemplo, o método branch and cut que combina os métodos branch and bound e cutting plane. Algoritmos branch and bound têm uma série de vantagens sobre algoritmos que usam apenas planos de corte. Uma vantagem é que os algoritmos podem ser encerrados cedo 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 otimalidade a solução retornada está. Finalmente, métodos branch and bound podem ser usados ​​para retornar múltiplas soluções ótimas.

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

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

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 . [13] O caso geral foi resolvido em 1983 por Hendrik Lenstra , combinando ideias de László Lovász e Peter van Emde Boas . [14] O teorema de Doignon afirma que um programa inteiro é viável sempre que cada subconjunto de restrições for viável; um método que combina esse resultado com algoritmos para problemas do tipo LP pode ser usado para resolver programas inteiros em tempo que são lineares em e tratáveis ​​por parâmetros fixos (FPT) em , mas possivelmente duplamente exponenciais em , sem dependência de . [15]

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 em tempo poli( 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 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 menor dimensão. A complexidade do tempo de execução do algoritmo foi melhorada em várias etapas:

  • O algoritmo original de Lenstra [14] tinha tempo de execução .
  • Kannan [16] apresentou um algoritmo melhorado com tempo de execução . [17]
  • Frank e Tardos [18] apresentaram um algoritmo melhorado com tempo de execução . [19] [20] : Prop.8 
  • Dadush [21] apresentou um algoritmo melhorado com tempo de execução .
  • Reis e Rothvoss [22] apresentaram um algoritmo melhorado com tempo de execução .

Esses algoritmos também podem ser usados ​​para programas lineares inteiros mistos (MILP) - programas nos quais algumas variáveis ​​são inteiras e algumas variáveis ​​são reais. [23] O algoritmo original de Lenstra [14] : Sec.5  tem tempo de execução , onde n é o número de variáveis ​​inteiras, d é o número de variáveis ​​contínuas e L é o tamanho da codificação binária do problema. Usando técnicas de algoritmos posteriores, o fator pode ser melhorado para ou para . [23]

Métodos heurísticos

Como a programação linear inteira é NP-difícil , muitas instâncias de problemas são intratáveis ​​e, portanto, métodos heurísticos devem ser usados. Por exemplo, a busca tabu pode ser usada para buscar soluções para ILPs. [24] Para usar a busca tabu para resolver ILPs, os movimentos podem ser definidos como incrementar ou decrementar uma variável com restrição de inteiros de uma solução viável, mantendo todas as outras variáveis ​​com restrição de inteiros 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 ​​com restrição de inteiros que resultaram em altos valores objetivos (assumindo que o ILP é um problema de maximização). Finalmente, a memória de longo prazo pode guiar a busca em direção a 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 do problema, como a heurística k-opt para o problema do caixeiro viajante. Uma desvantagem dos métodos heurísticos é que, se eles não encontrarem uma solução, não é possível determinar 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 próxima do ótimo uma solução retornada por esses métodos está.

Programação inteira esparsa

É comum que a matriz que define o programa inteiro seja esparsa . Em particular, isso ocorre quando a matriz tem uma estrutura de bloco , o que é o caso em muitas aplicações. A esparsidade da matriz pode ser medida da seguinte forma. O gráfico de tem vértices correspondentes a 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 compartilham uma desigualdade. A medida de esparsidade de é o mínimo da 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 . Seja o número de variáveis ​​do programa inteiro. Então foi mostrado em 2018 [25] que a programação inteira pode ser resolvida em tempo fortemente polinomial e tratável 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 em 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.

Veja também

Referências

  1. ^ Karp, Richard M. (1972). "Redutibilidade entre problemas combinatórios" (PDF) . Em RE Miller; JW Thatcher; JD Bohlinger (eds.). Complexidade de computações de computador . Nova York: Plenum. pp. 85–103. doi :10.1007/978-1-4684-2001-2_9. ISBN 978-1-4684-2003-6.
  2. ^ "Programação Linear Inteira Mista (MILP): Formulação de Modelo" (PDF) . Recuperado em 16 de abril de 2018 .
  3. ^ Papadimitriou, CH ; Steiglitz, K. (1998). Otimização combinatória: algoritmos e complexidade . Mineola, NY: Dover. ISBN 0486402584.
  4. ^ Erickson, J. (2015). "Redução de Programação Inteira" (PDF) . Arquivado do original (PDF) em 18 de maio de 2015.
  5. ^ Williams, HP (2009). Lógica e programação inteira . Série internacional em pesquisa operacional e ciência da gestão. Vol. 130. ISBN 978-0-387-92280-5.
  6. ^ Borndörfer, R.; Grötschel, M. (2012). "Projetando redes de telecomunicações por programação inteira" (PDF) .
  7. ^ Sharma, Deepak (2010). "Planejamento de frequência".
  8. ^ Morais, Hugo; Kádár, Péter; Faria, Pedro; Vale, Zita A.; Khodr, HM (01/01/2010). “Programação ideal de uma microrrede renovável em uma área de carga isolada usando programação linear inteira mista”. Energia Renovável . 35 (1): 151–156. Bibcode :2010REne...35..151M. doi :10.1016/j.renene.2009.02.031. hdl : 10400,22/1585 . ISSN0960-1481  .
  9. ^ Omu, Akomeno; Choudhary, Ruchi; Boies, Adam (2013-10-01). "Otimização do sistema de recursos energéticos distribuídos usando programação linear inteira mista". Política Energética . 61 : 249–266. Bibcode :2013EnPol..61..249O. doi :10.1016/j.enpol.2013.05.009. ISSN  0301-4215. S2CID  29369795.
  10. ^ Schouwenaars, T.; Valenti, M.; Feron, E.; How, J. (2005). "Implementação e resultados de testes de voo de orientação de UAV baseada em MILP". Conferência Aeroespacial IEEE de 2005. pp. 1–13. doi :10.1109/AERO.2005.1559600. ISBN 0-7803-8870-4. S2CID  13447718.
  11. ^ Radmanesh, Mohammadreza; Kumar, Manish (2016-03-01). "Formação de voo de UAVs na presença de obstáculos móveis usando programação linear inteira mista dinâmica rápida". Ciência e Tecnologia Aeroespacial . 50 : 149–160. Bibcode : 2016AeST... 50..149R. doi : 10.1016/j.ast.2015.12.021 . ISSN  1270-9638.
  12. ^ Bast, Hannah; Brosi, Patrick; Storandt, Sabine (2017-10-05). "Geração eficiente de mapas de trânsito geograficamente precisos". arXiv : 1710.02226 [cs.CG].
  13. ^ Scarf, 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.
  14. ^ abc 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. 
  15. ^ Amenta, Nina ; De Loera, Jesús A. ; Soberón, Pablo (2017). "Teorema de Helly: novas variações e aplicações". Em Harrington, Heather A. ; Omar, Mohamed; Wright, Matthew (eds.). Anais da Sessão Especial da AMS sobre Métodos Algébricos e Geométricos em Matemática Discreta Aplicada realizada em San Antonio, TX, 11 de janeiro de 2015 . Matemática Contemporânea. Vol. 685. Providence, Rhode Island: Sociedade Matemática Americana. pp. 55–95. arXiv : 1508.07606 . doi :10.1090/conm/685. ISBN 9781470423216. SR  3625571.
  16. ^ 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. S2CID  495512.
  17. ^ Goemans, Michel X. ; Rothvoss, Thomas (2020-11-07). "Polinomialidade para embalagem de bin com um número constante de tipos de itens". Journal of the ACM . 67 (6): 38:1–38:21. doi : 10.1145/3421750 . hdl : 1721.1/92865 . ISSN  0004-5411. S2CID  227154747.
  18. ^ Frank, András; Tardos, Éva (1987-03-01). "Uma aplicação de aproximação diofantina simultânea em otimização combinatória". Combinatorica . 7 (1): 49–65. doi :10.1007/BF02579200. ISSN  1439-6912. S2CID  45585308.
  19. ^ Bliem, Bernhard; Bredereck, Robert; Niedermeier, Rolf (2016-07-09). "Complexidade da alocação de recursos eficiente e livre de inveja: poucos agentes, recursos ou níveis de utilidade". Anais da Vigésima Quinta Conferência Internacional Conjunta sobre Inteligência Artificial . IJCAI'16. Nova York, Nova York, EUA: AAAI Press: 102–108. ISBN 978-1-57735-770-4.
  20. ^ Bredereck, Robert; Kaczmarczyk, Andrzej; Knop, Dušan; Niedermeier, Rolf (2019-06-17). "Alocação justa de alta multiplicidade: Lenstra fortalecida pela programação inteira N-fold". Anais da Conferência ACM de 2019 sobre economia e computação . EC '19. Phoenix, AZ, EUA: Association for Computing Machinery. pp. 505–523. doi :10.1145/3328526.3329649. ISBN 978-1-4503-6792-9. S2CID  195298520.
  21. ^ Dadush, Daniel (2012-06-14). "Programação Inteira, Algoritmos de Rede e Estimativa de Volume Determinística.
  22. ^ Reis, Victor; Rothvoss, Thomas (2023-03-26). "A conjectura da planura do subespaço e a programação inteira mais rápida".
  23. ^ ab Hildebrand, Robert (2016-10-07). "Algoritmo FPT para programa inteiro misto". Theoretical Computer Science Stack Exchange . Recuperado em 2024-05-21 .
  24. ^ Glover, F. (1989). "Busca Tabu-Parte II". ORSA Journal on Computing . 1 (3): 4–32. doi :10.1287/ijoc.2.1.4. S2CID  207225435.
  25. ^ Koutecký, Martin; Levin, Asaf; Onn, Shmuel (2018). "Um algoritmo fortemente polinomial parametrizado para programas inteiros estruturados em bloco". Em Chatzigiannakis, Ioannis; Kaklamanis, Christos; Marx, Dániel; Sannella, Donald (eds.). 45º Colóquio Internacional sobre Autômatos, Linguagens e Programação, ICALP 2018, 9 a 13 de julho de 2018, Praga, República Tcheca . Vol. 107. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 85:1–85:14. arXiv : 1802.05859 . doi : 10.4230/LIPICS.ICALP.2018.85 .

Leitura adicional

  • Um tutorial sobre programação inteira
  • Conferência Programação Inteira e Otimização Combinatória, IPCO
  • Oficina de Otimização Combinatória Aussois
Retrieved from "https://en.wikipedia.org/w/index.php?title=Integer_programming&oldid=1248563346"