Algorithms for Computing Minimal Unsatisfiable Subsets of Constraints

Much research in the area of constraint processing has recently been focused on extracting small unsatisfiable “cores” from unsatisfiable constraint systems with the goal of finding minimal unsatisfiable subsets (MUSes). While most techniques have provided ways to find an approximation of an MUS (not necessarily minimal), we have developed a sound and complete algorithm for producing all MUSes of an unsatisfiable constraint system. In this paper, we describe a relationship between satisfiable and unsatisfiable subsets of constraints that we subsequently use as the foundation for MUS extraction algorithms, implemented for Boolean satisfiability constraints. The algorithms provide a framework with which many related subproblems can be solved, including relaxations of completeness to handle intractable instances, and we develop several variations of the basic algorithms to illustrate this. Experimental results demonstrate the performance of our algorithms, showing how the base algorithms run quickly on many instances, while the variations are valuable for producing results on instances whose complete results are intractably large. Furthermore, our algorithms are shown to perform better than the existing algorithms for solving either of the two distinct phases of our approach.     

The patient bed assignment problem solved by autonomous bat algorithm

The patient bed assignment problem consists of managing, in the best possible way, a set of beds with particular features and assigning them to a set of patients with special requirements. This assignment problem can be seen an optimization problem, of which the intended aims are usually to minimize the number of internal movements within a unit and to maximize bed usage according to the levels of criticality of the patients, among others. The usual approaches for solving this problem follow a traditional model based on the constraint programming paradigm, mainly using hard constraints. However, in real-life problems, constraints that should ideally be satisfied are often violated. In this paper, we present a new model for the patient bed assignment problem based on the minimum sum of unsatisfied constraints. This technique enables the consideration of soft constraints in the potential solutions that exhibit the best performance. The aim is to find the assignment that minimizes a weighted sum of the unsatisfied constraints. To this end, we use an autonomous binary version of the bat algorithm, which is an optimization technique inspired by the bio-sonar behaviour of microbats, to find the best set of potential solutions without requiring any expert user knowledge to achieve an efficient solution process. To validate our proposal, we use our model to solve problem instances based on data from several hospitals, and we perform a detailed comparative statistical analysis with a traditional constraint programming solver and several well-known optimization algorithms, including the classic bat algorithm. Promising results show that our approach is capable of efficiently solving 30 instances with decreased solution times.     

Abstracting soft constraints: Framework, properties, examples

Soft constraints are very flexible and expressive. However, they are also very complex to handle. For this reason, it may be reasonable in several cases to pass to an abstract version of a given soft constraint problem, and then to bring some useful information from the abstract problem to the concrete one. This will hopefully make the search for a solution, or for an optimal solution, of the concrete problem, faster.In this paper we propose an abstraction scheme for soft constraint problems and we study its main properties. We show that processing the abstracted version of a soft constraint problem can help us in finding good approximations of the optimal solutions, or also in obtaining information that can make the subsequent search for the best solution easier.We also show how the abstraction scheme can be used to devise new hybrid algorithms for solving soft constraint problems, and also to import constraint propagation algorithms from the abstract scenario to the concrete one. This may be useful when we don't have any (or any efficient) propagation algorithm in the concrete setting.     

Automatic Generation of Redundant Models for Permutation Constraint Satisfaction Problems

If we have two representations of a problem as constraint satisfaction problem (CSP) models, it has been shown that combining the models using channeling constraints can increase constraint propagation in tree search CSP solvers. Handcrafting two CSP models for a problem, however, is often time-consuming. In this paper, we propose model induction, a process which generates a second CSP model from an existing model using channeling constraints, and study its theoretical properties. The generated induced model is in a different viewpoint, i.e., set of variables. It is mutually redundant to and can be combined with the input model, so that the combined model contains more redundant information, which is useful to increase constraint propagation. We also propose two methods of combining CSP models, namely model intersection and model channeling. The two methods allow combining two mutually redundant models in the same and different viewpoints respectively. We exploit the applications of model induction, intersection, and channeling and identify three new classes of combined models, which contain different amounts of redundant information. We construct combined models of permutation CSPs and show in extensive benchmark results that the combined models are more robust and efficient to solve than the single models.     

