1. • Sequenciamento: Refere-se à ordem em que um conjunto de trabalhos deve passar por uma máquina. Esta abordagem permite considerar aspectos como a duração de cada trabalho, a data de entrega, etc. O objetivo é encontrar a ordem ideal que permita cumprir os objetivos do projeto ou produção, minimizando a duração total ou maximizando a eficiência. Isto é possível utilizando máquinas que trabalham em paralelo/série.

2. • Rotas: Os problemas de rotas são projetados para estabelecer a melhor sequência de rotas para fornecer um determinado serviço. Um dos problemas clássicos desta categoria é o problema do caixeiro viajante (TSP), que envolve visitar um conjunto de pontos uma vez e apenas uma vez. Várias variantes podem ser acrescentadas a este problema, como incluir vários viajantes, limitar a capacidade dos camiões ou a disponibilidade de tempo, incorporar janelas temporárias de entrega ou recepção, entre outras. A complexidade destes problemas aumenta à medida que mais restrições são adicionadas, mas a sua resolução eficiente pode gerar benefícios significativos em termos de custos e eficiência.

Nesta categoria existem problemas como:

1. • O problema da mochila (unidimensional ou multidimensional).

2. • Fluxo máximo (ou mínimo).

3. • Problemas de Atribuição Quadrática.

4. • Problema de particionamento de grafos.

5. • Num caminho mais curto (ou mais longo).

6. • O problema do caixeiro viajante.

7. • Programação linear.

8. • O problema das n-rainhas.

Métodos de busca heurística (algoritmos metaheurísticos) como os listados abaixo têm sido usados ​​para resolver problemas deste tipo.

• - Local search&action=edit&redlink=1 "Pesquisa local (otimização) (ainda não escrita)").

• - Recozimento simulado.

• - ENTENDER").

• - Inteligência de enxame.

• - Pesquisa tabu.

• - Algoritmos genéticos.

• - Otimização baseada em colônias de formigas.

• - Pesquisa reativa").

• - Otimização discreta").

• - Algoritmos de pesquisa.

• - Evolução diferencial.

• - Otimização Combinatória.

• - William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver; Otimização Combinatória; John Wiley & Filhos; 1ª edição (12 de novembro de 1997); ISBN 047155894X.

• - Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger, Um Compêndio de Problemas de Otimização NP.

• - Christos H. Papadimitriou e Kenneth Steiglitz; Otimização Combinatória: Algoritmos e Complexidade; Dover Pubns; (brochura, edição integral, julho de 1998) ISBN 0486402584.

Um problema de otimização combinatória é definido como aquele em que o conjunto de soluções possíveis é discreto. Em outras palavras, é um problema de otimização que envolve um número finito ou contável de soluções possíveis.

Este tipo de problema difere dos problemas de otimização contínua, nos quais o conjunto de soluções possíveis é infinito e incontável. Este ramo da otimização está intimamente relacionado à pesquisa operacional, teoria algorítmica e teoria da complexidade computacional. Algoritmos de otimização combinatória resolvem problemas que geralmente são considerados difíceis, explorando o grande espaço de soluções do problema em questão. Bons algoritmos de otimização combinatória conseguem reduzir o tamanho efetivo do espaço de busca e explorá-lo de forma eficiente.

É aqui que entram os algoritmos de otimização combinatória. São capazes de resolver problemas normalmente considerados difíceis, pois exploram um amplo espaço de soluções. Para conseguir isso, esses algoritmos reduzem efetivamente o tamanho do espaço e o exploram de forma eficiente.

No campo da otimização combinatória, é comum que a maioria dos processos de resolução de problemas não consiga garantir a solução ótima, mesmo dentro do contexto do modelo utilizado. No entanto, a aproximação do ótimo geralmente é suficiente para resolver problemas na prática.

Existem diferentes métodos de resolução que podem ser classificados em quatro grandes grupos:

1. • Algoritmos construtivos, que constroem a solução a partir de uma solução incompleta e utilizando os dados do problema e conhecimentos prévios.

