Games: 0-1 knapsackGiochi: zaino 0-1

The branch-and-bound of PBeFS solves the same 0-1 knapsack side by side in three settings: sequential, with the tree shared by 4 threads, and distributed over 4 threads that exchange nodes. A node fixes the first k items, in the order of profit over weight, its bound is the fractional relaxation of Dantzig and its feasible value the greedy completion; on the board, an item is a block whose height is its weight and whose colour is its profit over weight, and the items that the node evaluated takes rise onto the gold strip of the knapsack, those it leaves out sink and fade, and the bar in front fills with the weight taken. Under the board the tree grows node by node, in the colour of the worker that branches, grey where a node is pruned by its bound, with the bound of the search and the incumbent closing in on each other. The instances are random ones of the weakly correlated class of Pisinger; the traces were recorded by TraceSearch of PBeFS, and the measure to compare is the number of nodes evaluated.

Il branch-and-bound di PBeFS risolve lo stesso zaino 0-1 affiancato in tre modi: sequenziale, con l'albero condiviso da 4 thread, e distribuito su 4 thread che si scambiano i nodi. Un nodo fissa i primi k oggetti, nell'ordine di profitto su peso, il suo bound è il rilassamento frazionario di Dantzig e il suo valore ammissibile il completamento greedy; sulla tavola, un oggetto è un blocco la cui altezza è il suo peso e il cui colore è il suo profitto su peso, e gli oggetti che il nodo valutato prende salgono sulla striscia dorata dello zaino, quelli che lascia fuori si abbassano e sbiadiscono, e la barra davanti si riempie del peso preso. Sotto la tavola l'albero cresce nodo per nodo, nel colore del worker che ramifica, grigio dove un nodo è potato dal suo bound, con il bound della ricerca e l'incumbente che si avvicinano. Le istanze sono casuali, della classe debolmente correlata di Pisinger; le tracce sono state registrate da TraceSearch di PBeFS, e la misura da confrontare è il numero dei nodi valutati.