Heuristic and exact algorithms for the max–min optimization of the multi-scenario knapsack problem

We are concerned with a variation of the standard 0–1 knapsack problem, where the values of items differ under possible S scenarios. By applying the ‘pegging test’ the ordinary knapsack problem can be reduced, often significantly, in size; but this is not directly applicable to our problem. We introduce a kind of surrogate relaxation to derive upper and lower bounds quickly, and show that, with this preprocessing, the similar pegging test can be applied to our problem. The reduced problem can be solved to optimality by the branch-and-bound algorithm. Here, we make use of the surrogate variables to evaluate the upper bound at each branch-and-bound node very quickly by solving a continuous knapsack problem. Through numerical experiments we show that the developed method finds upper and lower bounds of very high accuracy in a few seconds, and solves larger instances to optimality faster than the previously published algorithms.     

A two state reduction based dynamic programming algorithm for the bi-objective 0–1 knapsack problem

In this paper, we present a dynamic programming (DP) algorithm for the multi-objective 0–1 knapsack problem (MKP) by combining two state reduction techniques. One generates a backward reduced-state DP space (BRDS) by discarding some states systematically and the other reduces further the number of states to be calculated in the BRDS using a property governing the objective relations between states. We derive the condition under which the BRDS is effective to the MKP based on the analysis of solution time and memory requirements. To the authors’ knowledge, the BRDS is applied for the first time for developing a DP algorithm. The numerical results obtained with different types of bi-objective instances show that the algorithm can find the Pareto frontier faster than the benchmark algorithm for the large size instances, for three of the four types of instances conducted in the computational experiments. The larger the size of the problem, the larger improvement over the benchmark algorithm. Also, the algorithm is more efficient for the harder types of bi-objective instances as compared with the benchmark algorithm.     

考虑时间因素的0-1背包调度问题

文中提出考虑时间因素的0-1背包调度问题这一具有NP难度的组合优化问题。给定n个物体(每个物体i的重量为w_i,连续加工时间为t_i),以及一个容量为S的背包,要求给出一个调度方案(物品的放入顺序和放入时间),使得任意时刻放入背包的物品总重量不超过背包容量,每个物体需放入背包连续加工时长t_i后才能取出,该问题是求使所有物体均加工完毕的时间尽可能短的调度方案。提出了3种求解算法:迭代动态规划算法、基于分枝限界的完备算法和遗传进化算法。迭代动态规划算法使用动态规划策略放置尽可能多的未加工物体到背包中,然后每次迭代取出加工完成的物品后再使用动态规划放入尽可能多的剩余未加工物品,直至所有物品被加工完成。基于分枝限界的完备算法通过定义上下界及剪枝操作,有效地降低了算法的计算复杂度。遗传进化算法将一个物品装填序列定义为个体,并定义了相应的适应度、选择、交叉与变异操作。在所设计的3组共计36个算例上的实验结果表明,迭代动态规划算法可以很快求出高质量的解,基于分枝限界的完备算法对小规模算例有很好的效果,遗传算法在处理几百个物体的算例时能在1500s内得到比动态规划算法更好的结果。     

Determining the K-best solutions of knapsack problems

It is well-known that knapsack problems arise as subproblems of a number of large-scale integer optimization problems. In order to solve these large problems, it is necessary to solve the subproblems efficiently, and for many of them it can be useful to determine the K-best solutions. In this paper, a branch-and-bound method for the unbounded knapsack problem described in the literature is extended to determine the K-best solutions of unbounded and bounded knapsack problems. We show that the proposed extension determines exactly the K-best solutions and we solve important classical instances using high values of K.     

A dynamic programming method with lists for the knapsack sharing problem

In this paper, we propose a method to solve exactly the knapsack sharing problem (KSP) by using dynamic programming. The original problem (KSP) is decomposed into a set of knapsack problems. Our method is tested on correlated and uncorrelated instances from the literature. Computational results show that our method is able to find an optimal solution of large instances within reasonable computing time and low memory occupancy.     

A virtual pegging approach to the max–min optimization of the bi-criteria knapsack problem

