KNAPSACK
Algorithms for Knapsack Problems
KNAPSACK
is a FORTRAN77 library which
contains implementations of algorithms for a variety of knapsack problems,
by Silvano Martelo and Paolo Toth.
Code  Problem  Type 
MT1  01 Knapsack  Exact 
MT1R  01 Knapsack  Exact (real data) 
MT2  01 Knapsack  Exact/Approximate 
MTB2  Bounded Knapsack  Exact/Approximate 
MTU2  Unbounded Knapsack  Exact/Approximate 
MTSL  Subset Sum  Exact/Approximate 
MTC2  Change Making  Exact/Approximate 
MTCB  Bounded Change Making  Exact/Approximate 
MTM  01 Multiple Knapsack  Exact/Approximate 
MTHM  01 Multiple Knapsack  Approximate 
MTG  Generalized Assignment  Exact/Approximate 
MTHG  Generalized Assignment  Approximate 
MTP  Bin Packing  Exact/Approximate 
Languages:
KNAPSACK is available in
a FORTRAN77 version.
Related Data and Programs:
BIN_PACKING,
a dataset directory which
contains examples of the bin packing problem, in which a number of
objects are to be packed in the minimum possible number of uniform bins;
CHANGE_MAKING,
a dataset directory which
contains test data for the change making problem;
COMBO,
a FORTRAN90 library which
includes many combinatorial routines.
GENERALIZED_ASSIGNMENT,
a dataset directory which
contains test data for the generalized assignment problem;
KNAPSACK_01,
a FORTRAN77 library which
uses brute force to solve small versions of the 0/1 knapsack problem;
KNAPSACK_01,
a dataset directory which
contains test data for the 0/1 knapsack problem;
KNAPSACK_MULTIPLE,
a dataset directory which
contains test data for the multiple knapsack problem;
LAMP,
a FORTRAN77 library which
solves linear assignment and matching problems.
LAU_NP,
a FORTRAN90 library which
implements heuristic algorithms for various NPhard combinatorial problems.
PARTITION_PROBLEM,
a FORTRAN77 library which
seeks solutions of the partition problem, splitting a set of integers into
two subsets with equal sum.
SUBSET,
a FORTRAN77 library which
enumerates combinations, partitions, subsets, index sets,
and other combinatorial objects.
SUBSET_SUM,
a FORTRAN77 library which
seeks solutions of the subset sum problem.
SUBSET_SUM,
a dataset directory which
contains examples of the subset sum problem, in which a set of numbers is
given, and is desired to find at least one subset that sums to a given
target value.
TOMS632,
a FORTRAN77 library which
solves the multiple knapsack problem,
by Silvano Martello and Paolo Toth.
This is ACM TOMS algorithm 632.
Author:
Silvano Martello, Paolo Toth.
Reference:

Silvano Martello, Paolo Toth,
MKP: 01 multiple knapsack problem,
ACM Transactions on Mathematical Software,
Volume 11, Number 2, June 1985, pages 135140.

Silvano Martello, Paolo Toth,
Knapsack Problems: Algorithms and Computer Implementations,
Wiley, 1990,
ISBN: 0471924202,
LC: QA267.7.M37.
Source Code:
Examples and Tests:
List of Routines:

BLD explicitly determines set a  a1 or set a  a1  a2 when lev .gt. 1 .

BLDF explicitly determines set a1 or set a  a1 or set a  a1  a2 when lev .eq. 1 .

BLDSR1 explicitly determines set a1 when lev .gt. 1 .

CHMT1 checks the input data.

CHMT1R checks the input data.

CHMT2 checks the input data.

CHMTB2 checks the input data.

CHMTC2 checks the input data.

CHMTCB checks the input data.

CHMTG checks the input data.

CHMTHG checks the input data.

CHMTHM checks the input data.

CHMTM checks the input data.

CHMTP checks the input data.

CHMTSL checks the input data.

CHMTU2 checks the input data.

CMPB solves a bounded changemaking problem through the branchandbound algorithm.

CORE determines the core problem.

COREC determines the core problem.

CORES determines the core problem.

DEFPCK ?

DETNS1 computes the cardinality of set A1.

DETNS2 computes the cardinality of set A2.

DINSM determines the dynamic programming lists.

