基于启发式Q学习的汽车涂装车间作业排序优化

针对汽车涂装车间中的作业优化排序问题,提出一种基于启发式Q学习的优化算法。首先,建立包括满足总装车间生产顺序和最小化喷枪颜色切换次数的多目标整数规划模型。将涂装作业优化排序问题抽象为马尔可夫过程,建立基于启发式Q算法的求解方法。通过具体案例,对比分析了启发式Q学习、Q学习、遗传算法三种方案的优劣。结果表明：在大规模问题域中,启发式Q学习算法具有寻优效率更高、效果更好的优势。本研究为机器学习算法在汽车涂装作业优化排序问题的应用提出了新思路。     

A local search approximation algorithm for k-means clustering

In k-means clustering we are given a set of n data points in d-dimensional space and an integer k, and the problem is to determine a set of k points in  , called centers, to minimize the mean squared distance from each data point to its nearest center. No exact polynomial-time algorithms are known for this problem. Although asymptotically efficient approximation algorithms exist, these algorithms are not practical due to the very high constant factors involved. There are many heuristics that are used in practice, but we know of no bounds on their performance.

We consider the question of whether there exists a simple and practical approximation algorithm for k-means clustering. We present a local improvement heuristic based on swapping centers in and out. We prove that this yields a (9+)-approximation algorithm. We present an example showing that any approach based on performing a fixed number of swaps achieves an approximation factor of at least (9−) in all sufficiently high dimensions. Thus, our approximation factor is almost tight for algorithms based on performing a fixed number of swaps. To establish the practical value of the heuristic, we present an empirical study that shows that, when combined with Lloyd's algorithm, this heuristic performs quite well in practice.     

Lock-Gain Based Graph Partitioning

We propose a new heuristic for the graph partitioning problem. Based on the traditional iterative improvement framework, the heuristic uses a new type of gain in selecting vertices to move between partitions. The new type of gain provides a good explanation for the performance difference of tie-breaking strategies in KL-based iterative improvement graph partitioning algorithms. The new heuristic performed excellently. Theoretical arguments supporting its efficacy are also provided. As the proposed heuristic is considered a good candidate for local optimization engines in metaheuristics, we combined it with a genetic algorithm as a sample case and obtained a surprising result that even the average results over 1,000 runs equalled the best known for most graphs.     

Spectral partitioning with multiple eigenvectors

The graph partitioning problem is to divide the vertices of a graph into disjoint clusters to minimize the total cost of the edges cut by the clusters. A spectral partitioning heuristic uses the graph's eigenvectors to construct a geometric representation of the graph (e.g., linear orderings) which are subsequently partitioned. Our main result shows that when all the eigenvectors are used, graph partitioning reduces to a new vector partitioning problem. This result implies that as many eigenvectors as are practically possible should be used to construct a solution. This philosophy is in contrast to that of the widely used spectral bipartitioning (SB) heuristic (which uses only a single eigenvector) and several previous multi-way partitioning heuristics [8, 11, 17, 27, 38] (which use k eigenvectors to construct k-way partitionings). Our result motivates a simple ordering heuristic that is a multiple-eigenvector extension of SB. This heuristic not only significantly outperforms recursive SB, but can also yield excellent multi-way VLSI circuit partitionings as compared to [1, 11]. Our experiments suggest that the vector partitioning perspective opens the door to new and effective partitioning heuristics. The present paper updates and improves a preliminary version of this work [5].     

A practical map labeling algorithm

The map labeling problem is a classical problem of cartography. There is a theoretically optimal approximation algorithm A. Unfortunately A is useless in practice as it typically produces results that are intolerably far off the optimal size. On the other hand there are heuristics with good practical results.

In this paper we present an algorithm B that (1) guarantees the optimal approximation quality and runtime behaviour of A, and (2) yields results significantly closer to the optimum than the best heuristic known so far.

The sample data used in the experimental evaluation consists of three different classes of random problems and a selection of problems arising in the production of groundwater quality maps by the authorities of the City of Munich.     

Continuous bottleneck tree partitioning problems

