Problema de la motxilla

El problema de la motxilla, altrament dit KP (en anglès, Knapsack Problem) és un problema d'optimització combinatòria. Modelitza una situació anàloga al fet d'omplir una motxilla, en la que no es pot posar més d'un cert pes, amb tot o una part d'un conjunt d'objectes. Aquests objectes tenen un pes i un valor determinat. Els objectes que es posen dins la motxilla han de maximitzar el valor total sense sobrepassar el pes màxim.

Història modifica

Recerca modifica

El problema de la motxilla és un dels 21 problemes NP-complets de Richard Karp, exposats en el seu article de 1972. Ha estat estudiat des de meitats del segle XX i se'n troben referències des de 1897, en un article de George Ballard Mathews.^[1] La formulació del problema és força senzilla, però la seva solució és més complexa. Els algorismes existents poden resoldre casos concrets però l'estructura singular del problema i el fet que és un sub-problema d'altres problemes més generals, fan que actualment encara sigui estudiat per diferents grups de recerca científica.

Complexitat i criptografia modifica

Aquest problema és l'origen del primer algorisme de criptografia asimètrica (o de clau pública) presentat per Martin Hellman, Ralph Merkle i Whitfield Diffie a la Universitat de Stanford el 1976.^[2] De totes maneres, encara que la idea és deguda al problema de la motxilla, RSA és considerat com el veritable algorisme de xifratge asimètric.

La versió NP-difícil d'aquest problema ha estat utilitzat en algunes primitives i alguns protocols de criptografia, com el criptosistema de Merkle-Hellman o el criptosistema de Chor-Rivest. El seu avantatge amb respecte als criptosistemes asimètrics basats en la dificultat de la descomposició en producte de factors primers és la seva velocitat de xifratge i dexifratge. Però, l'algorisme de Hellman, Merkle i Diffie està subjecte a "portes posteriors " algorítmiques, la qual cosa implica que s'ha « trencat», és a dir criptoanalitzat.^[3] El problema de la motxilla és un exemple clàssic que menysprea tot allò que té a veure amb els lligams entre els problemes NP-complets i la criptografia. Una versió revisada de l'algorisme, amb una iteració del problema de la motxilla, va ser presentada però es va trencar ben aviat.^[4] Fins a l'actualitat, tots els algorismes de xifratge asimètrics basats en el problema de la motxilla han estat desxifrats, l'últim el de Chor-Rivest.^[5]

Altres àmbits relacionats modifica

També s'utilitza per a modelitzar les següents situacions, algunes vegades utilitzant-lo com a sub-problema:

en sistemes de suport a la gestió del portafolis: per equilibrar la selecció i la diversificació amb l'objectiu de trobar el millor equilibri entre el rendiment i el risc d'un capital col·locat en diferents actius financers (accions...);
en la càrrega d'un vaixell o d'un avió: tot l'equipatge que es pot portar sense sobrepès

en el tall dels materials: per minimitzar les pèrdues degudes als talls (de diferents mides) realitzats en barres de ferro.

Una altra raó per la qual és interessant aquest problema és que apareix en alguns mètodes de generació de columnes (així com pel problema de bin packing).