Increasing Constraint Propagation by Redundant Modeling: an Experience Report

This paper describes our experience with a simple modeling and programming approach for increasing the amount of constraint propagation in the constraint solving process. The idea, although similar to redundant constraints, is based on the concept of redundant modeling. We introduce the notions of CSP model and model redundancy, and show how mutually redundant models can be combined and connected using channeling constraints. The combined model contains the mutually redundant models as sub-models. Channeling constraints allow the sub-models to cooperate during constraint solving by propagating constraints freely amongst the sub-models. This extra level of pruning and propagation activities becomes the source of execution speedup. real-life nurse rostering system. We perform two case studies to evaluate the effectiveness and efficiency of our method. The first case study is based on the simple and well-known n-queens problem, while the second case study applies our method in the design and construction of a real-life nurse rostering system. Experimental results provide empirical evidence in line with our prediction.     

Filtering algorithms for the multiset ordering constraint

Constraint programming (CP) has been used with great success to tackle a wide variety of constraint satisfaction problems which are computationally intractable in general. Global constraints are one of the important factors behind the success of CP. In this paper, we study a new global constraint, the multiset ordering constraint, which is shown to be useful in symmetry breaking and searching for leximin optimal solutions in CP. We propose efficient and effective filtering algorithms for propagating this global constraint. We show that the algorithms maintain generalised arc-consistency and we discuss possible extensions. We also consider alternative propagation methods based on existing constraints in CP toolkits. Our experimental results on a number of benchmark problems demonstrate that propagating the multiset ordering constraint via a dedicated algorithm can be very beneficial.     

一种基于图分解的几何约束求解方法

为了提高几何约束求解的效率和鲁棒性 ,对基于图的构造方法进行了改进 ,即加入虚约束进行扩展和过约束问题的一致性判定 ,提出了一种基于图分解的方法 ,用此方法可以处理包括完全约束、过约束和欠约束等多种情况的约束求解问题 ,另外 ,在该方法中还通过引入分解树将约束求解的范围由整体下降到局部 ,使大部分求解过程能够采用几何求解实现 ,提高了求解和后续修改的效率 ,通过实验数据测试证明 ,该方法对于大型约束求解问题可以达到实时处理的效果 ,具有较强的实用性     

Bagging Constraint Score for feature selection with pairwise constraints

Constraint Score is a recently proposed method for feature selection by using pairwise constraints which specify whether a pair of instances belongs to the same class or not. It has been shown that the Constraint Score, with only a small amount of pairwise constraints, achieves comparable performance to those fully supervised feature selection methods such as Fisher Score. However, one major disadvantage of the Constraint Score is that its performance is dependent on a good selection on the composition and cardinality of constraint set, which is very challenging in practice. In this work, we address the problem by importing Bagging into Constraint Score and a new method called Bagging Constraint Score (BCS) is proposed. Instead of seeking one appropriate constraint set for single Constraint Score, in BCS we perform multiple Constraint Score, each of which uses a bootstrapped subset of original given constraint set. Diversity analysis on individuals of ensemble shows that resampling pairwise constraints is helpful for simultaneously improving accuracy and diversity of individuals. We conduct extensive experiments on a series of high-dimensional datasets from UCI repository and gene databases, and the experimental results validate the effectiveness of the proposed method.     

An effective heuristic for multistage linear programming with a stochastic right-hand side

The multistage Stochastic Linear Programming (SLP) problem may become numerically intractable for huge instances, in which case one can solve an approximation for example the well known multistage Expected Value (EV) problem. We introduce a new approximation to the SLP problem that we call the multistage Event Linear Programming (ELP) problem. To obtain this approximation the SLP constraints are aggregated by means of the conditional expectation operator. Based on this new problem we derive the ELP heuristic that produces a lower and an upper bound for the SLP problem. We have assessed the validity of the ELP heuristic by solving large scale instances of the network revenue management problem, where the new approach has clearly outperformed the EV approach. One limitation of this paper is that it only considers randomness on the right-hand side, which is assumed to be discrete and stagewise independent.     

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.     

Newton-conjugate gradient （CG） augmented Lagrangian method for path constrained dynamic process optimization