We study continuous partitioning problems on tree network spaces whose edges and nodes are points in Euclidean spaces. A continuous partition of this space into p connected components is a collection of p subtrees, such that no pair of them intersect at more than one point, and their union is the tree space. An edge-partition is a continuous partition defined by selecting p−1 cut points along the edges of the underlying tree, which is assumed to have n nodes. These cut points induce a partition into p subtrees (connected components). The objective is to minimize (maximize) the maximum (minimum) “size” of the components (the min–max (max–min) problem). When the size is the length of a subtree, the min–max and the max–min partitioning problems are NP-hard. We present O(n² log(min(p,n))) algorithms for the edge-partitioning versions of the problem. When the size is the diameter, the min–max problems coincide with the continuous p-center problem. We describe O(n log³ n) and O(n log² n) algorithms for the max–min partitioning and edge-partitioning problems, respectively, where the size is the diameter of a component.     

Finding near-optimal independent sets at scale

The maximum independent set problem is NP-hard and particularly difficult to solve in sparse graphs, which typically take exponential time to solve exactly using the best-known exact algorithms. In this paper, we present two new novel heuristic algorithms for computing large independent sets on huge sparse graphs, which are intractable in practice. First, we develop an advanced evolutionary algorithm that uses fast graph partitioning with local search algorithms to implement efficient combine operations that exchange whole blocks of given independent sets. Though the evolutionary algorithm itself is highly competitive with existing heuristic algorithms on large social networks, we further show that it can be effectively used as an oracle to guess vertices that are likely to be in large independent sets. We then show how to combine these guesses with kernelization techniques in a branch-and-reduce-like algorithm to compute high-quality independent sets quickly in huge complex networks. Our experiments against a recent (and fast) exact algorithm for large sparse graphs show that our technique always computes an optimal solution when the exact solution is known, and it further computes consistent results on even larger instances where the solution is unknown. Ultimately, we show that identifying and removing vertices likely to be in large independent sets opens up the reduction space—which not only speeds up the computation of large independent sets drastically, but also enables us to compute high-quality independent sets on much larger instances than previously reported in the literature.     

A dual ascent procedure for the set partitioning problem

The set partitioning problem is a fundamental model for many important real-life transportation problems, including airline crew and bus driver scheduling and vehicle routing.In this paper we propose a new dual ascent heuristic and an exact method for the set partitioning problem. The dual ascent heuristic finds an effective dual solution of the linear relaxation of the set partitioning problem and it is faster than traditional simplex based methods. Moreover, we show that the lower bound achieved dominates the one achieved by the classic Lagrangean relaxation of the set partitioning constraints. We describe a simple exact method that uses the dual solution to define a sequence of reduced set partitioning problems that are solved by a general purpose integer programming solver. Our computational results indicate that the new bounding procedure is fast and produces very good dual solutions. Moreover, the exact method proposed is easy to implement and it is competitive with the best branch and cut algorithms published in the literature so far.     

On-line construction of the upper envelope of triangles and surface patches in three dimensions

In this paper, we describe a randomized incremental algorithm for computing the upper envelope (i.e., the pointwise maximum) of a set of n triangles in three dimensions. This algorithm is an on-line algorithm. It is structure-sensitive: the expected cost of inserting the n-th triangle is O(log nΣ_r=1ⁿτ(r)/r²) and depends on the expected size τ(r) of an intermediate result for r triangles. Since τ(r) can be Θ(r²(r)) in the worst case, this cost is bounded in the worst case by O(n(n) log n). (The expected behaviour is analyzed by averaging over all possible orderings of the input.) The main new characteristics is the use of a two-level history graph. (The history graph is an auxiliary data structure maintained by randomized incremental algorithms.) Our algorithm is fairly simple and appears to be efficient in practice. It extends to surfaces and surface patches of fixed maximum algebraic degree.     

Receiver set partitioning and sequencing for multicasting traffic in a WDM lightwave single-hop network

