Adaptive memory search for multidemand multidimensional knapsack problems

We describe a simple adaptive memory search method for the 0/1 Multidemand Multidimensional Knapsack Problem (0/1 MDMKP). The search balances the level of infeasibility against the quality of the solution, and uses a simple dynamic tabu search mechanism. A weighting scheme to balance out the differences in the tightness of the constraints is also implemented. Computational results on a portfolio of test problems taken from the literature are reported, showing very favorable results, both in terms of solution quality and the ability of the search to find feasible solutions.     

A simulation-optimization approach for integrated sourcing and inventory decisions

In this paper, we study a generalized vendor selection problem that integrates vendor selection and inventory replenishment decisions of a firm. In addition to vendor-specific procurement and management costs, we consider inventory replenishment, holding, and backorder costs explicitly to meet stationary stochastic demand faced by the firm. Our goal is to select the best set of vendors along with the optimum inventory decisions at each plant of the firm so that we minimize the system-wide total costs and achieve desired service and reliability levels. Due to uncertainties inherent in the problem related to demand observed by the firm, quality provided by vendors, and disruptions observed by vendors, we utilize a simulation-optimization approach to solve the problem. More specifically, we build a discrete-event simulation model to evaluate the objective function of the problem that works in concert with a scatter search-based metaheuristic optimization approach to search the solution space. Computational results not only provide managerial insights and measure the significance of intangible factors in the vendor selection process but also highlight the importance of computational tools such as simulation-optimization for the vendor selection problem.     

一种新的求解MMKP问题的ACO&PR算法

针对多选择多维背包问题(MMKP)的特点,设计一种新型混合算法(ACO＆PR).该算法将线路重连算法(PR)嵌入蚁群算法(ACO),在搜索过程中既考虑解的质量,又考虑解的分散性.线路重连算法在重连过程中,向导解的属性逐步引入起始解属性中,可快速获得该线路上的最优解.实验结果表明,该算法优于其他现有较好的方法,获得了较好的结果.     

On separating cover inequalities for the multidimensional knapsack problem

We propose a simple and a quite efficient separation procedure to identify cover inequalities for the multidimensional knapsack problem. It is based on the solution of a conventional integer programming model. Solving this kind of integer programs is usually considered expensive and the proposed method may have been overlooked because of this assumption. The results of our experiments with a small set of randomly generated problems and problems taken from the literature indicate that the method may be a reasonable alternative to the one currently in use.     

A k-means binarization framework applied to multidimensional knapsack problem

The multidimensional knapsack problem (MKP) is one of the widely known integer programming problems. The MKP has received significant attention from the operational research community for its large number of applications. Solving this NP-hard problem remains a very interesting challenge, especially when the number of constraints increases. In this paper we present a k-means transition ranking (KMTR) framework to solve the MKP. This framework has the property to binarize continuous population-based metaheuristics using a data mining k-means technique. In particular we binarize a Cuckoo Search and Black Hole metaheuristics. These techniques were chosen by the difference between their iteration mechanisms. We provide necessary experiments to investigate the role of key ingredients of the framework. Finally to demonstrate the efficiency of our proposal, MKP benchmark instances of the literature show that KMTR competes with the state-of-the-art algorithms.     

Tight oscillations tabu search for multidimensional knapsack problems with generalized upper bound constraints

In a recent paper, the author and Curry solved the multidimensional knapsack problem with generalized upper bound constraints by a critical-event tabu-search method which navigates both sides of the feasibility boundary with varied depth of oscillations. Efforts were made to explore the solution space near the feasibility boundary by using local swaps according to the objective function values (the resulting solutions are referred to as simple trial solutions). In this paper, a specialized tight-oscillation process is launched to intensify the search when the previous method finds good solutions or simple trial solutions near the feasibility boundary. Both feasibility changes and objective-function value changes are incorporated into the choice of moves process. This paper demonstrates the merits of using different choice rules at different stages of the heuristic. The balance of intensification and diversification is achieved by using two levels of strategic oscillation approaches together with tabu memory at the main heuristic stage and the trial solution stage. With the tight oscillation method, the heuristic is able to find high-quality solutions very efficiently.     