In this paper, a Newton-conjugate gradient (CG) augmented Lagrangian method is proposed for solving the path constrained dynamic process optimization problems. The path constraints are simplified as a single final time constraint by using a novel constraint aggregation function. Then, a control vector parameterization (CVP) approach is applied to convert the constraints simplified dynamic optimization problem into a nonlinear programming (NLP) problem with inequality constraints. By constructing an augmented Lagrangian function, the inequality constraints are introduced into the augmented objective function, and a box constrained NLP problem is generated. Then, a linear search Newton-CG approach, also known as truncated Newton (TN) approach, is applied to solve the problem. By constructing the Hamiltonian functions of objective and constraint functions, two adjoint systems are generated to calculate the gradients which are needed in the process of NLP solution. Simulation examples demonstrate the effectiveness of the algorithm.     

Structural decompositions for problems with global constraints

A wide range of problems can be modelled as constraint satisfaction problems (CSPs), that is, a set of constraints that must be satisfied simultaneously. Constraints can either be represented extensionally, by explicitly listing allowed combinations of values, or implicitly, by special-purpose algorithms provided by a solver. Such implicitly represented constraints, known as global constraints, are widely used; indeed, they are one of the key reasons for the success of constraint programming in solving real-world problems. In recent years, a variety of restrictions on the structure of CSP instances have been shown to yield tractable classes of CSPs. However, most such restrictions fail to guarantee tractability for CSPs with global constraints. We therefore study the applicability of structural restrictions to instances with such constraints. We show that when the number of solutions to a CSP instance is bounded in key parts of the problem, structural restrictions can be used to derive new tractable classes. Furthermore, we show that this result extends to combinations of instances drawn from known tractable classes, as well as to CSP instances where constraints assign costs to satisfying assignments.     

几何约束有向图的规划分解研究

在基于有向图表达的几何约束系统中,几何约束的匹配方向、分布状态以及有向图中强连通分量的规模直接影响到整个约束系统的求解;如何对几何约束系统进行合理规划,得到正确有效的求解序列,是目前约束分解研究的重要内容。该文提出了一个规划分解算法,它针对欠约束几何系统的特点,能够优化约束的初始匹配方向,对于约束匹配过程中生成的强连通子图,通过调整约束匹配方向,自适应地改善约束分布,从而减小强连通子图的规模,以求得到几何约束系统正确而高效的求解序列。同时,基于规划分解算法,完成了约束的奇异性分析,提供了面向分解的奇异性分析算法。     

负表约束的简单表缩减广泛弧相容算法

广泛弧相容算法（generalized arc consistency,简称GAC）,是求解约束满足问题的核心方法.表约束理论上可以表示所有约束关系,在过去10年中,有很多应用于表约束的广泛弧相容算法被提出来.在这些算法中,表缩减算法的效率非常高.但是目前的表缩减算法只能应用于正表约束,无法直接应用于负表约束.首先,提出一种表缩减算法STR-N,可以直接应用于负表约束;然后,给出了STR-N的两个改进版本STR-N2和STR-NIC.实验结果显示,STR-N算法在负表约束上的求解效率具有明显的优势.     

Interactive scheduling as a constraint satisfiability problem

A constraint satisfiability problem consists of a set of variables, their associated domains (i.e., the set of values the variable can take) and a set of constraints on these variables. A solution to the CSP is an instantiation (or labeling) of all the variables which does not violate any of the constraints. Since constraint satisfiability problems are, in general, NP-complete, it is of interest to compare the effectiveness and efficiency of heuristic algorithms as applied, in particular, to our application. Our research effort attempts to determine which algorithms perform best in solving the student scheduling problem (SSP) and under what conditions. We also investigate the probabilistic techniques of Nudel for finding a near-optimal instantiation order for search algorithms, and develop our own modifications which can yield a significant improvement in efficiency for the SSP. Experimental results have been collected and are reported here. Our system was developed for and used at Bar-Ilan University during the registration period, being available for students to construct their timetables.     

Modelling and Solving Employee Timetabling Problems

