Ratios of optimal values of objective functions of the knapsack problem and its linear relaxation

The ratios of the values of objective functions for optimal solutions of linear and integer knapsack problems are considered. Estimates for these ratios are obtained. One-dimensional and multi-dimensional knapsack problems with Boolean variables are studied experimentally. For these problems, a hypothesis is formulated on the asymptotic behavior of the ratio as the number of variables grows.     

Exact solution of the robust knapsack problem

We consider an uncertain variant of the knapsack problem in which the weight of the items is not exactly known in advance, but belongs to a given interval, and an upper bound is imposed on the number of items whose weight differs from the expected one. For this problem, we provide a dynamic programming algorithm and present techniques aimed at reducing its space and time complexities. Finally, we computationally compare the performances of the proposed algorithm with those of different exact algorithms presented so far in the literature for robust optimization problems.     

求解背包问题的更贪心粒子群算法

将粒子群算法与贪心思想相融合,提出一种用于求解0/1背包问题的更贪心混合粒子群算法。对超过背包重量约束的粒子的处理措施是去掉已经装进去且性价比最差的物品,直至满足重量约束为止,这种思想在改善粒子质量的同时避免了通常罚函数方法中敏感的参数选择问题;对当前可行粒子的处理措施是将还未装入背包且性价比最好的物品装进背包,直至不能装为止。通过与文献中基于经典算例的计算结果比较表明,更贪心粒子群算法无论在寻优能力、计算速度和稳定性方面都超过了文献中提到的混合遗传算法（HGA）、贪心遗传算法（GGA）和混合粒子群算法（GBPSOA）。     

Solving 0-1 knapsack problem by greedy degree and expectation efficiency

It is well known that 0-1 knapsack problem (KP01) plays an important role in both computing theory and real life application. Due to its NP-hardness, lots of impressive research work has been performed on many variants of the problem. Inspired by region partition of items, an effective hybrid algorithm based on greedy degree and expectation efficiency (GDEE) is presented in this paper. In the proposed algorithm, initially determinate items region, candidate items region and unknown items region are generated to direct the selection of items. A greedy degree model inspired by greedy strategy is devised to select some items as initially determinate region. Dynamic expectation efficiency strategy is designed and used to select some other items as candidate region, and the remaining items are regarded as unknown region. To obtain the final items to which the best profit corresponds, static expectation efficiency strategy is proposed whilst the parallel computing method is adopted to update the objective function value. Extensive numerical investigations based on a large number of instances are conducted. The proposed GDEE algorithm is evaluated against chemical reaction optimization algorithm and modified discrete shuffled frog leaping algorithm. The comparative results show that GDEE is much more effective in solving KP01 than other algorithms and that it is a promising tool for solving combinatorial optimization problems such as resource allocation and production scheduling.     

基于贪婪离散类电磁机制算法求解背包问题

针对基本类电磁机制算法不能够有效解决离散型的背包问题,提出了一种贪婪离散类电磁机制算法。首先,提出一种交叉操作;然后,利用提出的交叉操作对基本类电磁机制算法中的合力计算公式和粒子移动方法进行修改,使其能够适用于离散型问题;最后,引入贪婪算法的机制来处理经过类电磁机制算法迭代得到的解,使这些解满足背包问题的约束条件。通过对3个经典的背包测试问题进行的测试结果表明:该算法可以解决离散型的背包问题,并且具有较优的求解性能。     

求解0-1背包问题的混合贪婪遗传算法

求解0-1背包问题（KP）的最优解的时候,传统遗传算法（GA）的局部求精能力不足而简单局部搜索算法的全局探索能力有限,针对上述问题,将这两个算法整合并提出了混合贪婪遗传算法（HGGA）。在GA全局搜索框架下增加局部搜索模块,并改进传统仅基于物品价值密度的修复算子,增加基于物品价值的贪婪混合选项,从而加速寻优过程。HGGA一方面引导种群在进化的优质解空间中展开精细搜索,另一方面依靠GA的经典操作算子开拓全局搜索空间,从而达到算法求精能力和开拓能力的良好平衡。HGGA分别在三组数据上做了测试,结果表明在第一组15个测试用例中的12个上,HGGA能够百分百找到最优解,成功率达到80%;在第二组小规模数据集上,HGGA的性能明显好于其他同类GA和其他元启发算法;在第三组大规模数据集上,HGGA较其他元启发式算法具有更好的稳定性和高效性。     