2. • Algoritmos de melhoria, que partem de uma solução viável e completa e vão modificando-a gradativamente de forma progressiva.

3. • Estratégias de “dividir e conquistar”, que dividem o problema em fragmentos e aplicam qualquer outra estratégia para resolver cada fragmento, e finalmente recompõem a solução.

4. • Estratégias de aprendizagem, que tomam decisões com base em dados conhecidos do resultado de resoluções anteriores ou na mesma resolução.

Os métodos mais comuns utilizados para resolver problemas de otimização combinatória são heurísticas ou metaheurísticas. Esses métodos são capazes de gerar soluções para o problema, embora sejam aproximações que não necessariamente alcançam a solução ótima.

Nos primórdios da Pesquisa Operacional, as limitações do cálculo automático levaram à criação de procedimentos heurísticos que poderiam encontrar soluções rapidamente, embora não necessariamente as melhores.

Embora os métodos de resolução heurística não possam garantir a solução ótima, eles são essenciais por diversas razões. Primeiro, são capazes de gerar soluções, o que é melhor do que não ter nenhuma solução. Em segundo lugar, obter a solução óptima para um modelo que não representa exactamente o problema real não é necessariamente essencial. Finalmente, conceber uma boa heurística requer uma compreensão profunda do problema, o que pode levar a outros tipos de melhorias.

Portanto, métodos heurísticos, incluindo processos de melhoria local e algoritmos metaheurísticos, são ferramentas valiosas para resolver problemas de otimização combinatória na prática.

1. • Sequenciamento: Refere-se à ordem em que um conjunto de trabalhos deve passar por uma máquina. Esta abordagem permite considerar aspectos como a duração de cada trabalho, a data de entrega, etc. O objetivo é encontrar a ordem ideal que permita cumprir os objetivos do projeto ou produção, minimizando a duração total ou maximizando a eficiência. Isto é possível utilizando máquinas que trabalham em paralelo/série.

2. • Rotas: Os problemas de rotas são projetados para estabelecer a melhor sequência de rotas para fornecer um determinado serviço. Um dos problemas clássicos desta categoria é o problema do caixeiro viajante (TSP), que envolve visitar um conjunto de pontos uma vez e apenas uma vez. Várias variantes podem ser acrescentadas a este problema, como incluir vários viajantes, limitar a capacidade dos camiões ou a disponibilidade de tempo, incorporar janelas temporárias de entrega ou recepção, entre outras. A complexidade destes problemas aumenta à medida que mais restrições são adicionadas, mas a sua resolução eficiente pode gerar benefícios significativos em termos de custos e eficiência.

Nesta categoria existem problemas como:

1. • O problema da mochila (unidimensional ou multidimensional).

2. • Fluxo máximo (ou mínimo).

3. • Problemas de Atribuição Quadrática.

4. • Problema de particionamento de grafos.

5. • Num caminho mais curto (ou mais longo).

6. • O problema do caixeiro viajante.

7. • Programação linear.

8. • O problema das n-rainhas.

Métodos de busca heurística (algoritmos metaheurísticos) como os listados abaixo têm sido usados ​​para resolver problemas deste tipo.

• - Local search&action=edit&redlink=1 "Pesquisa local (otimização) (ainda não escrita)").

• - Recozimento simulado.

• - ENTENDER").

• - Inteligência de enxame.

• - Pesquisa tabu.

• - Algoritmos genéticos.

• - Otimização baseada em colônias de formigas.

• - Pesquisa reativa").

• - Otimização discreta").

• - Algoritmos de pesquisa.

• - Evolução diferencial.

• - Otimização Combinatória.

• - William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver; Otimização Combinatória; John Wiley & Filhos; 1ª edição (12 de novembro de 1997); ISBN 047155894X.

• - Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger, Um Compêndio de Problemas de Otimização NP.

• - Christos H. Papadimitriou e Kenneth Steiglitz; Otimização Combinatória: Algoritmos e Complexidade; Dover Pubns; (brochura, edição integral, julho de 1998) ISBN 0486402584.