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

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:
- As variáveis inteiras representam quantidades que só podem ser inteiras. Por exemplo, não é possível construir 3,7 carros.
- 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
- Correspondência de fluxo de caixa
- Otimização do sistema energético [8] [9]
- Orientação de UAV [10] [11]
- Layout do mapa de trânsito [12]
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
- Escalada de montanha
- Recozimento simulado
- Otimização de pesquisa reativa
- Otimização de colônia de formigas
- Redes neurais de Hopfield
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
- Mínimos quadrados restritos
- Equação diofantina – Equação polinomial cujas soluções inteiras são procuradas
Referências
- ^ 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.
- ^ "Programação Linear Inteira Mista (MILP): Formulação de Modelo" (PDF) . Recuperado em 16 de abril de 2018 .
- ^ Papadimitriou, CH ; Steiglitz, K. (1998). Otimização combinatória: algoritmos e complexidade . Mineola, NY: Dover. ISBN 0486402584.
- ^ Erickson, J. (2015). "Redução de Programação Inteira" (PDF) . Arquivado do original (PDF) em 18 de maio de 2015.
- ^ 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.
- ^ Borndörfer, R.; Grötschel, M. (2012). "Projetando redes de telecomunicações por programação inteira" (PDF) .
- ^ Sharma, Deepak (2010). "Planejamento de frequência".
- ^ 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 .
- ^ 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.
- ^ 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.
- ^ 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.
- ^ Bast, Hannah; Brosi, Patrick; Storandt, Sabine (2017-10-05). "Geração eficiente de mapas de trânsito geograficamente precisos". arXiv : 1710.02226 [cs.CG].
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ Dadush, Daniel (2012-06-14). "Programação Inteira, Algoritmos de Rede e Estimativa de Volume Determinística.
- ^ Reis, Victor; Rothvoss, Thomas (2023-03-26). "A conjectura da planura do subespaço e a programação inteira mais rápida".
- ^ ab Hildebrand, Robert (2016-10-07). "Algoritmo FPT para programa inteiro misto". Theoretical Computer Science Stack Exchange . Recuperado em 2024-05-21 .
- ^ Glover, F. (1989). "Busca Tabu-Parte II". ORSA Journal on Computing . 1 (3): 4–32. doi :10.1287/ijoc.2.1.4. S2CID 207225435.
- ^ 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
- George L. Nemhauser ; Laurence A. Wolsey (1988). Otimização combinatória e inteira . 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 . Ideias 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). Lógica e Programação 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 Inteira: Teoria e Prática . Imprensa CRC. ISBN 978-1-498-71016-9.
Links externos
- Um tutorial sobre programação inteira
- Conferência Programação Inteira e Otimização Combinatória, IPCO
- Oficina de Otimização Combinatória Aussois