Anecdòticament aquest problema es pot aplicar a la decisió que ha de prendre un excursionista quan ha de planificar la seva excursió: la motxilla té una capacitat limitada, per tant, cal decidir què emportar-se (per exemple, dues llaunes de conserva i una carmanyola de cinquanta centilitres o només una sola capsa de conserva i una carmanyola d'un litre.

Enunciat matemàtic modifica

Les dades del problema es poden expressar en termes matemàtics. Els objectes es numeren mitjançant un índex i que varia d'1 a n. Els nombres $w_{i}$ i $p_{i}$ representen respectivament el pes i el valor de l'objecte numerat i. Anomenarem W a la capacitat de la motxilla.

Hi ha moltes maneres d'omplir la motxilla. Per descriure qualsevol d'elles només cal indicar si l'hem agafat o no. Es pot utilitzar un codi binari per codificar aquesta situació: l'estat de l'element i-èsim valdrà $x_{i}=1$ si s'ha ficat l'element a la motxilla, o $x_{i}=0$ si no s'ha ficat. Per tant, una manera qualsevol d'omplir la motxilla queda completament descrita per un vector, anomenat vector del contingut, o simplement contingut: $X=(x_{1},x_{2},...,x_{n})$ . Per tant, el pes associat, així com el valor associat a aquesta manera d'omplir la motxilla es poden expressar com una funció del vector del contingut.

Donat un contingut X, el valor total contingut en la motxilla és, evidentment:

z(X)=\sum _{\{i,\,x_{i}=1\}}p_{i}=\sum _{i=1}^{n}x_{i}p_{i}

De la mateixa manera, la suma dels pesos dels objectes escollits és:

w(X)=\sum _{i=1}^{n}x_{i}w_{i}

Per tant, el problema es pot reformular com la recerca d'un vector de contingut $X=(x_{1},x_{2},\dots ,x_{n})$ (les components del qual valen 0 o 1), tal que maximitzin la funció valor total $z(X)$ , amb les restriccions:

w(X)=\sum _{i=1}^{n}x_{i}w_{i}\leq W

(1)

És a dir que la suma dels pesos dels objectes escollits no passi la capacitat de la motxilla.

En general, s'afegeixen les restriccions següents per tal d'evitar casos singulars:

$\sum _{i=1}^{n}w_{i}>W$ : no es poden ficar tots els objectes;
$p_{i}>0,\forall i\in \{1,\dots ,n\}$ : tots els objectes aporten algun benefici;
$w_{i}>0,\forall i\in \{1,\dots ,n\}$ : tot objecte consumeix recursos (i.e. ocupa lloc).

Terminologia :

$z(X)$ s'anomena funció objectiu ;
tot vector $X$ que verifica la restricció (1) s'anomena realitzable ;
si el valor de $z(X)$ és màxim, llavors es diu que $X$ és òptim.

NP-complet modifica

El problema de la motxilla es pot representar sota una forma de decisió canviant la maximització per la qüestió següent: donat un nombre $k$ , existeix un valor de les $x_{i}$ pel qual $\sum _{i=1}^{n}p_{i}x_{i}\geq k$ , tot respectant la restricció? Hi ha un lligam entre la versió « decisió » i la versió « optimització» del problema tenint en compte que hi ha un algorisme polinòmic que resol la versió de « decisió », de la mateixa manera que es pot trobar el valor màxim pel problema d'optimització de manera polinomial aplicant iterativament aquest algorisme mentre es va augmentant el valor de k. Per d'altra banda, si un algorisme troba el valor òptim del problema d'optimització en un temps polinomial, llavors el problema de decisió es pot resoldre en temps polinomial comparant el valor de la solució proporcionada per aquest algorisme amb el valor de k. Per tant, les dues versions del problema són de dificultat similar. Sota la forma de decisió, el problema és NP-complet, cosa que significa que no es coneix cap mètode general per construir una solució òptima, a part l'examen sistemàtic de totes les possibles solucions. El problema d'optimització és NP-complet, la seva resolució és com a mínim tan difícil que la del problema de decisió, i no existeix cap algorisme polinomial conegut que, donada una solució, pugui dir si és òptima (cosa que voldria dir que no existeix cap solució amb un $k$ més gran, per tant, resoldre el problema de decisió NP-complet).

Procediment d'exploració sistemàtica modifica

Aquest examen sistemàtic es pot realitzar amb ajuda d'un arbre d'exploració binaria..... el representat aquí al costat (els triangles representen sub-arbres).

L'arbre es descriu baixant des del cim fins a la part baixa dels triangles (les fulles de l'arbre). Cada cas correspon a un únic recorregut possible. Seguint les indicacions donades al llarg de les arestes de l'arbre, a cada camí li correspon una tira de valors per $x_{0},x_{1},...,x_{n}$ formant un vector contingut. Per tant és possible dir en cada cas el valor total i el pes total corresponent al contingut. Només queda eliminar els casos que no satisfan la restricció, i escollir entre aquelles que queden, aquella (o una d'aquelles) que fa assolir el màxim a la funció objectiu.

Cada vegada que un objecte s'afegeix a la llista dels objectes disponibles s'afegeix un nivell a l'arbre d'exploració binari, i el nombre de casos es multiplica per 2. L'exploració de l'arbre i la completació de casos tenen un cost que creix exponencialment amb el nombre d'objectes.

Prova de la NP-completitud modifica

Aquesta prova de la NP-completitud va ser presentat per Maichail G. Lagoudakis^[6] recuperant un article de Richard Karp i un article de J.E. Savage.

Detalls de la demostració

