约束可满足性中求解RB模型实例的算法综述

约束满足问题是人工智能领域中最基本的NP完全问题之一。多年来,随着约束满足问题的深入研究,国内外学者提出多种实例模型。其中,RB模型是一种能生成具有精确相变的增长域约束满足问题实例,其求解难度极具挑战性。为了寻找其求解的新型高效算法,促进约束可满足问题的RB模型求解算法领域的研究,首先从约束满足问题的模型发展、求解技术进行分析;其次,对各类求解RB模型实例算法进行梳理,将求解的算法文献划分为回溯启发式类、信息传播类和元启发式类相关改进算法,从算法原理、改进策略、收敛性和精确度等方面进行对比综述;最后给出求解RB模型实例算法的研究趋势和发展方向。     

基于约束满足的热轧批量计划模型与算法

将热轧批量计划问题作为一个约束满足问题处理,建立不确定计划数的VRPSTw约束满足模型．在求解过程中．先用约束满足的一致性技术过滤变量的值域,收缩搜索空间;然后用变量选择和值选择构造轧制计划的解．为变量赋值之后,实施约束传播,保证每块板坯只被访问一次并动态禁止子回路．在已有的解的基础上,应用基于禁忌的k-opt互换改进解的质量．数据实验证明模型和算法是有效的．     

基于约束满足方法求解炼钢—连铸生产调度问题

针对各阶段均有并行机的炼钢—连铸生产调度问题,建立了问题的约束满足模型．通过分析炼钢—连铸调度问题特点,将其归结为最小化操作开工时间偏移的调度问题．在求解过程中,首先用变量选择和值选择启发式方法构造时间可行的初始调度,然后应用冲突检查算法检测资源冲突，基于回跳的后向修剪组合算法修复冲突,直至得到一个一致性的最终解．数据实验表明本文提出的方法是有效的.     

Solving Hierarchical Constraints over Finite Domains with Local Search

Many real world problems have requirements and constraints which conflict with each other. One approach for dealing with such over-constrained problems is with constraint hierarchies. In the constraint hierarchy framework, constraints are classified into ranks, and appropriate solutions are selected using a comparator which takes into account the constraints and their ranks. In this paper, we present a local search solution to solving hierarchical constraint problems over finite domains (HCPs). This is an extension of local search for over-constrained integer programs WSAT(OIP) to constraint hierarchies and general finite domain constraints. The motivation for this work arose from solving large airport gate allocation problems. We show how gate allocation problems can be formulated as HCPs using typical gate allocation constraints. Using the gate allocation benchmarks, we investigate how constraint heirarchy selection strategies and the problem formulation using two models: a 0–1 linear constraint hierarchy model and a nonlinear finite domain constraint hierarchy model.     

随机约束满足问题相变研究综述

随机约束满足问题是经典的NP完全问题,在理论研究和现实生活中有着广泛应用。研究人员发现随机约束满足问题存在相变现象,近几十年来关于此问题相变的研究成果不断涌现。从随机图着色问题和随机可满足问题2个最经典的随机约束满足问题入手,从算法研究、理论物理和数学证明3个方面综述了随机图着色问题和随机可满足问题的相变研究成果。最后对随机约束满足问题相变的研究趋势进行了展望。     

Issues in the performance measurement of constraint-satisfaction techniques

The richness of the constraint satisfaction problem (or CSP) in representing combinatorial search maladies has resulted in a torrent of techniques for efficiently solving them. These techniques have focused on discovering better backtrack points, learning from dead-ends and avoiding repetitious interference, problem reduction method and the use of network heuristics. Much of this research has derived innovative methods for solving the CSP, however, the evaluations of the techniques have remained diverse and in many cases, statistically inaccurate.Another issue with regard to the performance measurement of constraint satisfaction techniques is the inability to model computational constraint processing cost. It is not uncommon to find evaluations that are based on CSPs that differ only on the percentage of constraints and the tightness of each constraint. This may be justifiable if it can be established that they are the only contributing factors of the performance variable. The three aspects mentioned above comprise this paper's main focus points. They come under the general headings of Modelling CSP Difficulty, Modelling Constraint Cost and Elucidating Major Performance Factors respectively. This paper seeks to provide a set of proposals with respect to the above three well-known areas so as collectively to enhance the robustness of evaluations conducted in the field of constraint satisfaction.     