A new hybrid combinatorial genetic algorithm for multidimensional knapsack problems

Multidimensional knapsack problem (MKP) is known to be a NP-hard problem, more specifically a NP-complete problem, which cannot be resolved in polynomial time up to now. MKP can be applicable in many management, industry and engineering fields, such as cargo loading, capital budgeting and resource allocation, etc. In this article, using a combinational permutation constructed by the convex combinatorial value \(M_j=(1-\lambda ) u_j+ \lambda x^\mathrm{LP}_j\) of both the pseudo-utility ratios of MKP and the optimal solution \(x^\mathrm{LP}\) of relaxed LP, we present a new hybrid combinatorial genetic algorithm (HCGA) to address multidimensional knapsack problems. Comparing to Chu’s GA (J Heuristics 4:63–86, 1998), empirical results show that our new heuristic algorithm HCGA obtains better solutions over 270 standard test problem instances.     

An improved firefly algorithm for solving dynamic multidimensional knapsack problems

There is a wide range of publications reported in the literature, considering optimization problems where the entire problem related data remains stationary throughout optimization. However, most of the real-life problems have indeed a dynamic nature arising from the uncertainty of future events. Optimization in dynamic environments is a relatively new and hot research area and has attracted notable attention of the researchers in the past decade. Firefly Algorithm (FA), Genetic Algorithm (GA) and Differential Evolution (DE) have been widely used for static optimization problems, but the applications of those algorithms in dynamic environments are relatively lacking. In the present study, an effective FA introducing diversity with partial random restarts and with an adaptive move procedure is developed and proposed for solving dynamic multidimensional knapsack problems. To the best of our knowledge this paper constitutes the first study on the performance of FA on a dynamic combinatorial problem. In order to evaluate the performance of the proposed algorithm the same problem is also modeled and solved by GA, DE and original FA. Based on the computational results and convergence capabilities we concluded that improved FA is a very powerful algorithm for solving the multidimensional knapsack problems for both static and dynamic environments.     

An effective hybrid EDA-based algorithm for solving multidimensional knapsack problem

In this paper, an effective hybrid algorithm based on estimation of distribution algorithm (EDA) is proposed to solve the multidimensional knapsack problem (MKP). With the framework of EDA, the probability model is built with the superior population and the new individuals are generated based on probability model. In addition, an updating mechanism of the probability model is proposed and a mechanism for initializing the probability model based on the specific knowledge of the MKP is also proposed to improve the convergence speed. Meanwhile, an adaptive local search is proposed to enhance the exploitation ability. Furthermore, the influences of parameters are investigated based on Taguchi method of design of experiment and the importance of repair operator is also studied via simulation testing and comparisons. Finally, numerical simulation is carried out based on the benchmark instances, and the comparisons with some existing algorithms demonstrate the effectiveness of the proposed algorithm.     

Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem

Recently several hybrid methods combining exact algorithms and heuristics have been proposed for solving hard combinatorial optimization problems. In this paper, we propose new iterative relaxation-based heuristics for the 0-1 Mixed Integer Programming problem (0-1 MIP), which generate a sequence of lower and upper bounds. The upper bounds are obtained from relaxations of the problem and refined iteratively by including pseudo-cuts in the problem. Lower bounds are obtained from the solving of restricted problems generated by exploiting information from relaxation and memory of the search process. We propose a new semi-continuous relaxation (SCR) that relaxes partially the integrality constraints to force the variables values close to 0 or 1. Several variants of the new iterative semi-continuous relaxation based heuristic can be designed by a given update procedure of multiplier of SCR. These heuristics are enhanced by using local search procedure to improve the feasible solution found and rounding procedure to restore infeasibility if possible. Finally we present computational results of the new methods to solve the multiple-choice multidimensional knapsack problem which is an NP-hard problem, even to find a feasible solution. The approach is evaluated on a set of problem instances from the literature, and compared to the results reached by both CPLEX solver and an efficient column generation-based algorithm. The results show that our algorithms converge rapidly to good lower bounds and visit new best-known solutions.     

