An exact algorithm for minimum distortion embedding

Let G be an unweighted connected graph on n vertices. We show that an embedding of the shortest path metric of G into the line with minimum distortion can be found in time 5^n+o(n). This is the first algorithm breaking the trivial n!-barrier.     

一种解决车辆调度问题的算法研究

针对运输费用的逐年提高,企业配送环节的成本大幅度增加的问题,为降低物流成本,提高企业利润,研究了一种解决车辆调度问题的算法。在考虑实际需求的基础上,建立了单配送中心的配载车辆调度模型,满足基本的约束条件。同时,论述了节约算法的基本原理并采用改进的节约算法对配载车辆调度问题进行求解,即在基本的节约算法中加入时间窗约束条件。通过各种数据的实验验证,此算法都能得到较满意的解,既能节约时间,又能够节约运输里程和费用。     

A genetic algorithm for the Flexible Job-shop Scheduling Problem

In this paper, we present a genetic algorithm for the Flexible Job-shop Scheduling Problem (FJSP). The algorithm integrates different strategies for generating the initial population, selecting the individuals for reproduction and reproducing new individuals. Computational result shows that the integration of more strategies in a genetic framework leads to better results, with respect to other genetic algorithms. Moreover, results are quite comparable to those obtained by the best-known algorithm, based on tabu search. These two results, together with the flexibility of genetic paradigm, prove that genetic algorithms are effective for solving FJSP.     

An exact algorithm for the knapsack sharing problem

In this paper, we develop an exact algorithm for solving the knapsack sharing problem. The algorithm is a new version of the method proposed in Hifi and Sadfi (J. Combin. Optim. 6 (2002) 35). It seems quite efficient in the sense that it solves quickly some large problem instances. Its main principle consists of (i) finding a good set of capacities, representing a set of critical elements, using a heuristic approach, and (ii) varying the values of the obtained set in order to stabilize the optimal solution of the problem. Then, by exploiting dynamic programming properties, we obtain good equilibrium which lead to significant improvements. The performance of the proposed algorithm, based on a set of medium and large problem instances, is compared to the standard version of Hifi and Sadfi (2002). Encouraging results have been obtained.     

An exact algorithm for Min-Max hyperstructure equipartition with a connected constraint

Hyperstructure is a topological concept that shares characteristics with both graphs and hypergraphs. The Min-Max hyperstructure equipartition with a connected constraint problem consists in partitioning a hyperstructure into K equal-sized connected parts that minimizes the maximum load in each part (the number of hyperedges assigned to each part). This problem, proved to be NP-hard, is an integer nonlinear programming problem. The linearized version of this problem has been introduced.Shrink and Cut algorithm is designed to simplify original complex hyperstructure without changing the optimal solution of the Min-Max hyperstructure equipartition with a connected constraint problem. By the use of this algorithm, Min-Max hyper-tree equipartition with a connected constraint can be solved in polynomial time. An exact algorithm: Min-Max hyperstructure partitioning algorithm, based on a Shrink and Cut algorithm and algorithm S for finding all the spanning trees, is designed to solve ordinary cases, which shows well on experimental results.     

An exact subexponential-time lattice algorithm for Asian options

Asian options are popular financial derivative securities. Unfortunately, no exact pricing formulas exist for their price under continuous-time models. Asian options can also be priced on the lattice, which is a discretized version of the continuous- time model. But only exponential-time algorithms exist if the options are priced on the lattice without approximations. Although efficient approximation methods are available, they lack accuracy guarantees in general. This paper proposes a novel lattice structure for pricing Asian options. The resulting pricing algorithm is exact (i.e., without approximations), converges to the value under the continuous-time model, and runs in subexponential time. This is the first exact, convergent lattice algorithm to break the long-standing exponential-time barrier. An early version of this paper appeared in the Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, 2004. T.-S. Dai was supported in part by NSC grant 94-2213-E-033-024. Y.-D. Lyuu was supported in part by NSC grant 94-2213-E-002-088.     

作业调度问题研究

生产调度理论与方法研究是一类NP完全问题.在CIMS广泛地应用于企业管理的过程中,会遇到企业生产自动生成及其实时调整的问题.本文分析了当前实际作业调度存在的一些问题和需要考虑的各种因素,列举了主要的作业调度方法和典型应用,指出了各种方法的优缺点,并对未来研究方向做出了展望.     

