Solution techniques for the Large Set Covering Problem

Given a finite set E and a family F={E₁,…,E_m} of subsets of E such that F covers E, the famous unicost set covering problem (USCP) is to determine the smallest possible subset of F that also covers E. We study in this paper a variant, called the Large Set Covering Problem (LSCP), which differs from the USCP in that E and the subsets E_i are not given in extension because they are very large sets that are possibly infinite. We propose three exact algorithms for solving the LSCP. Two of them determine minimal covers, while the third one produces minimum covers. Heuristic versions of these algorithms are also proposed and analysed. We then give several procedures for the computation of a lower bound on the minimum size of a cover. We finally present algorithms for finding the largest possible subset of F that does not cover E. We also show that a particular case of the LSCP is to determine irreducible infeasible sets in inconsistent constraint satisfaction problems. All concepts presented in the paper are illustrated on the k-colouring problem which is formulated as a constraint satisfaction problem.     

Definability of Geometric Properties in Algebraically Closed Fields

We prove that there exists no sentence F of the language of rings with an extra binary predicat I₂ satisfying the following property: for every definable set X ? ?², X is connected if and only if (?, X) ? F, where I₂ is interpreted by X. We conjecture that the same result holds for closed subset of ?². We prove some results motivated by this conjecture.     

求解约束极大极小问题的一种熵函数法

１引言熵函数法的原始思想源于Ｋｒｅｉｓｓｅｌｍｅｉｅｒ和Ｓｔｅｉｎｈａｕｓｅｒ于１９７９年发表的文［１］．由于使用该方法容易编制可以求解多类优化问题的通用软件,并在具有某种凸性的情况下都能求得满足工程精度要求的解,因而受到国内外工程技术人员的喜爱,进入八十年代以来,该方法被广泛地应用于结构优化和工程设计等领域［２－５］．近年来,熵函数法在求解约束和无约束极大极小问题、线性规划以及半无限规划等问题的算法研究中,也取得了一些很好的成果［６－９］带有等式或不等式约束的极大极小问题是一类具有广泛代表性的…     

有偿付约束的无限期资产经济均衡的存在性

本文通过一个简单的模型证明了有偿付约束的无限期资产经济均衡存在性,所用条件与已有文献相比更加简明．这一研究可望为我们今后研究无限期经济提供方向：同时也可以更好地理解偿付约束（或保证金制度）在资本市场中的作用     

均衡约束数学规划问题的一种新的约束规格

本文研究了均衡约束数学规划(MPEC)问题.利用其弱稳定点,获得了一种新的约束规格–MPEC的伪正规约束规格.用一种简单的方式,证明了该约束规格是介于MPEC-MFCQ(即MPEC,Mangasarian-Fromowitz约束规格)与MPEC-ACQ(即MPEC,Abadie约束规格)之间的约束规格,因此该约束规格也可以导出MPEC问题的M-稳定点.最后通过两个例子,说明了该约束规格与MPEC-MFCQ以及与MPEC-ACQ之间是严格的强弱关系.     

模糊数和模糊值函数的等式限定运算

通过模糊数的结构元表示方法,利用两个单调函数的自反单调变换构造了等式限定算子,推广了文[6]中的等式限定运算,处理了存在负模糊情况下关于乘法运算的不可逆问题.同时,本文还将等式限定运算推广到模糊值函数上,提出了模糊值函数等式限定运算的结构元方法,解决了模糊值函数运算的不可逆问题.     

Hybrid Flow-Shop: a Memetic Algorithm Using Constraint-Based Scheduling for Efficient Search

The paper considers the hybrid flow-shop scheduling problem with multiprocessor tasks. Motivated by the computational complexity of the problem, we propose a memetic algorithm for this problem in the paper. We first describe the implementation details of a genetic algorithm, which is used in the memetic algorithm. We then propose a constraint programming based branch-and-bound algorithm to be employed as the local search engine of the memetic algorithm. Next, we present the new memetic algorithm. We lastly explain the computational experiments carried out to evaluate the performance of three algorithms (genetic algorithm, constraint programming based branch-and-bound algorithm, and memetic algorithm) in terms of both the quality of the solutions produced and the efficiency. These results demonstrate that the memetic algorithm produces better quality solutions and that it is very efficient.     

An application of matrix computations to classical second-order optimality conditions

For finite dimensional optimization problems with equality and inequality constraints, a weak constant rank condition (WCR) was introduced by Andreani–Martinez–Schuverdt (AMS) (Optimization 5–6:529–542, 2007) to study classical necessary second-order optimality conditions. However, this condition is not easy to check. Using a polynomial and matrix computation tools, we can substitute it by a weak constant rank condition (WCRQ) for an approximated problem and we present a method for checking points that satisfy WCRQ. We extend the result of (Andreani et al. in Optimization 5–6:529–542, 2007), we show that WCR can be replaced by WCRQ and we prove that these two conditions are independent.     

陆用定位定向系统定位精度标准检测线设计

定位定向系统是自行火炮的核心设备,其定位精度直接影响火控系统射击诸元计算的准确性,是关键的战术技术指标。针对定位定向系统的定位精度在不同路线上的试验结果表现出的较大差异且陆用定位定向系统鉴定领域检测线不规范等问题,研究定位定向系统的定位误差产生机理,根据里程计标度因数误差和航向角误差这两种主要误差与定位误差定量关系,分析检测路形、路况对定位精度的影响,并通过行车实验验证了理论分析的准确性。考虑到建造成本和试验成本的实际问题,同时兼顾测试效率和工程可实现性,设计了一条简洁等效定位精度标准检测线,提出了定位定向系统定位精度试验场建设方案和选取最优原则,为科学鉴定定位定向系统的定位精度提供理论依据。     

Quasi-Multiplier Rules for Quasidifferentiable Extremum Problems

The purpose of the present article is to contribute to clarify the role of the Lagrange multipliers within the theory of the first order necessary optimality conditions for nonsmooth constrained optimization, when the directional derivatives of functions involved in the extremum problems are not sublinear. This task is accomplished in the particular case of quasidifferentiable problems with side constraints. In such setting, making use of the image-space approach, it is possible to establish a generalized (nonlinear) separation result by means of which a new Lagrange principle is obtained. According to this principle, which seems to fit better quasidifferentiable extremum problems than the classic one, the concept of linear multiplier is to be replaced with that of quasi-multiplier, a sublinear and continuous functional whose existence can be guaranteed under mild assumptions, even when classic multipliers fail to exist. Such as extension allows to formulate in terms of Lagrange function the known optimality necessary condition for unconstrained quasidifferentiable optimization expressed in form of quasidifferential inclusion. Along with this, other multiplier rules are established.