Jour : 18 mars 2016

In this paper a fast large neighborhood search-based heuristic is proposed for solving the Disjunctively Constrained Knapsack Problem (DCKP). The proposed method combines a two-phase procedure and a large neighborhood search. First, a two-phase procedure is applied in order to construct a starting feasible solution of the DCKP. Its first phase serves to determine a feasible solution by combining two complementary problems: the weighted independent set problem and the classical binary knapsack problem. Its second phase uses a descent method trying to improve the current solution by applying both degrading and re-optimizing strategies. Second, a large neighborhood search is used for diversifying the search space. Finally, the performance of the proposed method is computationally analyzed on a set of benchmark instances for the literature and its results are compared to those reached by both Cplex solver and more recent algorithms in the literature. Several improved solutions have been obtained within small average runtime.

Keywords: Heuristic; knapsack; neighborhood; re-optimisation.

Mhand Hifi, Sagvan Saleh, Lei Wu

doi:10.1007/978-3-319-09174-7_34

A version on ResearchGate: source

Benchmark instances: download (I1-13 and INST01-20)

In this paper, we study the knapsack sharing problem (KSP), which is a variant of the well-known NP-Hard knapsack problem. We investigate the use of a dichotomous search-based exact method for solving the KSP. Such a method is based on decomposing the original problem into a series of minimizing and maximizing knapsack problems, where each of them is embedded into a dichotomous search bounded by both lower and upper bounds. Throughout the interval search, we introduce new upper bounds and incremental valid lower bounds. One of these upper bounds can be viewed as an extended of Dantzig upper bound whereas a series of valid lower bounds are obtained when solving a subset of knapsack problems. Finally, the proposed algorithm is evaluated on a set of problem instances of the literature and other new harder ones. The provided results are compared to those reached by the Cplex solver and a more recent exact algorithm of the literature. The computational part shows the dominance of the new exact method.

Keywords: Combinatorial optimization; Decomposition; Discrete optimization; Knapsack; Optimality; Sharing; Upper bound.

Mhand Hifi and Lei Wu

doi:10.1007/s10479-011-1004-2

Abstract

In this paper, we propose to solve the three-dimensional single bin-size bin packing problem (3D-SBSBPP) using a simple strategy based on integer linear programming (ILP) heuristics, without using any improvement based on metaheuristics. We first propose an ILP that is converted into a series of three-dimensional single knapsack problems (3D-SKP). Then, the first tailored heuristic can be viewed as a hybrid approach in which both “selection” and “positioning” phases are combined. The first phase serves to select a subset of items where each of these items is susceptible to belonging to an active container. The positioning phase serves to pack a subset of items already preselected by the selection phase. Then, both phases cooperate till packing all items into their corresponding containers. The second heuristic can be viewed as an extended version of the first one. Indeed, before deciding whether the current container is closed or a new container is activated, “a local reoptimization phase” is considered. Finally, both proposed heuristics are evaluated on a set of random instances obtained by using the standard generator scheme of the literature. The provided results show that both proposed heuristics remain competitive when compared to the results obtained by one of the best methods of the literature.

Keywords: Bin packing; heuristics; linear programming; two-dimensional knapsack.

Mhand Hifi, Stephane Negre, Lei Wu

doi:10.1111/itor.12035

Benchmark instances:

download (mpv10-90), download (mpv50-200)

Abstract

In this paper we consider the three-dimensional bin packing problem (3D-BPP), when the bins are identical with the aim of minimizing the number of the used bins. We introduce a mixed-integer linear programming formulation (MILP1). Some special valid inequalities will be presented in order to improve the relaxed lower bound of MILP1. A large set of experimental tests has been carried out. The obtained results show that our method provides a satisfactory performance.

Keywords: Bin-packing; integer linear programming; scheduling.

Mhand Hifi, Imed Kacem, Stephane Negre, Lei Wu

doi:10.1016/j.endm.2010.05.126

Benchmark instances: download