DEPICT:A High-level Formal Language for Modeling Constraint Satisfaction Problems

The past decade witnessed rapid development of constraint satisfaction technologies, where algorithms are now able to cope with larger and harder problems. However, owing to the fact that constraints are inherently declarative, attention is quickly turning toward developing high-level programming languages within which such problems can be modeled and also solved. Along these lines, this paper presents DEPICT, the language. Its use is illustrated through modeling a number of benchmark examples. The paper continues with a description of a prototype system within which such models may be interpreted. The paper concludes with a description of a sample run of this interpreter showing how a problem modeled as such is typically solved.

Reduction and Analysis of a Max-Plus Linear System to a Constraint Satisfaction Problem for Mixed Integer Programming

This research develops a solution method for project scheduling represented by a max-plus-linear (MPL) form. Max-plus-linear representation is an approach to model and analyze a class of discrete-event systems, in which the behavior of a target system is represented by linear equations in max-plus algebra. Several types of MPL equations can be reduced to a constraint satisfaction problem (CSP) for mixed integer programming. The resulting formulation is flexible and easy-to-use for project scheduling;for example, we can obtain the earliest output times, latest task-starting times, and latest input times using an MPL form. We also develop a key method for identifying critical tasks under the framework of CSP. The developed methods are validated through a numerical example.

Autonomous planning system based on temporal constraint satisfaction

In order to realize spacecraft autonomy activity duration and complex temporal relations must be taken into consideration. In the space mission planning system, the traditional planners are unable to describe this knowledge, so an object-oriented temporal knowledge representation method is proposed to model every activity as an object to describe the activity's duration, start-time, end-time and the temporal relations with other activities. The layered planning agent architecture is then designed for spacecraft autonomous operation, and the functions of every component are given. A planning algorithm based on the temporal constraint satisfaction is built in detail using this knowledge representation and system architecture. The prototype of Deep Space Mission Autonomous Planning System is implemented. The results show that with the object-oriented temporal knowledge description method, the space mission planning system can be used to describe simultaneous activities, resource and temporal constraints, and produce a complete plan for exploration mission quickly under complex constraints.

The Application of Constraint Satisfaction Technique in Conflict Detection and Resolution

The conflict detection and resolution in collaborative design is a key issue to maintain multi disciplinary design consistency. This paper proposes a new method for conflict detection and resolution based on constraint satisfaction technique. The representation of design constraint, the interval arithmetic of the constraint satisfaction problem CSP and the conflict resolution strategy based on constraint relaxation and adjustment are introduced. A constraint satisfaction based conflict detection and resolution tool CSCDR is then developed. It can help collaborative designers to detect and resolve the conflicts in time in the early stage of the design process so that the unnecessary design iteration and repeated negotiation are avoided and the design efficiency is then much improved. A design case illustrates the effectiveness of CSCDR.

考虑个体客户满意度的多车程生鲜品配送路径优化

随着生鲜电商的兴起,生鲜品的道路运输量越来越大,其配送任务越来越复杂,提升客户满意度是生鲜品配送的重要目标组成。文章以一个具有配送自主权的生鲜品供应商为研究对象,以整个计划周期内生鲜品配送的车辆运输成本最小及客户满意度最大为双目标,且客户满意度从顾客的个体视角考虑,构建双目标多车程带时间窗及考虑订单打包时间的车辆路径优化模型。基于ε-约束方法,设计了两阶段变邻域搜索(VNS)和模拟退火(SA)相结合的元启发式算法,基于车辆构造初始路线,并针对性地提出了3点改进措施,包括通过数学性质推导下界、减少求解过程中不必要的搜索空间以及规避求解过程中被支配解的后优化处理。最后,以Solomon标准算例为基础构造算例对所设计的算法进行了计算实验,其求解结果表明:其设计的算法具有有效性,并通过敏感性分析得出相关管理启示。

云资源调度的回答集程序描述性求解

针对求解难度为NP完全的基础设施即服务(IaaS)模式云资源调度问题,本文提出一种基于回答集程序(ASP)的描述性优化求解方法,并对其正确性进行分析。首先,把满足虚拟机CPU使用的情况下关闭尽可能多的主机做为减少云平台能耗的方法,将云资源调度问题形式化表述;其次,结合形式化描述以及减少云平台能耗的策略,将云资源调度问题用ASP编码为描述性(优化)问题,并分析其正确性;最后,在公开的PlanetLab数据集上进行实验,结果显示,ASP方法可在保障服务质量的同时减少集群能耗,最高可节能13%以上。这表明ASP方法在云资源调度问题上是有效的,从而提供一种易理解、易修改并能充分利用ASP最新工具成果的有效云资源调度新方法。

两种高效局部搜索算法求解RB模型实例