La prova de NP-completitud es fa utilitzant el problema de la motxilla sota la forma d'un problema de decisió. Es fa en dues etapes, primerament es verifica que (KP) pertany a la classe NP i, en segon lloc, demostrant que (KP) és NP-difícil.

Per realitzar la prova de pertinença a NP-difícil utilitzarem la versió suma de sub-conjunts (vegeu les variants, més a baix), notat (SSE), una versió particular del de la motxilla en la que el benefici que aporta un objecte és igual al seu pes. Si aquesta versió particular és NP-difícil llavors (KP) en general, també ho és.

Es pot obtenir el problema (SSE) a partir del problema de la motxilla posant $w_{i}=p_{i}$ . Posant W = k, s'obté :

Trobar X tal que

$\sum _{i=1}^{n}w_{i}x_{i}\geq W$
$\sum _{i=1}^{n}w_{i}x_{i}\leq W$

Pertinença a NP modifica

Abans de res s'ha de provar que (KP) pertany a la classe NP, és a dir que existeix un algorisme polinomial que, donada una solució del problema, pot verificar que aquesta solució és la bona. Per verificar una solució simplement cal calcular la suma dels pesos dels objectes escollits i comparar-la amb W, de la mateixa manera que la suma dels seus valors s'han de comparar amb $k$ . El total és evidentment polinomial. (KP) pertany per tant a la classe dels problemes NP.

Pertinença a NP-difícil modifica

Es demostra també que (SSE) és un problema NP-difícil transformant el problema de la cobertura exacta (notat (EC), de l'anglès exact cover) en un problema (SSE). El problema (EC) s'expressa així:

Sigui U un conjunt d'elements i

S=\{S_{1},\dots ,S_{n}\}

un conjunt de sub-conjunts d'U. Existeix un sub-conjunt

S^{*}

de S tal que :

$\bigcup _{s\in S^{*}}s=U$ : tots els elements d'U hi siguin;
$s\cap t=\emptyset ~\forall s,t\in S^{*},s\neq t$ : cada element d'U està únicament en un sol dels subconjunts escollits.

El problema (EC) és NP-complet. Si s'arriba a demostrar que en tota instància d'(EC) es pot transformar polinomialment en una instància de (SSE) llavors haurem pogut provar que (SSE) (i per tant (KP)) pertany a la classe de problemes NP-complets.

Sigui I = (U,S) una instància qualsevol de (EC). Sense perdre la generalitat, considerem que $U=\{1,\dots ,|U|\}$ . Notarem:

$x_{i}\in \{0,1\}$ l'estat del conjunt $S_{i}$ ( $x_{i}=1$ si i només si $S_{i}\in S^{*}$ ) ;
$y_{ij}\in \{0,1\}$ la pertinença del valor j al conjunt $S_{i}$ ( $y_{ij}=1$ si i només si $j\in S_{i}$ ).

Sigui $b=|U|+1$ . Les variables del problema (SSE) són les $x_{i}$ del problema (EC). Definim el seu pes de la manera següent:

$w_{i}=\sum _{j\in U}y_{ij}b^{j-1}$ .

Definim la capacitat W per

$W={\frac {b^{|U|}-1}{b-1}}=\sum _{j\in U}b^{j-1}$ .

El pes de l'objecte i és una suma de potències de b i $b^{j-1}$ està a $w_{i}$ si i només si $j\in s_{i}$ . Per tant, hi ha una correspondència d'u a u entre la solució del problema(SSE) construït i la instància d'(EC). Cada valor $w_{i}$ es calcula en $O(|U|)$ i la valor de W es calcula en O(1). La transformació té per tant una complexitat temporal en $O(n|U|)$ . El problema (SSE) (i per tant el problema(KP)) pertany a la classe dels problemes NP-difícil.

Conclusió modifica

Hem provat que (KP) és NP i NP-difícil. Per tant, el problema (KP) pertany a la classe de problemes NP-complets.

Resolució aproximada modifica

Com a la majoria dels problemes NP-complets, pot ser interessant trobar possibles solucions encara que no siguin òptimes. Preferentment amb un control sobre la diferència entre el valor de la solució i el valor de la solució òptima.

S'adopta la següent terminologia:

s'anomena eficàcia d'un objecte la raó (quocient) del seu valor entre el seu pes. Com més gran és el valor de l'objecte comparat amb el que consumeix, més interessant és l'objecte;

Algorisme golafre modifica

L'algorisme més senzill és un algorisme golafre. La idea és afegir primer els objectes més eficaços, fins a omplir la motxilla:

triar els objectes per ordre decreixent d'eficàcia
w_conso := 0

per i de 1 a n
si w[i] + w_conso <= W llavors
x[i] := 1
w_conso := w_conso + w[i]
sino
x[i] := 0
fi si
fi per

On en acabar, la variable w_conso conté el pes total dels objectes que s'han ficat a la motxilla i els elements del vector w[i] contenen un 1 si l'objecte i s'ha ficat a la motxilla i 0 si no.

Les dos fases de l'algorisme golafre. A l'esquerra: tria de caixes per ordre d'interès (en aquest cas, en dòlars per quilogram). A la dreta: la integració en les caixes, si és possible. Aquí tenim a 11$ per 11 kg, mentre que la solució òptima és de 12$ i 14 kg.

Anàlisi de l'algorisme golafre modifica

Denotem $z^{*}$ el valor de les solucions òptimes.

La solució $X$ donada per l'algorisme golafre pot ser realment dolenta. Considereu, per exemple, que tenim dos objectes per col·locar a la motxilla. El primer dona un benefici de 2 i un pes d'1, el segon té un benefici i un pes iguals tots dos, de valor W (on W.és el pes màxim que es pot ficar a la motxilla). El primer objecte serà el més eficaç i per tant serà elegit en primer lloc i evitarà que s'agafi el segon (perquè ara el pes màxim que hi queda per omplir és W-1 que és més petit que el de l'objecte que queda), donant llavors el valor 2 com a solució mentre que W és el valor òptim per a tot W més gran que 2. Així que hi ha valors del problema pels quals la relació entre la solució trobada i la solució òptima és tant propera a zero com es vulgui (només cal triar un W prou gran).

