Sensitivity analysis to perturbations of the weight of a subset of items: The knapsack case study

In this paper, we study the sensitivity of the optimum to perturbations of the weight of a subset of items of both the knapsack problem (denoted KP) and knapsack sharing problem (denoted KSP). The sensitivity interval of the weight associated to an item is characterized by two limits, called lower and upper values, which guarantee the optimality of the solution at hand whenever the new weight’s value belongs to such an interval. For each perturbed weight, we try to establish approximate values of the sensitivity interval whenever the original problem is solved. We do it by applying a dynamic programming method where all established results require a negligible runtime. First, two cases are studied when considering an optimal solution of KP: (i) the case in which all perturbations are (non)negatives and (ii) the general case in which the set of the perturbed items is divided into two disjoint subsets (the first subset contains the nonnegative perturbations and the second one represents the subset of negative perturbations). Second, we show how we can adapt the results of KP to the KSP. All established results require a negligible runtime which grows the interest of such a study. Finally, for each of these problems, we will see the impact of the established results on an example while considering the various cases.     

An exact algorithm for the knapsack sharing problem with common items

We are concerned with a variation of the knapsack problem as well as of the knapsack sharing problem, where we are given a set of n items and a knapsack of a fixed capacity. As usual, each item is associated with its profit and weight, and the problem is to determine the subset of items to be packed into the knapsack. However, in the problem there are s players and the items are divided into s + 1 disjoint groups, N_k (k = 0, 1, … , s). The player k is concerned only with the items in N₀ ∪ N_k, where N₀ is the set of ‘common’ items, while N_k represents the set of his own items. The problem is to maximize the minimum of the profits of all the players. An algorithm is developed to solve this problem to optimality, and through a series of computational experiments, we evaluate the performance of the developed algorithm.     

Unbounded knapsack problem with controllable rates: the case of a random demand for items

This paper focuses on a dynamic, continuous-time control generalization of the unbounded knapsack problem. This generalization implies that putting items in a knapsack takes time and has a due date. Specifically, the problem is characterized by a limited production horizon and a number of item types. Given an unbounded number of copies of each type of item, the items can be put into a knapsack at a controllable production rate subject to the available capacity. The demand for items is not known until the end of the production horizon. The objective is to collect items of each type in order to minimize shortage and surplus costs with respect to the demand. We prove that this continuous-time problem can be reduced to a number of discrete-time problems. As a result, solvable cases are found and a polynomial-time algorithm is suggested to approximate the optimal solution with any desired precision.     

Cover by disjoint cliques cuts for the knapsack problem with conflicting items

The knapsack problem with conflicting items arises in several real-world applications. We propose a family of strong cutting planes and prove that a subfamily of these cuts can be facet-defining. Computational experiments show that the proposed cuts are very effective in reducing integrality gaps, providing dual bounds up to 78% tighter than formulations strengthened with traditional combinatorial cuts. We also show that it is possible to adapt a recently proposed lifting procedure to further strengthen the proposed cuts.     

Sensitivity analysis of a greedy heuristic for knapsack problems

In this paper, we carry out parametric analysis as well as a tolerance limit based sensitivity analysis of a greedy heuristic for two knapsack problems—the 0–1 knapsack problem and the subset sum problem. We carry out the parametric analysis based on all problem parameters. In the tolerance limit based approach, we use a definition of the sensitivity analysis problem that is polynomial for polynomial heuristics. One of the interesting and counterintuitive results described in this paper is that the tolerance limits obtained from the heuristic sensitivity analysis cannot be used as bounds for the tolerance limits of the sensitivity analysis of optimal solutions in most cases.     

An algorithm and efficient data structures for the binary knapsack problem

A branch-and-bound algorithm for the binary knapsack problem is presented which uses a combined stack and deque for storing the tree and the corresponding LP-relaxation. A reduction scheme is used to reduce the problem size. The algorithm was implemented in FORTRAN. Computational experience is based on 600 randomly generated test problems with up to 9000 zero-one variables. The average solution times (excluding an initial sorting step) increase linearly with problem size and compare favorably with other codes designed to solve binary knapsack problems.     

Asymptotic analysis of a perturbation problem

An asymptotic expansion is constructed for the solution of the initial-value problem

when t is restricted to the interval [0,T/ε], where T is any given number. Our analysis is mathematically rigorous; that is, we show that the difference between the true solution u(t,x;ε) and the Nth partial sum of the asymptotic series is bounded by ε^N+1 multiplied by a constant depending on T but not on x and t.     

Solving the linear multiple choice knapsack problem with two objectives: profit and equity