A genetic algorithm for solving economic lot size scheduling problem

The purpose of this research is to determine an optimal batch size for a product and purchasing policy of associated raw materials. Like most other practical situation, this manufacturing firm has a limited storage space and transportation fleet of known capacity. The mathematical formulation of the problem indicates that the model is a constrained nonlinear integer program. Considering the complexity of solving such model, we investigate the use of genetic algorithms (GAs) for solving this model. We develop GA code with three different penalty functions usually used for constraint optimizations. The model is also solved using an existing commercial optimization package to compare the solution. The detailed computational results are presented.     

约束满足技术在板坯排序中的应用

热轧调度中的板坯排序问题是一类特殊的排序问题,具有约束条件复杂、NP难特点。为了简化问题,将板坯排序问题转化为一个约束满足问题处理。给出板坯排序问题的约束满足模型,设计了基于约束满足和启发式混合求解算法。用3组实际生产数据对算法性能进行验证,说明了算法的有效性。     

基于MAS的分布式约束满足求解在供应链研究中的应用

简要介绍了多智能体系统(MAS)在供应链研究中的应用，给出了约束满足问题(Constraint Satisfaction Problem,CSP)和分布式约束满足问题(Distributed CSP)的定义以及其应用现状，提出了一个利用基于MAS的分布式约束满足求解来研究供应链问题的基本框架，并给出了其求解过程。     

Constraint satisfaction techniques in planning and scheduling

Over the last few years constraint satisfaction, planning, and scheduling have received increased attention, and substantial effort has been invested in exploiting constraint satisfaction techniques when solving real life planning and scheduling problems. Constraint satisfaction is the process of finding a solution to a set of constraints. Planning is the process of finding a sequence of actions that transfer the world from some initial state to a desired state. Scheduling is the problem of assigning a set of tasks to a set of resources subject to a set of constraints. In this paper, we introduce the main definitions and techniques of constraint satisfaction, planning and scheduling from the Artificial Intelligence point of view.     

对象族拓扑约束求解的研究

针对当前对象族模型在求解拓扑约束时存在的缺陷,提出一种求解拓扑约束的新方法,这种方法在求解拓扑约束时,把拓扑约束映射为布尔约束满足问题,通过用SAT求解器求解布尔约束来求解拓扑约束。实践证明,该方法不仅直接关联与拓扑约束指定的特征的语义,而且当模型中存在大量相交的特征时也是可行的,提高了拓扑约束求解的效率。     

Constraint satisfaction with succinctly specified relations

The general intractability of the constraint satisfaction problem (CSP) has motivated the study of the complexity of restricted cases of this problem. Thus far, the literature has primarily considered the formulation of the CSP where constraint relations are given explicitly. We initiate the systematic study of CSP complexity with succinctly specified constraint relations.     

Dynamic constraint satisfaction problems over models

In early phases of designing complex systems, models are not sufficiently detailed to serve as an input for automated synthesis tools. Instead, a design space is constituted by multiple models representing different valid design candidates. Design space exploration aims at searching through these candidates defined in the design space to find solutions that satisfy the structural and numeric design constraints and provide a balanced choice with respect to various quality metrics. Design space exploration in an model-driven engineering (MDE) context is frequently tackled as specific sort of constraint satisfaction problem (CSP). In CSP, declarative constraints capture restrictions over variables with finite domains where both the number of variables and their domains are required to be a priori finite. However, the existing formulation of constraint satisfaction problems can be too restrictive to capture design space exploration in many MDE applications with complex structural constraints expressed over the underlying models. In this paper, we interpret flexible and dynamic constraint satisfaction problems directly in the context of models. These extensions allow the relaxation of constraints during a solving process and address problems that are subject to change and require incremental re-evaluation. Furthermore, we present our prototype constraint solver for the domain of graph models built upon the Viatra2 model transformation framework and provide an evaluation of its performance with comparison to related tools.     

