Rollout Algorithms for Combinatorial Optimization

We consider the approximate solution of discrete optimization problems using procedures that are capable of magnifying the effectiveness of any given heuristic algorithm through sequential application. In particular, we embed the problem within a dynamic programming framework, and we introduce several types of rollout algorithms, which are related to notions of policy iteration. We provide conditions guaranteeing that the rollout algorithm improves the performance of the original heuristic algorithm. The method is illustrated in the context of a machine maintenance and repair problem.     

Sparse Harmonic Transforms: A New Class of Sublinear-Time Algorithms for Learning Functions of Many Variables

Foundations of Computational Mathematics - In this paper we develop fast and memory efficient numerical methods for learning functions of many variables that admit sparse representations in terms...     

一些组合地图新算法的实现

本文主要讨论组合地图列举问题.刘的一部专著中提出了一个判定两个地图是否同构的算法.该算法的时间复杂度为O(m2),其中m为下图的规模.在此基础上,本文给出一个用于地图列举以及进而计算任意连通下图的地图亏格分布的通用算法.本文所得结果比之前文献中所给结果更优.     

国内生产总值的一种组合预测方法

对于国内生产总值的预测问题,运用贝叶斯估计方法将主观先验信息、样本拟合区信息和单个模型的预测信息进行了有效综合,导出了三种组合预测方法,并给出了误差方差的估计量.最后是一个应用实例.     

A Taxonomy of Evolutionary Algorithms in Combinatorial Optimization

This paper shows how evolutionary algorithms can be described in a concise, yet comprehensive and accurate way. A classification scheme is introduced and presented in a tabular form called TEA (Table of Evolutionary Algorithms). It distinguishes between different classes of evolutionary algorithms (e.g., genetic algorithms, ant systems) by enumerating the fundamental ingredients of each of these algorithms. At the end, possible uses of the TEA are illustrated on classical evolutionary algorithms.     

Combinatorial Optimization Algorithms for detecting Collapse Mechanisms of Concrete Slabs

Journal of Optimization Theory and Applications - Nowadays, large part of the technical knowledge associated with collapses of slabs is based on past failures of bridges, floors, flat roofs and...     

一类组合最优化问题及其算法

本文介绍三个新的组合最优化模型，并分别给出复杂性为Ｏ（Ｎ２）和Ｏ（Ｎ２α）的多项式算法和拟多项式算法．     

Some Algorithms for Use with the Fast Fourier Transform

This paper gives algorithms for the Fast Fourier Transform ofreal half range even data, real half range odd data and complexhalf range even data.     

Relaxation,New Combinatorial and Polynomial Algorithms for the Linear Feasibility Problem

We consider the homogenized linear feasibility problem, to find an x on the unit sphere satisfying n linear inequalities a_i ^Tx \ge 0. To solve this problem we consider the centers of the inspheres of spherical simplices, whose facets are determined by a subset of the constraints. As a result we find a new combinatorial algorithm for the linear feasibility problem. If we allow rescaling, this algorithm becomes polynomial. We point out that the algorithm also solves the more general convex feasibility problem. Moreover, numerical experiments show that the algorithm could be of practical interest.     

Semi-Iterative Minimum Cross-Entropy Algorithms for Rare-Events,Counting, Combinatorial and Integer Programming

We present a new generic minimum cross-entropy method, called the semi-iterative MinxEnt, or simply SME, for rare-event probability estimation, counting, and approximation of the optimal solutions of a broad class of NP-hard linear integer and combinatorial optimization problems (COP’s). The main idea of our approach is to associate with each original problem an auxiliary single-constrained convex MinxEnt program of a special type, which has a closed-form solution. We prove that the optimal pdf obtained from the solution of such a specially designed MinxEnt program is a zero variance pdf, provided the “temperature” parameter is set to minus infinity. In addition we prove that the parametric pdf based on the product of marginals obtained from the optimal zero variance pdf coincides with the parametric pdf of the standard cross-entropy (CE) method. Thus, originally designed at the end of 1990s as a heuristics for estimation of rare-events and COP’s, CE has strong connection with MinxEnt, and thus, strong mathematical foundation. The crucial difference between the proposed SME method and the standard CE counterparts lies in their simulation-based versions: in the latter we always require to generate (via Monte Carlo) a sequence of tuples including the temperature parameter and the parameter vector in the optimal marginal pdf’s, while in the former we can fix in advance the temperature parameter (to be set to a large negative number) and then generate (via Monte Carlo) a sequence of parameter vectors of the optimal marginal pdf’s alone. In addition, in contrast to CE, neither the elite sample no the rarity parameter is needed in SME. As result, the proposed SME algorithm becomes simpler, faster and at least as accurate as the standard CE. Motivated by the SME method we introduce a new updating rule for the parameter vector in the parametric pdf of the CE program. We show that the CE algorithm based on the new updating rule, called the combined CE (CCE), is at least as fast and accurate as its standard CE and SME counterparts. We also found numerically that the variance minimization (VM)-based algorithms are the most robust ones. We, finally, demonstrate numerically that the proposed algorithms, and in particular the CCE one, allows accurate estimation of counting quantities up to the order of hundred of decision variables and hundreds of constraints. This research was supported by the Israel Science Foundation (grant No 191-565).     

