单调线性互补问题的最小原则(II)

在文［１］的基础上，对单调线性互补问题（ＭＬＣＰ）给出了不同于文［１７］的最小原则的另一形式，并提出了一个在有限步内求出单调线性互补问题解集的新算法；给出了单调线性互补问题的三个误差界公式．这些公式推广了文［６］的有关结果，并且较文［８］中的误差界表示形式简洁和易于检验．     

求解一类非单调线性互补问题的路径跟踪法及其计算复杂性

１．引言及记号 线性互补问题的一般形式是;求（ｘ,ｓ） 　　　　　　　 使其中 众所周知,当Ω＋非空时,单调线性互补问题可在多项式时间内求解,而且人们已经设计出了多种求解单调线性互补问题的有效的内点算法（见［１］和［７］）．然而,对于求解非单调线性互补问题的内点算法的研究可以说才刚刚开始．文［２］讨论了当Ｍ为Ｐ矩阵时问题（１）的中心路径的存在唯一性;文［３］给出了设计求解一类非单调线性互补问题的内点算法的一般框架;文［４］给出了求解一类非单调线性互补问题的一种势能函数约减法并讨论了其算法的计算复杂…     

关于一类自由作业机器排序问题

文章研究文［１］中提出的加工时间依赖于机器的自由作业排序问题。Ｍ．Ｄｏｒｏｒ在［１］中提出了一个算法（算法３．４）。最近，Ａ．Ｊ．Ｖａｋｈａｒｉａ、Ｂ．Ｃａｔａｙ［２］及项思明、唐国春［３］均指出Ｍ．Ｄｏｒｏｒ的算法不是最优的。项思明和唐国春提出对这类问题在机器连续加工情形下的一种求解方法，即将排序问题化成指派问题。本文对这种解法作了简化，并回答文［３］中提出的几个问题。     

复数形式的四边形面积公式

复数形式的四边形面积公式李显权（四川省富顺师范学校６４３２００）文［１］给出了复数形式的三角形面积公式：对任意三角形ＡＢＣ有Ｓ△ＡＢＣ＝１２Ｉｍ［（Ｂ－Ａ）（Ｃ－Ａ）］（）当Ａ，Ｂ，Ｃ依逆时针方向绕行时，（）式右边为正值；反之．（）式右边为负值...     

中立型时滞模型的周期正解

本文通过使用某些新技巧，研究了中立型时滞模型Ｎ＇（ｔ）＝Ｎ（ｔ）［ａ（ｔ）－－β（ｔ）－ｂ（ｔ）Ｎ（ｔ－Ｔ（ｔ））－Ｃ（ｔ）Ｎ＇（ｔ－Ｔ（ｔ））］周期正解的存在性，解决了文［１］中的一个公开问题，并改正了文［２］中的错误。     

Drazin逆的一个性质特征

对任意的ｎ阶方阵A ∈C^n×n，本文给出它的Ｄｒａｚｉｎ逆的一个重要性质（见定理１），并给出Ａ的Ｄ－逆的一个求解算法，从而推广了［２］中的结论．     

借助单调区间求解

借助单调区间求解甘肃省武威六中赵多彪文［１］讨论了含参数的对数方程的解法，文［２］对含参数问题的各种解法进行了多方位的探讨，文［３］则对文［１］中的解法进行了改进．本文不揣浅陋，根据教学中的一些体会，对含参数方程有几个解的问题抛开分类讨论的思维定势提...     

关于多复变数Cauchy型积分的边界性质

本文用新的方法研究Ｂ－Ｍ型积分的边界性质，所得结果推进了文［１］的结果，并指出文［４］证明有错误     

一个与G－分次环和G－集的Smash积有关的Maschke－Type定理

对任意群Ｇ，［１］研究了有单位元１的Ｇ－分次环与有限可迁Ｇ－集的Ｓｍａｓｈ积．在本文中，我们对任意可迁Ｇ－集Ａ讨论了具有局部单位元的Ｇ－分次环与Ｇ－集Ａ的Ｓｍａｓｈ积，证明了有关的一个Ｍａｓｃｈｋｅ－ｔｙＰｅ定理．推广了［２］［３］中的一些重要结果．     

求解线性方程组和一种迭代解法

本文对任意线性方程组ＡＸ＝Ｂ（Ａ∈Ｒ（ｎ×ｍ），Ｂ∈Ｒｎ），在文［１］基础上给出了一种迭代算法。其收敛速度比文［１］方法快，并证明了该算法的收敛性。最后，通过几个算例说明了本文算法的有效性。     

Solving Graph Coloring Problems with the Douglas-Rachford Algorithm

We present the Douglas-Rachford algorithm as a successful heuristic for solving graph coloring problems. Given a set of colors, these types of problems consist in assigning a color to each node of a graph, in such a way that every pair of adjacent nodes are assigned with different colors. We formulate the graph coloring problem as an appropriate feasibility problem that can be effectively solved by the Douglas-Rachford algorithm, despite the nonconvexity arising from the combinatorial nature of the problem. Different modifications of the graph coloring problem and applications are also presented. The good performance of the method is shown in various computational experiments.     

扰动方程的改进正则解及其数值分析

对滞右端扰动数据的第一类紧算子病态方程,文[2]给出了改进的Tokhonov正则化解法,本文以此为依据,对该解法举例进行例法分析。     

