O mito do botão mágico
Os sistemas que resolvem tudo…
O problema que estamos a tentar optimizar!!
Qual o plano de produção óptimo para produzir os serviços respeitando as regras especialmente as legais e laborais?
Para responder a esta questão é preciso entender a natureza do problema, o que significa optimizar e como os diferentes tipos de custos se relacionam.
Este tipo de problemas é designado como um problema de combinatória e apresenta particularidades ocultas à primeira vista. Em termos simplistas, o que se pretende é alocar um conjunto de viagens a 2 recursos, a viatura e o motorista.
Em problemas pequenos é possivel enumerar todas as possibilidades, no entanto, assim que o problema começa a crescer (mais viagens, mais motoristas, mais viaturas) esta abordagem deixa de ser viável precisamente por dispararem as combinações possíveis.
Ok, precisamos de uma capacidade de processamento maior!
Não, isso não resolve. A dimensão dos problemas de que estamos a falar atinge números astronómicos, para um problema de tamanho médio, há mais combinações possíveis do que grãos de areia no planeta!! Mesmo o computador mais potente com a possibilidade de enumerar milhares de combinações por segundo demoraria mais do que o tempo da humanidade. Mesmo que fosse possível duplicar a capacidade, demoraria metade do tempo da humanidade… continuaria a não ser muito útil.
Em matemática estes problemas são designados por intratáveis!
A resposta está em reduzir o espaço de procura (designado por espaço de soluções) utilizando algoritmos.
O que significa optimizar neste contexto?
Uma afirmação legítima e recorrente é “como foi possivel obter uma solução melhor, não tinhamos optimizado?”
Pois… Não é fácil explicar isto de forma simples, há muitos pressupostos escondidos que têm de ser desconstruidos.
Com o uso de algoritmos aproximados, nem sempre temos a garantia de que no final da optimização o resultado é o óptimo absoluto, ou seja, que não há nenhuma outra solução que seja melhor. O algoritmo não resolve o problema na sua totalidade, o que faz é procurar reduzir as combinações descartando aquelas que aparentemente são menos promissoras, formando um problema mais pequeno (que se pretende equivalente) e procura a melhor apresentando-a como óptima.
Não é descabido que, no processo de redução do espaço de soluções, sejam eliminadas combinações, que apesar de pouco promissoras se viriam a revelar como boas soluções. É por isso que, por vezes é possível melhorar uma solução optimizada.
Heurísticas - mais simples do que parecem
As heurísticas não são mais do que pequenas regras que permitem avaliar se uma solução é promissora ou não. Em termos simples, o que fazem é avaliar rapidamente qual será o custo previsto da solução. No contexto deste problema, torna-se complexo dar exemplos concretos, por isso vou usar um exemplo que é de fácil entendimento e que explicita o conceito.
Quando queremos saber o caminho mais curto entre duas cidades, existe um conjunto de decisões gigantesco a avaliar, em cada intersecção que caminho escolher, para onde devo virar em cada cruzamento que encontro.
Avaliar todas as combinações de todos os cruzamentos é inviável e até disparatado aos olhos de um humano. É aqui que entram em cena as heurísticas!
A heurística vai dar a intuição ao sistema guiando-o para as decisões que parecem interessantes. Por exemplo, uma função que é normalmente usada é a distância em linha reta. A heurística vai classificar como mais promissoras as opções que mais nos aproximam da cidade de destino com menor distância percorrida (quanto já percorremos + a distância em linha reta estamos do destino). Mediante um critério de corte (seja em função de tempo de computação, número de iterações, em número de opções já encontradas ou em percentagem da estimativa para a melhor solução) e eliminar as outras opções.
Esta heuristica em particular vai avaliar como mais promissores os caminhos com a orientação da cidade de destino. Ir na direção contrária ao destino não parece ser promissor, mas pode efetivamente ser o caminho mais curto. É exatamente isso que pode acontecer também no nosso cenário.
Na prática os algoritmos de roteamento usados hoje em dia são bastante mais sofisticados, o exemplo simples é o Algoritmo A* (A Star) mas existem outros mais interessantes e eficientes como o Bidirectional search, este tem uma abordagem muito curiosa, divide o problema em dois e faz o processo nas duas direções (da cidade de origem e da cidade de destino) até que se encontram e formam a solução final (isto permite reduzir drásticamente o espaço de soluções). Existem ainda outras técnicas de clustering de pontos, que dividem o problema em camadas e fazem pré-computação de caminhos óptimos, reduzindo o grafo para conter apenas os caminhos óptimos, sempre com o mesmo objetivo, reduzir o espaço de soluções.
Função objectivo - Estrutura de custos
Já vimos o papel fundamental das heurísticas e como as suas funções objectivo simplificadas têm de estar bem alinhadas, ainda que simplificadas, com a função objectivo global do problema. O modelo matemático tem 3 elementos fundamentais, as restrições hard constraints, soft constraints e os custos. Enquanto que as primeiras são restrições invioláveis, ou seja, não são admitidas soluções que as violem, as segundas podem ser violadas mas essa violação acarreta um custo adicional que é incorporado na solução objectivo.
Estas soft constraints são também normalmente designadas como as preferências de optimização e estão intimamente ligadas aos critérios mais subjectivos do que representa uma boa solução.
Com a introdução das soft constraints na função objectivo do modelo, o custo para efeito de optimização e o custo real da solução passam a ser diferentes. Uma solução que na realidade é melhor em termos de custos reais pode ser preterida devido à violação de algumas preferências subjectivas que adicionam custo fictício na função objectivo.
Daqui resulta que seja possível melhorar uma solução optimizada se estivermos unicamente a comparar os custos reais, sem valorizar o custo das violações das preferências.
Em relação aos custos, de forma muito simplista, existem dois grandes grupos de custos, os custos de meios e os custos variáveis. O profundo conhecimento da relação entre estes tipos de custos (muito para além da relação aritmética) é a chave para obter boa intuição e navegar eficientemente o espaço de soluções para encontrar boas soluções.
Trata-se de ser capaz de avaliar se, por exemplo, é melhor adicionar uma viatura ou realizar X kms em vazio para realizar o serviço. Que outras diferenças (não monetárias) têm as duas hipóteses?
Homem vs Máquina
Pelo que já vimos, estes problemas são gigantes e mesmo as máquinas não conseguem dar uma resposta garantidamente óptima para todos os casos.
Ainda assim, o humano consegue muitas vezes competir com a máquina e até melhorar as soluções da máquina. Mas como é possível que o humano possa “bater” a máquina?
Depois de muitos anos de experiência acumulada, a minha resposta provocadora é “fazendo batota” ou se quisermos ser mais diplomáticos “usando criatividade”.
A máquina está amarrada às regras que lhe foram dadas, enquanto que o humano consegue “jogar” com as regras não escritas se o benefício for evidente, por exemplo, se for dito à máquina que uma viagem chega às 10:01 e outra viagem tem partida às 10:00, todas as combinações em que essas viagens são realizadas pela mesma viatura são descartadas.
O humano, perante esta situação, tem um olhar mais crítico. Se verificar que esta é a origem de um incremento de meios (e consequentemente um salto significativo nos custos reais) questionará se é possivel alterar os dados base tendo em conta o seu conhecimento com vista a viabilizar esta combinação (“é um horário fora da hora de ponta logo sujeito a menos trânsito, será que o tempo de percurso pode ser encurtado?” e “se a viagem seguinte sair 2 minutos mais tarde?”)
Em resumo, o humano dificilmente “bate” a máquina, o que faz é alterar o problema, mas para efeitos de negócio é como se o fizesse. É por isso que o botão mágico é um mito!!
Então, podemos concluir que na prática os sistemas são inutéis?
Nem pensar nisso!! Os sistemas dão garantias de controlo das violações de restrições e dão boas soluções com as regras que têm, cabe ao humano, questionar as regras e calibrar as preferências.
Estes sistemas são ferramentas potentes mas não substituem o humano, dão superpoderes!
E antes que digam “Mas agora com os avanços da Inteligência Artificial já vai ser possível!”
Não creio. A Inteligência Artificial poderá contribuir no processo mas sou muito céptico. Penso que muito mais relevante serão os avanços em computação quântica que permitirão “atacar” problemas maiores!
Mas não fica por aqui
Tinha muito mais a dizer sobre este assunto mas o artigo já vai longo, por isso fica o compromisso de escrever um artigo dedicado aos Minutos Mágicos, deixo-vos uma breve nota sobre MUS para despertar o vosso interesse e por último um avanço recente face a um dos algoritmos clássicos.
Para os mais curiosos, deixo uma nota que me parece muito relevante sobre novos algoritmos que estão a ser desenvolvidos para “auditar” as soluções. Isto sim, irá revolucionar a resolução destes problemas ao orientar o humano para reavaliar e questionar as restrições.
Os MUS (Minimum unsatisfiable Subset) são um subconjunto de restrições que têm 3 características importantes: - Nenhuma solução consegue satisfazer simultaneamente estas restrições - Removendo qualquer uma das restrições do subconjunto, o sistema passa a ter solução - Cada sistema pode ter multiplos MUSes e estes não são necessariamente compostos pelo mesma quantidade de restrições
Na prática, o que um MUS permite é identificar qual a combinação de restrições que está impedir a resolução do problema. As abordagens mais recentes e promissoras, calculam o MUS com menor cardinalidade (o que tem menos restrições) para gerar explicações da impossibilidade de resolver o problema.
No nosso caso temos um problema de optimização de restrições, e não um problema de satisfação de restrições, ainda assim a técnica pode ser usada introduzindo restrições adicionais, por exemplo se queremos que o sistema explique porque não conseguiu usar menos viaturas, podemos adicionar uma restrição n_viaturas < Y.
Um dos algoritmos clássicos é o Algoritmo Dijkstra que permite encontrar o caminho mais curto. O algoritmo desenvolvido em 1956 e publicado em 1959 é ainda uma referência.
A Universidade de Tsinghua publicou este verão (Julho 2025), um Algoritmo que o supera de forma deterministica em certas circunstâncias.
A complexidade algorítmica de Djikstra é O(m + n log n) enquanto que o novo algoritmo apresenta O(m. log^(2/3) n)
Quando o gráfico é disperso, m ≈ n o novo algoritmo apresenta uma melhoria da complexidade na ordem de log^(1/3)n, o reverso da medalha, se o grafo é denso será ao contrário, piora num factor de log^(2/3).