Hi ha altres algorismes d'aproximació per al problema de la motxilla que permeten garantir que la solució donada està a una distància $k$ o a una raó $\epsilon$ de la solució òptima. És a dir, que la solució $X$ trobada compleix $z^{*}-z(X)\leq k$ o ${\frac {z(X)}{z^{*}}}\leq 1-\epsilon$ . La complexitat d'aquests algorismes és, generalment, inversament proporcional a la qualitat esperada, per exemple, $O(n^{\frac {1}{\epsilon }})$ ou $O(n^{2}+{\frac {1}{\epsilon ^{2}}})$ . El temps d'execució pot ser molt important.

Metaheurística modifica

Els mètodes metaheurístics com els algorismes genètics o les optimitzacions basades en algorismes de colònies de formigues permeten obtenir una aproximació raonablement bona evitant monopolitzar molts recursos.

Algorisme genètic modifica

Exemple de l'evolució d'una població amb un algorisme genètic. Els objectes són els mateixos que els utilitzats a l'exemple de l'algorisme voraç. Per exemple, el genoma (0,1,0,1,0) correspon a una selecció de la capsa de 12 kg i una de 7 kg.

Els algorismes genètics s'utilitzen habitualment en problemes d'optimització difícils com el problema de la motxilla. Són relativament fàcils de posar en pràctica i permeten obtenir ràpidament una solució satisfactòria encara que la mida del problema sigui gran.

Es tracta de generar una població d'individus on el cromosoma de cada individu simbolitza una solució del problema. La representació d'un individu és binària, ja que cada objecte serà, o bé agafat, o bé escartat de la motxilla. El nombre de bits del genoma de cada individu correspon al nombre d'objectes disponibles.

L'optimització segueix els principis habituals de l'algorítme genètic. Els individus són avaluats i només els millors se seleccionen per a la reproducció. Segons l'evolució, els operadors de reproducció poden ser més o menys complexes (cross-over), poden també intervenir mutacions (substituint un 0 per un 1 o a la inversa). També es pot decidir copiar el millor individu per a la generació següent (elitisme). Després d'un cert nombre de generacions, la població tendeix cap a un òptim, és a dir, la solució exacta.

Algorismes basats en les colònies de formigues modifica

Analogia amb les formigues: el camí que porta a la gota de mel (molt ensucrada) rep més feromones que aquells que porten a les gotes d'aigua poc ensucrades, més grans però menys interessants per la colònia, que té recursos limitats (el nombre de formigues o l'emplaçament de les reserves disponibles)

Aquest concepte ha estat utilitzat per a resoldre el problema de la motxilla multidimensional en què s'han de complir diverses restriccions a la vegada.