This paper considers a receiver set partitioning and sequencing problem in a wavelength division multiplexing single-hop lightwave network for multicasting traffic. The problem is analysed in the approach of uncapacitated single batch-processing machine scheduling. In the analysis, several solution properties are characterized with respect to a mean flow time measure, based upon which two heuristic algorithms are developed, along with a dynamic programming algorithm. Several numerical experiments show that the heuristic algorithms generate good schedules. The problem is extended to consider two measures simultaneously including the mean flow time and the number of transmissions, for which the proposed algorithms also perform well.     

移动传感器网络中的最大价值路径扫描覆盖算法

扫描覆盖是当前移动传感器网络的一个重要覆盖技术,其主要通过规划移动传感器的巡逻路径对事件兴趣点（Points of Interest,POI）进行定期监测,从而以相对于普通覆盖方案更低廉的成本实现对POI监控．研究最大价值路径扫描覆盖,即使用移动传感器扫描覆盖分布在一条路径上的POI集合,使得被覆盖POI的价值总和达到最大．首先设计了一个基于线性规划随机取整的近似算法,通过将问题松弛并刻画为一个线性规划,然后对线性规划最优解取整得到一个扫描覆盖方案．该算法可在O（mn^3.5L）时间内求解,并具有可证明的近似比1-1/e．其次,通过扩展基于贪心策略的集合覆盖算法,设计了一个时间复杂度为O（m²n²）的贪心算法,其主要思想为循环选取一个单位巡逻范围覆盖POI价值最大的传感器．为优化运行时间,基于MVSCP问题的特殊结构将算法时间进一步改进至O（m log m+mn²）．最后,通过仿真实验分析所设计算法的实际性能.实验结果表明,线性规划随机取整算法运行时间低至整数规划算法的百分之一,但其所求解的质量只略低于整数规划算法;改进的贪心算法虽然不具有可证明的近似比,但其实际所求解的质量并不弱于线性规划随机取整算法,并且具有三者中最佳的运行时间．     

On embedding an outer-planar graph in a point set

Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(nlog³n) time and O(n) space algorithm to compute a straight-line embedding of G in P, improving upon the algorithm in [8,12] that requires O(n²) time. Our algorithm is near-optimal as there is an Ω(nlogn) lower bound for the problem [4]. We present a simpler O(nd) time and O(n) space algorithm to compute a straight-line embedding of G in P where lognd2n is the length of the longest vertex disjoint path in the dual of G. Therefore, the time complexity of the simpler algorithm varies between O(nlogn) and O(n²) depending on the value of d. More efficient algorithms are presented for certain restricted cases. If the dual of G is a path, then an optimal Θ(nlogn) time algorithm is presented. If the given point set is in convex position then we show that O(n) time suffices.     

A fast and simple Steiner routing heuristic

This paper presents a simple yet efficient heuristic for rectilinear Steiner routing. The basic heuristic introduces a new edge into the existing tree for another, costlier edge such that the resulting graph remains a tree. The simplicity of the heuristic led to an O(n²) implementation using basic data structures. Asymptotic time requirement of the heuristic can be further improved to O(n log n) using sophisticated data structures. Due to the generality of the heuristic different cost criteria can be applied to produce routes with different properties. The heuristic has been successfully applied to the problem of minimum-length Steiner routing and minimizing critical-sink Elmore delay.     

Single vehicle routing with predefined client sequence and multiple warehouse returns: the case of two warehouses

We examine three interesting cases of the single vehicle routing problem with a predefined client sequence and two load replenishment warehouses. Given the location and demand of the clients, we seek the minimal cost route, which includes optimal load replenishment visits to the warehouses in order to fully satisfy the client demand. The cases studied vary with respect to inventory availability at each warehouse and are of increasing complexity. We have developed solution algorithms that address this complexity, ranging from a standard dynamic programming algorithm for the simplest case, to labeling algorithms and a new partitioning heuristic. The efficiency of these algorithms has been studied by solving a wide range of problem instances, and by comparing the results with those obtained from a state-of-the-art MILP solver.     

General polynomial roots and their multiplicities in O(N)memory and O(N2)Time

For a given real or complex polynomial p of degree n we modify the Euclidean algorithm to find a general tridiagonal matrix representation T of the monic version of p and then use the tridiagonal DQR eigenvalue algorithm on T in order to find