RB(revised B)模型是一种在约束可满足问题中具备精确相变增长域的随机实例模型,提出两种高效的启发式局部搜索算法用于解决RB模型生成的大值域约束可满足问题。首先为基于权重指导搜索的W-MCH算法,该算法通过约束判断和违反约束数计分来进行搜索,并引入了基于约束违反概率的权重计算公式,根据其关联的约束权重进行修正,再对变量进行迭代调整。然后提出最小化值域的MDMCH算法,该算法通过记录违反约束和逐步消除已违反约束变量的启发式策略来减少搜索空间,并在最小化后的变量域内重新校准变量赋值,进而有效提高算法的收敛速度。此外,还提出了融入模拟退火策略的WSCH和MDSCH算法,这两种算法都能根据变量的表征特点对变量域进行针对性的搜索。实验结果表明,与多种启发式算法相比,这两种算法在精度与时间效率方面均呈现明显提升,在复杂难解的实例中能够提供高效的求解效率,验证了算法的有效性和优越性。

基于文献计量的国外生态旅游游客管理研究热点分析

游客管理是旅游目的地和景区管理的关键环节,对推动生态旅游资源的保护与可持续发展具有重要意义,通过对国外生态旅游游客管理研究情况进行分析。本研究运用CiteSpace软件,对Web of Science数据库中近30年收录的有关生态旅游游客管理方面的文献,进行关键词聚类和时间线视图分析国外生态旅游游客管理研究热点。结果表明:游客教育研究热点利用教育和宣传等手段,实现旅游目的地的可持续发展;游客行为约束通过游客指南、科普视频和语音解说等手段提升游客的环保意识,约束游客行为;游客安全管理利用解说牌和导游讲解等方式向游客传播安全知识,实现游客安全管理;游客对目的地管理的反馈是当前研究的热点,主要集中在评估游客满意度、环境保护措施、当地文化保护、参与度以及教育和信息传达等方面。据此,提出应该重视实施游客教育、加强游客行为管理、重视游客体验反馈等建议。

基于学习-推理的约束求解方法研究进展

机器学习与自动推理的融合是当前人工智能研究的新趋势.约束满足问题是人工智能研究的经典问题,现实世界中大量的调度、规划和配置等问题均可以建模为约束满足问题,高效的求解算法一直是研究热点.近年来涌现出众多将机器学习应用于约束满足问题求解的新方法,这些基于“学习-推理”的新方法为约束满足问题求解开辟了新方向并展示出巨大发展潜力,方法的突出优点是适应性强、可在线优化并具有更强的可扩展性.将当前的“学习-推理”方法分为基于消息传递神经网络、基于序列到序列和基于最优化等3类进行综述,详细分析各类方法的特点和在不同的问题集上求解效果,尤其对每类方法所涵盖的相关工作进行多角度的对比分析.最后,对基于“学习-推理”的约束求解方法进行总结和展望.

船舶动力定位非线性模型预测控制

针对受船舶运动状态和推力饱和约束影响的动力定位控制问题,本文提出了一种非线性模型预测控制方法。依据多面体描述理论建立了船舶动力定位多面体描述偏差模型,针对上述模型采用线性矩阵不等式设计非线性模型预测控制器中的终端要素,并证明了闭环系统的稳定性。仿真结果表明:设计的控制器能在满足约束条件和受环境干扰条件下快速控制船舶稳定在计划航向和计划船位,验证了控制器的有效性和本质鲁棒性。

Concurrent Constraint Programming:A Language and Its Execution Model

To overcome inefficiency in traditional logic programming, a declarative programming language COPS is designed based on the notion of concurrent constraint programming (CCP). The improvement is achieved by the adoption of constraint-based heuristic strategy and the introduction of deterministic components in the framework of CCP. Syntax specification and an operational semantic description are presented.

Constraints Based Decision Support for Site-Specific Preliminary Design of Wind Turbines

This study presents a decision-support tool for preliminary design of a horizontal wind turbine system. The function of this tool is to assist the various actors in making decisions about choices inherent to their activities in the field of wind energy. Wind turbine cost and site characteristics are taken into account in the used models which are mainly based on the engineering knowledge. The present tool uses a constraint-modelling technique in combination with a CSP solver (numerical CSPs which are based on an arithmetic interval). In this way, it generates solutions and automatically performs the concept selection and costing of a given wind turbine. The data generated by the tool and required for decision making are: the quality index of solution (wind turbine), the amount of energy produced, the total cost of the wind turbine and the design variables which define the architecture of the wind turbine system. When applied to redesign a standard wind turbine in adequacy with a given site, the present tool proved both its ability to implement constraint modelling and its usefulness in conducting an appraisal.

An Optimized Constraint Decomposition Method in Concurrent Engineering