Els primers algorismes se sostenien en la idea de l'algorisme golafre: les formigues seleccionen progressivament els objectes més interessants. Aquesta selecció pot variar però es basa sempre en traces de feromones depositades per les formigues que condicionen les seves eleccions posteriors. Entre totes les solucions proposades, es troba posar feromones sobre els objectes triats, posar-ne sobre parells d'objectes triats a la solució un darrere l'altre i fins i tot afegir feromones sobre parells d'objectes, independentment de l'ordre en què es van triar.

Una síntesi realitzada per investigadors tunisians i francesos va demostrar que l'algorisme que consisteix a deixar restes sobre parells d'objectes successivament seleccionats és menys eficaç que les variants que es focalitzen sobre un objecte o parells qualssevol.^[7] Sempre es poden millorar, ja que aquests algorismes es poden combinar amb d'altres metaheurístics a fi d'apropar-se a la solució òptima.

Resolució exacta modifica

El problema de la motxilla, a la seva versió clàssica, ha estat estudiat en profunditat. Per tant, avui en dia, existeixen molts mètodes per resoldre'l. La majoria d'aquests mètodes corresponen a una versió millorada d'un dels següents mètodes.

Programació dinàmica modifica

El problema de la motxilla posseeix la propietat de sub-estructura optima, és a dir que es pot construir la solució òptima del problema amb i variables a partir del problema amb i-1 variables. Aquesta propietat permet utilitzar un mètode de resolució de programació dinàmica.

Aquesta propietat prové de les següents observacions suposada coneguda la solució:

Si la variable i no entra en la solució llavors l'òptim del problema sense aquesta variable ha de ser el mateix que amb ella.

Si la variable i hi entra, llavors un problema amb una motxilla que admeti un pes reduït pel pes de l'objecte i amb tots els altres objectes ha de tenir com a resultat òptim el mateix que el problema en qüestió (sense l'objecte i). Altrament si hi hagués una selecció d'objectes millor sempre es podria afegit l'objecte i (ja que a la motxilla s'ha reservat capacitat per ficar-hi l'objecte i) i es trobaria un resultat millor que l'òptim el que és una contradicció.

Sigui KP(i,c) el problema reduït a i variables i amb capacitat c. La idea és la següent:

Siguin i una variable i c una capacitat, les solucions òptimes de KP(i,c) són, o bé :

les solucions òptimes del problema amb i-1 variables amb la mateixa capacitat c (KP(i-1,c)), a les que s'afegeix $x_{i}=0$ ;
les solucions òptimes del problema amb i-1 variables amb capacitat $c-w_{i}$ (KP(i-1, $c-w_{i}$ )), a les que s'afegeix $x_{i}=1$ .

El problema de la motxilla amb variable zero (KP(0,*)) té una solució òptima de valor nul.

Llavors es construeix una taula T[i,c] que conté els valors de les solucions òptimes de tot problema KP(i,c) de la manera següent :

per c de 0 a W fer
 T[0,c] := 0
fi per

per i de 1 a n fer
 per c de 0 a W fer
 si c>=w[i] llavors
 T[i,c] := max(T[i-1,c], T[i-1, c-w[i]] + p[i])
 sino
 T[i,c] := T[i-1,c]
 fi si
 fi per
fi per

Un cop s'ha construït la taula, n'hi ha prou amb començar a partir del cas T[n,W] i d'anar deduint l'estat dels objectes anant pujant fins al cas T[0,*].

Aquest algorisme té una complexitat temporal i espacial $O(nW)$ . Malgrat això, es pot reduir el consum de la memòria fins a $O(n+W)$ , i fins i tot, si el valor de la solució optima és important, a $O(W)$ . Té dos avantatges:

velocitat
no cal triar les variables.

i un inconvenient :

consumeix molta memòira (per tant, no es poden resoldre problemes de mida gran).

Aquesta aproximació la va fer Garfinkel i Nemhauser (1972).^[8]

Procediment de separació i d'avaluació modifica

Com tot problema combinatòric, el problema de la motxilla es pot solucionar amb l'ajuda d'un procediment de separació i d'avaluació (PSE). La funció d'avaluació d'un nodes consisteix sovint a resoldre un problema en variables contínues (vegeu avall). La implementació proposada per Martello i Toth (1990)^[9] és un referent, ja que:

té una avaluació de nodes millorada;
té un recerca local, ja que la darrera variable afegida a la motxilla ha portat a un fracàs;
necessita un esforç intel·lectual considerable per comprendre el codi font.

L'avantatge d'aquest mètode és el consum responsable de la memòria.

Aproximacions híbrides modifica

L'aproximació híbrida no és realment un nou mètode de resolució. Consisteix simplement a combinar els dos mètodes precedents amb l'objectiu d'aprofitar tots els avantatges. Típicament s'aplicarà un PSE fins a una profunditat de búsqueda on el subproblema es considerarà prou petit per ser resolt per programació dinàmica.

Els precursors d'aquest enfocament són Plateau i Elkihel (1985),^[10] seguits per Martello i Toth (1990).^[9] Posteriorment s'han fet d'altres millores.

Variants modifica

El problema presentat fins al moment és el problema de la motxilla en variables binàries (01KP). De fet, es tracta d'una variant entre altres possibles. Aquesta secció presenta aquestes altres variants. Les particularitats es fan sobre el domini de les variables, la quantitat de valors dels objectes, la quantitat de dimensions de la motxilla, etc. Aquestes particularitats es poden combinar entre si.

Variables contínues modifica

El problema de la motxilla en variables contínues (LKP) s'obté traient la restricció que les variables siguin nombres enters. És a dir que es permet agafar simplement una fracció dels objectes dins la motxilla: $x_{i}\in [0,1]$ . A diferència de KP, LKP pertany a la classe de complexitat P.

Algorisme que calcula una solució òptima del problema LKP : Escollir els objectes en ordre decreixent d'eficàcia

i := 1
w_dispo := W

mentre w_dispo >= w[i] fer
x[i] := 1
w_dispo := w_dispo - w[i]
i := i + 1
fi mentre

x[i] := w_dispo / w[i]

mentre i < n fer
i := i + 1
x[i] := 0
fi mentre

Cal destacar que el valor de la solució òptima de LKP és com a molt igual al doble del valor de la solució òptima del problema KP corresponent : $z^{*}(LKP)\leq 2\times z^{*}(KP)$

Variables enteres modifica

En el problema de la motxilla en variables senceres, es considera que es té diversos exemplars de cada objecte. El problema consisteix a trobar el nombre d'exemplars que s'ha d'agafar de cadascun.

Si el nombre d'exemplars és limitat, es parla d'un problema de la motxilla acotat (bounded) (BKP), en cas contrari es parla d'un problema no acotat (unbounded) (UKP). El problema BKP es pot transformar en 01KP sense dificultat.

El problema de la motxilla multidimensional modifica

Aquí es considera que la motxilla té d dimensions, amb d > 0 (d-KP). Per exemple, ens podem imaginar una capsa. Cada objecte té tres dimensions, i no ens podem excedir en cap de les dimensions. La restricció (1) és substituïda per:

$\sum _{i=1}^{n}x_{i}w_{i}^{k}\leq W^{k},\forall k\in \{1,\dots ,d\}$

Utilització pràctica modifica

A la pràctica, la versió multidimensional es pot utilitzar per modelitzar i resoldre el problema d'omplir un container amb un volum i càrrega màxima limitats.

Un altre exemple és el de la gestió de personal. En una versió simplificada, s'estima la productivitat o la competència de cada persona (el seu « pes » dins el problema), i se li atribueixen d'altres variables: el seu cost i la seva disponibilitat. Cadascun d'aquests paràmetres representa una dimensió de la motxilla. Finalment es defineixen les restriccions lligades al seu projecte segons els paràmetres precedents: el pressupost disponible i el temps impartit per a realitzar el treball. La resolució permet determinar quines persones s'han de mantenir per a realitzar el projecte.

El problema de la motxilla multi-objectiu modifica

Una variant del problema consisteix, a partir d'objectes que tenen diversos valors, maximitzar diverses funcions objectiu, és el problema de la motxilla multi-objectiu (MOKP). Ens endinsem dins del domini de l'optimització multi-objectiu.

Per exemple, suposem que es posa en marxa una empresa especialitzada en creuers. Per donar-vos a conèixer decidiu convidar a gent famosa a bord del vostre vaixell més luxós. Aquest vaixell no pot aguantar més d'una tona de passatgers (aquesta serà la constant W). Cada passatger té una massa (w_i), proporciona publicitat a l'empresa deguda a la seva popularitat (p_i¹ : índex de popularitat) i us demana un salari (p_i² : salari negatiu). Evidentment es vol maximitzar la publicitat aportada i minimitzar el salari total que s'ha de pagar (maximitzar el salari negatiu). A més a més es vol tenir el màxim de gent en el vaixell (p_i³ = 1). Per tant hi ha tres variables que s'han de maximitzar.

