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	0-1 Knapsack	Exact
MT1R	0-1 Knapsack	Exact (real data)
MT2	0-1 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	0-1 Multiple Knapsack	Exact/Approximate
MTHM	0-1 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 NP-hard 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:

1. Silvano Martello, Paolo Toth,
   MKP: 0-1 multiple knapsack problem,
   ACM Transactions on Mathematical Software,
   Volume 11, Number 2, June 1985, pages 135-140.
2. Silvano Martello, Paolo Toth,
   Knapsack Problems: Algorithms and Computer Implementations,
   Wiley, 1990,
   ISBN: 0-471-92420-2,
   LC: QA267.7.M37.

Source Code:

• knapsack.f, the source code.
• knapsack.sh, commands to compile the source code.

Examples and Tests:

• knapsack_prb.f, a sample calling program.
• knapsack_prb.sh, commands to compile and run the sample program.
• knapsack_prb_output.txt, the output file.

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 change-making problem through the branch-and-bound 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 branch-and-bound search.
• FEAS checks for infeasibility.
• FFDLS performs a first-fit 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 1-9.
• 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 best-fit 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 branch-and-bound, a 0-1 single knapsack problem.
• KPMAX solves a 0-1 single knapsack problem using an initial solution.
• KPMIN solves a 0-1 single knapsack problem in minimization form.
• KSMALL finds the k-th 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+i1-1) contains the it-th smallest element.
• MT1 solves the 0-1 single knapsack problem.
• MT1R solves the 0-1 single knapsack problem with real parameters.
• MT2 solves the 0-1 single knapsack problem.
• MTB2 solves the bounded single knapsack problem
• MTC1 solves a change-making problem through the branch-and-bound algorithm.
• MTC2 solves the unbounded change-making problem
• MTCB solves the bounded change-making problem
• MTG solves the generalized assignment problem
• MTHG heuristically solves the generalized assignment problem
• MTHM heuristically solves the 0-1 multiple knapsack problem
• MTM solves the 0-1 multiple knapsack problem
• MTP solves the bin packing problem
• MTS solves a small subset sum problem.
• MTSL solves the subset-sum problem
• MTU1 solves the unbounded single knapsack problem
• MTU2 solves the unbounded single knapsack problem
• MWFDS performs a modified worst-fit 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 re-arranges 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 0-1 single knapsack problem.
• SKP2 solves the 0-1 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 fisher-jaikumar-van wassenhove upper bound.
• UBRS computes the improved ross-soland 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.