Simplifying maximum flow computations: The effect of shrinking and good initial flows

Maximum flow problems occur in a wide range of applications. Although already well studied, they are still an area of active research. The fastest available implementations for determining maximum flows in graphs are either based on augmenting path or on push-relabel algorithms. In this work, we present two ingredients that, appropriately used, can considerably speed up these methods. On the theoretical side, we present flow-conserving conditions under which subgraphs can be contracted to a single vertex. These rules are in the same spirit as presented by Padberg and Rinaldi (1990) [12] for the minimum cut problem in graphs. These rules allow the reduction of known worst-case instances for different maximum flow algorithms to equivalent trivial instances. On the practical side, we propose a two-step max-flow algorithm for solving the problem on instances coming from physics and computer vision. In the two-step algorithm, flow is first sent along augmenting paths of restricted lengths only. Starting from this flow, the problem is then solved to optimality using some known max-flow methods. By extensive experiments on instances coming from applications in theoretical physics and computer vision, we show that a suitable combination of the proposed techniques speeds up traditionally used methods.     

An algorithm for solving new trust region subproblem with conic model

The new trust region subproblem with the conic model was proposed in 2005, and was divided into three different cases. The first two cases can be converted into a quadratic model or a convex problem with quadratic constraints, while the third one is a nonconvex problem. In this paper, first we analyze the nonconvex problem, and reduce it to two convex problems. Then we discuss some dual properties of these problems and give an algorithm for solving them. At last, we present an algorithm for solving the new trust region subproblem with the conic model and report some numerical examples to illustrate the efficiency of the algorithm.     

Algorithme de Neumann–Dirichlet pour des problèmes de contact unilatéral : Résultat de convergenceNeumann–Dirichlet algorithm for unilateral contact problems: Convergence results

In this Note, we propose and we prove the convergence of a Neumann–Dirichlet algorithm in order to approximate a Signorini problem between two elastic bodies. The idea is to retain the natural interface between the two bodies as numerical interface for the domain decomposition and to replace the Dirichlet problem in [4] by a variational inequality. To cite this article: G. Bayada et al., C. R. Acad. Sci. Paris, Ser. I 335 (2002) 381–386.     

DCA for solving the scheduling of lifting vehicle in an automated port container terminal

The container was introduced as a universal carrier for various goods in the 1960s and soon became a standard worldwide transportation. The competitiveness of a container seaport is marked by different success factors, particularly the time in port for ships. Operational problems of container terminals is divided into several problems, such as assignment of vessels, loading/unloading and storage of the containers, quay cranes scheduling cite, planning yard cranes cite and assignment of storage containers cite. In this work, the study will focus on piloting yard trucks. Two different types of vehicles can be used, namely automated guided vehicles (AGVs) and lifting vehicles (LVs). An AGV receives a container from a quay crane and transports containers over fixed path. LVs are capable of lifting a container from the ground by itself. The model that we consider is formulated as a mixed integer programming problem, and the difficulty arises when the number of binary variables increases. There are a lot of algorithms designed for mixed integer programming problem such as Branch and Bound method, cutting plane algorithm, . . . By using an exact penalty technique we treat this problem as a DC program in the context of continuous optimization. Further, we combine the DCA with the classical Branch and Bound method for finding global solutions.     

Soft car sequencing with colors: Lower bounds and optimality proofs

This paper is a study of the car sequencing problem, when feature spacing constraints are soft and colors of vehicles are taken into account. Both pseudo-polynomial algorithms and lower bounds are presented for parts of the problem or family of instances. With this set of lower bounds, we establish the optimality (up to the first non-trivial criteria) of 54% of best known solutions for the benchmark used for the Roadef Challenge 2005. We also prove that the optimal penalty for a single ratio constraint N/P can be computed in O(P) and that determining the feasibility of a car sequencing instance limited to a pair of simple ratio constraints can be achieved by dynamic programming. Finally, we propose a solving algorithm exploiting these results within a local search approach. To achieve this goal, a new meta-heuristic (star relinking) is introduced, designed for the optimization of an aggregation of criteria, when the optimization of each single criterion is a polynomial problem.     

无单调性集值变分不等式的一种投影算法

本文给出了求解无单调性集值变分不等式的一个新的投影算法，该算法所产生的迭代序列在Minty变分不等式解集非空且映射满足一定的连续性条件下收敛到解.对比文献[10]中的算法，本文中的算法使用了不同的线性搜索和半空间，在计算本文所引的两个数值例子时，该算法比文献[10]中的算法所需迭代步更少.     

Local search and suffix tree for car-sequencing problem with colors

This paper describes an approximation solution method for the car sequencing problem with colors. Firstly, we study the optimality of problems with a single ratio constraint. This study also introduces a data structure for efficient calculation of the penalties related to ratio constraints. We describe the constructive greedy algorithm and variable neighborhood search adjusted for the problem with colors. Tabu metaheuristic is used to improve the results obtained by VNS. We then represent the cars with their constraints as letters over an alphabet and apply the algorithm to spell the motifs in order to improve the number of batch colors without decreasing the costs associated to the set of ratio constraints. The algorithm achieves 19 out of the 64 best results for instance sets A and B. These instances are the reference instances for Challenge ROADEF.