We are concerned with a variation of the knapsack problem, the bi-objective max–min knapsack problem (BKP), where the values of items differ under two possible scenarios. We have given a heuristic algorithm and an exact algorithm to solve this problem. In particular, we introduce a surrogate relaxation to derive upper and lower bounds very quickly, and apply the pegging test to reduce the size of BKP. We also exploit this relaxation to obtain an upper bound in the branch-and-bound algorithm to solve the reduced problem. To further reduce the problem size, we propose a ‘virtual pegging’ algorithm and solve BKP to optimality. As a result, for problems with up to 16,000 items, we obtain a very accurate approximate solution in less than a few seconds. Except for some instances, exact solutions can also be obtained in less than a few minutes on ordinary computers. However, the proposed algorithm is less effective for strongly correlated instances.     

Computational performance of basic state reduction based dynamic programming algorithms for bi-objective 0–1 knapsack problems

This paper studies a group of basic state reduction based dynamic programming (DP) algorithms for the multi-objective 0–1 knapsack problem (MKP), which are related to the backward reduced-state DP space (BRDS) and forward reduced-state DP space (FRDS). The BRDS is widely ignored in the literature because it imposes disadvantage for the single objective knapsack problem (KP) in terms of memory requirements. The FRDS based DP algorithm in a general sense is related to state dominance checking, which can be time consuming for the MKP while it can be done efficiently for the KP. Consequently, no algorithm purely based on the FRDS with state dominance checking has ever been developed for the MKP. In this paper, we attempt to get some insights into the state reduction techniques efficient to the MKP. We first propose an FRDS based algorithm with a local state dominance checking for the MKP. Then we evaluate the relative advantage of the BRDS and FRDS based algorithms by analyzing their computational time and memory requirements for the MKP. Finally different combinations of the BRDS and FRDS based algorithms are developed on this basis. Numerical experiments based on the bi-objective KP instances are conducted to compare systematically between these algorithms and the recently developed BRDS based DP algorithm as well as the existing FRDS based DP algorithm without state dominance checking.     

Algorithms for 3D guillotine cutting problems: Unbounded knapsack, cutting stock and strip packing

We present algorithms for the following three-dimensional (3D) guillotine cutting problems: unbounded knapsack, cutting stock and strip packing. We consider the case where the items have fixed orientation and the case where orthogonal rotations around all axes are allowed. For the unbounded 3D knapsack problem, we extend the recurrence formula proposed by [1] for the rectangular knapsack problem and present a dynamic programming algorithm that uses reduced raster points. We also consider a variant of the unbounded knapsack problem in which the cuts must be staged. For the 3D cutting stock problem and its variants in which the bins have different sizes (and the cuts must be staged), we present column generation-based algorithms. Modified versions of the algorithms for the 3D cutting stock problems with stages are then used to build algorithms for the 3D strip packing problem and its variants. The computational tests performed with the algorithms described in this paper indicate that they are useful to solve instances of moderate size.     

Shuffled frog leaping algorithm and its application to 0/1 knapsack problem

This paper proposes a modified discrete shuffled frog leaping algorithm (MDSFL) to solve 01 knapsack problems. The proposed algorithm includes two important operations: the local search of the ‘particle swarm optimization’ technique; and the competitiveness mixing of information of the ‘shuffled complex evolution’ technique. Different types of knapsack problem instances are generated to test the convergence property of MDSFLA and the result shows that it is very effective in solving small to medium sized knapsack problems. Further, computational experiments with a set of large-scale instances show that MDSFL can be an efficient alternative for solving tightly constrained 01 knapsack problems.     

An incomplete m-exchange algorithm for solving the large-scale multi-scenario knapsack problem

This paper introduces a fast heuristic based algorithm for the max-min multi-scenario knapsack problem. The problem is a variation of the standard 0-1 knapsack problem, in which the profits of the items vary under different scenarios, though the capacity of the knapsack is fixed. The objective of the problem is to find the optimal packing of a set of items so that the minimum total profits of the items in the knapsack over all different scenarios is maximized. For some large-scaled instances, traditional branch-and-bound techniques cannot find an optimal solution within reasonable time, thus we propose a collection of incomplete m-exchange algorithms which are able to produce high quality solutions in just a few minutes of cpu time. Various computational results are also given.     

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.     

