O que se sabe sobre soluções para problemas esparsos de programação linear inteira?

Se eu tiver um conjunto de restrições lineares em que cada restrição tenha no máximo (digamos) 4 variáveis ​​(todas não-negativas e com coeficientes {0,1}, exceto uma variável que pode ter um coeficiente -1), o que se sabe sobre a solução espaço? Estou menos preocupado com uma solução eficiente (embora indique se é conhecida) do que com saber quão pequeno pode ser o mínimo da função objetivo, em função do número de variáveis ​​e do número de restrições e do número de variáveis ​​por limitação.

Mais concretamente, o programa é algo como

minimizar t
  sujeito a
para todos i, x_i é um número inteiro positivo
x1 + x2 + x3 - t <0
x1 + x4 + x5 - t <0
...
x3 + x6 - t ≥ 0
x1 + x2 + x7 - t ≥ 0
...

Se for necessária uma pergunta concreta, será que a solução mínima obedece a t <= O (max {# de variáveis, # de restrições}), com a constante em O () dependendo da escassez? Mas, mesmo que a resposta seja negativa, estou mais interessado em saber que tipo de livro ou trabalho estudar para uma discussão sobre essas questões e se existe uma área de estudo dedicada a esse tipo de coisa, mas simplesmente não sei. os termos a serem pesquisados. Obrigado.

Atualização: Com uma reflexão mais aprofundada (e pensando na simples redução de 3SAT para ILP, que utiliza restrições com três variáveis), percebo que a questão dos coeficientes é crítica (se houver um algoritmo eficiente). Mais precisamente, todas as variáveis ​​x_i têm 0 ou 1 coeficiente (com no máximo três coeficientes 1 em qualquer restrição), e todas as variáveis ​​t têm coeficientes -1, e todas as comparações têm variáveis ​​à esquerda e 0 à direita. Eu atualizei o exemplo acima para esclarecer.

A resposta para isso (pelo menos para a pergunta concreta sobre limitar linearmente a solução) é não. Isso faz parte do seguinte artigo: http://arxiv.org/abs/1011.3493 . O teorema 5.1 foi a motivação para esta pergunta.

O contraexemplo é este:

caso base:

a_1 '+ b_1' - t ≥ 0
a_1 '' + b_1 '' - t ≥ 0
a_1 + b_1 '- t ≤ -1
a_1 '+ b_1' '- t ≤ -1

caso recursivo:

a_n '+ b_n' + a_ {n-1} - t ≥ 0
a_n '' + b_n '' + a_ {n-1} - t ≥ 0
a_n + b_n '+ a_ {n-1}' '- t ≤ -1
a_n '+ b_n' + a_ {n-1} '' - t ≤ -1

além de exigir que todos eles não sejam negativos.

Você pode provar por indução que qualquer solução real deve satisfazer a_n ''> = a_n + 2 ^ n. Alteramos as desigualdades "<0" para "≤ -1" porque qualquer solução inteira satisfaz "≤ -1" se e somente se satisfaz "<0".

Portanto, a moral é que n desigualdades dessa forma podem ter a propriedade de que todas as soluções inteiras têm pelo menos um número inteiro pelo menos exponencial em n, certamente não linearmente delimitadas como inicialmente suspeitávamos.

Se a matriz do coeficiente for totalmente unimodular , existe uma solução eficiente por meio de programação linear comum. Isso vale para qualquer ILP, não apenas os esparsos - embora seja mais provável que você possa explorar essa propriedade para um ILP esparso como o seu.

Eu suspeito que você já saiba disso, então deixe-me tentar dar uma resposta melhor. Antes de pensar profundamente nos detalhes, a resposta para sua pergunta concreta é "sim", existe um limite. A interseção de n desigualdades em m variáveis ​​define um politopo. Como os coeficientes são muito bem-comportados, podemos calcular um limite superior na dimensão das coordenadas de seus vértices com um pouco de aritmética. Isso fornece um limite superior muito fácil para a dimensão de qualquer ponto inteiro dentro do politopo e, portanto, para uma solução para o seu programa inteiro. Você já tentou isso?

Seu problema, em particular, tem um pouco de estrutura (estou curioso, de onde vem?), Então estou confiante de que podemos ser muito mais precisos que isso se discutirmos mais a fundo.

Agora, para a pergunta mais geral sobre como encontrar informações sobre este tópico. Esse é o tipo de problema que tradicionalmente se enquadra na teoria da programação linear e inteira, um subconjunto da programação matemática.

É uma área de pesquisa bastante ativa, mas grande parte do trabalho ocorre nos departamentos de pesquisa operacional sob os títulos "otimização" e "programação matemática" em vez de ciência da computação. Existem muitos livros didáticos disponíveis sobre o assunto. Você pode considerar o de Wolsey , que usamos em Berkeley. Aqui está uma lista subutilizada de mitos e contra-exemplos de Greenberg, incluindo programação inteira e linear, que pode lhe dar uma idéia do que as pessoas consideram ao analisar esses problemas. Wolsey é densa, mas é um bom ponto de partida - existem várias técnicas para analisar ILPs e melhorar as formulações de problemas a ponto de serem eficientes.

Permitam-me acrescentar que, se você seguir a abordagem ingênua, sugiro que, analisando a geometria do politopo, os termos a serem pesquisados ​​sejam relacionados ao limite do tamanho das coordenadas dos vértices do politopo. Esses termos surgem com mais frequência na literatura matemática sobre politopos.

Você pode encontrar esta conta de seu interesse:

http://en.wikipedia.org/wiki/Polyhedral_combinatorics

e, em particular, o artigo de G. Ziegler:

Palestras sobre polítopos 0-1

em:

Kalai, Gil; Ziegler, Günter M. (2000), Polytopes: Combinatorics and Computation, DMV Seminar, 29, Birkhäuser, ISBN 9783764363512.