求解作业车间调度问题的一种改进遗传算法

为了避免遗传算法的早熟收敛问题,降低算法对初始种群的敏感程度,提高收敛速度,建立了以工件完工时间最小和加工设备利用率最高为目标的数学模型,并提出一种改进遗传算法。在约束条件处理中引入可能解空间概念;设计了适应路径柔性调度问题的基于工序的编码。父代个体和交叉变异得到的个体在选择操作中具有同等选择机会,保证最优个体保留到下一代,又能保持子代的多样性。在遗传过程中引入修正种群,实现多种群杂交,以保持种群的多样性。应用实例分析和工程实践表明,算法稳定可靠,运行效率大大提高。     

An exact constructive algorithm for the knapsack sharing problem

In this paper, we study the knapsack sharing problem (KSP), a variant of the well-known NP-hard single knapsack problem. We propose an exact constructive tree search that combines two complementary procedures: a reduction interval search and a branch and bound. The reduction search has three phases. The first phase applies a polynomial reduction strategy that decomposes the problem into a series of knapsack problems. The second phase is a size reduction strategy that makes the resolution more efficient. The third phase is an interval reduction search that identifies a set of optimal capacities characterizing the knapsack problems. Experimental results provide computational evidence of the better performance of the proposed exact algorithm in comparison to KSPs best exact algorithm, to Cplex and to KSPs latest heuristic approach. Furthermore, they emphasize the importance of the reduction strategies.     

An exact algorithm for generating homogenous T-shape cutting patterns

Both the material usage and the complexity of the cutting process should be considered in generating cutting patterns. This paper presents an exact algorithm for constrained two-dimensional guillotine-cutting problems of rectangles. It uses homogenous T-shape patterns to simplify the cutting process. Only homogenous strips are allowed, each of which contains rectangular blanks of the same size and direction. The sheet is divided into two segments. Each segment consists of strips of the same length and direction. The strip directions of the two segments are perpendicular to each other. The algorithm is based on branch and bound procedure combined with dynamic programming techniques. It is a bottom-up tree-search approach that searches the solution tree from the branches to the root. Tighter bounds are established to shorten the searching space. The computational results indicate that the algorithm is efficient both in computation time and in material usage.     

An exact exponential time algorithm for counting bipartite cliques

We present a simple exact algorithm for counting bicliques of given size in a bipartite graph on n   vertices. We achieve running time of O(1.2491ⁿ)$O({1.2491}^n)$, improving upon known exact algorithms for finding and counting bipartite cliques.     

An exact algorithm for the budget-constrained multiple knapsack problem

This paper is concerned with a variant of the multiple knapsack problem (MKP), where knapsacks are available by paying certain ‘costs’, and we have a fixed budget to buy these knapsacks. Then, the problem is to determine the set of knapsacks to be purchased, as well as to allocate items into the accepted knapsacks in such a way as to maximize the net total profit. We call this the budget-constrained MKP and present a branch-and-bound algorithm to solve this problem to optimality. We employ the Lagrangian relaxation approach to obtain an upper bound. Together with the lower bound obtained by a greedy heuristic, we apply the pegging test to reduce the problem size. Next, in the branch-and-bound framework, we make use of the Lagrangian multipliers obtained above for pruning subproblems, and at each terminal subproblem, we solve MKP exactly by calling the MULKNAP code [D. Pisinger, An exact algorithm for large multiple knapsack problem, European J. Oper. Res. 114 (1999), pp. 528–541]. Thus, we were able to solve test problems with up to 160,000 items and 150 knapsacks within a few minutes in our computing environment. However, solving instances with relatively large number of knapsacks, when compared with the number of items, still remains hard. This is due to the weakness of MULKNAP to this type of problems, and our algorithm inherits this weakness as well.     

An exact end-to-end blocking probability algorithm for multicast networks