Heuristics for two-dimensional knapsack and cutting stock problems with items of irregular shape

In this paper, the two-dimensional cutting/packing problem with items that correspond to simple polygons that may contain holes are studied in which we propose algorithms based on no-fit polygon computation. We present a GRASP based heuristic for the 0/1 version of the knapsack problem, and another heuristic for the unconstrained version of the knapsack problem. This last heuristic is divided in two steps: first it packs items in rectangles and then use the rectangles as items to be packed into the bin. We also solve the cutting stock problem with items of irregular shape, by combining this last heuristic with a column generation algorithm. The algorithms proposed found optimal solutions for several of the tested instances within a reasonable runtime. For some instances, the algorithms obtained solutions with occupancy rates above 90% with relatively fast execution time.     

A variable-grouping based genetic algorithm for large-scale integer programming

To effectively reduce the dimensionality of search space, this paper proposes a variable-grouping based genetic algorithm (VGGA) for large-scale integer programming problems (IPs). The VGGA first groups IP’s decision variables based on the optimal solution to the IP’s continuous relaxation problem, and then applies a standard genetic algorithm (GA) to the subproblem for each group of variables. We compare the VGGA with the standard GA and GAs based on even variable-grouping by applying them to solve randomly generated convex quadratic knapsack problems and integer knapsack problems. Numerical results suggest that the VGGA is superior to the standard GA and GAs based on even variable-grouping both on computation time and solution quality.     

An exact algorithm for the budget-constrained multiple knapsack problem

This paper is concerned with a variant of the multiple knapsack problem (MKP), where knapsacks are available by paying certain ‘costs’, and we have a fixed budget to buy these knapsacks. Then, the problem is to determine the set of knapsacks to be purchased, as well as to allocate items into the accepted knapsacks in such a way as to maximize the net total profit. We call this the budget-constrained MKP and present a branch-and-bound algorithm to solve this problem to optimality. We employ the Lagrangian relaxation approach to obtain an upper bound. Together with the lower bound obtained by a greedy heuristic, we apply the pegging test to reduce the problem size. Next, in the branch-and-bound framework, we make use of the Lagrangian multipliers obtained above for pruning subproblems, and at each terminal subproblem, we solve MKP exactly by calling the MULKNAP code [D. Pisinger, An exact algorithm for large multiple knapsack problem, European J. Oper. Res. 114 (1999), pp. 528–541]. Thus, we were able to solve test problems with up to 160,000 items and 150 knapsacks within a few minutes in our computing environment. However, solving instances with relatively large number of knapsacks, when compared with the number of items, still remains hard. This is due to the weakness of MULKNAP to this type of problems, and our algorithm inherits this weakness as well.     

Decision-making based on approximate and smoothed Pareto curves

We consider bicriteria optimization problems and investigate the relationship between two standard approaches to solving them: (i) computing the Pareto curve and (ii) the so-called decision maker’s approach in which both criteria are combined into a single (usually nonlinear) objective function. Previous work by Papadimitriou and Yannakakis showed how to efficiently approximate the Pareto curve for problems like Shortest Path, Spanning Tree, and Perfect Matching. We wish to determine for which classes of combined objective functions the approximate Pareto curve also yields an approximate solution to the decision maker’s problem. We show that an FPTAS for the Pareto curve also gives an FPTAS for the decision-maker’s problem if the combined objective function is growth bounded like a quasi-polynomial function. If the objective function, however, shows exponential growth then the decision-maker’s problem is NP-hard to approximate within any polynomial factor. In order to bypass these limitations of approximate decision making, we turn our attention to Pareto curves in the probabilistic framework of smoothed analysis. We show that in a smoothed model, we can efficiently generate the (complete and exact) Pareto curve with a small failure probability if there exists an algorithm for generating the Pareto curve whose worst-case running time is pseudopolynomial. This way, we can solve the decision-maker’s problem w.r.t. any non-decreasing objective function for randomly perturbed instances of, e.g. Shortest Path, Spanning Tree, and Perfect Matching.     

混合差异演化算法求解多维背包问题