Fusing ant colony optimization with Lagrangian relaxation for the multiple-choice multidimensional knapsack problem

The multiple-choice multidimensional knapsack problem (MMKP) concerns a wide variety of practical problems. It is strongly constrained and NP-hard; thus searching for an efficient heuristic approach for MMKP is of great significance. In this study, we attempt to solve MMKP by fusing ant colony optimization (ACO) with Lagrangian relaxation (LR). The algorithm used here follows the algorithmic scheme of max–min ant system for its outstanding performance in solving many other combinatorial optimization problems. The Lagrangian value of the item in MMKP, obtained from LR, is used as the heuristic factor in ACO since it performs best among the six domain-based heuristic factors we define. Furthermore, a novel infeasibility index is proposed for the development of a new repair operator, which converts possibly infeasible solutions into feasible ones. The proposed algorithm was compared with four existing algorithms by applying them to three groups of instances. Computational results demonstrate that the proposed algorithm is capable of producing competitive solutions.     

Hard multidimensional multiple choice knapsack problems, an empirical study

Recent advances in algorithms for the multidimensional multiple choice knapsack problems have enabled us to solve rather large problem instances. However, these algorithms are evaluated with very limited benchmark instances. In this study, we propose new methods to systematically generate comprehensive benchmark instances. Some instances with special correlation properties between parameters are found to be several orders of magnitude harder than those currently used for benchmarking the algorithms. Experiments on an existing exact algorithm and two generic solvers show that instances whose weights are uncorrelated with the profits are easier compared with weakly or strongly correlated cases. Instances with classes containing similar set of profits for items and with weights strongly correlated to the profits are the hardest among all instance groups investigated. These hard instances deserve further study and understanding their properties may shed light to better algorithms.     

Development of core to solve the multidimensional multiple-choice knapsack problem

The multidimensional multiple-choice knapsack problem (MMKP) is an extension of the 0–1 knapsack problem. The core concept has been used to design efficient algorithms for the knapsack problem but the core has not been developed for the MMKP so far. In this paper, we develop an approximate core for the MMKP and utilize it to solve the problem exactly.     

Solving multidimensional knapsack problems with generalized upper bound constraints using critical event tabu search

A critical event tabu search method which navigates both sides of the feasibility boundary has been shown effective for solving the multidimensional knapsack problem. In this paper, we apply the method to the multidimensional knapsack problem with generalized upper bound constraints. This paper also demonstrates the merits of using surrogate constraint information vs. a Lagrangian relaxation scheme as choice rules for the problem class. A constraint normalization method is presented to strengthen the surrogate constraint information and improve the computational results. The advantages of intensifying the search at critical solutions are also demonstrated.     

An efficient binary differential evolution algorithm for the multidimensional knapsack problem

Engineering with Computers - This paper proposes a novel approach for the multidimensional knapsack problem (MDKP) using differential evolution. Firstly, the principle and the pseudo-code of binary...     

An effective hybrid harmony search-based algorithm for solving multidimensional knapsack problems

This study presents an effective hybrid algorithm based on harmony search (HHS) for solving multidimensional knapsack problems (MKPs). In the proposed HHS algorithm, a novel harmony improvisation mechanism is developed with the modified memory consideration rule and the global-best pitch adjustment scheme to enhance the global exploration. A parallel updating strategy is employed to enrich the harmony memory diversity. To well balance the exploration and the exploitation, the fruit fly optimization (FFO) scheme is integrated as a local search strategy. For solving MKPs, binary strings are used to represent solutions and two repair operators are applied to guarantee the feasibility of the solutions. The HHS is calibrated based on the Taguchi method of design-of-experiment. Extensive numerical investigations based on well-known benchmark instances are conducted. The comparative evaluations indicate the HHS is much more effective than the existing HS and FFO variants in solving MKPs.     