Employee timetabling is the operation of assigning employees to tasks in a set of shifts during a fixed period of time, typically a week. We present a general definition of employee timetabling problems (ETPs) that captures many real-world problem formulations and includes complex constraints. The proposed model of ETPs can be represented in a tabular form that is both intuitive and efficient for constraint representation and processing. The constraint networks of ETPs include non-binary constraints and are difficult to formulate in terms of simple constraint solvers. We investigate the use of local search techniques for solving ETPs. In particular, we propose several versions of hill-climbing that make use of a novel search space that includes also partial assignments. We show that, on large and difficult instances of real world ETPs, where systematic search fails, local search methods perform well and solve the hardest instances. According to our experimental results on various techniques, a simple version of hill climbing based on random moves is the best method for solving large ETP instances.     

Complexity of Clausal Constraints Over Chains

We investigate the complexity of the satisfiability problem of constraints over finite totally ordered domains. In our context, a clausal constraint is a disjunction of inequalities of the form x≥d and x≤d. We classify the complexity of constraints based on clausal patterns. A pattern abstracts away from variables and contains only information about the domain elements and the type of inequalities occurring in a constraint. Every finite set of patterns gives rise to a (clausal) constraint satisfaction problem in which all constraints in instances must have an allowed pattern. We prove that every such problem is either polynomially decidable or NP-complete, and give a polynomial-time algorithm for recognizing the tractable cases. Some of these tractable cases are new and have not been previously identified in the literature.     

Cardinal: A Finite Sets Constraint Solver

In this paper we present Cardinal, a general finite sets constraint solver just made publicly available in ECLiPSe Constraint System, suitable for combinatorial problem solving by exploiting inferences over sets cardinality. In fact, to deal with set variables and set constraints, existing set constraint solvers are not adequate to handle a number of problems, as they do not actively use important information about the cardinality of the sets, a key feature in such problems. Cardinal is formally presented as a set of rewriting rules on a constraint store and we illustrate its efficiency with experimental results. We show the importance of propagating constraints on sets cardinality, by comparing Cardinal with other solvers. Another contribution of this paper is on modelling: we focus essentially on digital circuits problems, for which we present new modelling approaches and prove that sets alone can be used to model these problems in a clean manner and solve them efficiently using Cardinal. Results on a set of diagnostic problems show that Cardinal obtains a speed up of about two orders of magnitude over Conjunto, a previous available set constraint solver, which uses a more limited amount of constraint propagation on cardinalities. Additionally, to further extend modelling capabilities and efficiency, we generalized Cardinal to actively consider constraints over set functions other than cardinality. The Cardinal version just released allows declaring union, minimum and maximum functions on set variables, and easily constraining those functions, letting Cardinal especial inferences efficiently take care of different problems. We describe such extensions and discuss its potentialities, which promise interesting research directions.     

E-CARGO模型在CSP问题中的描述

基于角色的协同RBC(Role-Based Collaboration)是一套研究角色及它们之间复杂关系的方法、理论和技术。在RBC中,群组角色分配GRA(Group Role Assignment)既是一个关键问题,也是一个难题。已有许多研究探讨了基于Q(Qualification)矩阵来处理GRA问题,但仅利用Q矩阵难以描述问题中的复杂约束关系。因此,将约束集(Constraint)引进E-CARGO模型,提出了带约束的EC-CARGO模型,研究了RBC、GRA、SAT(SATisfaction)和CSP(Constraint Satisfaction Problem)之间的联系,建立了RBC-GRA-SAT-CSP问题求解转换关系;提出应用EC-CARGO模型求解经典CSP约束满足问题的方法,进而描述了应用GRA求解CSP约束满足问题的通用框架。最后以N皇后问题为例,验证了通过GRA的约束指派求解CSP问题的有效性。     

Symmetry Definitions for Constraint Satisfaction Problems

We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, and show that a symmetry can be defined in two fundamentally different ways: as an operation preserving the solutions of a CSP instance, or else as an operation preserving the constraints. We refer to these as solution symmetries and constraint symmetries. We define a constraint symmetry more precisely as an automorphism of a hypergraph associated with a CSP instance, the microstructure complement. We show that the solution symmetries of a CSP instance can also be obtained as the automorphisms of a related hypergraph, the k-ary nogood hypergraph and give examples to show that some instances have many more solution symmetries than constraint symmetries. Finally, we discuss the practical implications of these different notions of symmetry.