Algorithms for solving Hermite interpolation problems using the Fast Fourier Transform

We present a method for computing the Hermite interpolation polynomial based on equally spaced nodes on the unit circle with an arbitrary number of derivatives in the case of algebraic and Laurent polynomials. It is an adaptation of the method of the Fast Fourier Transform (FFT) for this type of problems with the following characteristics: easy computation, small number of operations and easy implementation.In the second part of the paper we adapt the algorithm for computing the Hermite interpolation polynomial based on the nodes of the Tchebycheff polynomials and we also study Hermite trigonometric interpolation problems.     

Combinatorial Algorithms for Some Variants of Inverse Obnoxious Median Location Problem on Tree Networks

This paper concerns with some variants of the inverse obnoxious median location problem on tree networks, where the aim is either to augment or to reduce the edge lengths at the minimum total cost such that a prespecified subset of vertices becomes an obnoxious multi-facility median location with respect to the perturbed edge lengths. For both augmentation and reduction models, under the rectilinear norm and the sum-type Hamming distance, we develop novel combinatorial algorithms with polynomial time complexities. Particularly, if the underlying tree is an extended star graph, then the problems can be solved in linear time.     

组合恒等式

本文利用函数１ｆ（ｘ）展开式定理,导出一批新的组合恒等式．     

Combinatorial pseudo-triangulations

We prove that a planar graph is generically rigid in the plane if and only if it can be embedded as a pseudo-triangulation. This generalizes the main result of [Haas et al. Planar minimally rigid graphs and pseudo-triangulations, Comput. Geom. 31(1–2) (2005) 31–61] which treats the minimally generically rigid case.The proof uses the concept of combinatorial pseudo-triangulation, CPT, in the plane and has two main steps: showing that a certain “generalized Laman property” is a necessary and sufficient condition for a CPT to be “stretchable”, and showing that all generically rigid plane graphs admit a CPT assignment with that property.Additionally, we propose the study of CPTs on closed surfaces.     

Combinatorial maps

The classical approach to maps, as surveyed by Coxeter and Moser (“Generators and Relations for Discrete Groups,” Springer-Verlag, 1980), is by cell decomposition of a surface. A more recent approach, by way of graph embedding schemes, is taken by Edmonds (Notices Amer. Math. Soc.7 (1960), 646), Tutte (Canad. J. Math.31 (5) (1979), 986–1004), and others. Our intention is to formulate a purely combinatorial generalization of a map, called a combinatorial map. Besides maps on orientable and nonorientable surfaces, combinatorial maps include polytopes, tessellations, the hypermaps of Walsh, higher dimensional analogues of maps, and certain toroidal complexes of Coxeter and Shephard (J. Combin. Theory Ser. B.22 (1977), 131–138) and Grünbaum (Colloques internationaux C.N.R.S. No. 260, Problèmes Combinatoire et Théorie des Graphes, Orsay, 1976). The concept of a combinatorial map is formulated graph theoretically. The present paper treats the incidence structure, the diagram, reduciblity, order, geometric realizations, and group theoretic and topological properties of combinatorial maps. Another paper investigates highly symmetric combinatorial maps.     

Combinatorial polarization

This paper presents a systematic development of a polarization process for functions on Abelian groups. The process facilitates computation of bounds for the degrees of polynomials obtained from functions like the weight function of a linear code. A later paper will present applications, but one is given here, to formally self-dual codes over GF(4).     

Combinatorial auctions

Combinatorial auctions are an important class of market mechanisms in which participants are allowed to bid on bundles of multiple heterogeneous items. In this paper, we discuss several complex issues that are encountered in the design of combinatorial auctions. These issues are related to the formulation of the winner determination problem, the expression of combined bids, the design of progressive combinatorial auctions that require less information revelation, and the need for decision support tools to help participants make profitable bidding decisions. For each issue, we survey the existing literature and propose avenues for further research. An earlier version of this paper appeared in 4OR 2, 1–33, 2004.