Em que casos é a solução de Binário Linear Programa fácil (i.e.**P** complexidade)?Eu estou olhando para problemas de programação, em particular

Question

Em que casos é a solução de Binário Linear Programa fácil (i.e. P complexidade)?

A razão que eu estou pedindo é para entender se posso reformular um problema de programação atualmente estou trabalhando em uma forma de garantia de encontrar o valor ótimo global dentro de um tempo razoável, assim, qualquer conselho em que a direção é mais bem-vindo.

Eu estava sob a impressão de que quando a solução de um problema de agendamento, onde o valor de uma variável de 1 representa que um particular (intervalo de tempo x pessoa) par é parte da programação, se o resultado contém não inteiros, o que significa que existem vários válido horários, e o resultado é uma combinação linear de tais agendas;para obter um número inteiro válido solução, você simplesmente precisa re-executar o algoritmo de solução atual, com uma restrição adicional para um dos valores reais das variáveis iguais a 0 ou 1.

Estou enganado nesse entendimento?Há um particular subconjunto de (agendamento) problemas onde isso seria uma estratégia válida?Qualquer papers / livro capítulo sugestões são muito bem-vindos também.

Answer 1

Não é verdade que fracionário soluções podem, necessariamente, ser transformado em soluções integrais.Por exemplo, suponha que 1 necessita de fendas A e B, ou faixas D e e;2 requer tanto slots B e C, ou faixas e e F;e 3 necessita de fendas A e C, ou slots D e F.É fácil verificar não há solução integral em (A,B,C, juntos, podem acomodar mais de uma, e, D,E,F, juntos, podem acomodar mais de um).No entanto, há uma solução fracionária de dar a todos 1/2 de cada slot que poderia acomodar-los.

Há condições, tais como total unimodularity que garante que não sejam as melhores soluções integrais.Nesse caso, o problema está em P, porque tudo o que é necessário para resolver o LP de relaxamento que pode ser feito em tempo polinomial.