A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems

In this paper we present a genetic algorithm-based heuristic especially for the weighted maximum independent set problem (IS). The proposed approach treats also some equivalent combinatorial optimization problems. We introduce several modifications to the basic genetic algorithm, by (i) using a crossover called two-fusion operator which creates two new different children and (ii) replacing the mutation operator by the heuristic-feasibility operator tailored specifically for the weighted independent set. The performance of our algorithm was evaluated on several randomly generated problem instances for the weighted independent set and on some instances of the DIMACS Workshop for the particular case: the unweighted maximum clique problem. Computational results show that the proposed approach is able to produce high-quality solutions within reasonable computational times. This algorithm is easily parallelizable and this is one of its important features.     

A parallel algorithm for two-staged two-dimensional fixed-orientation cutting problems

In this paper, we study the two-staged two-dimensional fixed-orientation cutting problem. We investigate the use of the parallel beam search algorithm for approximately solving the problem. The beam-search can be viewed as a truncated tree-search in which a subset of generated nodes are investigated. The proposed approach tries to explore some of these nodes in parallel by applying a master-slave paradigm. The master processor serves to guide the search-resolution by using a best-first search strategy for selecting the successive sets of nodes, called elite nodes. Whereas each slave processor develops the search tree and updates the global list of the master processor in an asynchronous manner. Each processor is based on combining a partial lower bound and a complementary upper bound, obtained by solving a series of bounded knapsack problems. The proposed method is analyzed computationally on a set of benchmark instances of the literature and their results are compared to those provided by existing algorithms. Encouraging and new results have been obtained.     

Exact Algorithms for Large-Scale Unconstrained Two and Three Staged Cutting Problems

In this paper we propose two exact algorithms for solving both two-staged and three staged unconstrained (un)weighted cutting problems. The two-staged problem is solved by applying a dynamic programming procedure originally developed by Gilmore and Gomory [Gilmore and Gomory, Operations Research, vol. 13, pp. 94–119, 1965]. The three-staged problem is solved by using a top-down approach combined with a dynamic programming procedure. The performance of the exact algorithms are evaluated on some problem instances of the literature and other hard randomly-generated problem instances (a total of 53 problem instances). A parallel implementation is an important feature of the algorithm used for solving the three-staged version.     

Constrained two-dimensional cutting: an improvement of Christofides and Whitlock's exact algorithm

Christofides and Whitlock have developed a top-down algorithm which combines in a nice tree search procedure Gilmore and Gomory's algorithm and a transportation routine called at each node of the tree for solving exactly the constrained two-dimensional cutting problem. Recently, another bottom-up algorithm has been developed and reported as being more efficient. In this paper, we propose a modification to the branching strategy and we introduce the one-dimensional bounded knapsack in the original Christofides and Whitlock algorithm. Then, by exploiting dynamic programming properties we obtain good lower and upper bounds which lead to significant branching cuts, resulting in a drastic reduction of calls of the transportation routine. Finally, we propose an incremental solution of the numerous generated transportation problems. The resulting algorithm reveals superior performance to other known algorithms.     

A reactive local search-based algorithm for the disjunctively constrained knapsack problem

In this paper, we propose a reactive local search-based algorithm for the disjunctively constrained knapsack problem (DCKP). DCKP is a variant of the standard knapsack problem, an NP-hard combinatorial optimization problem, with special disjunctive constraints. A disjunctive constraint is a couple of items for which only one item is packed. The proposed algorithm is based upon a reactive local search, where an explicit check for the repetition of configurations is added to the search process. Initially, two complementary greedy procedures are applied in order to construct a starting solution. Second, a degrading procedure is introduced in order (i) to escape to local optima and (ii) to introduce a diversification in the search space. Finally, a memory list is added in order to forbid the repetition of configurations. The performance of two versions of the algorithm has been evaluated on several problem instances and compared to the results obtained by running the Cplex solver. Encouraging results have been obtained.     

An Efficient Algorithm for the Knapsack Sharing Problem

The Knapsack Sharing Problem (KSP) is an NP-Hard combinatorial optimization problem, admitted in numerous real world applications. In the KSP, we have a knapsack of capacity c and a set of n objects, namely N, where each object j, j = 1,...,n, is associated with a profit p _j and a weight w _j. The set of objects N is composed of m different classes of objects J _i, i = 1,...,m, and N = ^m _i=1 J _i. The aim is to determine a subset of objects to be included in the knapsack that realizes a max-min value over all classes.In this article, we solve the KSP using an approximate solution method based upon tabu search. First, we describe a simple local search in which a depthparameter and a tabu list are used. Next, we enhance the algorithm by introducing some intensifying and diversifying strategies. The two versions of the algorithm yield satisfactory results within reasonable computational time. Extensive computational testing on problem instances taken from the literature shows the effectiveness of the proposed approach.     

Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem

In this paper, we propose approximate and exact algorithms for the double constrained two-dimensional guillotine cutting stock problem (DCTDC). The approximate algorithm is a two-stage procedure. The first stage attempts to produce a starting feasible solution to DCTDC by solving a single constrained two dimensional cutting problem, CDTC. If the solution to CTDC is not feasible to DCTDC, the second stage is used to eliminate non-feasibility. The exact algorithm is a branch-and-bound that uses efficient lower and upper bounding schemes. It starts with a lower bound reached by the approximate two-stage algorithm. At each internal node of the branching tree, a tailored upper bound is obtained by solving (relaxed) knapsack problems. To speed up the branch and bound, we implement, in addition to ordered data structures of lists, symmetry, duplicate, and non-feasibility detection strategies which fathom some unnecessary branches. We evaluate the performance of the algorithm on different problem instances which can become benchmark problems for the cutting and packing literature.     

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.     

A column generation method for the multiple-choice multi-dimensional knapsack problem

In this paper, we propose to solve large-scale multiple-choice multi-dimensional knapsack problems. We investigate the use of the column generation and effective solution procedures. The method is in the spirit of well-known local search metaheuristics, in which the search process is composed of two complementary stages: (i) a rounding solution stage and (ii) a restricted exact solution procedure. The method is analyzed computationally on a set of problem instances of the literature and compared to the results reached by both Cplex solver and a recent reactive local search. For these instances, most of which cannot be solved to proven optimality in a reasonable runtime, the proposed method improves 21 out of 27.     

Adaptive and restarting techniques-based algorithms for circular packing problems

In this paper, we study the circular packing problem (CPP) which consists of packing a set of non-identical circles of known radii into the smallest circle with no overlap of any pair of circles. To solve CPP, we propose a three-phase approximate algorithm. During its first phase, the algorithm successively packs the ordered set of circles. It searches for each circle’s “best” position given the positions of the already packed circles where the best position minimizes the radius of the current containing circle. During its second phase, the algorithm tries to reduce the radius of the containing circle by applying (i) an intensified search, based on a reduction search interval, and (ii) a diversified search, based on the application of a number of layout techniques. Finally, during its third phase, the algorithm introduces a restarting procedure that explores the neighborhood of the current solution in search for a better ordering of the circles. The performance of the proposed algorithm is evaluated on several problem instances taken from the literature.