贪婪封装二进制差分进化算法求解高维背包问题

提出一种处理高维背包问题(KP)的贪婪封装二进制差分进化算法(GPBDE),并设计了一种贪婪封装的修补策略处理不可行解.为了提高种群的多样性及算法的全局搜索能力,对适应度较低的个体执行对偶变换.数值实验选取4种KP对GPBDE的优化能力进行测试,并将所提出的算法与4种同类算法进行比较,结果表明,GPBDE具有较强的寻优和约束处理能力,且收敛速度较快.     

基于绝对贪心和预期效率的0-1背包问题优化

With analysis and research the traditional theory of solving knapsack problem, and then to optimize enigmatical knapsack problems, this paper proposed a new algorithm based on the absolute greedy and expected efficiency strategy. Through the three sets of simulation experiments, it shows that the algorithm can solve a class of knapsack problems and it is superior to greedy algorithm, backtracking algorithm, dynamic programming algorithm, branch and bound algorithm. The convergence speed is ten times as the artificial glowworm swam algorithm by comparing with these two algorithms. Finally, it analyzed discrete degree of data and determined an adaptive scope of the algorithm.     

Exact and approximate solutions of the container ship stowage problem

This paper deals with a stowage plan for containers in a container ship. Containers on board a container ship are placed in stacks, located in many bays. Since the access to the containers is only from the top of the stack, a common situation is that contianers designated for port J must be unloaded and reloaded at port I (before J) in order to access containers below them, designated for port I. This operation is called “shifting”. A container ship calling many ports, may encounter a large number of shifting operations, some of which can be avoided by efficient stowage planning. In general, the stowage plan must also take into account stability and strength requirements, as well as several other constraints on the placement of containers. In this paper we deal with stowage planning in order to minimize the number of shiftings, without considering stability constraints. First, a 0–1 binary linear programming formulating is presented that can find the optimal solution for stowage in a single rectangular bay of a vessel calling a given number of ports, assuming that the number of constainers to ship is known in advance. This model was successfully implemented using the GAMS software system. It was found, however, that finding the optimal solution using this model is quite limited, because of the large number of binary variables needed for the formulation. For this reason, several alternative heuristic algorithms were developed. The one presented here is based on a “reduced” transportation matrix. Containers with the same source and destination ports are stowed in full stacks as much as possible, and only the remaining containers are allocated by the binary linear programming model. This approach often allows the stowage planning of a much larger number of containers than using the exact formulation.     

Exact algorithms for the two-dimensional guillotine knapsack

The two-dimensional knapsack problem requires to pack a maximum profit subset of “small” rectangular items into a unique “large” rectangular sheet. Packing must be orthogonal without rotation, i.e., all the rectangle heights must be parallel in the packing, and parallel to the height of the sheet. In addition, we require that each item can be unloaded from the sheet in stages, i.e., by unloading simultaneously all items packed at the same either y or x coordinate. This corresponds to use guillotine cuts in the associated cutting problem.In this paper we present a recursive exact procedure that, given a set of items and a unique sheet, constructs the set of associated guillotine packings. Such a procedure is then embedded into two exact algorithms for solving the guillotine two-dimensional knapsack problem. The algorithms are computationally evaluated on well-known benchmark instances from the literature.The C++ source code of the recursive procedure is available upon request from the authors.     

Learning automata-based solutions to the optimal web polling problem modelled as a nonlinear fractional knapsack problem