In order to facilitate solution, a complex problem is normally decomposed into many small sub-problems during product development process. Teams are formed to resolve each sub-problem. The original problem is resolved from solutions of sub-problems. Ideally, sub-problems are not only mutually independent but also inherent parameters of original problem. Solution of original problem can be directly derived from the collection of solutions from simplified sub-problems. In practice, the degree of interdependency is indeed reduced, sub-problems are neither totally independent nor all inherent parameters of original problem. This paper discusses team coordination under this condition and design solution from each team, which not only satisfies total requirements but also is an optimal one. The suggested optimized constraint decomposition method will insure workable Pareto solution.

资源独立工作流可满足性的最小增量模式回溯

工作流可满足性是业务安全规划的基本问题,正在面临高资源配比(资源数n显著大于步骤数k)造成的性能挑战.在资源独立约束下,其最高效求解途径是模式空间上的增量回溯法IPB.为克服结点真实性验证的性能瓶颈,它增量计算模式k指派(二部)图及其(左完备)匹配,分别需要O(kn)和O(k^(2))时间.利用父子模式的原子差异增量计算完全指派图,只需O(n)时间,特别是其实际性能,将随模式块规模增长迅速提高.但该图的O(kn)规模导致了同样的增量匹配时间.进而引入完备k核心匹配概念,证明其存在性等价于左完备匹配,且其增量计算时间为O(k^(2)).由此,建立了时间复杂度更低的最小增量模式回溯法.在含互斥和两种全局值势约束而授权比例约为1/4的扩展公开实例集上进行实验,结果表明:当n/k=10(及n/k=100),而k变化时,该方法较IPB有平均超过2(及5)倍、最低1.5(及2.9)倍的性能优势;当k=18(及k=36),而n/k=2~4096(及n/k=2~2048)时,该方法有平均超过2.6(及3.6)倍优势;而较2021年Minizinc挑战赛的冠军求解器Google OR-Tools CP-SAT,该方法最低有超过3倍优势.

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

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

约束决策轮联合床旁约束核查单在危重患者中应用效果研究

目的探讨约束决策轮联合床旁约束核查单在危重患者中的临床应用效果。方法抽选重庆市长寿区人民医院2021年3月-2022年3月接收的危重患者200例作为研究对象,按随机数字表法将其分成2组,每组100例。对照组在护士常规经验评估后决定是否给予约束,试验组予以约束决策轮联合床旁约束核查单管理,对比分析2组患者的约束情况及不良事件发生情况。结果试验组患者的约束率显著低于对照组(P<0.05);试验组约束皮肤异常、肢端水肿及情绪烦躁等发生率均显著低于对照组(P<0.05);试验组满意度比对照组高,存在显著性差异(P<0.05)。结论约束决策轮联合床旁约束核查单能有效降低危重患者的约束率,避免约束皮肤异常等不良事件发生,并能提升患者及家属的满意度,值得借荐。

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 fiuctuation 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.

基于改进布谷鸟搜索的卫星成像规划方法

针对多卫星区域目标的成像规划问题,提出一种基于改进布谷鸟搜索的卫星成像规划方法。为最大限度地利用卫星资源,首先基于卫星的单次过境活动将区域目标按条带分解,然后考虑卫星姿态约束、传感器使用约束、过境时间约束、成像时云量及光照约束等,建立约束满足模型,针对模型设计编码和更新策略,并在布谷鸟搜索算法中引入非线性惯性权重对其进行改进,最后采用改进的布谷鸟搜索算法求解约束满足模型。求解结果表明,与遗传算法相比,本文算法的收敛性好、目标完成率高且稳定性强,验证了该算法的有效性。

复杂约束条件下导引头抗干扰试验样本空间分析

针对试验样本空间组成要素众多、动态变化且存在复杂关联约束的特点,围绕典型作战场景下导引头、目标、背景和干扰等4类要素及其相互作用,提出复杂约束条件下抗干扰试验样本空间的分析框架,实现“典型作战场景—全干扰对抗要素—全因子试验样本空间—约束满足的有限样本空间”的转化与映射。同时,重点关注对抗战术动态博弈影响下样本空间规范化描述以及多重约束下样本空间的不规则特征分析等问题,提出综合运用复杂网络、图分解、约束满足优化等理论解决其中关键问题的建模流程,为结合典型作战实例进行深入分析及后续的试验设计提供有效输入。

QFT preflter design for multivariable systems using interval constraint satisfaction technique

In this paper, a computationally efficient method is proposed for automated design of the prefilters for multivariable systems. In quantitative feedback theory （QFT） method, proposed by Horowitz, the prefilter is designed to achieve the desired tracking specifications. In the proposed approach, we pose the prefilter design problem as an interval constraint satisfaction problem and solve it using the well-established interval constraint satisfaction techniques. The proposed method finds optimal values of the parameters of fixed structure prefilter within the initial search domain. An approach based on prefilter synthesis for single-input single-output is already developed. The purpose of this paper is to extend this approach to QFT prefilter design for general multivariable systems. To validate the above design approach, we applied the method to a laboratory setup of magnetic levitation system.