基于约束满足的炼钢批量计划的制定方法

将炼钢批量计划问题转化为一个约束满足问题处理,建立问题的约束满足模型,给出了基于约束满足的求解算法。仿真实验证明了模型和算法是有效的。     

考虑特殊时间约束的混合流水车间调度

针对等待时间受限的准时制混合流水车间调度问题,建立其约束满足优化模型。考虑到模型具有二元变量的复杂性特点,将原问题分解为多能力流水车间调度和机器指派两个子问题。在对多能力流水车间调度问题的约束满足优化求解过程中嵌入邻域搜索,从而提高算法的收敛性。数据实验表明模型和算法是可行和有效的。     

收货时间窗软约束下绿色多式联运路径优化

绿色多式联运不仅能有效降低物流成本,提升物流效率,而且能减少环境污染,随着我国综合运输体系的建设与完善,对绿色多式联运的研究已成为热点问题。针对带收货时间窗的绿色多式联运路径选择问题,将收货时间窗作为软约束,运输时限与收货人满意度结合,同时考虑基于运输成本大小的承运人满意度,构建了满意度权重不确定的绿色多式联运路径选择模型。通过Matlab仿真求解,结果表明,模型对运输时限与收货时间窗的关系把控合理,兼顾了承运人和收货人双方的利益。针对不同的运输货物,通过调整双方满意度权重可以得出更加切合实际的最优运输路径,运输时间不拘泥于固定收货时间窗内,且在运输费用上具有明显的优越性。     

On the phase transitions of random k-constraint satisfaction problems

Constraint satisfaction has received increasing attention over the years. Intense research has focused on solving all kinds of constraint satisfaction problems (CSPs). In this paper, first we propose a random CSP model, named k-CSP, that guarantees the existence of phase transitions under certain circumstances. The exact location of the phase transition is quantified and experimental results are provided to illustrate the performance of the proposed model. Second, we revise the model k-CSP to a random linear CSP by incorporating certain linear structure to constraint relations. We also prove the existence of the phase transition and exhibit its exact location for this random linear CSP model.     

一种基于修改的约束满足算法

求解约束满足问题的修改算法从实始的有冲突的完整解出发，不断修改理有的变量赋值，从而得到无冲突的完整解。本文将启发式方法应用了修改型算法，提出了一种高效的基于修改的约束满足算法。     

两种改进的模拟退火算法求解大值域约束满足问题

随机约束满足问题的相变现象及求解算法是NP-完全问题的研究热点。RB模型（Revised B）是一个非平凡的随机约束满足问题,它具有精确的可满足性相变现象和极易产生难解实例这两个重要特征。针对RB模型这一类具有大值域的随机约束满足问题,提出了两种基于模拟退火的改进算法即RSA（Revised Simulated Annealing Algorithm）和GSA（Genetic-simulated Annealing Algorithm）。将这两种算法用于求解RB模型的随机实例,数值实验结果表明：在进入相变区域时,RSA和GSA算法依然可以有效地找到随机实例的解,并且在求解效率上明显优于随机游走算法。在接近相变阈值点时,由这两种算法得到的最优解仅使得极少数的约束无法满足。     

协同设计中定量化约束求解方法

通过对约束满足与约束冲突的分析，提出了约束求解的定量化策略．基于变量不确定性，量化了约束满足程度与约束冲突程度，解决了约束求解过程中的优先权问题；给出了约束变化量及关联函数，为约束求解确立了具体的目标和实施方法，实现了约束求解过程的有序搜索．定量化约束求解策略不仅实现了对约束的有序及有效求解，而且真正地实现了在上游约束求解过程中定量地考虑下游约束求解问题．最后，利用随机仿真技术实现了基于变量不确定性的约束求解策略的验证．