We consider the calculation of blocking probabilities in multicast trees with dynamic membership. We extend the work by Karvo et al., where an approximate algorithm based on the reduced load approximation (RLA) was given to calculate end-to-end blocking for infinite sized user populations in multicast networks. The new algorithm for calculating end-to-end call blocking exactly for an arbitrary sized user population is based on the known blocking probability algorithm in hierarchical multiservice access networks, where link occupancy distributions are alternately convolved and truncated. We show that the algorithm can be applied to multicast trees embedded in a network with an arbitrary topology carrying also non-multicast traffic. The resource sharing of multicast connections, however, requires the modification of the algorithm by introducing a new type of convolution, the OR-convolution. In addition, we discuss several different user population models for which the algorithm is applicable.     

An improved exact algorithm for the domatic number problem

The 3-domatic number problem asks whether a given graph can be partitioned into three dominating sets. We prove that this problem can be solved by a deterministic algorithm in time n^2.695 (up to polynomial factors) and in polynomial space. This result improves the previous bound of n^2.8805, which is due to Björklund and Husfeldt. To prove our result, we combine an algorithm by Fomin et al. with Yamamoto's algorithm for the satisfiability problem. In addition, we show that the 3-domatic number problem can be solved for graphs G with bounded maximum degree Δ(G) by a randomized polynomial-space algorithm, whose running time is better than the previous bound due to Riege and Rothe whenever Δ(G)?5. Our new randomized algorithm employs Schöning's approach to constraint satisfaction problems.     

An exact bit-parallel algorithm for the maximum clique problem

This paper presents a new exact maximum clique algorithm which improves the bounds obtained in state of the art approximate coloring by reordering the vertices at each step. Moreover, the algorithm can make full use of bit strings to sort vertices in constant time as well as to compute graph transitions and bounds efficiently, exploiting the ability of CPUs to process bitwise operations in blocks of size the ALU register word. As a result it significantly outperforms a current leading algorithm.     

An exact algorithm for parallel machine scheduling with conflicts

We consider an extension of classic parallel machine scheduling where a set of jobs is scheduled on identical parallel machines and an undirected conflict graph is part of the input. Each node in the graph represents a job, and an edge implies that its two jobs are conflicting, meaning that they cannot be scheduled on the same machine. The goal is to find an assignment of the jobs to the machines such that the maximum completion time (makespan) is minimized. We present an exact algorithm based on branch and price that combines methods from bin packing, scheduling, and graph coloring, with appropriate modifications. The algorithm has a good computational performance even for parallel machine scheduling without conflicting jobs.     

面向Flow Shop的智能优化调度系统

综述了FlowShop调度问题的研究方法,构造了一个基于遗传算法的智能化调度系统,给出了系统的结构组成及工作机制。     

施工项目调度问题的一种智能优化算法

研究了施工项目进度调度问题,提出了一种基于启发式规则和遗传算法的综合智能优化算法,并在施工项目调度问题的描述、带资源约束的施工项目调度问题的分解方法、遗传算法的编码、交叉、变异方法和解码方法等方面进行了研究。不同规模的数值计算结果表明,该算法在解决复杂工程施工项目调度问题上具有良好的性能,并能较好地适用于带时序、资源约束的施工项目调度问题。     

An exact wide field digital imaging algorithm

Abstract

A new imaging algorithm is presented for Synthetic Aperture Radar (SAR) that is exact in the sense that it is capable of producing a complex image with excellent geometrical, radiometrical and phase fidelity. No interpolations or significant approximations are required, yet the method accomplishes range curvature correction over the complete range swath. The key to the approach is a quadratic phase perturbation of the range linearly frequency modulated signals while in the range signal, azimuth frequency transform (Doppler) domain. Range curvature correction is completed by a phase multiply in the two-dimensional frequency domain. Other operations required are relatively conventional. The method is generalizable to imaging geometries encountered in squint and spotlight SAR, inverse SAR, seismics, sonar, and tomography.     

混合流水车间提前/拖期调度问题的DE优化解

针对JIT生产模式下的混合流水车间调度问题特点,提出了采用DE算法与指派规则联合调度策略求解流水车间提前/拖期调度问题。构建了混合流水车间的提前/拖期调度模型。详细论述了DE算法的实施流程和关键问题。在算法实施过程中,首先,采用DE算法进行全局寻优,完成生产任务指派,确定某个工件在某个工序在哪个工位加工;然后采用局部指派规则来确定工件在该工序的开工时间。在满足目标完成时间(交货期)的前提下,使提前惩罚费用与拖期惩罚费用之和最小。数值计算结果证明了该算法的有效性。