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:
-
Silvano Martello, Paolo Toth,
MKP: 0-1 multiple knapsack problem,
ACM Transactions on Mathematical Software,
Volume 11, Number 2, June 1985, pages 135-140.
-
Silvano Martello, Paolo Toth,
Knapsack Problems: Algorithms and Computer Implementations,
Wiley, 1990,
ISBN: 0-471-92420-2,
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 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.
Last revised on 06 December 2009.