Quadrilateral surface meshes without self-intersecting dual cycles for hexahedral mesh generation

Several promising approaches for hexahedral mesh generation work as follows: Given a prescribed quadrilateral surface mesh they first build the combinatorial dual of the hexahedral mesh. This dual mesh is converted into the primal hexahedral mesh, and finally embedded and smoothed into the given domain. Two such approaches, the modified whisker weaving algorithm by Folwell and Mitchell, as well as a method proposed by the author, rely on an iterative elimination of certain dual cycles in the surface mesh. An intuitive interpretation of the latter method is that cycle eliminations correspond to complete sheets of hexahedra in the volume mesh.

Although these methods can be shown to work in principle, the quality of the generated meshes heavily relies on the dual cycle structure of the given surface mesh. In particular, it seems that difficulties in the hexahedral meshing process and poor mesh qualities are often due to self-intersecting dual cycles. Unfortunately, all previous work on quadrilateral surface mesh generation has focused on quality issues of the surface mesh alone but has disregarded its suitability for a high-quality extension to a three-dimensional mesh.

In this paper, we develop a new method to generate quadrilateral surface meshes without self-intersecting dual cycles. This method reuses previous b-matching problem formulations of the quadrilateral mesh refinement problem. The key insight is that the b-matching solution can be decomposed into a collection of simple cycles and paths of multiplicity two, and that these cycles and paths can be consistently embedded into the dual surface mesh.

A second tool uses recursive splitting of components into simpler subcomponents by insertion of internal two-manifolds. We show that such a two-manifold can be meshed with quadrilaterals such that the induced dual cycle structure of each subcomponent is free of self-intersections if the original component satisfies this property. Experiments show that we can achieve hexahedral meshes with a good quality.     

A constructive characterization of the split closure of a mixed integer linear program

Two independent proofs of the polyhedrality of the split closure of mixed integer linear program have been previously presented. Unfortunately neither of these proofs is constructive. In this paper, we present a constructive version of this proof. We also show that split cuts dominate a family of inequalities introduced by Köppe and Weismantel.     

Analysis of Decomposition Algorithms with Benders Cuts for p-Median Problem

In this paper the algorithms for solving the p-median problem based on the Benders decomposition are investigated. A family of problems hard for solving with such algorithms is constructed and then generalized to a special NP-hard case of the p-median problem. It is shown that the effectiveness of the considered algorithms depends on the choice of the optimal values of the dual variables used in Benders cuts. In particular, the depth of the cuts can be equal to one.     

New Branch-and-Cut Algorithm for Bilevel Linear Programming

Linear mixed 0–1 integer programming problems may be reformulated as equivalent continuous bilevel linear programming (BLP) problems. We exploit these equivalences to transpose the concept of mixed 0–1 Gomory cuts to BLP. The first phase of our new algorithm generates Gomory-like cuts. The second phase consists of a branch-and-bound procedure to ensure finite termination with a global optimal solution. Different features of the algorithm, in particular, the cut selection and branching criteria are studied in details. We propose also a set of algorithmic tests and procedures to improve the method. Finally, we illustrate the performance through numerical experiments. Our algorithm outperforms pure branch-and-bound when tested on a series of randomly generated problems. Work of the authors was partially supported by FCAR, MITACS and NSERC grants.     

Enumerating disjunctions and conjunctions of paths and cuts in reliability theory

Let G=(V,E) be a (directed) graph with vertex set V and edge (arc) set E. Given a set P of source-sink pairs of vertices of G, an important problem that arises in the computation of network reliability is the enumeration of minimal subsets of edges (arcs) that connect/disconnect all/at least one of the given source-sink pairs of P. For undirected graphs, we show that the enumeration problems for conjunctions of paths and disjunctions of cuts can be solved in incremental polynomial time. Furthermore, under the assumption that P consists of all pairs within a given vertex set, we also give incremental polynomial time algorithm for enumerating all minimal path disjunctions and cut conjunctions. For directed graphs, the enumeration problem for cut disjunction is known to be NP-complete. We extend this result to path conjunctions and path disjunctions, leaving open the complexity of the enumeration of cut conjunctions. Finally, we give a polynomial delay algorithm for enumerating all minimal sets of arcs connecting two given nodes s₁ and s₂ to, respectively, a given vertex t₁, and each vertex of a given subset of vertices T₂.     

A note on packing paths in planar graphs

Seymour (1981) proved that the cut criterion is necessary and sufficient for the solvability of the edge-disjoint paths problem when the union of the supply graph and the demand graph is planar and Eulerian. When only planarity is required, Middendorf and Pfeiffer (1993) proved the problem to be NP-complete. For this case, Korach and Penn (1992) proved that the cut criterion is sufficient for the existence of a near-complete packing of paths. Here we generalize this result by showing how a natural strengthening of the cut criterion yields better packings of paths.Analogously to Seymour's approach, we actually prove a theorem on packing cuts in an arbitrary graph and then the planar edge-disjoint paths case is obtained by planar dualization. The main result is derived from a theorem of Seb (1990) on the structure of ±1 weightings of a bipartite graph with no negative circuits.Research partially supported by the Hungarian National Foundation for Scientific Research Grants OTKA 2118 and 4271.     

Sample evaporation in conventional GC split/splitless injectors. Part 1: Some quantitative estimates concerning heat consumption during evaporation

During sample evaporation in conventional vaporizing injection, the supply of heat to the evaporating liquid is a problem, first because the amounts of heat consumed are relatively large and, secondly, because the heat must be transferred to the sample within a very short time. Times available for evaporation, required amounts of heat, possible sources of heat, and the time required to transfer the heat to the sample liquid are discussed. It is shown that mixing with carrier gas contributes little heat to the evaporation process, but also that packings with glass wool have too low a heat capacity to deliver the required amount of heat to the evaporating sample. Transfer of heat from the insert wall to the sample easily requires several seconds, even if cooling of the vaporizing zone by 20° is accepted. Thus “flash evaporation” is usually impossible and most liquids must be held in the vaporizing chamber to allow full evaporation.     

Lift-and-project for general two-term disjunctions

In this paper we generalize the cut strengthening method of Balas and Perregaard for 0/1 mixed-integer programming to disjunctive programs with general two-term disjunctions. We apply our results to linear programs with complementarity constraints.     

On the structure of split Leibniz triple systems

We study the structure of arbitrary split Leibniz triple systems with a coherent 0-root space. By developing techniques of connections of roots for this kind of triple systems, under certain conditions, in the case of T being of maximal length, the simplicity of the Leibniz triple systems is characterized.     

N1取代基结构对菲并咪唑荧光色纯度的影响

以1,2-二苯基菲并咪唑(PPI)为模型化合物, 通过改变N1苯环上取代基结构制备了2类PPI衍生物, 并采用核磁共振谱对其化学结构进行了确认. 通过对PPI及其衍生物的单分子荧光光谱精细结构的分析, 比较了取代基位置和结构的变化对菲并咪唑类化合物荧光过程中发射主峰精细振动结构及所占比例的影响. 其中, N1链接苯环中R4位的取代基效应最显著, 当引入推电子或弱的吸电子取代基时, 菲并咪唑类衍生物的低能级发射比例降低, 荧光色纯度提高; 当引入强吸电子取代基时, 低能级发射比例增加, 光谱半峰宽加大. 本文结果为菲并咪唑基“蓝光”材料的设计提供了一定数据的支持与科学依据.