DMIND defines array MIND to contain the pointers to the sorted items

ENUMER performs a branchandbound search.

FEAS checks for infeasibility.

FFDLS performs a firstfit decreasing heuristic and initializes LS and LSB.

FIXRED fixes the variables after a local reduction.

FMED computes median of the ratios of the first 2 and the last item.

FORWRD performs statements 19.

GHA applies the approximate algorithm gh with function (a).

GHBCD applies the approximate algorithm gh with functions (b), (c) and (d).

GHX applies the approximate algorithm gh with function (b) or (c) or (d).

GR1 reduces a maximization gap.

GR2 reduces a maximization gap.

HBFDS performs a bestfit decreasing heuristic.

HEUR determines the best initial heuristic solution.

IMPR1: first improvement.

IMPR2: second improvement.

INSERT inserts item i in bin m and updates fs, x, ifp, k.

KP01M solves, through branchandbound, a 01 single knapsack problem.

KPMAX solves a 01 single knapsack problem using an initial solution.

KPMIN solves a 01 single knapsack problem in minimization form.

KSMALL finds the kth smallest of n elements in o(n) time.

L2 computes the lower bound.

L3 reduces the current problem, and compute lower bound l3 and a new upper bound nub .

LCL2 computes a local lower bound and execute a preprocessing for reduction.

MAXT determines the three items of maximum weight.

MGR1 finds an initial solution (quick algorithm).

MGR2 finds an initial solution (accurate algorithm).

MPSORT rearranges a(i1:i2) so a(it+i11) contains the itth smallest element.

MT1 solves the 01 single knapsack problem.

MT1R solves the 01 single knapsack problem with real parameters.

MT2 solves the 01 single knapsack problem.

MTB2 solves the bounded single knapsack problem

MTC1 solves a changemaking problem through the branchandbound algorithm.

MTC2 solves the unbounded changemaking problem

MTCB solves the bounded changemaking problem

MTG solves the generalized assignment problem

MTHG heuristically solves the generalized assignment problem

MTHM heuristically solves the 01 multiple knapsack problem

MTM solves the 01 multiple knapsack problem

MTP solves the bin packing problem

MTS solves a small subset sum problem.

MTSL solves the subsetsum problem

MTU1 solves the unbounded single knapsack problem

MTU2 solves the unbounded single knapsack problem

MWFDS performs a modified worstfit decreasing heuristic.

NEWBimproves on the current upper bound iubf0 by taking into account the

PAR does a parametric computation of the upper bounds.

PEN0 computes the penalty for an item j which was assigned to no knapsack.

PEN1 computes the penalty foro an item j which was assigned more than one knapsack.

PI computes a feasible solution to the current problem.

PREPEN determines pak , kap and pakl (pointers for computing penalties)

PRESP defines the core problem.

REARR rearranges the initial solution.

REDNS reduces, without sorting, the items not in core.

REDS reduces the original problem.

REDU reduces an unbounded knapsack problem (po,wo) through dominance relations.

RESTOR restores the situation preceding the reduction of level k and update lastw .

SEARCH finds largest NL such that R < W(NL).

SIGMA computes an upper bound ub on the best final solution which

SKP1 solves a 01 single knapsack problem.

SKP2 solves the 01 single knapsack problem

SOL determines the solution vector x for the original problem.

SORT7 sorts in increasing order the elements from

SORTI sorts the integer array a by decreasing values (derived from

SORTI2 sorts the integer array a by increasing values (derived from

SORTR sorts the real array a by decreasing values (derived from subroutine

TAB builds the new dynamic programming list tdb from the current

TERMIN terminates the execution.

TIMESTAMP prints out the current YMDHMS date as a timestamp.

TRANS transforms a bounded knapsack problem (n, p, w, b) into

TRIN transforms an gap in minimization form to an equivalent instance in maximization form.

UBFJV computes the fisherjaikumarvan wassenhove upper bound.

UBRS computes the improved rosssoland upper bound.

UPDATE updates the optimal solution after a local heuristic.

UPSTAR updates the current optimal solution.

USEDIN determines, through binary search, the location loc of td

YDEF sets y(l,i,j) = ny .

YUSE sets ny = y(l,i,j) .
You can go up one level to
the FORTRAN77 source codes.
Last revised on 06 December 2009.