Programmation linéaire entière

21

introduction

Écrivez un solveur pour la programmation linéaire entière .

Défi

Votre tâche consiste à écrire un solveur pour la programmation linéaire entière (ILP). En ILP, les inégalités linéaires d'un ensemble d'inconnues (qui sont toutes des entiers) sont données, et le but est de trouver le minimum ou le maximum d'une fonction linéaire.

Par exemple, pour les inégalités (exemple tiré de la programmation linéaire mixte en nombres entiers )

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

et la fonction objectif 3x+2y, le maximum de la fonction objectif devrait être 12( x=2,y=3), tandis que le minimum devrait être 0( x=y=0).

L'entrée est donnée sous la forme d'un tableau 2D (ou tout équivalent suivant les spécifications standard), chaque ligne correspond à une inégalité, à l'exception de la dernière ligne. Les nombres dans le tableau sont les coefficients et la ≤0partie est toujours omise. S'il y a des néléments dans chaque ligne, cela signifie qu'il y a des n-1inconnues.

La dernière ligne du tableau correspond à la fonction linéaire. Les coefficients sont répertoriés.

Par exemple, le tableau d'entrée pour le problème ci-dessus est

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

La sortie doit être le minimum et le maximum, donnés sous toute forme raisonnable.

Pour le problème suivant (deux des restrictions sont supprimées du problème ci-dessus):

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

Le maximum est encore 12, mais le minimum n'existe pas et la fonction objectif peut avoir des valeurs négatives arbitrairement grandes (au sens de valeur absolue). Dans ce cas, le programme doit sortir 12, suivant une valeur de falsification qui est décidée par le répondeur. Un autre cas est qu'il n'y a pas de solution du tout, par exemple,

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

Dans ce cas, les valeurs de falsification doivent également être sorties. Ce serait bien de discerner le cas où la "valeur optimale" pour la fonction objectif est l'infini et le cas où il n'y a pas du tout de solution, mais ce n'est pas nécessaire.

L'entrée ne contient que des coefficients entiers à la fois pour les inégalités et pour la fonction objectif. Toutes les inconnues sont également des nombres entiers. La matrice des coefficients des inégalités est garantie d'avoir un rang complet.

Cas de test

Nous remercions @KirillL. pour avoir trouvé un bogue dans la suite de tests d'origine et approfondi ma compréhension des problèmes 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]

Spécifications

  • Pas besoin de vous soucier de la gestion des exceptions.

  • C'est le , le plus petit nombre d'octets gagne.

  • Nombre d'inconnues Maximal: 9. Nombre maximal d'inégalités: 12.

  • Vous pouvez prendre des entrées et fournir des sorties sous n'importe quelle forme standard , et vous êtes libre de choisir le format.

  • Comme d'habitude, les failles par défaut s'appliquent ici.

Weijun Zhou
la source
Généraliser codegolf.stackexchange.com/q/155460/194
Peter Taylor
Vous ne l'avez pas explicitement mentionné dans la description de la tâche, mais je soupçonne que vous recherchez des implémentations originales de l'algorithme, et pas un code ennuyeux qui utilise des bibliothèques existantes? Néanmoins, j'ai joué avec vos cas de test en R et je n'ai pas pu reproduire exactement les résultats. Le cas d'Eg, [55, inf] ne fonctionne que lorsque les variables sont limitées pour être non négatives. Mais alors, le cas [-inf, 12] produit également des résultats normaux [0, 12]. D'un autre côté, lorsque la borne inférieure est -inf, le cas [55, inf] ne parvient pas à résoudre dans les scénarios min et max.
Kirill L.
Oui je recherche des implémentations originales.
Weijun Zhou
@KirillL. Pouvez-vous fournir un vecteur où la fonction dans le cas de test [55, inf] donne une valeur inférieure à 55? Je viens de le vérifier par rapport à un solveur en ligne et l'affaire semble aller bien. J'ai le raisonnement suivant en faisant ce cas de test: La première restriction exige que la somme de toutes les variables libres soit geq 8, mais la seconde exige que la somme de toutes sauf la dernière soit leq 0. Si jamais nous essayons de diminuer la objectif en réduisant l'une des 4 premières var libres, il faudrait que la var finale soit augmentée du même montant, d'où une valeur plus élevée pour l'objectif.
Weijun Zhou
Voici mon extrait de code , bien qu'il ne fonctionnera pas sur TIO en raison de la bibliothèque manquante. Cela donne 55, mais les sorties avec "le modèle est illimité" lorsque je décommente la ligne set.bounds. Très probablement, l'erreur est de mon côté, cependant. Pourriez-vous également donner un lien vers le solveur en ligne?
Kirill L.

Réponses:

2

Python 3 , 534 octets

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

Essayez-le en ligne!

Présentation

Il s'agit d'un algorithme itératif, à partir de l'origo. Il recueille les positions voisines et attribue une fonction potentielle: x:(a,b)xest la position, aest la somme des distances de la position par rapport aux demi-espaces de chaque inégalité linéaire, best la valeur de l'objectif à cette position.

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

L'itération s'arrête lorsque:

  • la première coordonnée du potentiel n'a pas diminué et positive: le système est infaisable
  • la distance de chaque demi-espace a diminué tout comme l'objectif: le système est illimité.
  • aucun des précédents et le potentiel n'a pas diminué: c'est la valeur optimale.
mmuntag
la source
1

Matlab, 226 octets

AVERTISSEMENT : Pas une implémentation "originale", seulement pour le plaisir.

Solution simple tirant parti de la intlinprogfonction:

function r=f(a);b=-1*a(1:end-1,end);p=a(end,1:end-1);c=a(1:end-1,1:end-1);[~,f,h]=intlinprog(p,1:size(a,2)-1,c,b);[~,g,i]=intlinprog(-p,1:size(a,2)-1,c,b);s=[inf,nan,f];t=[inf,nan,g];r=a(end,end)+[s(4-abs(h)) -t(4-abs(i))];end

Il renvoie les valeurs optimales, ou inf (-inf) si le problème est illimité ou nan s'il est irréalisable.

a = [4 2 -15; 1 2 -8; 1 1 -5; -1 0 0; 0 -1 0; 3 2 1]
b = [4 2 -15; 1 2 -8; 1 1 -5; 3 2 0]
c = [4 2 -15; -1 -2 7; -1 0 3; 0 1 0; 3 2 0]
d = [-1 -1 -1 -1 -1 8;  1 1 1 1 0 0; 0 0 0 0 0 4]
e = [4 2 -15; -1 -2 7; -1 0 3; 0 1 0; 0 0 4]

>> f(a)
ans =

     1    13

>> f(b)
ans =

   Inf    12

>> f(c)
ans =

   NaN   NaN

>> f(d)
ans =

     4     4

>> f(e)
ans =

   NaN   NaN
PieCot
la source