We consider the problem of polling web pages as a strategy for monitoring the world wide web. The problem consists of repeatedly polling a selection of web pages so that changes that occur over time are detected. In particular, we consider the case where we are constrained to poll a maximum number of web pages per unit of time, and this constraint is typically dictated by the governing communication bandwidth, and by the speed limitations associated with the processing. Since only a fraction of the web pages can be polled within a given unit of time, the issue at stake is one of determining which web pages are to be polled, and we attempt to do it in a manner that maximizes the number of changes detected. We solve the problem by first modelling it as a stochastic nonlinear fractional knapsack problem. We then present an online learning automata (LA) system, namely, the hierarchy of twofold resource allocation automata (H-TRAA), whose primitive component is a twofold resource allocation automaton (TRAA). Both the TRAA and the H-TRAA have been proven to be asymptotically optimal. Finally, we demonstrate empirically that the H-TRAA provides orders of magnitude faster convergence compared to the learning automata knapsack game (LAKG) which represents the state-of-the-art for this problem. Further, in contrast to the LAKG, the H-TRAA scales sub-linearly. Based on these results, we believe that the H-TRAA has also tremendous potential to handle demanding real-world applications, particularly those which deal with the world wide web.     

An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem

Permutation flowshop scheduling problems (PFSPs) and, in particular, the variant with the objective of minimizing makespan have received an enormous attention in scheduling research and combinatorial optimization. As a result, the algorithmic approaches to this PFSP variant have reached extremely high performance. Currently, one of the most effective algorithm for this problem is a structurally rather simple iterated greedy algorithm. In this paper, we explore the possibility of re-optimizing partial solutions obtained after the solution destruction step of the iterated greedy algorithm. We show that with this extension, the performance of the state-of-the-art algorithm for the PFSP under makespan criterion can be significantly improved and we give experimental evidence that the local search on partial solutions is the key component for the high performance of the algorithm.     

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.     

Analysis of the knapsack problem using L-partition

A periodicity region of the knapsack problem with a parameter in the right-hand side is analyzed using a partition of a finite-dimensional space. Upper bounds are constructed on the cardinality of L-covers and on the number of regular cuts required to solve the problem.Translated from Kibernetika, No. 2, pp. 38–43, March–April, 1991.     

Sensitivity analysis of the knapsack problem: a negative result

We consider the Blair hypothesis on the computational complexity of the problem connected with optimal solutions to the so-called adjacent knapsack problems. The hypothesis is proved for generalized adjacent knapsack problems.     

Heuristic algorithms for the multiple knapsack problem

Given a set of items, each having a profit and a weight, and a set of knapsacks, each having a capacity, we consider the problem of inserting items into the knapsacks in such a way that the subset of inserted, items has the maximum total profit without the total weight in each knapsack exceeding its capacity. The best algorithms for the exact solution of this problem can be applied, with acceptable running times, to cases with a maximum of 200 items and 4 knapsacks, but real world applications (such as, for example, cutting stock and loading problems), often involving a greater number of variables, call for the use of heuristics. This paper presents methods for finding suboptimal, solutions to the Multiple Knapsack Problem. An extensive computational experience was carried out both on small-size and large-size randomly generated problems; the results indicate that the proposed algorithms have a satisfactory behaviour with regard both to running times and quality of the solutions found. A Fortrans IV implementation of the algorithms is given.     

Learning automata-based solutions to the nonlinear fractional knapsack problem with applications to optimal resource allocation.

This paper considers the nonlinear fractional knapsack problem and demonstrates how its solution can be effectively applied to two resource allocation problems dealing with the World Wide Web. The novel solution involves a "team" of deterministic learning automata (LA). The first real-life problem relates to resource allocation in web monitoring so as to "optimize" information discovery when the polling capacity is constrained. The disadvantages of the currently reported solutions are explained in this paper. The second problem concerns allocating limited sampling resources in a "real-time" manner with the purpose of estimating multiple binomial proportions. This is the scenario encountered when the user has to evaluate multiple web sites by accessing a limited number of web pages, and the proportions of interest are the fraction of each web site that is successfully validated by an HTML validator. Using the general LA paradigm to tackle both of the real-life problems, the proposed scheme improves a current solution in an online manner through a series of informed guesses that move toward the optimal solution. At the heart of the scheme, a team of deterministic LA performs a controlled random walk on a discretized solution space. Comprehensive experimental results demonstrate that the discretization resolution determines the precision of the scheme, and that for a given precision, the current solution (to both problems) is consistently improved until a nearly optimal solution is found--even for switching environments. Thus, the scheme, while being novel to the entire field of LA, also efficiently handles a class of resource allocation problems previously not addressed in the literature.