经典一维装箱问题近似算法的研究进展

自20世纪70年代开始,随着计算复杂性理论的建立,近似算法逐渐成为组合优化的重要研究方向。作为第一批研究对象,装箱问题引起了组合优化领域学者的极大关注。装箱问题模型简单、拓展性强,广泛出现在各种带容量约束的资源分配问题中。除了在物流装载和材料切割等方面愈来愈重要的应用外,装箱算法的任何理论突破都关乎到整个组合优化领域的发展。直到今天,对装箱问题近似算法的研究仍如火如荼。本文主要针对一维模型,简述若干经典Fit算法的发展历程,分析基于线性规划松弛的近似方案的主要思路,总结当前的研究现状并对未来的研究提供一些参考建议。     

三维装箱问题的模型与改进遗传算法

三维装箱问题是一类NP-hard的组合优化问题,构建一个适当的数学模型并设计高效快速的算法具有重要的理论和现实意义.该文将箱子空间划分为立方体单元,依此构建三维装箱问题的混合整数规划模型,并通过改进遗传算法求解,剔除大量不可行解提高了收敛速度.实验结果表明此算法运算过程及结果稳定,具有较强的实际应用价值,能有效解决复杂的三维装箱问题.     

负载均衡问题

自Ron Graham20世纪60年代发表第一篇负载均衡算法的论文以来,平行机排序作为组合优化近似算法理论的首个问题引起了学界的广泛兴趣,其本身研究的不断深化也一路见证了该领域的发展历程.介绍负载均衡问题的来龙去脉,特别是作者所在团队在相关问题的研究进展,从算法和复杂性不同的视角分析经典问题的计算本质,并对未来的研究提出一些建议.     

装箱问题的算法及最新进展

装箱问题在经济社会发展中扮演着重要的角色,该问题研究的是寻找较好的布局方式,尽可能实现利益的最大化.装箱问题具有NP-难性质,其理论和应用研究存在一定的挑战,但因其有广泛的应用背景而受到研究者高度的关注.本文主要总结近几十年来装箱问题的研究成果,特别针对一维、二维和三维单目标装箱问题和算法,以及多目标装箱问题的算法进行概括和总结,并提出装箱问题算法上有待进一步的研究工作.     

非凸约束优化的随机近似算法

在人工智能、科学计算等领域,众多应用驱动的数学优化模型因依赖于庞大的数据集和/或不确定的信息而呈现出随机性、且伴有复杂非凸算子约束。于是精确计算模型中的函数信息往往代价高昂,同时非凸约束的存在也给模型求解和算法分析带来极大的挑战。近年来,结合模型的结构、利用函数的随机近似信息来设计、分析非凸约束优化算法开始引起关注。目前主流的求解非凸约束优化的随机近似算法主要分为三类:基于随机近似的罚方法、邻近点算法和随机序列二次规划算法。本文对这几类算法的研究进展进行梳理和总结,简要地介绍相关算法的设计思想和基本的理论性质,如渐近收敛性理论、复杂度理论等。     

求解非减上模集函数最小值问题的近似算法及其性能保证

上模集函数的优化问题在组合优化问题中有广泛应用,许多组合优化问题,如设备选址问题、p-中心问题等都可化为上模集函数的优化问题.本文给出了求解非减上模集函数最小值问题的一种近似算法,并讨论了所给算法的性能保证.     

鲁棒投资组合选择优化问题的研究进展

对近年来投资组合研究优化研究的热点问题——鲁棒投资组合优化研究的现状和发展趋势作了综述性研究．在投资组合选择优化的均值-方差模型的基础上,回顾了鲁棒投资组合选择优化问题的发展历史;详细地介绍了鲁棒投资组合选择优化的研究热点及国内外研究现状,就鲁棒投资组合选择优化问题的未来发展方向和主要研究内容,提出了新的观点,以期为相关领域的研究工作提供参考依据．     

求解多维约束下下模函数最大值的改进贪婪算法

提出了多维约束下下模函数最大值问题,分析其在组合优化中的重要应用.此问题是NP-难的,故给出了求解该问题的改进贪婪算法.最后,从理论上证明了这一算法的时间复杂性和性能保证.说明该算法是多项式时间近似算法,同时也具有较好的性能保证.     

基于图着色模型的冲突装箱问题启发式算法

带有冲突关系装箱问题的优化目标是在满足货物冲突关系的前提下,使用数量最少的货箱完成货物装箱的目的。本文分析了冲突装箱问题的数学模型,提出了基于图着色模型的启发式算法进行求解。首先,使用冲突图来描述货物之间的冲突关系;其次,基于冲突图,采取图着色的方式将货物进行分组,并且组内的货物之间不存在冲突关系;最后,采取改进FFD算法对每组的货物进行装箱操作。实验表明,本文提出的启发式算法能够快速有效地找到问题的可行解,为此类装箱问题的求解提供了新思路。     

求解非增次模集函数最大值问题的近似算法及其性能保证

次模集函数的最值问题在组合优化问题中有广泛的应用,给出了求解非增次模集函数最大值问题的一种近似算法,并讨论了所给算法的性能保证.     

Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems

We study two-stage, finite-scenario stochastic versions of several combinatorial optimization problems, and provide nearly tight approximation algorithms for them. Our problems range from the graph-theoretic (shortest path, vertex cover, facility location) to set-theoretic (set cover, bin packing), and contain representatives with different approximation ratios. The approximation ratio of the stochastic variant of a typical problem is found to be of the same order of magnitude as its deterministic counterpart. Furthermore, we show that common techniques for designing approximation algorithms such as LP rounding, the primal-dual method, and the greedy algorithm, can be adapted to obtain these results.     

