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

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

关于大学课程表问题的研究

大学课程表问题可以表述为：如何为给定的一组课程编排一个时间表，以使得所有的学生选课要求都得到满足，并且这些课程所用的不同课时段数目最少。在本中我们首先证明了即使每位学生最多选两门课程，该问题仍然是NP-难解的，然后我们提出了求解该问题一般情形的一个启发式算法。     

基于背包模型的人员优化配置问题

运用背包模型解决油库人员在各岗位的优化配置问题,并运用贪婪算法进行求解.考虑到各人员的总工作时间的均衡性,运用反向排序的方法对原有的贪婪算法进行改进.最后,通过举例对两种算法进行评价.     

背包问题的性质研究

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

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

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

求解课程表问题的分支定界算法

本通过对中学排课程表问题的特征分析，给出了基于分支定界法的优化算法，数值试验表明这是解决一般编排中学课程表问题的有效算法。     

下料问题的优化模型及其快速算法

结合生产实际中具体的下料问题,本文建立了该类问题的优化模型,并提出下料方式的遴选三准则,即高利用率优先准则,长度优先准则和时间优先准则.运用本文的算法对一维下料的利用率高达99.6%,机器时间4秒.对二维的利用率为98.9%,机器时间约7秒.     

关于最大权k－子集分拆问题

对给定规模为ｎ的集合Ｓ，其每一个规模至多为ｋ的子集对应一个权．本文研究如何将Ｓ分为　个互不相交的规模至多为ｋ的子集且满足权和最大的问题．我们证明了该问题当ｋ＝２时是多项式时间可解的；当ｋ≥３时为ＮＰ－完全的；同时给出了一个Ｏ（ｎ￣（ｋ＋１））时间的启发式算法，所得到的解与最优解之比不小于１／ｋ．     

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

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.     

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

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

基于遗传算法的大学课程表问题研究

课程表问题是时间表问题之一 ,也是 NP难问题 .根据大学授课形式的特点建立了大学课程表问题的数学模型 ,给出了求解该问题的遗传算法 .根据模型和大学课程表问题的特点设计了一种全新的编码 ,提出了一种新形式的交叉方式 .实验结果表明该方法是可行和有效的 .     

An improved algorithm for selecting <Emphasis Type="Italic">p</Emphasis> items with uncertain returns according to the minmax-regret criterion

We consider the problem of selecting a subset of p investments of maximum total return out of a set of n available investments with uncertain returns, where uncertainty is represented by interval estimates for the returns, and the minmax regret objective is used. We develop an algorithm that solves this problem in O(min{p,n–p}n) time. This improves the previously known complexity O(min{p,n–p}²n).This research has been supported by the Spanish Science and Technology Ministry and FEDER Grant No. BFM2002-04525-C02-02.Received: October 2002 / Accepted: September 2003     

An efficient alorithm for the general multiple-choice knapsack problem (GMKP)

A common problem frequently faced by business firms and individual investors is to select a few investment opportunities from many available possibilities. This problem, in its simplest form, can be modeled as a 0–1 knapsack problem. In a more general investment scenario, however, we obtain a model which is a general knapsack problem with a multiple-choice constraint. To solve this problem, an efficient enumerative algorithm is developed. The algorithm includes an efficient procedure to solve the LP-relaxed problem, a reduction algorithm which may allow the initial fixing of some of the variables, and various other implicit enumeration criteria derived from the group problem. Extensive computational experience illustrates the efficiency of the algorithm and related results.     

滑雪场最佳收益问题的数学模型

为了评估冬季旅游资源开发获得的经济效益,以长春市莲花山滑雪场为研究对象,采用线性规划法研究滑雪场的最佳经济收益.研究表明:2008年冬季,莲花山滑雪场按照滑雪每人每天120元来估算,其一个冬季的经济收益仅为450万元.为了更多地招揽顾客,雪场又设计出四种其他的收费方式.针对这四种收费方式进行定价分析和收益分析,通过13个约束条件建立了滑雪场最佳收益的优化模型评估得到莲花山滑雪场的最佳经济收益为684万元,这一结果与2010年冬季莲花山滑雪场的收益基本相符.研究结果为政府部门决策以及莲花山风景区的旅游资源管理与开发提供参考.     

A note on the solution of group knapsack problems

Using the Nicholson principle the algorithm of Shapiro for solving group knapsack problems is improved. An approximation method is derived and numerical results are presented. The solution of the approximation method will be characterized.     

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

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

Securitization of Financial Assets: Approximation in Theory and Practice

Asset-Backed Securitization (ABS) is an emerging sector of today banks' business. It represents an effective tool to turn unrated assets, such as commercial papers or lease contracts, into marketable financial products through the issuance of special notes, namely the asset-backed securities.In this paper we analyze the problem of optimally selecting the assets to be converted into notes with respect to scenarios motivated by real-world problems. In particular, we study the case in which the assets amortization rule is characterized by constant periodic principal installments instead of the more classical amortization rule based on constant general (principal plus interests) installments. We show the computational advantages and the practical implications of this choice. The particular shape of the outstanding principal for the case of constant principal installments is exploited in the solution of a general model which selects assets at different dates.Four approximation algorithms, based on LP-relaxation and on the implicit knapsack structure of the problem, are proposed for this general model. From a theoretical point of view we analyze the exact worst-case behavior of these algorithms compared to the optimal solution. Computational experiments are performed for a practical scenario suggested by a leasing bank. The results show that the proposed approximation algorithms are, on average, highly efficient and effective.     

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 fractional algorithm for optimal cutting of lumber into dimension parts

A fractional algorithm is described which optimizes the cutting of boards or lumber into dimension parts. The model is an extension of previously developed models and is purposely designed for cutting scenarios where the customer order for the dimension parts can be satisfied within a given range, i.e., flexible rather than exact demand. An illustrative example is presented simply to describe the model and compare results between the standard procedure and the modified procedure proposed in this paper.