Introducción

Escriba un solucionador para la programación lineal entera .

Reto

Su tarea es escribir un solucionador para la programación lineal de enteros (ILP). En ILP, se dan las desigualdades lineales de un conjunto de incógnitas (todas las cuales son enteras), y el objetivo es encontrar el mínimo o el máximo de una función lineal.

Por ejemplo, para las desigualdades (ejemplo tomado de la Programación lineal de enteros mixtos )

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

y la función objetivo 3x+2y, el máximo de la función objetivo debería ser 12( x=2,y=3), mientras que el mínimo debería ser 0( x=y=0).

La entrada se proporciona como una matriz 2D (o cualquier equivalente que siga las especificaciones estándar), cada fila corresponde a una desigualdad, con la excepción de la fila final. Los números en la matriz son los coeficientes, y la ≤0parte siempre se omite. Si hay nelementos en cada fila, significa que hay n-1incógnitas.

La última fila de la matriz corresponde a la función lineal. Los coeficientes están listados.

Por ejemplo, la matriz de entrada para el problema anterior es

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

El resultado debe ser el mínimo y el máximo, dado en cualquier forma razonable.

Para el siguiente problema (dos de las restricciones se eliminan del problema anterior):

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

El máximo es todavía 12, pero el mínimo no existe y la función objetivo puede tener valores negativos arbitrariamente grandes (en el sentido del valor absoluto). En este caso, el programa debería salir 12, siguiendo un valor falso que es decidido por el respondedor. Otro caso es que no hay ninguna solución, por ejemplo,

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

En este caso, los valores falsos también se deben generar. Sería bueno discernir el caso donde el "valor óptimo" para la función objetivo es el infinito y el caso donde no hay soluciones, pero esto no es necesario.

La entrada solo contiene coeficientes enteros tanto para las desigualdades como para la función objetivo. Todas las incógnitas también son enteros. Se garantiza que la matriz de coeficientes de las desigualdades tiene rango completo.

Casos de prueba

Crédito a @KirillL. por encontrar un error en el conjunto de pruebas original y profundizar mi comprensión de los 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]

Especificaciones

No necesita preocuparse por el manejo de excepciones.
Este es el código de golf , gana el menor número de bytes.
Máximo número de incógnitas: 9. Número máximo de desigualdades: 12.
Puede tomar entrada y proporcionar salida a través de cualquier formulario estándar , y puede elegir el formato.
Como de costumbre, las lagunas predeterminadas se aplican aquí.

code-golf math optimization Weijun Zhou
fuente

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

Peter Taylor

No lo ha mencionado explícitamente en la descripción de la tarea, pero sospecho que está buscando implementaciones originales del algoritmo, y no algún código aburrido que hace uso de las bibliotecas existentes. Sin embargo, jugué con sus casos de prueba en R y no pude reproducir exactamente los resultados. Por ejemplo, el caso [55, inf] solo funciona cuando las variables están limitadas a ser no negativas. Pero entonces el caso [-inf, 12] también produce resultados normales [0, 12]. Por otro lado, cuando el límite inferior es -inf, el caso [55, inf] no se resuelve en los escenarios mínimo y máximo.

Kirill L.

Sí, estoy buscando implementaciones originales.

Weijun Zhou

@KirillL. ¿Puede proporcionar un vector donde la función en el caso de prueba [55, inf] da un valor menor que 55? Acabo de comprobarlo con un solucionador en línea y el caso parece estar bien. Tengo el siguiente razonamiento al hacer este caso de prueba: la primera restricción requiere que la suma de todas las variables libres sea geq 8, pero la segunda requiere que la suma de todas excepto la última sea leq 0. Si alguna vez tratamos de disminuir objetivo al reducir cualquiera de las primeras 4 var libre, requeriría que la var final se incremente en la misma cantidad, por lo tanto, un valor mayor para el objetivo.

Weijun Zhou

Aquí está mi fragmento , aunque no funcionará en TIO debido a la falta de biblioteca. Esto da 55, pero sale con "el modelo no tiene límites" cuando descomento la línea set.bounds. Muy posiblemente, el error está de mi lado, sin embargo. ¿Podría también dar un enlace al solucionador en línea?

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))

Pruébalo en línea!

Visión general

Es un algoritmo iterativo, que comienza desde el origo. Recoge las posiciones vecinas y asigna una función potencial: x:(a,b)dónde xestá la posición, aes la suma de las distancias de la posición desde los medios espacios de cada desigualdad lineal, bes el valor del objetivo en esa posición.

x:(a,b) < y:(c,d)si a<coa=c and b<d

La iteración se detiene cuando:

la primera coordenada del potencial no ha disminuido y es positiva: el sistema no es factible
la distancia desde cada medio espacio ha disminuido al igual que el objetivo: el sistema no tiene límites.
ninguno de los anteriores y el potencial no ha disminuido: es el valor óptimo.

mmuntag
fuente

Programación lineal entera