On fuzzy B-algebras

The fuzzification of (normal) B-subalgebras is considered, and some related properties are investigated. A characterization of a fuzzy B-algebra is given.     

指派矩阵同解改造理论变换定理论证

本文对指派问题的“周良泽算法”赖以成立而又尚未具体证明的一个重要的基础性定理，给出了严谨的论证，对指派矩阵同解改造理论作了抬遗补证的工作。     

Projected Chvátal–Gomory cuts for mixed integer linear programs

Recent experiments by Fischetti and Lodi show that the first Chvátal closure of a pure integer linear program (ILP) often gives a surprisingly tight approximation of the integer hull. They optimize over the first Chvátal closure by modeling the Chvátal–Gomory (CG) separation problem as a mixed integer linear program (MILP) which is then solved by a general- purpose MILP solver. Unfortunately, this approach does not extend immediately to the Gomory mixed integer (GMI) closure of an MILP, since the GMI separation problem involves the solution of a nonlinear mixed integer program or a parametric MILP. In this paper we introduce a projected version of the CG cuts, and study their practical effectiveness for MILP problems. The idea is to project first the linear programming relaxation of the MILP at hand onto the space of the integer variables, and then to derive Chvátal–Gomory cuts for the projected polyhedron. Though theoretically dominated by GMI cuts, projected CG cuts have the advantage of producing a separation model very similar to the one introduced by Fischetti and Lodi, which can typically be solved in a reasonable amount of computing time. Gérard Cornuéjols was supported in part by NSF grant DMI-0352885, ONR grant N00014-03-1-0188, and ANR grant BLAN 06-1-138894. Matteo Fischetti was supported in part by the EU projects ADONET (contract n. MRTN-CT-2003-504438) and ARRIVAL (contract n. FP6-021235-2). Andrea Lodi was supported in part by the EU projects ADONET (contract n. MRTN-CT-2003-504438) and ARRIVAL (contract n. FP6-021235-2).     

On finding the K best cuts in a network

We show that the O(K · n⁴) algorithm of Hamacher (1982) for finding the K best cut-sets fails because it may produce cuts rather than cut-sets. With the convention that two cuts $\text{(X,}\text{X}\text{)}$ and $\text{(Y,}\text{Y}\text{)}$ are different whenever X ≠ Y the K best cut problem can be solved in O(K · n⁴).     

Packing Steiner trees: a cutting plane algorithm and computational results

In this paper we describe a cutting plane algorithm for the Steiner tree packing problem. We use our algorithm to solve some switchbox routing problems of VLSI-design and report on our computational experience. This includes a brief discussion of separation algorithms, a new LP-based primal heuristic and implementation details. The paper is based on the polyhedral theory for the Steiner tree packing polyhedron developed in our companion paper (this issue) and meant to turn this theory into an algorithmic tool for the solution of practical problems.     

A unified theory for coherent systems in reliability part III: Two special cases for multinary systems—binary-type coherence and homogeneous coherence

As shown in a companion-paper,¹ binary and multinary coherent systems can be studied with unified arguments, through monotone binary coherent systems. These are binary coherent systems submitted to some monotone constraint and generalize the classic theory of free binary coherent systems. By considering the unified point of view thus obtained, this paper gives what is perhaps the most suggestive representation for multinary coherent systems, since this extends the definition of binary coherent systems in terms of series-parallel (parallel-series) structures. Then, this paper examines the special case of multinary systems that can be studied directly with the classic theory of free binary coherent systems. It thus enlarges and complements, in a shorter unified manner, the particular cases considered in earlier studies.     

一种网格参数化的优化算法

网格参数化是数字几何处理(Digital Geometry Processing)中的一个基本问题.作者利用Floater的具有保形权或均值权的凸线性组合参数化引入一种新的参数化的扭曲度量--点密度,以及网格上的最短切割路径来优化原来的参数化.切割路径由网格上的一内点和网格上的一边界点连接而成,内点位于参数区域上最密集区域,也是扭曲最严重的区域.具有最短切割路径的网格模型,被重新参数化成为一个具有较小扭曲的参数化.最后给出实例说明了此方法是可行和有效的,并且是优于原来的参数化的.     

A branch and cut algorithm for hub location problems with single assignment

The hub location problem with single assignment is the problem of locating hubs and assigning the terminal nodes to hubs in order to minimize the cost of hub installation and the cost of routing the traffic in the network. There may also be capacity restrictions on the amount of traffic that can transit by hubs. The aim of this paper is to investigate polyhedral properties of these problems and to develop a branch and cut algorithm based on these results.Acknowledgement The research of the first author was partially supported by the Banque Nationale de Belgique. The research of the second author was supported by France Telecom R&D under contract no. 99 1B 774. Their support is gratefully acknowledged.     

一种基于重标极差方法的动力学结构突变检测新方法

提出了一种针对相关性时间序列动力学结构突变检测的新方法——滑动移除重标极差分析.数值试验表明,新方法能够准确的检测出理想序列中的动力学结构突变,其检测结果对于子序列的长度依赖性较小,而且具有很强的抗噪能力,弥补了滑动去趋势波动分析的不足. 关键词： 标度指数 滑动移除重标极差分析 滑动去趋势波动分析 动力学结构突变     

On active redundancy allocation for coherent systems—from the viewpoint of minimal cut decomposition

This paper deals with coherent systems with one active redundancy. For systems with the subclass of minimal cuts associated with one component covering that of another, assigning the redundancy to the former component is proved to bring forth a more reliable redundant system. As for symmetric systems with lower tail permutation decreasing component lifetimes, allocating the redundancy to the less reliable component results in a longer system lifetime. Several numerical examples are also presented to illustrate the new findings.