提出了一种求解多维0-1背包问题的混合差异演化算法,算法使用了两个主要的思想策略,即依据物品单位容积价值的高低选择物品的贪婪算法和基于二进制编码的差异演化算法。对10个测试算例进行了仿真试验,结果表明文章提出的算法可以快速找到这些测试算例的最优解,是求解多维背包问题的一种有效方法。     

A multi-start iterated local search algorithm for the generalized quadratic multiple knapsack problem

The quadratic multiple knapsack problem (QMKP) is a variant of the classical knapsack problem where multiple knapsacks are considered and the objective is to maximize a quadratic objective function subject to capacity constraints. The generalized quadratic multiple knapsack problem (G-QMKP) extends the QMKP by considering the setups, assignment conditions and the knapsack preferences of the items. In this study, a multi-start iterated local search algorithm (MS-ILS) in w the variable neighborhood descent (VND) algorithm is integrated with an adaptive perturbation mechanism is proposed to solve the G-QMKP. The multi-start implementation together with the adaptive perturbation mechanism enables the search process to explore different search regions in the search space while VND is applied to obtain high-quality solutions from the examined regions. Another remarkable feature of MS-ILS is its simplicity and adaptiveness that ease its implementation. The proposed MS-ILS is tested on G-QMKP benchmark instances derived from the literature. The results indicate that the developed MS-ILS can produce high-quality solutions for the G-QMKP. Particularly, it has been observed that the developed MS-ILS has improved the best known solutions for 35 out of 48 large-size G-QMKP instances.     

背包问题无存储冲突的并行三表算法

背包问题属于经典的NP难问题，在信息密码学和数论等研究中具有极重要的应用，将求解背包问题著名的二表算法的设计思想应用于三表搜索中，利用分治策略和无存储冲突的最优归并算法，提出一种基于EREW-SIMD共享存储模型的并行三表算法，算法使用O（2^n/4）个处理机单元和O（2^3n/8）的共享存储空间，在O（2^3n/8）时间内求解n维背包问题．将提出的算法与已有文献结论进行的对比分析表明：文中算法明显改进了现有文献的研究结果，是一种可在小于O（2^n/2）的硬件资源上，以小于O（2n/2）的计算时问求解背包问题的无存储冲突并行算法。     

RelaxMCD: Smooth optimisation for the Minimum Covariance Determinant estimator

The Minimum Covariance Determinant (MCD) estimator is a highly robust procedure for estimating the centre and shape of a high dimensional data set. It consists of determining a subsample of h points out of n which minimises the generalised variance. By definition, the computation of this estimator gives rise to a combinatorial optimisation problem, for which several approximate algorithms have been developed. Some of these approximations are quite powerful, but they do not take advantage of any smoothness in the objective function. Recently, in a general framework, an approach transforming any discrete and high dimensional combinatorial problem of this type into a continuous and low-dimensional one has been developed and a general algorithm to solve the transformed problem has been designed. The idea is to build on that general algorithm in order to take into account particular features of the MCD methodology. More specifically, two main goals are considered: (a) adaptation of the algorithm to the specific MCD target function and (b) comparison of this ‘tuned’ algorithm with the usual competitors for computing MCD. The adaptation focuses on the design of ‘clever’ starting points in order to systematically investigate the search domain. Accordingly, a new and surprisingly efficient procedure based on a suitably equivariant modification of the well-known k-means algorithm is constructed. The adapted algorithm, called RelaxMCD, is then compared by means of simulations with FASTMCD and the Feasible Subset Algorithm, both benchmark algorithms for computing MCD. As a by-product, it is shown that RelaxMCD is a general technique encompassing the two others, yielding insight into their overall good performance.     

基于采样和MIMD结构的背包问题并行算法

背包问题属于著名的NP完全问题，在信息密码学和数论研究中有着极其重要的应用。在深入分析背包问题现有并行算法的基础上，本文提出了一种基于采样和MIMD结构的背包问题并行求解算法，并给出了算法性能的理论分析和在IBMP690超级计算机上的实验结果。实验结果表明，当背包实例的维数n≥40时，本算法的并行效率可达60％以上。因此，本并行算法具有较好的可扩展性，能应用于各种MIMD结构的并行机上有效地求解背包问题。