基于核算法解决多维多选择背包问题

针对目前尚无多维多选择背包问题(MMKP)高效核算法的现状,提出用多种方法来构造处理这种类型背包的核。首先论述了如何在一般背包问题中获得核;接着根据事先设定的度量指标详细讨论了MMKP的基本解和两种排序关系,并利用三种备选方案得出MMKP的核,亦即子空间。第一种方案是基于观察数据E[lc]和E[d∞]比较小来得到核;第二种方案基于基本解和最优解的曼哈顿距离不算太远来实施;第三种方案是为所有元素定义一个全序并取第一组k元素作为核。比较了这三种方案的不同与优劣,结果表明：第一种方案比其他两种方案无论从定义子空间的精度和枚举时间平均值上,性能都更优越,利用该方案定义的核能高效解决MMKP。     

The multiobjective multidimensional knapsack problem: a survey and a new approach

The knapsack problem (KP) and its multidimensional version (MKP) are basic problems in combinatorial optimization. In this paper, we consider their multiobjective extension (MOKP and MOMKP), for which the aim is to obtain or approximate the set of efficient solutions. In the first step, we classify and briefly describe the existing works that are essentially based on the use of metaheuristics. In the second step, we propose the adaptation of the two‐phase Pareto local search (2PPLS) to the resolution of the MOMKP. With this aim, we use a very large scale neighborhood in the second phase of the method, that is the PLS. We compare our results with state‐of‐the‐art results and show that the results we obtained were never reached before by heuristics for biobjective instances. Finally, we consider the extension to three‐objective instances.     

一种新的求解多维背包问题的分散算法

为了避免蚁群算法在优化搜索过程中易陷入局部最优和早熟收敛,提出一种求解多维背包问题的新型分散搜索算法。该算法是把蚁群算法的构解方法引入到分散搜索算法中,在搜索过程中,既考虑解的质量,又考虑解的分散性。同时,该分散算法还采用了动态更新参考集与阈值接收算法的阈值参数,以控制搜索空间来加快收敛速度。通过选取国际通用MDKP实例库中的多个实例进行测试表明,该算法可以避免陷入局部最优解,能提高全局寻优能力,其结果优于其他现有的方法,并获得了较好的结果。     

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.     

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.     

改进二进制布谷鸟搜索算法求解多维背包问题

针对多约束组合优化问题--多维背包问题(MKP),提出了一种改进二进制布谷鸟搜索(MBCS)算法.首先,采用经典的二进制代码变换公式构建了二进制布谷鸟搜索(BCS)算法.其次,引入病毒生物进化机制和病毒感染操作,一方面赋予布谷鸟鸟巢位置自变异机制增加种群多样性;一方面将布谷鸟鸟巢位置所组成的主群体的纵向全局搜索和病毒群体的横向局部搜索进行动态结合,进一步提高了算法的收敛速度,降低了陷入局部极值的概率.再次,针对MKP特点设计了不可行解的混合修复策略.最后将MBCS算法同量子遗传算法(QGA)、二进制粒子群优化(BPSO)算法、BCS算法就来源于ELIB数据库和OR_LIB数据库的15个算例进行了仿真对比.实验结果表明,所提算法计算误差均小于1%,标准差小于170,相比这3种算法具有相对更好的寻优精度和求解稳定性,是一种求解多维背包等NP难问题有效的算法.     

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.     

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.     

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

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

改进的差分演化算法求解多维背包问题

多维背包（MKP）是组合优化中一个典型的NP难问题,广泛应用于工程和管理中。提出了一种改进的二进制差分演化算法（Modified Binary Differential Evolution algorithm,MBDE）求解MKP问题,算法关键步骤可分为两部分：二进制群体生成;得到候选可行解。提出了一种有效的衡量商品价值密度的方法用于对二进制个体修正和优化;设计了反向测试搜索和精英局部搜索策略来提高算法探索和开发能力,从而进一步提高了MBDE的求解精度和收敛速度。为验证MBDE算法的有效性,进行了三组实验,并和近期提出的解决MKP问题的其他启发式算法进行了比较,实验结果显示,MBDE算法求解精度更高。从算法运行时间看,求解速度快,非常适合求解大规模的MKP问题。     

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.     

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.     

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.     

求解多维背包问题的二级协作果蝇优化算法

针对多维背包问题(MKP)约束性强和复杂度高的特点,提出一种新型二级协作果蝇优化算法(TCFOA).提出一级果蝇和二级果蝇的产生机制,将二级果蝇划分为开发用果蝇和探索用果蝇两类以协调开发与探索之间的平衡;设计果蝇交流策略以及基于全局性价比的解的修复补偿机制,并利用二级结构扩大搜索范围、改善一级果蝇的质量,以提高求解质量.基于MKP两个标准测试集的测试结果和算法性能对比,表明TCFOA在求解MKP方面具有较强的优势.     

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.     

A binary grey wolf optimizer for the multidimensional knapsack problem

Grey Wolf Optimizer (GWO) is a new meta-heuristic that mimics the leadership hierarchy and group hunting mechanism of grey wolves in nature. A binary version is developed to tackle the multidimensional knapsack problem which has an extensive engineering background. The proposed binary grey wolf optimizer integrates some important features including an initial elite population generator, a pseudo-utility-based quick repair operator, a new evolutionary mechanism with a differentiated position updating strategy. The proposed algorithm takes full advantage of the knowledge of the problem to be solved and highlights the distinctive feature of the optimizer in the family of evolutionary algorithm. Experimental results statistically show the effectiveness of the new optimizer and the superiority of the proposed algorithm in solving the multidimensional knapsack problem, especially the large-scale problem.     

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.     

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.     

一种求解多维背包问题的混合分布估计算法

针对多维背包问题（MKP）,提出一种基于分布估计算法的混合求解算法,该算法基于优势种群构建概率模型,并基于概率模型采样产生新个体;同时,提出一种基于MKP问题信息的修复机制,有效修复采样后种群中的不可行解．另外,设计了一种自适应的局部搜索操作,以增强算法的局部搜索能力,基于标准测试集的仿真结果和算法比较验证了所提出的混合算法的有效性和鲁棒性．