Search

Byline: Mhand Hifi, Toufik Saadi In this paper, we propose a cooperative algorithm for approximately solving the two-staged two-dimensional cutting stock problem (2TDC). We solve 2TDC by considering three key features: a search strategy, a fast filling procedure (FP) and a tighter complementary upper bound. Firstly, the search strategy uses a beam-search method which considers both priority and total cost evaluation operators. Secondly, the FP is used for improving the quality of the obtained results. Finally, a tighter upper bound is applied for refining the selected paths. The method is analysed computationally on a set of instances of the literature and compared to the results provided by several algorithms of the literature. Encouraging results have been obtained.

Byline: Hakim Akeb, Mhand Hifi In this paper, the Circular Cutting (CC)/packing problem is studied. Its objective is to cut/pack a set of circular pieces into a rectangular plate R of dimensions L × W. Each piece's type i, i = 1, . . .,m, is characterised by its radius ri and its demand bi. This problem is solved using an adaptive algorithm that combines Beam Search (BS) and various hill-climbing strategies. Decisions at each node of the truncated tree are based on the so-called best local position using a Minimum Local-Distance Position (MLDP) rule. The computational results show, on a set of problem instances of the literature, the effectiveness of the proposed algorithm.

Byline: Nawal Cherfi, Mhand Hifi In this paper, we propose three versions of an algorithm for approximately solving large-scale Multiple-choice Multi-dimensional Knapsack Problems (MMKP). First, an adaptation of the local branching is proposed. Second, a hybrid solution procedure is presented that is based on two complementary solution procedures: a local branching which cooperates with a column generation solution procedure. Third and last, an augmented algorithm of the last hybrid algorithm is developed. It can also be viewed as a special truncated branch and bound in which the first hybrid algorithm is applied to a subset of elite nodes generated according to some variables/constraint branchings. The proposed methods are analysed computationally on a set of instances of the literature and compared to the results provided by other algorithms of the literature. Encouraging results have been obtained.

The setup knapsack problem can be viewed as a more complex version of the well-known classical knapsack problem. An instance of such a problem may be defined by a set [ABSTRACT FROM AUTHOR]

Several practical applications depend on different criteria or scenarios and belong to the combinatorial optimization family. For example, in engineering design of a car, two criteria may be needed to optimize its production: the profit that can bring a car as well as its reliability for the customer. In water distribution networks, designing contaminant warning system of water is necessary. In this case, the problem consists in determining the level of protection under the worst possible scenario on the sensors that should be placed. In this paper, a max-min problem under several scenarios is tackled, called max-min knapsack problem with multi-scenarios. We propose to solve it by using a hybrid reactive search algorithm that uses two main features: (i) the restoring/exploring phase and the perturbation phase. The first phase yields a feasible solution and tries to improving it by using an intensification search. The second phase can be viewed as a diversification search in which a series of subspaces are investigated in order to make a quick convergence to a global optimum. Finally, the proposed method is evaluated on a set of benchmark instances taken from the literature, whereby its obtained results are compared to those reached by recent methods available in the literature. The results show that the method is competitive and it is able to provide better solutions than those already published. [ABSTRACT FROM PUBLISHER]

This article addresses a Lagrangian heuristic-based neighbourhood search for the multiple-choice multi-dimensional knapsack problem, an NP-hard combinatorial optimization problem. The problem is solved by using a cooperative approach that uses a local search for exploring a series of neighbourhoods induced from the Lagrangian relaxation. Each neighbourhood is submitted to an optimization process using two alternative strategies: reducing and moving strategies. The reducing strategy serves to reduce the current search space whereas the moving strategy explores the new search space. The performance of the proposed approach is evaluated on benchmark instances taken from the literature. Its obtained results are compared with those reached by some recent methods available in the literature. New solutions have been obtained for almost 80% of the instances tested. [ABSTRACT FROM AUTHOR]