En termes matemàtics, cal cercar el vector X de gent famosa que satisfaci el problema:

max $z^{1}(X)=\sum _{i=1}^{n}x_{i}p_{i}^{1}$ : es vol una popularitat màxima ;
max $z^{2}(X)=\sum _{i=1}^{n}x_{i}p_{i}^{2}$ : minimitzar el salari a pagar (maximitzar el salari negatiu) ;
max $z^{3}(X)=\sum _{i=1}^{n}x_{i}p_{i}^{3}$ : i tenir un màxim de gent al vaixell

Amb les restriccions

$\sum _{i=1}^{n}x_{i}w_{i}\leq W$ : el vaixell no es pot enfonsar.

D'una maniera general, se substitueix la funció objectiu del problema inicial per una familia de funcions objectius:

max $z^{j}(X)=\sum _{i=1}^{n}x_{i}p_{i}^{j},\forall j\in \{1,\dots ,m\}$

El problema de la motxilla quadràtic modifica

El problema de la motxilla quadràtic es denota QKP. Aquí es té un guany suplementari $g_{ij}$ quan dos objectes (i i j) s'agafen simultàniament. Per exemple, suposem que es desitja maximitzar la qualitat del vostre cafè a partir d'una comanda amb una motxilla. És obvi que és més interessant aportar una cullera i sucre que simplement una de les dues coses.

La funció objectiu s'escriu llavors:

max $z(X)=\sum _{i=1}^{n}x_{i}p_{i}+\sum _{i=1}^{n}\sum _{j=1}^{n}x_{i}x_{j}g_{ij}$

Problema de la suma de subconjunts o del subset sum modifica

La particularitat del problema de la suma de subconjunts (en anglès : subset sum) és que el valor i el pes dels objectes són idèntics ( $p_{i}=w_{i}$ ). És un problema important dins del camp de la criptografia, utilitzat en diversos sistemes de generació de clau pública.

Problema de la motxilla de tria múltiple modifica

En el p roblema de la motxilla de tria múltiple (MCKP), els objectes es reagrupen en classes, i simplement s'ha d'agafar un sol representant de cada classe.

Per exemple, si es vol dissenyar una caixa d'eines. Si hi ha cinc claus angleses es pot triar, o bé la menys pesada per tal de poder agafar un martell bo que és pesat, o triar la clau més versàtil i un martell de gamma baixa (poc pesat). La idea general és que no es pot agafar més d'una clau ni més d'un martell.

Si els objectes estan classificats en k classes, es denota $N_{j},j\in \{1,\dots ,k\}$ el conjunt dels índexs dels objectes que pertanyen a la classe j. Es considera que un objecte només pertany a una classe. La formulació del problema és:

max $z(X)=\sum _{j=1}^{k}\sum _{i\in N_{j}}x_{i}^{j}p_{i}^{j}$

amb les restriccions:

$\sum _{j=1}^{k}\sum _{i\in N_{j}}x_{i}^{j}w_{i}^{j}\leq W$ : no es pot superar la capacitat del sac;
$\sum _{i\in N_{j}}x_{i}^{j}\leq 1,\forall j\in \{1,\dots ,k\}$ : s'escull com a màxim un representant de cada classe.

Problema de la motxilla múltiple modifica

El problema de la motxilla múltiple (MKP) consisteix a repartir un conjunt d'objectes en diverses motxilles de capacitats diferents. El valor d'un objecte depèn ara de la motxilla en què s'ha col·locat. Per exemple, es pot considerar que un euro té més valor en un compte a termini fix que en un compte corrent.

Si es tenen k motxilles, es denota $x_{i}^{j}=1$ si l'objecte i està col·locat en la motxilla j. La formulació del problema és:

max $z(X)=\sum _{j=1}^{k}\sum _{i=1}^{n}x_{i}^{j}p_{i}^{j}$

amb les restriccions

$\sum _{i=1}^{n}x_{i}^{j}w_{i}\leq W^{j},\forall j\in \{1,\dots ,k\}$ : no se supera la capacitat de les motxilles;
$\sum _{j=1}^{k}x_{i}^{j}\leq 1,\forall i\in \{1,\dots ,n\}$ : un objecte només es posa en una sola motxilla.

