基于遗传算法的二层线性规划问题的求解算法

本研究了下层以最优解返回上层的二层线性规划问题的遗传算法。在提出可行度概念的基础上，构造了二层线性规划上层规划问题的适应度函数，由此设计了求解二层线性规划问题遗传算法。为了提高遗传算法处理约束的能力，在产生初始种群时将随机产生的初始种群变为满足约束的初始种群，从而避免了使用罚函数处理约束带来的困难，最后用实例验证了本提出的二层线性规划的遗传算法的有效性。     

Asymptotic analysis of the effect of arrival model uncertainties in some optimal routing problems

We study the effect of arrival model uncertainties on the optimal routing in a system of parallel queues. For exponential service time distributions and Bernoulli routing, the optimal mean system delay generally depends on the interarrival time distribution. Any error in modeling the arriving process will cause a model-based optimal routing algorithm to produce a mean system delay higher than the true optimum. In this paper, we present an asymptotic analysis of the behavior of this error under heavy traffic conditions for a general renewal arrival process. An asymptotic analysis of the error in optimal mean delay due to uncertainties in the service time distribution for Poisson arrivals was reported in Ref. 6, where it was shown that, when the first moment of the service time distribution is known, this error in performance vanishes asymptotically as the traffic load approaches the system capacity. In contrast, this paper establishes the somewhat surprising result that, when only the first moment of the arrival distribution is known, the error in optimal mean delay due to uncertainties in the arrival model is unbounded as the traffic approaches the system capacity. However, when both first and second moments are known, the error vanishes asymptotically. Numerical examples corroborating the theoretical results are also presented.This work was supported by the National Science Foundation under Grants ECS-88-01912 and EID-92-12122 and by NASA under Contract NAG 2-595.The authors wish to thank an anonymous referee for pointing out Ref. 20, thus avoiding the need for an explicit proof of convexity of the cost function considered in the paper.     

Polynomial-time approximation schemes for packing and piercing fat objects

We consider two problems: given a collection of n fat objects in a fixed dimension, (1) ( packing) find the maximum subcollection of pairwise disjoint objects, and (2) ( piercing) find the minimum point set that intersects every object. Recently, Erlebach, Jansen, and Seidel gave a polynomial-time approximation scheme (PTAS) for the packing problem, based on a shifted hierarchical subdivision method. Using shifted quadtrees, we describe a similar algorithm for packing but with a smaller time bound. Erlebach et al.'s algorithm requires polynomial space. We describe a different algorithm, based on geometric separators, that requires only linear space. This algorithm can also be applied to piercing, yielding the first PTAS for that problem.     

Five-step phase-shifting algorithms with unknown values of phase shift

The presented work offers new algorithms for phase evaluation in interferometric measurements. Several phase-shifting algorithms with an arbitrary but constant phase-shift between captured intensity frames are proposed. These phase calculation algorithms need to measure five frames of the intensity of the interference field. The algorithms are similarly derived as so called Carré algorithm. The phase evaluation process then does not depend on the linear phase shift errors. Furthermore, the detailed analysis of the algorithms with respect to most important factors, which affect interferometric measurements, is carried out. It is also studied the dependency of the evaluation algorithms on the phase shift values, and the proposed phase calculation algorithms are compared with respect to the resulting phase errors. The influence of most important factors in the measurement and evaluation process was simulated as systematic and random errors using a proposed mathematical model.     

Convergent Algorithm Based on Progressive Regularization for Solving Pseudomonotone Variational Inequalities

In this paper, we extend the Moreau-Yosida regularization of monotone variational inequalities to the case of weakly monotone and pseudomonotone operators. With these properties, the regularized operator satisfies the pseudo-Dunn property with respect to any solution of the variational inequality problem. As a consequence, the regularized version of the auxiliary problem algorithm converges. In this case, when the operator involved in the variational inequality problem is Lipschitz continuous (a property stronger than weak monotonicity) and pseudomonotone, we prove the convergence of the progressive regularization introduced in Refs. 1, 2.     

Algorithms for Finite and Semi-Infinite Min–Max–Min Problems Using Adaptive Smoothing Techniques

We develop two implementable algorithms, the first for the solution of finite and the second for the solution of semi-infinite min-max-min problems. A smoothing technique (together with discretization for the semi-infinite case) is used to construct a sequence of approximating finite min-max problems, which are solved with increasing precision. The smoothing and discretization approximations are initially coarse, but are made progressively finer as the number of iterations is increased. This reduces the potential ill-conditioning due to high smoothing precision parameter values and computational cost due to high levels of discretization. The behavior of the algorithms is illustrated with three semi-infinite numerical examples.     

Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width

The Multicut problem can be defined as: given a graph G and a collection of pairs of distinct vertices {s_i,t_i} of G, find a minimum set of edges of G whose removal disconnects each s_i from the corresponding t_i. Multicut is known to be NP-hard and Max SNP-hard even when the input graph is restricted to being a tree. The main result of the paper is a polynomial-time approximation scheme (PTAS) for Multicut in unweighted graphs with bounded degree and bounded tree-width. That is, for any ε>0, we present a polynomial-time (1+ε)-approximation algorithm. In the particular case when the input is a bounded-degree tree, we have a linear-time implementation of the algorithm. We also provide some hardness results: we prove that Multicut is still NP-hard for binary trees and that it is Max SNP-hard if we drop any of the three conditions (unweighted, bounded-degree, bounded tree-width). Finally we show that some of these results extend to the vertex version of Multicut and to a directed version of Multicut.     

A Hybrid Approach to Scheduling with Earliness and Tardiness Costs

A hybrid technique using constraint programming and linear programming is applied to the problem of scheduling with earliness and tardiness costs. The linear model maintains a set of relaxed optimal start times which are used to guide the constraint programming search heuristic. In addition, the constraint programming problem model employs the strong constraint propagation techniques responsible for many of the advances in constraint programming for scheduling in the past few years. Empirical results validate our approach and show, in particular, that creating and solving a subproblem containing only the activities with direct impact on the cost function and then using this solution in the main search, significantly increases the number of problems that can be solved to optimality while significantly decreasing the search time.     

K终端可靠度分解算法中多边形→链简化定理的完善

无向网络K终端可靠度的分解算法中,包括多边形→链简化在内的等可靠度简化和分解定理结合,可以降低算法的复杂度。本文完善了边随机无向网络和混合随机无向网络的4#,6#,7#型多边形→链简化定理。计算机编程验证了其正确性。     

A class of polynomial variable metric algorithms for linear optimization

In the paper, the behaviour of interior point algorithms is analyzed by using a variable metric method approach. A class of polynomial variable metric algorithms is given achieving O ((n/β)L) iterations for solving a canonical form linear optimization problem with respect to a wide class of Riemannian metrics, wheren is the number of dimensions and β a fixed value. It is shown that the vector fields of several interior point algorithms for linear optimization is the negative Riemannian gradient vector field of a linear a potential or a logarithmic barrier function for suitable Riemannian metrics. Research Partially supported by the Hungarian National Research Foundation, Grant Nos. OTKA-T016413 and OTKA-2116.