0-1背包问题的蜂群优化算法

在项目决策与规划、资源分配、货物装载、预算控制等工作中,提出了0-1背包问题.0-1背包问题是组合优化中的典型NP难题,根据群集智能原理,给出一种基于蜂群寻优思想的新算法—蜂群算法,并针对0-1背包问题进行求解.经实验仿真并与蚁群算法计算结果作对比,验证了算法在0-1背包问题求解上的有效性和更快的收敛速度.     

关于销售集团投资设置销售分店问题的IP模型

针对一个实际投资实例建立了一个基于 0 -1背包问题的数学模型 ,并利用多个算法加以求解 ,并对结果进行了比较 .该模型具有很高的应用价值和参考价值 .     

求解具有单连续变量背包问题的精确算法

具有单连续变量背包问题(KPC)是标准0-1背包问题(0-1KP)的一个新颖扩展形式,由于其中的背包载重不再固定不变,而是由一个连续变量进行连续调整,因此KPC是一个比0-1KP更难求解的背包问题.首先提出了一个带有实函数的变载重背包问题(0-1KP(Σ,f)),基于动态规划法给出了求解它的一般方法;然后,利用放缩法将KPC中的连续变量离散化,在建立KPC的一个新数学模型的基础上,将它转化成为0-1KP(Σ,f)的一个特例,利用0-1KP(Σ,f)的求解方法给出了KPC的一个简单且易于实现的精确算法.     

求解多维0-1背包问题的人工鱼群算法

对于多维0-1背包问题,国内外学者提出了诸如模拟退火、遗传算法、蚁群算法以及其他启发式算法.给出一种新的智能寻优方法——人工鱼群算法.算法通过各人工鱼的局部寻优,从而在群体中体现出全局最优.描述了人工鱼群算法的具体步骤并编程实现,通过多维背包算例进行了求解测试,获得了满意的效果.     

非线性0-1规划问题的混沌粒子群算法

针对非线性0-1规划问题,提出了一种混沌粒子群优化算法.该算法利用罚函数法将非线性0-1规划问题处理为无约束的0-1规划问题,引入了混沌策略来初始化种群,增加其多样性,为预测算法是否出现早熟现象,采用了适应度方差.数值实验表明,提出的算法是求解非线性0-1规划问题的一种有效且可行的全局优化算法.     

哈明距离下圈图上1-重心问题的反问题

主要讨论哈明距离下圈图上1-重心问题的反问题.1-重心问题的反问题主要研究如何尽可能少地改变网络中的参数值,使得给定的顶点到其它顶点的加权距离之和不超过一个给定的上界.通过将该问题转化为0-1背包问题,证明了在哈明距离下该问题是NP困难的,并运用动态规划的思想,在考虑改变边的长度的情况下,对圈图进行了求解.     

一种求解分组0-1背包问题的动态规划法

研究了分组0-1背包问题,提出了一种动态规划解决方法,在物品总数为n个和背包承重量为W时,递推过程的复杂度为O(nW),回溯过程的复杂度为O(n).计算实例表明利用该方法易于找到最优解.     

两阶段特殊结构混合0-1规划的分解算法

本文介绍了一种用于求解具有特殊结构的两阶段混合0-1规划问题的原始-对偶分解算法,并以CPLEX软件作为核心求解器将算法实现.该算法将原问题分解成两个相对简单的子问题,较传统分解算法有更平衡的分解结构和收敛性.实验数据表明,该算法在求解较大规模、稀疏度较大、耦合度较大的复杂两阶段下三角结构混合0-1规划问题时,相比CPLEX提供的分枝剪枝法,在时间效率上有明显提高.算法最后通过固定0-1变量的取值可以得到满足管理精度要求的近似最优解.     

可分离的二次背包问题的一种直接算法

研究了可分离二次背包问题的一种直接算法.此类背包问题的目标函数是二次的,且含有严格的一次项,其不等式约束是线性的.给出所求模型的一般形式,经过预处理该模型,最终归为求解两类问题（P1）和（P2）.重点是求解（P2）问题的最优解,通过分析（P2）问题的结构特点,假设固定一次项后问题的最优解和相应不等式的拉格朗日乘子已求出,通过比较拉格朗日乘子和（P2）问题的一次项系数来调节λ的大小,从而求出（P2）问题的最优解.对于（P1）问题,改进了Bretthauer和Shetty给出的算法（Bretthauer K M,Shetty B.A pegging algorithm for the nonlinear resource allocation problem.Computers and Operations Research,2002,29（5）：505-527）.此算法的计算复杂性为O（n）.数值算例表明,将这种固定变量算法和文中的定理5结合起来,能够快速有效地求解此类更一般的二次背包问题.     

非线性0-1规划问题的蜂群算法

针对非线性0-1规划,提出采用一种智能优化算法——蜂群算法进行求解.描述了蜂群算法的实现过程,并在计算机上编程予以实现.经大量实例测试,并与其它算法进行比较,获得了满意的结果.说明了蜂群算法在解决非线性0-1规划问题上的可行性与有效性,同时具有良好的优化能力..     