In this paper, we study an extension of the Linear Multiple Choice Knapsack (LMCK) Problem that considers two objectives. The problem can be used to find the optimal allocation of an available resource to a group of disjoint sets of activities, while also ensuring that a certain balance on the resource amounts allocated to the activity sets is attained. The first objective maximizes the profit incurred by the implementation of the considered activities. The second objective minimizes the maximum difference between the resource amounts allocated to any two sets of activities. We present the mathematical formulation and explore the fundamental properties of the problem. Based on these properties, we develop an efficient algorithm that obtains the entire nondominated frontier. The algorithm is more efficient than the application of the general theory of multiple objective linear programming (MOLP), although there is a close underlying relationship between the two. We present theoretical findings which provide insight into the behavior of the algorithm, and report computational results which demonstrate its efficiency for randomly generated problems. Electronic Supplementary Material  The online version of this article () contains supplementary material, which is available to authorized users.     

Sensitivity analysis for a Lagrange dual problem to a vector optimization problem

In this paper, sensitivity analysis for a Lagrange dual problem to a vector optimization problem is firstly studied. Then sensitivity analysis of the vector optimization problem is also discussed. Finally, the dual relationships between the obtained results are established.     

Resource capacity allocation to stochastic dynamic competitors: knapsack problem for perishable items and index-knapsack heuristic

In this paper we propose an approach for solving problems of optimal resource capacity allocation to a collection of stochastic dynamic competitors. In particular, we introduce the knapsack problem for perishable items, which concerns the optimal dynamic allocation of a limited knapsack to a collection of perishable or non-perishable items. We formulate the problem in the framework of Markov decision processes, we relax and decompose it, and we design a novel index-knapsack heuristic which generalizes the index rule and it is optimal in some specific instances. Such a heuristic bridges the gap between static/deterministic optimization and dynamic/stochastic optimization by stressing the connection between the classic knapsack problem and dynamic resource allocation. The performance of the proposed heuristic is evaluated in a systematic computational study, showing an exceptional near-optimality and a significant superiority over the index rule and over the benchmark earlier-deadline-first policy. Finally we extend our results to several related revenue management problems.     

A robust approach to the chance-constrained knapsack problem

In this paper, the chance-constrained knapsack problem (CKP) is addressed. Relying on robust optimization, a tractable combinatorial algorithm is proposed to solve approximately CKP. For two specific classes of uncertain knapsack problems, it is proved to solve CKP at optimality.     

A pegging approach to the precedence-constrained knapsack problem

The knapsack problem (KP) is generalized to the case where items are partially ordered through a set of precedence relations. As in ordinary KPs, each item is associated with profit and weight, the knapsack has a fixed capacity, and the problem is to determine the set of items to be packed in the knapsack. However, each item can be accepted only when all the preceding items have been included in the knapsack. The knapsack problem with these additional constraints is referred to as the precedence-constrained knapsack problem (PCKP). To solve PCKP exactly, we present a pegging approach, where the size of the original problem is reduced by applying the Lagrangian relaxation followed by a pegging test. Through this approach, we are able to solve PCKPs with thousands of items within a few minutes on an ordinary workstation.     

Worst-case and average-case analysis of an algorithm solving a generalized knapsack problem

The paper deals with a discontinuous linear knapsack problem of minimizing a linear objective function on a certain nonconnected subset of a polymatroid. The general problem is NP-hard but some practically interesting subclasses are solvable by a polynomial-time algorithm. Bounds of the expense of the solution process are given depending only on the subclass considered. The average-case behaviour is considered, too.     

Stochastic linear knapsack programming problem and its application to a portfolio selection problem

In this paper a probability maximization model of a stochastic linear knapsack problem is considered where the random variables consist of several groups with mutually correlated ones. We propose a solution algorithm to the equivalent nonlinear fractional programming problem with a simple ranking method. This approach will be effectively applied to one of the portfolio selection problems.     

Spectral analysis of a two body problem with zero-range perturbation

We consider a class of singular, zero-range perturbations of the Hamiltonian of a quantum system composed by a test particle and a harmonic oscillator in dimension one, two and three and we study its spectrum. In fact we give a detailed characterization of point spectrum and its asymptotic behavior with respect to the parameters entering the Hamiltonian. We also partially describe the positive spectrum and scattering properties of the Hamiltonian.     

Sensitivity analysis of the moments of the profit on an Income Protection Policy

The main purpose of this paper is to perform a sensitivity analysis where we quantify and analyse the effects on the mean of the profit on an Income Protection policy and two risk measures of changing the values of the transition intensities. All the calculations carried out are based on a multiple state model for Income Protection proposed in Continuous Mortality Investigation Committee (Continuous Mortality Investigation Reports 1991; 12 ). Within this model, we derive a formula for the mean of the profit, which enables to evaluate it more efficiently. In order to calculate the two risk measures we use the numerical algorithms for the calculation of the moments of the profit proposed by Waters (Insurance: Mathematics and Economics 1990; 9 :101–113). We carry out the sensitivity analysis considering two different situations: in the first situation, we update the premium rates used to calculate the moments of the profit, according to the changes in the values of the transition intensities; in the second one, we do not update the premium rates. Both analyses are of practical interest to insurance companies selling Income Protection policies. Copyright © 2009 John Wiley & Sons, Ltd.