A branch and bound algorithm for solving the multiple-choice knapsack problem

The multiple-choice knapsack problem is a binary knapsack problem with the addition of disjoint multiple-choice constraints. We describe a branch and bound algorithm based on embedding Glover and Klingman's method for the associated linear program within a depth-first search procedure. A heuristic is used to find a starting dual feasible solution to the associated linear program and a ‘pegging’ test is employed to reduce the size of the problem for the enumeration phase. Computational experience and comparisons with the code of Nauss and an algorithm of Armstrong et al. for the same problem are reported.     

The static stochastic knapsack problem with normally distributed item sizes

This paper develops exact and heuristic algorithms for a stochastic knapsack problem where items with random sizes may be assigned to a knapsack. An item’s value is given by the realization of the product of a random unit revenue and the random item size. When the realization of the sum of selected item sizes exceeds the knapsack capacity, a penalty cost is incurred for each unit of overflow, while our model allows for a salvage value for each unit of capacity that remains unused. We seek to maximize the expected net profit resulting from the assignment of items to the knapsack. Although the capacity is fixed in our core model, we show that problems with random capacity, as well as problems in which capacity is a decision variable subject to unit costs, fall within this class of problems as well. We focus on the case where item sizes are independent and normally distributed random variables, and provide an exact solution method for a continuous relaxation of the problem. We show that an optimal solution to this relaxation exists containing no more than two fractionally selected items, and develop a customized branch-and-bound algorithm for obtaining an optimal binary solution. In addition, we present an efficient heuristic solution method based on our algorithm for solving the relaxation and empirically show that it provides high-quality solutions.     

An Algorithm for the 0-1 Equality Knapsack Problem

The 0-1 knapsack problem is a linear integer-programming problem with a single constraint and binary variables. The knapsack problem with an inequality constraint has been widely studied, and several efficient algorithms have been published. We consider the equality-constraint knapsack problem, which has received relatively little attention. We describe a branch-and-bound algorithm for this problem, and present computational experience with up to 10,000 variables. An important feature of this algorithm is a least-lower-bound discipline for candidate problem selection.     

Approximate and exact algorithms for the fixed-charge knapsack problem

The subject of this paper is the formulation and solution of a variation of the classical binary knapsack problem. The variation that is addressed is termed the “fixed-charge knapsack problem”, in which sub-sets of variables (activities) are associated with fixed costs. These costs may represent certain set-ups and/or preparations required for the associated sub-set of activities to be scheduled. Several potential real-world applications as well as problem extensions/generalizations are discussed. The efficient solution of the problem is facilitated by a standard branch-and-bound algorithm based on (1) a non-iterative, polynomial algorithm to solve the LP relaxation, (2) various heuristic procedures to obtain good candidate solutions by adjusting the LP solution, and (3) powerful rules to peg the variables. Computational experience shows that the suggested branch-and-bound algorithm shows excellent potential in the solution of a wide variety of large fixed-charge knapsack problems.     

Shortest path algorithms for knapsack type problems

The group knapsack and knapsack problems are generalised to shortest path problems in a class of graphs called knapsack graphs. An efficient algorithm is described for finding shortest paths provided that arc lengths are non-negative. A more efficient algorithm is described for the acyclic case which includes the knapsack problem. In this latter case the algorithm reduces to a known algorithm.     

Exact methods for the knapsack problem and its generalizations

A unified approach and a summary of the most important results concerned with exact methods for solving the (binary) knapsack problem and its generalizations are given. We stress the importance of dual methods for solving linear programming relaxations of the considered problems. Two ways of generalization of the knapsack problem are described. If the special ordered sets are added, then the multiple-choice knapsack problem is obtained. If the constraints have the nested structure, then we get the nested knapsack problem. Also the multiple-choice nested knapsack problem is discussed.     

Extending Dantzig's bound to the bounded multiple-class binary Knapsack problem

 The bounded multiple-class binary knapsack problem is a variant of the knapsack problem where the items are partitioned into classes and the item weights in each class are a multiple of a class weight. Thus, each item has an associated multiplicity. The constraints consists of an upper bound on the total item weight that can be selected and upper bounds on the total multiplicity of items that can be selected in each class. The objective is to maximize the sum of the profits associated with the selected items. This problem arises as a sub-problem in a column generation approach to the cutting stock problem. A special case of this model, where item profits are restricted to be multiples of a class profit, corresponds to the problem obtained by transforming an integer knapsack problem into a 0-1 form. However, the transformation proposed here does not involve a duplication of solutions as the standard transformation typically does. The paper shows that the LP-relaxation of this model can be solved by a greedy algorithm in linear time, a result that extends those of Dantzig (1957) and Balas and Zemel (1980) for the 0-1 knapsack problem. Hence, one can derive exact algorithms for the multi-class binary knapsack problem by adapting existing algorithms for the 0-1 knapsack problem. Computational results are reported that compare solving a bounded integer knapsack problem by transforming it into a standard binary knapsack problem versus using the multiple-class model as a 0-1 form. Received: May 1998 / Accepted: February 2002-09-04 Published online: December 9, 2002 Key Words. Knapsack problem – integer programming – linear programming relaxation     

