Introdução

Escreva um solucionador para programação linear inteira .

Desafio

Sua tarefa é escrever um solucionador para programação linear inteira (ILP). No ILP, são dadas desigualdades lineares de um conjunto de incógnitas (todas inteiras), e o objetivo é encontrar o mínimo ou o máximo de uma função linear.

Por exemplo, para as desigualdades (exemplo extraído da Programação Linear Inteira Mista )

 4x+2y-15≤0
  x+2y- 8≤0
  x+ y- 5≤0
- x      ≤0
   - y   ≤0

e a função objetivo 3x+2y, o máximo da função objetivo deve ser 12( x=2,y=3), enquanto o mínimo deve ser 0( x=y=0).

A entrada é fornecida como uma matriz 2D (ou qualquer outro equivalente, seguindo as especificações padrão), cada linha corresponde a uma desigualdade, com exceção da linha final. Os números na matriz são os coeficientes e a ≤0parte é sempre omitida. Se houver nelementos em cada linha, isso significa que há n-1incógnitas.

A última linha da matriz corresponde à função linear. Os coeficientes são listados.

Por exemplo, a matriz de entrada para o problema acima é

[[4,2,-15],[1,2,-8],[1,1,-5],[-1,0,0],[0,-1,0],[3,2,0]].

A saída deve ser o mínimo e o máximo, fornecidos de qualquer forma razoável.

Para o seguinte problema (duas das restrições foram removidas do problema acima):

[[4,2,-15],[1,2,-8],[1,1,-5],[3,2,0]].

O máximo ainda é 12, mas o mínimo não existe e a função objetivo pode ter valores negativos arbitrariamente grandes (no sentido de valor absoluto). Nesse caso, o programa deve produzir 12, seguindo um valor falso que é decidido pelo atendedor. Outro caso é que não há solução, por exemplo,

[[4,2,-15],[-1,-2,7],[-1,0,3],[0,1,0],[3,2,0]].

Nesse caso, os valores falsos também devem ser gerados. Seria bom discernir o caso em que o "valor ideal" para a função objetivo é infinito e o caso em que não há soluções, mas isso não é necessário.

A entrada contém apenas coeficientes inteiros, tanto para as desigualdades quanto para a função objetivo. Todas as incógnitas também são números inteiros. A matriz do coeficiente das desigualdades é garantida para ter uma classificação completa.

Casos de teste

Crédito para @KirillL. por encontrar um bug no conjunto de testes original e aprofundar minha compreensão dos problemas de ILP.

Input
Output

[[4,2,-15],[1,2,-8],[1,1,-5],[-1,0,0],[0,-1,0],[3,2,1]]
[1,13]

[[4,2,-15],[1,2,-8],[1,1,-5],[3,2,0]]
[-inf, 12]

[[4,2,-15],[-1,-2,7],[-1,0,3],[0,1,0],[3,2,0]]
[NaN, NaN]

[[-1,-1,-1,-1,-1,8],[1,1,1,1,0,0],[5,5,5,5,6,7]]
[55, inf]

[[-1,-1,-1,-1,-1,8],[1,1,1,1,0,0],[0,0,0,0,0,4]]
[4, 4]

[[4,2,-15],[-1,-2,7],[-1,0,3],[0,1,0],[0,0,4]]
[NaN, NaN]

Especificações

Não precisa se preocupar com o tratamento de exceções.
Isso é código-golfe , o menor número de bytes vence.
Número máximo de incógnitas: 9. Número máximo de desigualdades: 12.
Você pode receber e fornecer saída através de qualquer formulário padrão e pode escolher o formato.
Como de costume, as brechas padrão se aplicam aqui.

code-golf math optimization Weijun Zhou
fonte

Generalises codegolf.stackexchange.com/q/155460/194

Peter Taylor

Você não o mencionou explicitamente na descrição da tarefa, mas suspeito que esteja buscando implementações originais do algoritmo, e não algum código chato que faça uso das bibliotecas existentes? No entanto, eu brinquei com seus casos de teste em R e não consegui reproduzir exatamente os resultados. Mas então o caso [-inf, 12] também produz resultados normais [0, 12]. Por outro lado, quando o limite inferior é -inf, o caso [55, inf] falha ao resolver nos cenários mínimo e máximo.

Kirill L.

Sim, estou procurando implementações originais.

Weijun Zhou

@KirillL. Você pode fornecer um vetor em que a função no caso de teste [55, inf] forneça um valor menor que 55? Acabei de compará-lo com um solucionador on-line e o caso parece estar bem. Eu tenho o seguinte raciocínio ao fazer esse caso de teste: A primeira restrição requer que a soma de todas as variáveis livres seja geq 8, mas a segunda requer que a soma de todas, exceto a última, seja leq 0. Se alguma vez tentarmos diminuir o meta, reduzindo qualquer um dos 4 primeiros var gratuitos, exigiria que o var final fosse aumentado na mesma quantidade, portanto, um valor maior para a meta.

Weijun Zhou

Aqui está meu trecho , embora não funcione no TIO devido à falta de biblioteca. Isso dá 55, mas sai com "model is bounded" quando descomente a linha set.bounds. Muito possivelmente, o erro está do meu lado, no entanto. Você também poderia fornecer um link para o solucionador on-line?

Kirill L.

Python 3 , 534 bytes

import itertools as t
import operator as o
I=float("inf")
e=lambda p,A:sum([i[0]*i[1]for i in zip(p,A[:-1])])+A[-1]
def w(x,j):
	d=len(x[0])-1;C=[0]*d;v,w=I,I
	while 1:
		L={(*n,):(sum([0 if e(n,A)<=0 else e(n,A)for A in x[:-1]]),j*e(n,x[-1]))for n in [[sum(a) for a in zip(C,c)]for c in t.product(*[[-1,0,1]]*d)]};C,P=min(L.items(),key=o.itemgetter(1))[0],C;v,w,p,q=L[C][0],L[C][1],v,w
		if(all([e(C,A)<=e(P,A)for A in x[:-1]]))*(j*(e(C,x[-1])-e(P,x[-1]))<0)+(p==v>0):return I
		if(p==v)*(q<=w):return j*q
f=lambda x:(w(x,1),w(x,-1))

Experimente online!

visão global

É um algoritmo iterativo, iniciando no origo. Ele coleta as posições vizinhas e atribui uma função potencial: x:(a,b)onde xestá a posição, aé a soma das distâncias da posição dos meios espaços de cada desigualdade linear, bé o valor do objetivo nessa posição.

x:(a,b) < y:(c,d)iff a<coua=c and b<d

A iteração para, quando:

a primeira coordenada do potencial não diminuiu e foi positiva: o sistema é inviável
a distância de cada meio espaço diminuiu exatamente como o objetivo: o sistema é ilimitado.
nenhuma das anteriores e o potencial não diminuiu: é o valor ideal.

mmuntag
fonte

Programação Linear Inteira