## PYAsUKP## Vincent Poirriez |

PYAsUKP: Yet Another solver for the Unbounded Knapsack Problem.

Join work of Poirriez,V (UVHC/LAMIH UMR CNRS 8530 France), Yanev,N (University of SOFIA, Bulgaria), Andonov,R (IRISA France)

PYAsUKP implements the EDUK2 algorithm distinguished by Kellerer et all. as the best known algorithm to solve the Unbounded Knapsack Problem in their 2005 book* Knapsack Problems.*

EDUK2 is described in: Vincent Poirriez, Nicola Yanev, Rumen Andonov: *A Hybrid Algorithm for the Unbounded Knapsack Problem*, Discrete Optimization,
Volume 6, Issue 1, February 2009, Pages 110-124. Available online:
DOI.

Here is the abstract of this publication:

this paper presents a new approach for exactly solving the Unbounded Knapsack Problem (UKP) and proposes a new bound that was proved to dominate the previous bounds on a special class of UKP instances. Integrating bounds within the framework of sparse dynamic programming led to the creation of an efficient and robust hybrid algorithm, called EDUK2. This algorithm takes advantage of the majority of the known properties of UKP, particularly the diverse dominance relations and the important periodicity property. Extensive computational results show that, in all but a very few cases, EDUK2 significantly outperforms both MTU2 and EDUK, the currently available UKP solvers, as well the well-known general purpose mathematical programming optimizer CPLEX of ILOG. These experimental results demonstrate that the class of hard UKP instances needs to be redefined, and the authors offer their insights into the creation of such instances.

`pyasukp` also implements a data set generator (see the option -form below).

Quite a lot of options are available, a short list is

-nobbto use a pure dynamic programing algorithm (roughly speaking the EDUK algorithm published in 2000 in EDUK paper).-form[s|c|w|u|saw|rh|hd]to generate UKP instances

suses the strong-correlated formulap_{i}=aw_{i}+bcw_{i}=w_{min}+ip_{i}=w_{i}+stepthe stpe is defined by the option-stepwweakly correlated formula:p_{i}is chosen randomly in the intervall [aw_{i}−b..aw_{i}+b]unot correlated without any simply dominated itemsrhp_{i}=i+w_{i}hdp_{i}=max(1 +p_{i−1};floor((w_{i}×p_{i1})/w_{i−1})) forula (6) in EDUK papersawto genarate a saw ukp (see the Listing 2 in DOI.)-wmin-wmax-pmin-pmax-capto define respectively the minimum[maximum] weight and profit and the knapsack capacity-nosolveto only generate data together with-saveto specify the named file-seed nto give the seednto the random generator

Dernière mise à jour: , . Me contacter

Ce document a été traduit de L^{A}T_{E}X parH^{E}V^{E}A