Problem reduction heuristic for the 0-1 multidimensional knapsack problem

This paper introduces new problem-size reduction heuristics for the multidimensional knapsack problem. These heuristics are based on solving a relaxed version of the problem, using the dual variables to formulate a Lagrangian relaxation of the original problem, and then solving an estimated core problem to achieve a heuristic solution to the original problem. We demonstrate the performance of these heuristics as compared to legacy heuristics and two other problem reduction heuristics for the multi-dimensional knapsack problem. We discuss problems with existing test problems and discuss the use of an improved test problem generation approach. We use a competitive test to highlight the performance of our heuristics versus the legacy heuristic approaches. We also introduce the concept of computational versus competitive problem test data sets as a means to focus the empirical analysis of heuristic performance.     

Genetic algorithms with decomposition procedures for multidimensional 0-1 knapsack problems with block angular structures

This paper presents a detailed treatment of genetic algorithms with decomposition procedures as developed for large scale multidimensional 0-1 knapsack problems with block angular structures. Through the introduction of a triple string representation and the corresponding decoding algorithm, it is shown that a potential solution satisfying not only block constraints but also coupling constraints can be obtained for each individual. Then genetic algorithms with decomposition procedures are presented as an approximate solution method for multidimensional 0-1 knapsack problems with block angular structures. Many computational experiments on numerical examples with 30, 50, 70, 100, 150, 200, 300, 500, and 1000 variables demonstrate the feasibility and efficiency of the proposed method.     

Solving the multidimensional knapsack problems with generalized upper bound constraints by the adaptive memory projection method

An adaptive memory projection (referred as AMP) method is developed for multidimensional knapsack problems (referred as the MKP) with generalized upper bound constraints. All the variables are divided into several generalized upper bound (referred as GUB) sets and at most one variable can be chosen from each of the GUB sets. The MKP with GUBs (referred as the GUBMKP) can be applied to many real-world problems, such as capital budgeting, resource allocation, cargo loading, and project selection. Due to the complexity of the GUBMKP, good metaheuristics are sought to tackle this problem.The AMP method keeps track of components of good solutions during the search and creates provisional solution by combining components of better solutions. The projection method, which can free the selected variables while fixing the others, is very useful for metaheuristics, especially when tackling large-scale combinatorial optimization. In this paper, the AMP method is implemented by iteratively using critical event tabu search as a search routine, and CPLEX in the referent optimization stage. Variables that are strongly determined, consistent, or attractive, are identified in the search process. Selected variables from this pool are fed into CPLEX as a small subproblem. In addition to the diversification effect within critical event tabu search, the pseudo-cut inequalities and an adjusted frequency penalty scalar are also applied to increase opportunities of exploring new regions.This study conducts a comprehensive sensitivity analysis on the parameters and strategies used in the proposed AMP method. The computational results show several variants of the AMP method outperforms the tight oscillation method in the literature of GUBMKP. On average, consistent variables tend to perform best as a pure strategy. A pure strategy equipped with local search can lead into even better results. Last but not least, testing different types of variables in the referent optimization stage before selecting just one of the pure strategies is found to be very helpful.     

MOTGA: A multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem

This paper presents a new multiobjective genetic algorithm based on the Tchebycheff scalarizing function, which aims to generate a good approximation of the nondominated solution set of the multiobjective problem. The algorithm performs several stages, each one intended for searching potentially nondominated solutions in a different part of the Pareto front. Pre-defined weight vectors act as pivots to define the weighted-Tchebycheff scalarizing functions used in each stage. Therefore, each stage focuses the search on a specific region, leading to an iterative approximation of the entire nondominated set.