Sensitivity of the Optimum to Perturbations of the Profit or Weight of an Item in the Binary Knapsack Problem

In the binary single constraint Knapsack Problem, denoted KP, we are given a knapsack of fixed capacity c and a set of n items. Each item j, j = 1,...,n, has an associated size or weight w_j and a profit p_j. The goal is to determine whether or not item j, j = 1,...,n, should be included in the knapsack. The objective is to maximize the total profit without exceeding the capacity c of the knapsack. In this paper, we study the sensitivity of the optimum of the KP to perturbations of either the profit or the weight of an item. We give approximate and exact interval limits for both cases (profit and weight) and propose several polynomial time algorithms able to reach these interval limits. The performance of the proposed algorithms are evaluated on a large number of problem instances.     

A hybrid beam search looking-ahead algorithm for the circular packing problem

In this paper, we study the circular packing problem. Its objective is to pack a set of n circular pieces into a rectangular plate R of fixed dimensions L×W. Each piece’s type i, i=1,…,m, is characterized by its radius r _i and its demand b _i . The objective is to determine the packing pattern corresponding to the minimum unused area of R for the circular pieces placed. This problem is solved by using a hybrid algorithm that adopts beam search and a looking-ahead strategy. A node at a level ℓ of the beam-search tree contains a partial solution corresponding to the circles already placed inside R. Each node is then evaluated using a looking-ahead strategy, based on the minimum local-distance heuristic, by computing the corresponding complete solution. The nodes leading to the best solutions at level ℓ are then chosen for branching. A multi-start strategy is also considered in order to diversify the search space. The computational results show, on a set of benchmark instances, the effectiveness of the proposed algorithm.     

The Knapsack Sharing Problem: An Exact Algorithm

In this paper, we propose an exact algorithm for the knapsack sharing problem. The proposed algorithm seems quite efficient in the sense that it solves quickly some large problem instances. The problem is decomposed into a series of single constraint knapsack problems; and by applying the dynamic programming and another strategy, we solve optimally the original problem. The performance of the exact algorithm is evaluated on a set of medium and large problem instances (a total of 240 problem instances). This algorithm is parallelizable and this is one of its important feature.     

Dynamic Programming and Hill-Climbing Techniques for Constrained Two-Dimensional Cutting Stock Problems

In this paper we propose an algorithm for the constrained two-dimensional cutting stock problem (TDC) in which a single stock sheet has to be cut into a set of small pieces, while maximizing the value of the pieces cut. The TDC problem is NP-hard in the strong sense and finds many practical applications in the cutting and packing area. The proposed algorithm is a hybrid approach in which a depth-first search using hill-climbing strategies and dynamic programming techniques are combined. The algorithm starts with an initial (feasible) lower bound computed by solving a series of single bounded knapsack problems. In order to enhance the first-level lower bound, we introduce an incremental procedure which is used within a top-down branch-and-bound procedure. We also propose some hill-climbing strategies in order to produce a good trade-off between the computational time and the solution quality. Extensive computational testing on problem instances from the literature shows the effectiveness of the proposed approach. The obtained results are compared to the results published by Alvarez-Valdés et al. (2002).     

Approximate and Exact Algorithms for Constrained (Un) Weighted Two-dimensional Two-staged Cutting Stock Problems

In this paper we propose two algorithms for solving both unweighted and weighted constrained two-dimensional two-staged cutting stock problems. The problem is called two-staged cutting problem because each produced (sub)optimal cutting pattern is realized by using two cut-phases. In the first cut-phase, the current stock rectangle is slit down its width (resp. length) into a set of vertical (resp. horizontal) strips and, in the second cut-phase, each of these strips is taken individually and chopped across its length (resp. width).First, we develop an approximate algorithm for the problem. The original problem is reduced to a series of single bounded knapsack problems and solved by applying a dynamic programming procedure. Second, we propose an exact algorithm tailored especially for the constrained two-staged cutting problem. The algorithm starts with an initial (feasible) lower bound computed by applying the proposed approximate algorithm. Then, by exploiting dynamic programming properties, we obtain good lower and upper bounds which lead to significant branching cuts. Extensive computational testing on problem instances from the literature shows the effectiveness of the proposed approximate and exact approaches.