Extending Dantzig's bound to the bounded multiple-class binary Knapsack problem

 The bounded multiple-class binary knapsack problem is a variant of the knapsack problem where the items are partitioned into classes and the item weights in each class are a multiple of a class weight. Thus, each item has an associated multiplicity. The constraints consists of an upper bound on the total item weight that can be selected and upper bounds on the total multiplicity of items that can be selected in each class. The objective is to maximize the sum of the profits associated with the selected items. This problem arises as a sub-problem in a column generation approach to the cutting stock problem. A special case of this model, where item profits are restricted to be multiples of a class profit, corresponds to the problem obtained by transforming an integer knapsack problem into a 0-1 form. However, the transformation proposed here does not involve a duplication of solutions as the standard transformation typically does. The paper shows that the LP-relaxation of this model can be solved by a greedy algorithm in linear time, a result that extends those of Dantzig (1957) and Balas and Zemel (1980) for the 0-1 knapsack problem. Hence, one can derive exact algorithms for the multi-class binary knapsack problem by adapting existing algorithms for the 0-1 knapsack problem. Computational results are reported that compare solving a bounded integer knapsack problem by transforming it into a standard binary knapsack problem versus using the multiple-class model as a 0-1 form. Received: May 1998 / Accepted: February 2002-09-04 Published online: December 9, 2002 Key Words. Knapsack problem – integer programming – linear programming relaxation     

An Algorithm for the 0-1 Equality Knapsack Problem

The 0-1 knapsack problem is a linear integer-programming problem with a single constraint and binary variables. The knapsack problem with an inequality constraint has been widely studied, and several efficient algorithms have been published. We consider the equality-constraint knapsack problem, which has received relatively little attention. We describe a branch-and-bound algorithm for this problem, and present computational experience with up to 10,000 variables. An important feature of this algorithm is a least-lower-bound discipline for candidate problem selection.     

An iterative variable-based fixation heuristic for the 0-1 multidimensional knapsack problem

An iterative scheme which is based on a dynamic fixation of the variables is developed to solve the 0-1 multidimensional knapsack problem. Such a scheme has the advantage of generating memory information, which is used on the one hand to choose the variables to fix either permanently or temporarily and on the other hand to construct feasible solutions of the problem. Adaptations of this mechanism are proposed to explore different parts of the search space and to enhance the behaviour of the algorithm. Encouraging results are presented when tested on the correlated instances of the 0-1 multidimensional knapsack problem.     

Time-Constrained Restless Bandits and the Knapsack Problem for Perishable Items (Extended Abstract)

Motivated by a food promotion problem, we introduce the Knapsack Problem for Perishable Items (KPPI) to address a dynamic problem of optimally filling a knapsack with items that disappear randomly. The KPPI naturally bridges the gap and elucidates the relation between the PSPACE-hard restless bandit problem and the NP-hard knapsack problem. Our main result is a problem decomposition method resulting in an approximate transformation of the KPPI into an associated 0-1 knapsack problem. The approach is based on calculating explicitly the marginal productivity indices in a generic finite-horizon restless bandit subproblem.     

Simple solution methods for separable mixed linear and quadratic knapsack problem

Quadratic knapsack problem has a central role in integer and nonlinear optimization, which has been intensively studied due to its immediate applications in many fields and theoretical reasons. Although quadratic knapsack problem can be solved using traditional nonlinear optimization methods, specialized algorithms are much faster and more reliable than the nonlinear programming solvers. In this paper, we study a mixed linear and quadratic knapsack with a convex separable objective function subject to a single linear constraint and box constraints. We investigate the structural properties of the studied problem, and develop a simple method for solving the continuous version of the problem based on bi-section search, and then we present heuristics for solving the integer version of the problem. Numerical experiments are conducted to show the effectiveness of the proposed solution methods by comparing our methods with some state of the art linear and quadratic convex solvers.     

The 0-1 Knapsack problem with a single continuous variable

Specifically we investigate the polyhedral structure of the knapsack problem with a single continuous variable, called the mixed 0-1 knapsack problem. First different classes of facet-defining inequalities are derived based on restriction and lifting. The order of lifting, particularly of the continuous variable, plays an important role. Secondly we show that the flow cover inequalities derived for the single node flow set, consisting of arc flows into and out of a single node with binary variable lower and upper bounds on each arc, can be obtained from valid inequalities for the mixed 0-1 knapsack problem. Thus the separation heuristic we derive for mixed knapsack sets can also be used to derive cuts for more general mixed 0-1 constraints. Initial computational results on a variety of problems are presented. Received May 22, 1997 / Revised version received December 22, 1997 Published online November 24, 1998     

Scatter Search for the 0–1 Multidimensional Knapsack Problem

The evolutionary metaheuristic called scatter search has been applied successfully to optimization problems for several years. In this paper, we apply the scatter search technique to the well-known 0–1 multidimensional knapsack problem. We propose a new relaxation-based diversification generator, which produces an initial population with elite solutions. The computational results obtained for a set of classic and correlated instances clearly show that (1) this generator can also be used as a heuristic for solving the multidimensional knapsack problem; (2) using the population produced by our generator as a starting point for the scatter search algorithm leads to better performance. We also enhance the scatter search algorithm by integrating memory and by using adapted intensification phases. Overall, the results are interesting and competitive compared to other population-based algorithms, such as genetic algorithms.