单背包问题的半定松弛算法

首先给出了单背包问题的秩1半定松驰规划，然后在此基础上提出了求解该问题的半定松驰随机算法KSSD。分析结果表明：（1）当σ＞0.19时，算法KSSD的近似比就会超过0.27。（2）算法KSSD中的参数θ对某种大规模情形将不起作用。     

箱覆盖问题的半定松驰算法

箱覆盖问题是NP困难问题中的经典问题，得到了广泛地研究，九十年代以来，半定松驰策略被用来求解组合优化问题，取得了很好的结果[13]，本文首次给箱覆盖问题的半定松驰算法，算法的理论分析结果表明它适合于求解大规模的箱覆盖问题。     

二次半定规划问题及其投影收缩算法

In this paper,we discuss the relations among the quadratic semi-definite programming problem,the linear semi-definite porgramming and the linearquadratic semi-definite programming problem.The duality theories are presented.After proving the equivalence of its optimality conditions and monotonous linear variational inequalities,we use the projection and contraction algorithms to solve(QSDP),We present the algorithms and its convergence analysis.     

求解最大割问题的半定规划松驰的序列线性规划方法

本文基于最大割问题的半定规划松弛,利用矩阵分解的方法给出了与半定规划松弛等价的非线性规划模型,提出一种序列线性规划方法求解该模型.并在适当的条件下,证明了算法的全局收敛性.数值实验表明:序列线性规划方法在时间上要优于半定规划的内点算法.所以序列线性规划方法能更有效地求解大规模的最大割问题的半定规划松弛.     

模糊人工蜂群算法的多选择多维背包问题求解

针对传统人工蜂群算法早熟收敛问题,基于模糊化处理和蜂群寻优的特点,提出一种模糊人工蜂群算法。将模糊输入输出机制引入到算法中来保持蜜源访问概率的动态更新。根据算法计算过程中的不同阶段对蜜源访问概率有效调整,避免算法陷入局部极值。通过对多选择多维背包问题的仿真实验和与其他算法的比较,表明本算法可行有效,有良好的鲁棒性。     

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

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

半定互补问题的全局收敛算法

基于某一效益函数,本文给出了求解半定互补问题的下降算法,并在适当的条件下证得其全局收敛性.     

半定优化与半光滑牛顿算法

本文讨论半光滑牛顿算法的基本概念与其在求解半定优化问题中的应用．特别地，该算法可用于求解线性或非线性半定互补问题．本文同时综述最近在矩阵方程，增广拉格朗日公式和半定优化稳定性方面的、源于半光滑牛顿算法的理论成果．     

背包问题的性质研究

本主要研究背包问题的一般性质和解的性质。     

电路二等分问题的一个强化半定松驰模型

由于电路二等分问题在超大规模集成电路 (VLSI)设计中的基础地位 ,电路二等分半定松驰问题一直引人关注 .能否找到更好的半定规划模型 ,使其为电路二等分问题提供一个更好的下界 ,成为一个重要的研究方向 ;本文在已有半定规划松驰模型的基础上 ,通过增加非线性约束 ,得出电路二等分问题的等价模型 ,再利用提升技巧 ,得到一个强化半定规划松驰模型 .理论证明该模型给出了原有问题的一个更好的下界 ,数值实验也说明了这一点 .     

An exact algorithm for the fixed-charge multiple knapsack problem

We formulate the fixed-charge multiple knapsack problem (FCMKP) as an extension of the multiple knapsack problem (MKP). The Lagrangian relaxation problem is easily solved, and together with a greedy heuristic we obtain a pair of upper and lower bounds quickly. We make use of these bounds in the pegging test to reduce the problem size. We also present a branch-and-bound (B&B) algorithm to solve FCMKP to optimality. This algorithm exploits the Lagrangian upper bound as well as the pegging result for pruning, and at each terminal subproblem solve MKP exactly by invoking MULKNAP code developed by Pisinger [Pisinger, D., 1999. An exact algorithm for large multiple knapsack problems. European Journal of Operational Research 114, 528–541]. As a result, we are able to solve almost all test problems with up to 32,000 items and 50 knapsacks within a few seconds on an ordinary computing environment, although the algorithm remains some weakness for small instances with relatively many knapsacks.     

Upper and lower bounding procedures for the multiple knapsack assignment problem

