Solution Space Coupling in the Random K-Satisfiability Problem

The random K-satisfiability (K-SAT) problem is very difficult when the clause density is close to the satisfiability threshold. In this paper we study this problem from the perspective of solution space coupling. We divide a given difficult random K-SAT formula into two easy sub-formulas and let the two corresponding solution spaces to interact with each other through a coupling field x. We investigate the statistical mechanical property of this coupled system by mean field theory and computer simulations. The coupled system has an ergodicity-breaking (clustering) transition at certain critical value x_d of the coupling field. At this transition point, the mean overlap value between the solutions of the two solution spaces is very close to 1. The mean energy density of the coupled system at its clustering transition point is less than the mean energy density of the original K-SAT problem at the temperature-induced clustering transition point. The implications of this work for designing new heuristic K-SAT solvers are discussed.     

基于Selectope解集和局中人最大满意度的合作对策解的研究

针对决策者在获取Selectope解集后难以聚焦到最终分配方案上的问题,论文对合作对策的解集进行了研究。首先借助Harsanyi红利在局中人中进行分配的思想,得到Selectope解集作为研究问题的可行域。之后,在局中人完全理性的条件下,充分考虑局中人参与合作的初衷,运用超出值的概念,构建了描述局中人最大满意度的目标函数,进而得到基于Selectope解集与局中人最大满意度的非线性规划模型,用于合作对策收益分配问题的求解。最后,通过算例验证了该求解思路的可行性与求解结果的合理性。研究结果表明,论文提出的求解思路能够有效缩减Selectope解集的体量,为决策者提供一个精炼的抉择空间,在一定程度上拓展了Selectope解集的应用,同时,构建的局中人最大满意度的非线性函数对局中人满意度研究也有一定的参考价值。     

List coloring with requests

Let be a graph with a list assignment . Suppose a preferred color is given for some of the vertices; how many of these preferences can be respected when -coloring ? We explore several natural questions arising in this context, and propose directions for further research.     

基于最大期望满意度与背景风险的模糊投资组合模型研究

模糊投资组合是不确定性理论研究的重要领域.然而,由于人的理性局限性,投资者在决策的过程中,可能不是追求理性的效用最大化,而是追求心理满意度的最大化;在金融市场中,投资者不仅面临市场风险,也需要承担由自身因素产生的背景风险.因此,提出了一个考虑背景风险等因素的最大期望满意度模型,该模型的目标是最大化投资组合收益与最小收益证券的差值;最后,以上海证券交易所180指数的十支证券构成的的投资组合为例,分析了此模型在分散投资风险与增加满意度方面的有效性.     

随机产出下考虑小微供应商成本利润率的供应链决策研究

小微型供应商由于产能、资金等限制,其目标可能是实现成本利润率最优,从而提高企业生存能力。基于该观察,区别于多数文献采用利润最优决策准则,本文研究由小微供应商和零售商组成的单周期供应链决策问题。小微供应商面临产出随机风险,以成本利润率最大为目标进行产能决策,零售商以利润最大为目标确定最优订购量。研究发现小微供应商的成本利润率受到自身成本偏重系数以及零售商盈利能力的共同影响,将出现亏损、合理盈利、超额盈利三种情况。并且,零售商采取不同订货策略也会对小微供应商盈利情况产生差异影响。保守(积极)订货策略下,零售商是否盈利取决于自身单位净利润能否弥补单位缺货损失(自身可盈利空间)。本文研究融合现实普遍存在的产出随机问题,为小微供应商和其他供应链成员的产能/订购决策问题提供有益的管理启示。     

A residual-based message passing algorithm for constraint satisfaction problems

Message passing algorithms, whose iterative nature captures complicated interactions among interconnected variables in complex systems and extracts information from the fixed point of iterated messages, provide a powerful toolkit in tackling hard computational tasks in optimization, inference, and learning problems. In the context of constraint satisfaction problems (CSPs), when a control parameter (such as constraint density) is tuned, multiple threshold phenomena emerge, signaling fundamental structural transitions in their solution space. Finding solutions around these transition points is exceedingly challenging for algorithm design, where message passing algorithms suffer from a large message fluctuation far from convergence. Here we introduce a residual-based updating step into message passing algorithms, in which messages with large variation between consecutive steps are given high priority in the updating process. For the specific example of model RB (revised B), a typical prototype of random CSPs with growing domains, we show that our algorithm improves the convergence of message updating and increases the success probability in finding solutions around the satisfiability threshold with a low computational cost. Our approach to message passing algorithms should be of value for exploring their power in developing algorithms to find ground-state solutions and understand the detailed structure of solution space of hard optimization problems.     

Core-generating approximate minimum entropy discretization for rough set feature selection in pattern classification

Rough set feature selection (RSFS) can be used to improve classifier performance. RSFS removes redundant attributes whilst retaining important ones that preserve the classification power of the original dataset. Reducts are feature subsets selected by RSFS. Core is the intersection of all the reducts of a dataset. RSFS can only handle discrete attributes, hence, continuous attributes need to be discretized before being input to RSFS. Discretization determines the core size of a discrete dataset. However, current discretization methods do not consider the core size during discretization. Earlier work has proposed core-generating approximate minimum entropy discretization (C-GAME) algorithm which selects the maximum number of minimum entropy cuts capable of generating a non-empty core within a discrete dataset. The contributions of this paper are as follows: (1) the C-GAME algorithm is improved by adding a new type of constraint to eliminate the possibility that only a single reduct is present in a C-GAME-discrete dataset; (2) performance evaluation of C-GAME in comparison to C4.5, multi-layer perceptrons, RBF networks and k-nearest neighbours classifiers on ten datasets chosen from the UCI Machine Learning Repository; (3) performance evaluation of C-GAME in comparison to Recursive Minimum Entropy Partition (RMEP), Chimerge, Boolean Reasoning and Equal Frequency discretization algorithms on the ten datasets; (4) evaluation of the effects of C-GAME and the other four discretization methods on the sizes of reducts; (5) an upper bound is defined on the total number of reducts within a dataset; (6) the effects of different discretization algorithms on the total number of reducts are analysed; (7) performance analysis of two RSFS algorithms (a genetic algorithm and Johnson’s algorithm).     

多数满意规则的一般陪审团概率及其极限

对于在一陪审团(群体)中,每一个决策者正确判断方案的满意性都具有各自不同概率的情况,建立了陪审团(群体)正确判断方案满意性概率的一般形式的定理.同时,证明了该陪审团(群体)正确判断方案满意性的概率,将随着参与决策者人数的增加趋于它的极限1.     

关系感知在银行业顾客忠诚形成中的中介机制研究

以银行业为背景,以顾客关系感知中的满意和信任为中介变量,建立企业形象、转换成本和服务质量三个典型营销要素影响顾客忠诚意向和忠诚行为的概念模型,并进行了实证检验.研究发现:企业形象、服务质量和转换成本会显著影响顾客忠诚行为,其中服务质量影响最大;顾客满意在企业形象和服务质量对顾客忠诚行为的影响中有不完全中介作用;信任在服务质量对顾客忠诚行为的影响中也有不完全中介作用.此外,顾客忠诚意向是营销要素影响顾客忠诚行为的重要中介变量.