立体角在结构化学中的应用

使用立体角概念,说明由一种或几种多面体组合,达到三维无隙结构充分必要条件。本文给出常见正多面体、常见阿基米德半正多面体顶角的立体角以及二面角,并结合结构化学实例分析阐述。在空间中须满足各立体角之和等于4π(sr),故通过简单的加和,即可判断无隙堆积的可能性,得知每个点的共用情况,进而推导出空间结构。运用这种方法,可以对一些尚不存在的结构进行大胆的预测。     

Recursive weighted treelike networks

We propose a geometric growth model for weighted scale-free networks, which is controlled by two tunable parameters. We derive exactly the main characteristics of the networks, which are partially determined by the parameters. Analytical results indicate that the resulting networks have power-law distributions of degree, strength, weight and betweenness, a scale-free behavior for degree correlations, logarithmic small average path length and diameter with network size. The obtained properties are in agreement with empirical data observed in many real-life networks, which shows that the presented model may provide valuable insight into the real systems.     

On the orthogonal Latin squares polytope

Since 1782, when Euler addressed the question of existence of a pair of orthogonal Latin squares (OLS) by stating his famous conjecture, these structures have remained an active area of research. In this paper, we examine the polyhedral aspects of OLS. In particular, we establish the dimension of the OLS polytope, describe all cliques of the underlying intersection graph and categorize them into three classes. Two of these classes are shown to induce facet-defining inequalities of Chvátal rank two. For each such class, we provide a polynomial separation algorithm of the lowest possible complexity.     

Description of 2-integer continuous knapsack polyhedra

In this paper we discuss the polyhedral structure of several mixed integer sets involving two integer variables. We show that the number of the corresponding facet-defining inequalities is polynomial on the size of the input data and their coefficients can also be computed in polynomial time using a known algorithm [D. Hirschberg, C. Wong, A polynomial-time algorithm for the knapsack problem with two variables, Journal of the Association for Computing Machinery 23 (1) (1976) 147–154] for the two integer knapsack problem. These mixed integer sets may arise as substructures of more complex mixed integer sets that model the feasible solutions of real application problems.     

Zigzag inequalities: a new class of facet-inducing inequalities for Arc Routing Problems

In this paper we introduce a new class of facet-inducing inequalities for the Windy Rural Postman Problem and the Windy General Routing Problem. These inequalities are called Zigzag inequalities because they cut off fractional solutions containing a zigzag associated with variables with 0.5 value. Two different types of inequalities, the Odd Zigzag and the Even Zigzag inequalities, are presented. Finally, their application to other known Arc Routing Problems is discussed.     

Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes

Cover inequalities are commonly used cutting planes for the 0–1 knapsack problem. This paper describes a linear-time algorithm (assuming the knapsack is sorted) to simultaneously lift a set of variables into a cover inequality. Conditions for this process to result in valid and facet-defining inequalities are presented. In many instances, the resulting simultaneously lifted cover inequality cannot be obtained by sequentially lifting over any cover inequality. Some computational results demonstrate that simultaneously lifted cover inequalities are plentiful, easy to find and can be computationally beneficial.     

On the Lipschitzian properties of polyhedral multifunctions

In this paper, we show that for a polyhedral multifunctionF:R ⁿ →R ^m with convex range, the inverse functionF ⁻¹ is locally lower Lipschitzian at every point of the range ofF (equivalently Lipschitzian on the range ofF) if and only if the functionF is open. As a consequence, we show that for a piecewise affine functionf:R ⁿ →R ⁿ ,f is surjective andf ⁻¹ is Lipschitzian if and only iff is coherently oriented. An application, via Robinson's normal map formulation, leads to the following result in the context of affine variational inequalities: the solution mapping (as a function of the data vector) is nonempty-valued and Lipschitzian on the entire space if and only if the solution mapping is single-valued. This extends a recent result of Murthy, Parthasarathy and Sabatini, proved in the setting of linear complementarity problems. Research supported by the National Science Foundation Grant CCR-9307685.     

Vector Variational Inequalities for Nondifferentiable Convex Vector Optimization Problems

In this paper, we consider a nondifferentiable convex vector optimization problem (VP), and formulate several kinds of vector variational inequalities with subdifferentials. Here we examine relations among solution sets of such vector variational inequalities and (VP). Mathematics Subject classification (2000). 90C25, 90C29, 65K10 This work was supported by the Brain Korea 21Project in 2003. The authors wish to express their appreciation to the anonymous referee for giving valuable comments.     

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.     

Polyhedral extensions of some theorems of linear programming

Three theorems of linear programming form our starting point: Tucker's theorem (1956) concerning the existence of optimal solutions satisfying the complementary slackness conditions strictly, and Williams' two theorems (1970) concerning the coordinatewise complementary behavior of feasible and optimal solutions. Here, we establish that the same phenomena hold in another, more versatile framework involving general polyhedral convexity. As one main application, the results are transferred into the context of the monotone complementarity problem. Several other theoretical applications are indicated.Research supported in part by the National Science Foundation under grant number MCS 79-05793 at the University of Illinois at Urbana-Champaign.