all roots ofp with their multiplicities in O(n²) operations

and 0(n) storage. We include details of the implementation and comparisons with several, standard and recent, essentially 0(n³) polynomial root finders.     

Finding groups with a simple genetic algorithm*

A new solution to the old problem of partitioning a matrix of social proximities into groups is proposed. It draws on a heuristic developed in computer science, the simple genetic algorithm. The algorithm is described and its utility is demonstrated with applications to three standard data sets.     

Full transversal matroids, strict gammoids, and the matroid components problem

We provide two algorithms for finding dependence graphs both in a full transversal matroid and in its dual, a strict gammoid. The first algorithm is based on directed paths in the directed graph associated with a strict gammoid; its complexity is O(|L|(|V-L|+|E|)), where L is the link-set of the gammoid. The second algorithm is based on a special property of Gaussian elimination in a matrix of indeterminates representing a full transversal matroid; it complexity is o(m²n), where m is the rank of the matroid and n the cardinality of the underlying set. We provide an algorithm for listing all bases in, and calculating the Whitney and Tutte polynomials for, a full transversal matroid or a strict gammoid. The complexity of this algorithm is 0(N(n-m) (|E| + m²)), where N is the number of bases.     

Simulated annealing for the unconstrained quadratic pseudo-Boolean function

In this paper, we develop a simulated annealing (SA) based heuristic for the unconstrained quadratic pseudo-Boolean function. An algorithm that solves the problem in O(n²) at each temperature of the cooling schedule is given. The performance of SA based heuristic is compared with existing bounding algorithms for this problem. Computational results and comparisons on several hundred test problems demonstrate the efficiency of our heuristic in terms of solution quality and computational time. A new set of hard test problems with their best solution is provided to facilitate future comparison.     

A warm-start dual simplex solution algorithm for the minimum flow networks with postoptimality analyses

This paper presents an algorithm for finding the minimum flow in general (s, t) networks with m directed arcs. The minimum flow problem (MFP) arises in many transportation and communication systems. Here, we construct a linear programming (LP) formulation of MFP and develop a simplex-type algorithm to find a minflow. Unlike other simplex-like algorithms, the algorithm developed here starts with an incomplete Basic Variable Set (BVS) initially and then fills-up the BVS completely while pushing toward an optimal vertex. If this results in pushing too far into infeasibility, the next step pulls the solution back to feasibility. Both phases use the Gauss-Jordan pivoting transformation used in the standard simplex and dual simplex algorithms.

The proposed approach has some common features with Dantzig's self-dual simplex algorithm. We have avoided, however, the need for extra variables (slack and surplus) for equality constraints, as well as an artificial constraint for the self-dual algorithm for initial phase and the dual simplex, respectively. The proposed Push phase takes at most 2m − 1 iterations to complete a tree (this augmentation may not be feasible). An infeasible path to the optimal solution contains at most 2m − 1 iterations; therefore in theory, the algorithm needs a sequence of at most 4m − 2 iterations.

Furthermore, the algorithm developed here makes available the full power of LP perturbation analysis and facilitates introducing network structural changes and side constraints also. It can also detect clerical errors in data entry which may make the problem infeasible or unbounded. It is assumed that the reader is familiar with LP terminology.     

A modified variable neighborhood search for the discrete ordered median problem

This paper presents a modified Variable Neighborhood Search (VNS) heuristic algorithm for solving the Discrete Ordered Median Problem (DOMP). This heuristic is based on new neighborhoods’ structures that allow an efficient encoding of the solutions of the DOMP avoiding sorting in the evaluation of the objective function at each considered solution. The algorithm is based on a data structure, computed in preprocessing, that organizes the minimal necessary information to update and evaluate solutions in linear time without sorting. In order to investigate the performance, the new algorithm is compared with other heuristic algorithms previously available in the literature for solving DOMP. We report on some computational experiments based on the well-known N-median instances of the ORLIB with up to 900 nodes. The obtained results are comparable or superior to existing algorithms in the literature, both in running times and number of best solutions found.