On a Polynomial Fractional Formulation for Independence Number of a Graph

In this paper we characterize the local maxima of a continuous global optimization formulation for finding the independence number of a graph. Classical Karush-Kuhn-Tucker conditions and simple combinatorial arguments are found sufficient to deduce several interesting properties of the local and global maxima. These properties can be utilized in developing new approaches to the maximum independent set problem.     

多目标半定规划的加权中心路径法

对于线性型多目标半定规划问题，引进加权中心路径的概念，并利用单目标半定规划的中心路径法，提出了求解多目标半定规划问题的加权中心路径法，先得型对一个叔向量的有效解，然后在此基础上，提出了通过一次迭代得到对应一定范围内其他任意权向量的有效解的一步修正方法．     

Parking Capacity and Pricing in Park'n Ride Trips: A Continuous Equilibrium Network Design Problem

In this paper we consider the problem of designing parking facilities for park'n ride trips. We present a new continuous equilibrium network design problem to decide the capacity and fare of these parking lots at a tactical level. We assume that the parking facilities have already been located and other topological decisions have already been taken.The modeling approach proposed is mathematical programming with equilibrium constraints. In the outer optimization problem, a central Authority evaluates the performance of the transport network for each network design decision. In the inner problem a multimodal traffic assignment with combined modes, formulated as a variational inequality problem, generates the share demand for modes of transportation, and for parking facilities as a function of the design variables of the parking lots. The objective is to make optimal parking investment and pricing decisions in order to minimize the total travel cost in a subnetwork of the multimodal transportation system.We present a new development in model formulation based on the use of generalized parking link cost as a design variable.The bilevel model is solved by a simulated annealing algorithm applied to the continuous and non-negative design decision variables. Numerical tests are reported in order to illustrate the use of the model, and the ability of the approach to solve applications of moderate size.     

计算全息图产生的锥面波在激光准直中的应用

本文提出了用计算全息图产生锥面波的方法.将全息图置于激光光路中,它的衍射图样中心在空间形成了一条准直线.文中对锥面波的传播、准直精度及准直距离作了理论分析,给出了实验结果.     

Pure adaptive search in monte carlo optimization

Pure adaptive search constructs a sequence of points uniformly distributed within a corresponding sequence of nested regions of the feasible space. At any stage, the next point in the sequence is chosen uniformly distributed over the region of feasible space containing all points that are equal or superior in value to the previous points in the sequence. We show that for convex programs the number of iterations required to achieve a given accuracy of solution increases at most linearly in the dimension of the problem. This compares to exponential growth in iterations required for pure random search.     

On Extracting Maximum Stable Sets in Perfect Graphs Using Lovász's Theta Function

We study the maximum stable set problem. For a given graph, we establish several transformations among feasible solutions of different formulations of Lovász's theta function. We propose reductions from feasible solutions corresponding to a graph to those corresponding to its induced subgraphs. We develop an efficient, polynomial-time algorithm to extract a maximum stable set in a perfect graph using the theta function. Our algorithm iteratively transforms an approximate solution of the semidefinite formulation of the theta function into an approximate solution of another formulation, which is then used to identify a vertex that belongs to a maximum stable set. The subgraph induced by that vertex and its neighbors is removed and the same procedure is repeated on successively smaller graphs. We establish that solving the theta problem up to an adaptively chosen, fairly rough accuracy suffices in order for the algorithm to work properly. Furthermore, our algorithm successfully employs a warm-start strategy to recompute the theta function on smaller subgraphs. Computational results demonstrate that our algorithm can efficiently extract maximum stable sets in comparable time it takes to solve the theta problem on the original graph to optimality. This work was supported in part by NSF through CAREER Grant DMI-0237415. Part of this work was performed while the first author was at the Department of Applied Mathematics and Statisticsat Stony Brook University, Stony Brook, NY, USA.     

About Regularity of Collections of Sets

The paper continues investigations of stationarity and regularity properties of collections of sets in normed spaces. It contains a summary of different characterizations (both primal and dual) of regularity and a list of sufficient conditions for a collection of sets to be regular.     

Generalized fractional programming duality: A parametric approach

Using a parametric approach, duality is presented for a minimax fractional programming problem that involves several ratios in the objective function.The first author is thankful to Natural Science and Engineering Research Council of Canada for financial support through Grant A-5319, and the authors are thankful to the anonymous referees for useful suggestions.     

倒置结构锥形束计算机层析的精确成像与Grangeat算法实现

研究了一种新的圆加垂直单弧段的锥顶轨迹的锥形束计算机层析（CT）的完全性条件和精确重建的Grangeat方法，提出了倒置结构锥形束计算机层析的便于实现的圆加垂直多弧段的成像结构及进行精确重建的完全性条件。利用倒置成像结构与现有成像结构之间的等价关系，给出了倒置结构锥形束计算机层析的重建算法。最后，对上述几方面进行了计算机模拟。