An exact algorithm for the fixed-charge multiple knapsack problem

We formulate the fixed-charge multiple knapsack problem (FCMKP) as an extension of the multiple knapsack problem (MKP). The Lagrangian relaxation problem is easily solved, and together with a greedy heuristic we obtain a pair of upper and lower bounds quickly. We make use of these bounds in the pegging test to reduce the problem size. We also present a branch-and-bound (B&B) algorithm to solve FCMKP to optimality. This algorithm exploits the Lagrangian upper bound as well as the pegging result for pruning, and at each terminal subproblem solve MKP exactly by invoking MULKNAP code developed by Pisinger [Pisinger, D., 1999. An exact algorithm for large multiple knapsack problems. European Journal of Operational Research 114, 528–541]. As a result, we are able to solve almost all test problems with up to 32,000 items and 50 knapsacks within a few seconds on an ordinary computing environment, although the algorithm remains some weakness for small instances with relatively many knapsacks.     

Finding all nondominated points of multi-objective integer programs

We develop exact algorithms for multi-objective integer programming (MIP) problems. The algorithms iteratively generate nondominated points and exclude the regions that are dominated by the previously-generated nondominated points. One algorithm generates new points by solving models with additional binary variables and constraints. The other algorithm employs a search procedure and solves a number of models to find the next point avoiding any additional binary variables. Both algorithms guarantee to find all nondominated points for any MIP problem. We test the performance of the algorithms on randomly-generated instances of the multi-objective knapsack, multi-objective shortest path and multi-objective spanning tree problems. The computational results show that the algorithms work well.     

Knapsack problems with setups

Knapsack problems with setups find their application in many concrete industrial and financial problems. Moreover, they also arise as subproblems in a Dantzig–Wolfe decomposition approach to more complex combinatorial optimization problems, where they need to be solved repeatedly and therefore efficiently. Here, we consider the multiple-class integer knapsack problem with setups. Items are partitioned into classes whose use implies a setup cost and associated capacity consumption. Item weights are assumed to be a multiple of their class weight. The total weight of selected items and setups is bounded. The objective is to maximize the difference between the profits of selected items and the fixed costs incurred for setting-up classes. A special case is the bounded integer knapsack problem with setups where each class holds a single item and its continuous version where a fraction of an item can be selected while incurring a full setup. The paper shows the extent to which classical results for the knapsack problem can be generalized to these variants with setups. In particular, an extension of the branch-and-bound algorithm of Horowitz and Sahni is developed for problems with positive setup costs. Our direct approach is compared experimentally with the approach proposed in the literature consisting in converting the problem into a multiple choice knapsack with pseudo-polynomial size.     

Description of 2-integer continuous knapsack polyhedra

In this paper we discuss the polyhedral structure of several mixed integer sets involving two integer variables. We show that the number of the corresponding facet-defining inequalities is polynomial on the size of the input data and their coefficients can also be computed in polynomial time using a known algorithm [D. Hirschberg, C. Wong, A polynomial-time algorithm for the knapsack problem with two variables, Journal of the Association for Computing Machinery 23 (1) (1976) 147–154] for the two integer knapsack problem. These mixed integer sets may arise as substructures of more complex mixed integer sets that model the feasible solutions of real application problems.     

Solving the bi-objective multi-dimensional knapsack problem exploiting the concept of core

This paper deals with the bi-objective multi-dimensional knapsack problem. We propose the adaptation of the core concept that is effectively used in single-objective multi-dimensional knapsack problems. The main idea of the core concept is based on the “divide and conquer” principle. Namely, instead of solving one problem with n variables we solve several sub-problems with a fraction of n variables (core variables). The quality of the obtained solution can be adjusted according to the size of the core and there is always a trade off between the solution time and the quality of solution. In the specific study we define the core problem for the multi-objective multi-dimensional knapsack problem. After defining the core we solve the bi-objective integer programming that comprises only the core variables using the Multicriteria Branch and Bound algorithm that can generate the complete Pareto set in small and medium size multi-objective integer programming problems. A small example is used to illustrate the method while computational and economy issues are also discussed. Computational experiments are also presented using available or appropriately modified benchmarks in order to examine the quality of Pareto set approximation with respect to the solution time. Extensions to the general multi-objective case as well as to the computation of the exact solution are also mentioned.     

Convergent Lagrangian and domain cut method for nonlinear knapsack problems

The nonlinear knapsack problem, which has been widely studied in the OR literature, is a bounded nonlinear integer programming problem that maximizes a separable nondecreasing function subject to separable nondecreasing constraints. In this paper we develop a convergent Lagrangian and domain cut method for solving this kind of problems. The proposed method exploits the special structure of the problem by Lagrangian decomposition and dual search. The domain cut is used to eliminate the duality gap and thus to guarantee the finding of an optimal exact solution to the primal problem. The algorithm is first motivated and developed for singly constrained nonlinear knapsack problems and is then extended to multiply constrained nonlinear knapsack problems. Computational results are presented for a variety of medium- or large-size nonlinear knapsack problems. Comparison results with other existing methods are also reported.     