A note on the approximability of cutting stock problems

Cutting stock problems and bin packing problems are basically the same problems. They differ essentially on the variability of the input items. In the first, we have a set of items, each item with a given multiplicity; in the second, we have simply a list of items (each of which we may assume to have multiplicity 1). Many approximation algorithms have been designed for packing problems; a natural question is whether some of these algorithms can be extended to cutting stock problems. We define the notion of “well-behaved” algorithms and show that well-behaved approximation algorithms for one, two and higher dimensional bin packing problems can be translated to approximation algorithms for cutting stock problems with the same approximation ratios.     

Bin packing and multiprocessor scheduling problems with side constraint on job types

This paper deals with the bin packing problem and the multiprocessor scheduling problem both with an additional constraint specifying the maximum number of jobs in each type to the processed on a processor. Since these problems are NP-complete, various approximation algorithms are proposed by generalizing those algorithms known for the ordinary bin packing and multiprocessor scheduling problems. The worst-case performance of the proposed algorithms are analyzed, and some computational results are reported to indicate their average case behavior.     

A note on the minimum bounded edge-partition of a tree

Minimum bounded edge-partition divides the edge set of a tree into the minimum number of disjoint connected components given a maximum weight for any component. It is an adaptation of the uniform edge-partition of a tree. An optimization algorithm is developed for this NP-hard problem, based on repeated bin packing of inter-related instances. The algorithm has linear running time for the class of ‘balanced trees’ common for the stochastic programming application which motivated investigation of this problem.Fast 2-approximation algorithms are formed for general instances by replacing the optimal bin packing with almost any bin packing heuristic. The asymptotic worst-case ratio of these approximation algorithms is never better than the absolute worst-case ratio of the bin packing heuristic used.     

Tight bounds for minimax grid matching with applications to the average case analysis of algorithms

The minimax grid matching problem is a fundamental combinatorial problem associated with the average case analysis of algorithms. The problem has arisen in a number of interesting and seemingly unrelated areas, including wafer-scale integration of systolic arrays, two-dimensional discrepancy problems, and testing pseudorandom number generators. However, the minimax grid matching problem is best known for its application to the maximum up-right matching problem. The maximum up-right matching problem was originally defined by Karp, Luby and Marchetti-Spaccamela in association with algorithms for 2-dimensional bin packing. More recently, the up-right matching problem has arisen in the average case analysis of on-line algorithms for 1-dimen-sional bin packing and dynamic allocation.In this paper, we solve both the minimax grid matching problem and the maximum up-right matching problem. As a direct result, we obtain tight upper bounds on the average case behavior of the best algorithms known for 2-dimensional bin packing, 1-dimensional on-line bin packing and on-line dynamic allocation. The results also solve a long-open question in mathematical statistics.This research was supported by Air Force Contracts AFOSR-82-0326 and AFOSR-86-0078, NSF Grant 8120790, and DARPA contract N00014-80-C-0326. In addition, Tom Leighton was supported by an NSF Presidential Young Investigator Award with matching funds from Xerox and IBM.     

Packing chained items in aligned bins with applications to container transshipment and project scheduling

Bin packing problems are at the core of many well-known combinatorial optimization problems and several practical applications alike. In this work we introduce a novel variant of an abstract bin packing problem which is subject to a chaining constraint among items. The problem stems from an application of container handling in rail freight terminals, but is also of relevance in other fields, such as project scheduling. The paper provides a structural analysis which establishes computational complexity of several problem versions and develops (pseudo-)polynomial algorithms for specific subproblems. We further propose and evaluate simple and fast heuristics for optimization versions of the problem.     

Bin packing with general cost structures

Following the work of Anily et?al., we consider a variant of bin packing called bin packing with general cost structures (GCBP) and design an asymptotic fully polynomial time approximation scheme (AFPTAS) for this problem. In the classic bin packing problem, a set of one-dimensional items is to be assigned to subsets of total size at most 1, that is, to be packed into unit sized bins. However, in GCBP, the cost of a bin is not 1 as in classic bin packing, but it is a non-decreasing and concave function of the number of items packed in it, where the cost of an empty bin is zero. The construction of the AFPTAS requires novel techniques for dealing with small items, which are developed in this work. In addition, we develop a fast approximation algorithm which acts identically for all non-decreasing and concave functions, and has an asymptotic approximation ratio of 1.5 for all functions simultaneously.     

一类带多重核元集在线装箱问题

本文讨论了一类在线变尺寸装箱问题,假定箱子的尺寸可以是不同的.箱子是在线到达的,仅当箱子到达后其尺寸才知道.给定一个带有核元的物品表及其上的核元关系图.我们的目标是要将表中元素装入到达的箱子中,保证任何箱子所装物品不互为核元,即所装物品对应的点所导出的子图是个空图,并使得所用的箱子总长最小.我们证明了该问题是NPHard的,并给出了基于图的点染色、图的团分解和基于背包问题的近似算法,给出了算法的时间复杂度和性能界.     

THE FFD ALGORITHM FOR THE BIN PACKING PROBLEM WITH KERNEL ITEMS

The FFD algorithm is one of the most famous algorithms for the classical bin packing problem. In this paper,some versions of the FFD algorithm are considered in several bin packing problems. Especially,two of them applied to the bin packing problem with kernel items are analyzed. Tight worst-case performance ratios are obtained.