一类连续可分离背包问题的直接算法

对于一类带有单个线性约束以及盒约束的一般连续可分离二次背包问题给出了一种直接的算法,根据模型特有的结构,通过调节线性约束的拉格朗日乘子λ 的取值范围,以及在算法求解过程中通过判断目标函数一次项中的变量是否在盒约束范围内,来逐步确定所有变量的最优值, 并通过该算法得到的实验结果与其他算法的比较,说明了这种算法的可行性和有效性．     

可卸货的移动在线背包问题模型和算法

提出可卸货的移动在线背包问题,即一个装有货物的背包从起点出发对n个指定需求点提供服务,将所装货物在每个点按已知需求量卸下,并将该点数量无法预知的待取回货物装入背包带回起点,如何决策背包对需求点的服务次序及途经需求点是否取回货物,使得取回的货物数量尽可能的多。针对该问题,采用在线理论和方法,建立模型并设计在线算法F,分析需求点待取回的货物数量与背包将该需求点的货物卸下后剩余承载量的差的不同情形,证明F的竞争比并对竞争比的影响因素进行分析,结果表明载货下限越大、需求点个数越多、需求点待取回货物总数越多,算法F的执行效果越好。     

二次规划的直接椭球算法

本文对凸二次规划问题，给出了一个直接椭球算法，并证明了算法的复杂度为Ｏ（ｎ４Ｌ）．     

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

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

二次规划的一种简易算法

本文对二次规划的单纯形算法，从算法到收敛条件均加以改进，得到更简易的程序和收敛准则。     

二次分配问题的大洪水算法求解

大洪水算法是一种求解组合优化问题的独特方法,该方法通过模拟洪水上涨的过程来达到求解一些组合优化难题的目的.本文运用该方法求解二次分配问题(QAP),设计了相应的算法程序,并对QAPLIB(二次分配基准问题库)中的算例进行了实验测试,结果表明,大洪水算法可以快速有效地求得二次分配问题的优化解,是求解二次分配问题的一个新的较好方案.     

多背包问题的半定松驰算法

The multiple knapsack problem denoted by MKP (B,S,rn,n) can be defined as follows. A set B of n items and a set S of rn knapsacks are given such that each item j has a profit pi and weight wj,and each knapsack i has a capacity Ci. The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks. MKP (B,S,m,n) is strongly NP-Complete and no polynomial time approximation algorithm can have an approximation ratio better than 0.5. In the last ten years,semi-definite programming has been empolyed to solve some combinatorial problems successfully. This paper firstly presents a semi-definite relaxation algorithm (MKPS) for MKP (B,S,rn,n). It is proved that MKPS have a approximation ratio better than 0. 5 for a subclass of MKP (B,S,m,n) with n≤100, m≤5 and max^nj=1{wj}/min^mi=1={Ci}≤2/3.     

一种推广的求解可分离凸优化问题的黄金比率邻近ADMM算法

ADMM算法是求解可分离凸优化问题的经典算法之一,但其无法保证原始迭代序列的收敛性且其子问题计算量很大.为了保证该算法所有迭代点列的全局收敛性及提高计算效率,采用凸组合技术的黄金比率邻近ADMM算法被提出,其中凸组合因子Ψ是关键参数.本文在黄金比率邻近ADMM算法的基础上,扩大了凸组合因子Ψ的取值范围,提出了收敛步长范围更广的推广黄金比率邻近ADMM算法.并在一定的假设下,证明了算法的全局收敛性及函数值残差和约束违反度在遍历意义下的O(1/N)次线性收敛速度.以及,当目标函数中任意一个函数强凸时,证明了算法在遍历意义下的O(1/N²)收敛率.最后,本文通过数值试验表明推广算法的有效性.     

背包问题的性质研究

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

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.     

On the continuous quadratic knapsack problem

We introduce a new algorithm for the continuous bounded quadratic knapsack problem. This algorithm is motivated by the geometry of the problem, is based on the iterative solution of a series of simple projection problems, and is easy to understand and implement. In practice, the method compares favorably to other well-known algorithms (some of which have superior worst-case complexity) on problem sizes up ton = 4000.     

An O(n) algorithm for quadratic knapsack problems

An algorithm is presented which solves bounded quadratic optimization problems with n variables and one linear constraint in at most O(n) steps. The algorithm is based on a parametric approach combined with well-known ideas for constructing efficient algorithms. It improves an O(n log n) algorithm which has been developed for a more restricted case of the problem.     

Local minima for indefinite quadratic knapsack problems

We consider the complexity of finding a local minimum for the nonconvex Quadratic Knapsack Problem. Global minimization for this example of quadratic programming is NP-hard. Moré and Vavasis have investigated the complexity of local minimization for the strictly concave case of QKP; here we extend their algorithm to the general indefinite case. Our main result is an algorithm that computes a local minimum in O(n(logn)²) steps. Our approach involves eliminating all but one of the convex variables through parametrization, yielding a nondifferentiable problem. We use a technique from computational geometry to address the nondifferentiable problem.Supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, Department of Energy, under contract W-31-109-Eng-38, in part by a Fannie and John Hertz Foundation graduate fellowship, and in part by Department of Energy grant DE-FG02-86ER25013.A000.     

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.     

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.     

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)$.