A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem

This paper presents an efficient solution algorithm for the multiconstraint zero-one knapsack problem through a branch and bound search process. The algorithm has been coded in FORTRAN; and a group of thirty 5-constraint knapsack problems with 30-90 variables were run on IBM 360/75 using two other codes as well, in order to compare the computational efficiency of the proposed method with that of the original Balas and an improved Balas additive algorithms. The computational results show that the proposed method is markedly faster with regard to the total as well as the individual solution times for these test problems, and such superiority becomes more evident as the number of variables and the difficulty of the problems increase. The results also indicated that the original Balas method is extremely inefficient for the type of problems being considered here. The total solution time for the thirty problems is 13 min for the proposed method, 109 min for the improved Balas algorithm, and over 380 min for the original Balas algorithm. Extension of the solution algorithm to the generalized knapsack problem is also suggested.     

Budgeting with bounded multiple-choice constraints

We consider a budgeting problem where a specified number of projects from some disjoint classes has to be selected such that the overall gain is largest possible, and such that the costs of the chosen projects do not exceed a fixed upper limit. The problem has several application in government budgeting, planning, and as relaxation from other combinatorial problems. It is demonstrated that the problem can be transformed to an equivalent multiple-choice knapsack problem through dynamic programming. A naive transformation however leads to a drastic increase in the number of variables, thus we propose an algorithm for the continuous problem based on Dantzig–Wolfe decomposition. A master problem solves a continuous multiple-choice knapsack problem knowing only some extreme points in each of the transformed classes. The individual subproblems find extreme points for each given direction, using a median search algorithm. An integer optimal solution is then derived by using the dynamic programming transformation to a multiple-choice knapsack problem for an expanding core. The individual classes are considered in an order given by their gradients, and the transformation to a multiple-choice knapsack problem is performed when needed. In this way, only a dozen of classes need to be transformed for standard instances from the literature. Computational experiments are presented, showing that the developed algorithm is orders of magnitude faster than a general LP/MIP algorithm.     

Binary knapsack problems with random budgets

The binary knapsack problem is a combinatorial optimization problem in which a subset of a given set of elements needs to be chosen in order to maximize profit, given a budget constraint. In this paper, we study a stochastic version of the problem in which the budget is random. We propose two different formulations of this problem, based on different ways of handling infeasibility, and propose an exact algorithm and a local search-based heuristic to solve the problems represented by these formulations. We also present the results from some computational experiments.     

Exact and heuristic solution approaches for the mixed integer setup knapsack problem

We consider a class of knapsack problems that include setup costs for families of items. An individual item can be loaded into the knapsack only if a setup cost is incurred for the family to which it belongs. A mixed integer programming formulation for the problem is provided along with exact and heuristic solution methods. The exact algorithm uses cross decomposition. The proposed heuristic gives fast and tight bounds. In addition, a Benders decomposition algorithm is presented to solve the continuous relaxation of the problem. This method for solving the continuous relaxation can be used to improve the performance of a branch and bound algorithm for solving the integer problem. Computational performance of the algorithms are reported and compared to CPLEX.     

Particle swarm optimization with time-varying acceleration coefficients for the multidimensional knapsack problem

The multidimensional knapsack problem (MKP) is a difficult combinatorial optimization problem, which has been proven as NP-hard problems. Various population-based search algorithms are applied to solve these problems. The particle swarm optimization (PSO) technique is adapted in our study, which proposes two novel PSO algorithms, namely, the binary PSO with time-varying acceleration coefficients (BPSOTVAC) and the chaotic binary PSO with time-varying acceleration coefficients (CBPSOTVAC). The two proposed methods were tested using 116 benchmark problems from the OR-Library to validate and demonstrate the efficiency of these algorithms in solving multidimensional knapsack problems. The results were then compared with those in the other two existing PSO algorithms. The simulation and evaluation results showed that the proposed algorithms, BPSOTVAC and CBPSOTVAC, are superior over the other methods according to its success rate, mean absolute deviation, mean absolute percentage error, least error, and standard deviation.     

A new upper bound for unconstrained two-dimensional cutting and packing

A new upper bound for the unconstrained two-dimensional cutting or packing problem is proposed in this paper. The proposed upper bound can be calculated for any size of plate by solving just two knapsack problems at the beginning of the algorithm. In this research, the proposed upper bound was applied to the well known exact cutting algorithm, although it can be used for both cutting and packing applications. The experimental results demonstrate that the new upper bound is very efficient, and reduces the search time required to find an optimal solution.     

An objective hyperplane search procedure for solving the general all-integer linear programming (ILP) problem

We describe an objective hyperplane search method for solving a class of integer linear programming (ILP) problems. We formulate the search as a bounded knapsack problem and develop requisite theory for formulating knapsack problems with composite constraints and composite objective functions that facilitate convergence to an ILP solution. A heuristic solution algorithm was developed and used to solve a variety of test problems found in the literature. The method obtains optimal or near-optimal solutions in acceptable ranges of computational effort.