We formulate the multiple knapsack assignment problem (MKAP) as an extension of the multiple knapsack problem (MKP), as well as of the assignment problem. Except for small instances, MKAP is hard to solve to optimality. We present a heuristic algorithm to solve this problem approximately but very quickly. We first discuss three approaches to evaluate its upper bound, and prove that these methods compute an identical upper bound. In this process, reference capacities are derived, which enables us to decompose the problem into mutually independent MKPs. These MKPs are solved euristically, and in total give an approximate solution to MKAP. Through numerical experiments, we evaluate the performance of our algorithm. Although the algorithm is weak for small instances, we find it prospective for large instances. Indeed, for instances with more than a few thousand items we usually obtain solutions with relative errors less than 0.1% within one CPU second.     

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

研究了可分离二次背包问题的一种直接算法.此类背包问题的目标函数是二次的,且含有严格的一次项,其不等式约束是线性的.给出所求模型的一般形式,经过预处理该模型,最终归为求解两类问题（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结合起来,能够快速有效地求解此类更一般的二次背包问题.     

Tabu-enhanced iterated greedy algorithm: A case study in the quadratic multiple knapsack problem

Iterated greedy search is a simple and effective metaheuristic for combinatorial problems. Its flexibility enables the incorporation of components from other metaheuristics with the aim of obtaining effective and powerful hybrid approaches. We propose a tabu-enhanced destruction mechanism for iterated greedy search that records the last removed objects and avoids removing them again in subsequent iterations. The aim is to provide a more diversified and successful search process with regards to the standard destruction mechanism, which selects the solution components for removal completely at random.     

The zero-one knapsack problem with equality constraint

The zero-one knapsack problem is a linear zero-one programming problem with a single inequality constraint. This problem has been extensively studied and many applications and efficient algorithms have been published. In this paper we consider a similar problem, one with an equality instead of the inequality constraint. By replacing the equality by two inequalities one of which is placed in the economic function, a Lagrangean relaxation of the problem is obtained. The relation between the relaxed problem and the original problem is examined and it is shown how the optimal value of the relaxed problem varies with increasing values of the Lagrangean multiplier. Using these results an algorithm for solving the problem is proposed.The paper concludes with a discussion of computational experience.     

Nonconvex piecewise linear knapsack problems

This paper considers the minimization version of a class of nonconvex knapsack problems with piecewise linear cost structure. The items to be included in the knapsack have a divisible quantity and a cost function. An item can be included partially in the given quantity range and the cost is a nonconvex piecewise linear function of quantity. Given a demand, the optimization problem is to choose an optimal quantity for each item such that the demand is satisfied and the total cost is minimized. This problem and its close variants are encountered in manufacturing planning, supply chain design, volume discount procurement auctions, and many other contemporary applications. Two separate mixed integer linear programming formulations of this problem are proposed and are compared with existing formulations. Motivated by different scenarios in which the problem is useful, the following algorithms are developed: (1) a fast polynomial time, near-optimal heuristic using convex envelopes; (2) exact pseudo-polynomial time dynamic programming algorithms; (3) a 2-approximation algorithm; and (4) a fully polynomial time approximation scheme. A comprehensive test suite is developed to generate representative problem instances with different characteristics. Extensive computational experiments show that the proposed formulations and algorithms are faster than the existing techniques.     

A polynomial algorithm for a continuous bilevel knapsack problem

In this note, we analyze a bilevel interdiction problem, where the follower’s program is a parametrized continuous knapsack. Based on the structure of the problem and an inverse optimization strategy, we propose for its solution an algorithm with worst-case complexity $O\left(n^2\right)$.     

A branch and bound algorithm for solving the multiple-choice knapsack problem

The multiple-choice knapsack problem is a binary knapsack problem with the addition of disjoint multiple-choice constraints. We describe a branch and bound algorithm based on embedding Glover and Klingman's method for the associated linear program within a depth-first search procedure. A heuristic is used to find a starting dual feasible solution to the associated linear program and a ‘pegging’ test is employed to reduce the size of the problem for the enumeration phase. Computational experience and comparisons with the code of Nauss and an algorithm of Armstrong et al. for the same problem are reported.     

LP based heuristics for the multiple knapsack problem with assignment restrictions

Starting with a problem in wireless telecommunication, we are led to study the multiple knapsack problem with assignment restrictions. This problem is NP-hard. We consider special cases and their computational complexity. We present both randomized and deterministic LP based algorithms, and show both theoretically and computationally their usefulness for large-scale problems.