Existeix una variant d'aquest problema en el que totes les motxilles tenen la mateixa capacitat, aquest problema es denota com MKP-I.

Vegeu també modifica

Bibliografia modifica

Hans Kellerer, Ulright Pferschy et David Pisinger, Knapsack Problems, Springer, 2004 (anglès) ISBN 3-540-40286-1

Referències modifica

↑ (anglès) G.B. Mathews, On the partition of numbers, Proceedings of the London Mathematical Society, 28:486-490, 1897.
↑ (anglès) Public Key Cryptography Arxivat 2006-04-28 a Wayback Machine., a la part d'Història d'un projecte de Eric Robert's Sophomore College class "The Intellectual Excitement of Computer Science" a la Universitat de Stanford. La publicació corresponent és: R.C. Merkle et M.E. Hellman, "Hiding Information and Receipts in Trap Door Knapsacks", Internal Symposium on Information Theory, Cornell University, Ithaca, New York, October 1977.
↑ (anglès) A. Shamir, A Polynomial-Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem, IEEE Transactions on Information Theory, Vol. IT-30, pp. 699-704, 1984. (Première publication en avril 1982.)
↑ (anglès) Knapsack Encryption Scheme Broken Arxivat 2007-11-22 a Wayback Machine., « Math Matrix », Département de mathématiques de l'Ohio State University, printemps 1985, Vol. 1, No. 3.
↑ (anglès) S. Vaudenay, Cryptanalysis of the Chor-Rivest Cryptosystem Arxivat 2006-06-30 a Wayback Machine..
↑ (anglès) Michail G. Lagoudakis, The 0-1 Knapsack Problem - An Introductory Survey Arxivat 2008-12-03 a Wayback Machine., 1996.
↑ ^{[enllaç sense format]} http://www710.univ-lyon1.fr/~csolnon/publications/TSI2006.pdf
↑ (anglès) R. S. Garfinkel et G. L. Nemhauser. Integer Pogramming. John Wiley & Sons, New York, 1972. ISBN 0-471-29195-1
↑ ^9,0 ^9,1 (anglès) Silvano Martello et Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons, 1990 ISBN 0471924202
↑ (anglès) Plateau, Gérard; Elkihel, Moussa. A hybrid method for the 0-1 knapsack problem. Methods Oper. Res. 49, 277-293, 1985.

[1] (anglès) G.B. Mathews, On the partition of numbers, Proceedings of the London Mathematical Society, 28:486-490, 1897.

[2] (anglès) Public Key Cryptography Arxivat 2006-04-28 a Wayback Machine., a la part d'Història d'un projecte de Eric Robert's Sophomore College class "The Intellectual Excitement of Computer Science" a la Universitat de Stanford. La publicació corresponent és: R.C. Merkle et M.E. Hellman, "Hiding Information and Receipts in Trap Door Knapsacks", Internal Symposium on Information Theory, Cornell University, Ithaca, New York, October 1977.

[3] (anglès) A. Shamir, A Polynomial-Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem, IEEE Transactions on Information Theory, Vol. IT-30, pp. 699-704, 1984. (Première publication en avril 1982.)

[4] (anglès) Knapsack Encryption Scheme Broken Arxivat 2007-11-22 a Wayback Machine., « Math Matrix », Département de mathématiques de l'Ohio State University, printemps 1985, Vol. 1, No. 3.

[5] (anglès) S. Vaudenay, Cryptanalysis of the Chor-Rivest Cryptosystem Arxivat 2006-06-30 a Wayback Machine..

[6] (anglès) Michail G. Lagoudakis, The 0-1 Knapsack Problem - An Introductory Survey Arxivat 2008-12-03 a Wayback Machine., 1996.

[7] {[enllaç sense format]} http://www710.univ-lyon1.fr/~csolnon/publications/TSI2006.pdf

[8] (anglès) R. S. Garfinkel et G. L. Nemhauser. Integer Pogramming. John Wiley & Sons, New York, 1972. ISBN 0-471-29195-1

[martello_toth_90-9] 9,0 ^9,1 (anglès) Silvano Martello et Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons, 1990 ISBN 0471924202

[10] (anglès) Plateau, Gérard; Elkihel, Moussa. A hybrid method for the 0-1 knapsack problem. Methods Oper. Res. 49, 277-293, 1985.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]