DISCRETE LINEAR OPTIMIZATION

Routines

Solution of Knapsack Problems
      A Knapsack solution, with bounds ................................................... KNAP_SACK

Usage Notes

Get these two pieces of code!

Compile these in the order shown. This order is important since Fortran modules are used. Missing routines and modules are found in the IMSL Fortran 90 MP Library product.

Solving Knapsack Problems

The routine KNAP_SACK solves the optimization problem:

maximize
subject to the constraint
and the integer constraints

If the xj = 0 or 1, use boundsj = 1. The input to the routine is the data aj , cj , j=1,...,n and b. If there are bounds on any variables then all variables must have a positive upper bound. If no upper bound is required for an individual xj , set boundsj = huge(1), the Fortran 90 elemental function for the largest default type integer . If upper bounds are not required as part of the problem statement, no bound information needs to be input. This is explained below with the optional argument X_BOUNDS(:). The routine checks that the data are consistent in the sense: aj > 0, cj > 0, boundsj > 0, j = 1,...,n.

KNAP_SACK

Solve a knapsack problem. The value of the integer n is the size of the assumed-shape arrays A(:), C(:), X_BEST(:) and optionally X_BOUNDS(:).

Usage

CALL KNAP_SACK(DEPTH, A, B, C, X_BEST, BEST_VALUE, X_BOUNDS)

Required Arguments

DEPTH (Input/Output)
This is an INTEGER. Its value controls the recursion or probe depth of the branch-and-bound algorithm used to compute a solution. If the value is non-positive then no recursion depth limit is imposed.
A(:) (Input/Output)
This is a DOUBLE PRECISION type, assumed-shape array of rank-1. The data values are not changed in the routine but they are moved and then moved back to their original order. The coefficients of the constraint equation are in this array: A(j) aj , j = 1,...,n.
B (Input)
This is a DOUBLE PRECISION scalar. It is the upper bound value for the single inequality constraint of the problem.
C(:) (Input/Output)
This is a DOUBLE PRECISION type, assumed-shape array of rank-1. The data values are not changed in the routine but they are moved and then moved back to their original order. The coefficients of the linear objective function are in this array: C(j) cj , j = 1,...n.
X_BEST(:) (Output)
This is a DOUBLE PRECISION type, assumed-shape array of rank-1. These are the solution values: X_BEST(j) xj , j = 1,...,n.
BEST_VALUE (Output)
This is a DOUBLE PRECISION scalar. It is the value of the objective function for the solution given by X_BEST(:).

Optional Argument

X_BOUNDS(:) (Input)
This is an INTEGER type, assumed-shape array of rank-1. If this argument is present then bounds for each variable must be given. The entries of this array are the respective upper bounds: X_BOUNDS(j) boundsj , j = 1,...,n. Each upper bound must be positive. If this argument is not present then internally boundsj =huge(1), j = 1,...,n.

Algorithm

Subroutine KNAP_SACK implements a branch-and-bound method for solving the knapsack problem. This is given in the book Linear Programming, (1983), Vi?ek Chvátal, W. H. Freeman, Inc., New York, NY, page 206, inset Box 13.1. We have added the additional feature of bounding each component of the solution to the algorithm. The pruning of solutions is accomplished after first sorting the efficiency ratios: . The new order implied by the sort is obtained as a product of cyclic interchanges. Both arrays A(:) and C(:) are moved to this internal order and then moved back again, just before the routine exits. The array X_BEST(:) is moved to correspond with the input order of A(:) and C(:). The IMSL MP Library routine SORT_REAL returns the cyclic interchanges. This complication is normally hidden from the user of KNAP_SACK but we mention it so that the user is not tempted to do sorting in their own program.

Chvátal's algorithm is recursive. Our implementation uses a feature of Fortran 90, the recursive subroutine. Since uncontrolled recursion is dangerous (perhaps causing the program to abort), we have included the parameter DEPTH, which limits the number of recursive or backtracking probes. We do not know how to choose DEPTH as a function of a particular data set. Our observation, based on a small amount of experience, is that this algorithm makes excellent maximizing progress early on and rarely finds a new best solution thereafter.

Example

The program unit KNAPSACK_ILLUSTRATOR in "knapex.f90" solves three small knapsack problems. The coefficients and solution are listed with the IMSL MP Library generic array printing subroutine SHOW found in the IMSL MP Library version 3. The first two problems allow only two values 0-1 for the solution. Thus the upper bounds are included as an optional argument, each with the value 1. The third problem has no prior bound on any component, so we do not use the optional argument for the bounds.