Constraint-Based Reasoning


Extracting Frequent Gradual Patterns Using Constraints Modeling

arXiv.org Artificial Intelligence

In this paper, we propose a constraint-based modeling approach for the problem of discovering frequent gradual patterns in a numerical dataset. This SAT-based declarative approach offers an additional possibility to benefit from the recent progress in satisfiability testing and to exploit the efficiency of modern SAT solvers for enumerating all frequent gradual patterns in a numerical dataset. Our approach can easily be extended with extra constraints, such as temporal constraints in order to extract more specific patterns in a broad range of gradual patterns mining applications. We show the practical feasibility of our SAT model by running experiments on two real world datasets.


Generating Difficult SAT Instances by Preventing Triangles

arXiv.org Artificial Intelligence

When creating benchmarks for SAT solvers, we need SAT instances that are easy to build but hard to solve. A recent development in the search for such methods has led to the Balanced SAT algorithm, which can create k-SAT instances with m clauses of high difficulty, for arbitrary k and m. In this paper we introduce the No-Triangle SAT algorithm, a SAT instance generator based on the cluster coefficient graph statistic. We empirically compare the two algorithms by fixing the arity and the number of variables, but varying the number of clauses. The hardest instances that we find are produced by No-Triangle SAT. Furthermore, difficult instances from No-Triangle SAT have a different number of clauses than difficult instances from Balanced SAT, potentially allowing a combination of the two methods to find hard SAT instances for a larger array of parameters.


Local Distance Restricted Bribery in Voting

arXiv.org Artificial Intelligence

Studying complexity of various bribery problems has been one of the main research focus in computational social choice. In all the models of bribery studied so far, the briber has to pay every voter some amount of money depending on what the briber wants the voter to report and the briber has some budget at her disposal. Although these models successfully capture many real world applications, in many other scenarios, the voters may be unwilling to deviate too much from their true preferences. In this paper, we study the computational complexity of the problem of finding a preference profile which is as close to the true preference profile as possible and still achieves the briber's goal subject to budget constraints. We call this problem Optimal Bribery. We consider three important measures of distances, namely, swap distance, footrule distance, and maximum displacement distance, and resolve the complexity of the optimal bribery problem for many common voting rules. We show that the problem is polynomial time solvable for the plurality and veto voting rules for all the three measures of distance. On the other hand, we prove that the problem is NP-complete for a class of scoring rules which includes the Borda voting rule, maximin, Copeland$^\alpha$ for any $\alpha\in[0,1]$, and Bucklin voting rules for all the three measures of distance even when the distance allowed per voter is $1$ for the swap and maximum displacement distances and $2$ for the footrule distance even without the budget constraints (which corresponds to having an infinite budget). For the $k$-approval voting rule for any constant $k>1$ and the simplified Bucklin voting rule, we show that the problem is NP-complete for the swap distance even when the distance allowed is $2$ and for the footrule distance even when the distance allowed is $4$ even without the budget constraints.


On constraint programming for a new flexible project scheduling problem with resource constraints

arXiv.org Artificial Intelligence

Real-world project scheduling often requires flexibility in terms of the selection and the exact length of alternative production activities. Moreover, the simultaneous scheduling of multiple lots is mandatory in many production planning applications. To meet these requirements, a new flexible resource-constrained multi-project scheduling problem is introduced where both decisions (activity selection flexibility and time flexibility) are integrated. Besides the minimization of makespan, two alternative objectives inspired by a steel industry application case are presented: maximization of balanced length of selected activities (time balance) and maximization of balanced resource utilization (resource balance). New mixed integer and constraint programming (CP) models are proposed for the developed integrated flexible project scheduling problem. The real-world applicability of the suggested CP models is shown by solving large steel industry instances with the CP Optimizer of IBM ILOG CPLEX. Furthermore, benchmark instances on flexible resource-constrained project scheduling problems (RCPSP) are solved to optimality.


Understanding Database Reconstruction Attacks on Public Data

Communications of the ACM

There exists a solution universe of all the possible solutions to this set of constraints. If the solution universe contains a single possible solution, then the published statistics completely reveal the underlying confidential data--provided that noise was not added to either the microdata or the tabulations as a disclosure-avoidance mechanism. If there are multiple satisfying solutions, then any element (person) in common among all of the solutions is revealed. If the equations have no solution, either the set of published statistics is inconsistent with the fictional statistical agency's claim that it is tabulated from a real confidential database or an error was made in that tabulation. This doesn't mean that a high-quality reconstruction is not possible.


Privacy of Existence of Secrets: Introducing Steganographic DCOPs and Revisiting DCOP Frameworks

arXiv.org Artificial Intelligence

Here we identify a type of privacy concern in Distributed Constraint Optimization (DCOPs) not previously addressed in literature, despite its importance and impact on the application field: the privacy of existence of secrets. Science only starts where metrics and assumptions are clearly defined. The area of Distributed Constraint Optimization has emerged at the intersection of the multi-agent system community and constraint programming. For the multi-agent community, the constraint optimization problems are an elegant way to express many of the problems occurring in trading and distributed robotics. For the theoretical constraint programming community the DCOPs are a natural extension of their main object of study, the constraint satisfaction problem. As such, the understanding of the DCOP framework has been refined with the needs of the two communities, but sometimes without spelling the new assumptions formally and therefore making it difficult to compare techniques. Here we give a direction to the efforts for structuring concepts in this area.


Time-aware Test Case Execution Scheduling for Cyber-Physical Systems

arXiv.org Artificial Intelligence

Testing cyber-physical systems involves the execution of test cases on target-machines equipped with the latest release of a software control system. When testing industrial robots, it is common that the target machines need to share some common resources, e.g., costly hardware devices, and so there is a need to schedule test case execution on the target machines, accounting for these shared resources. With a large number of such tests executed on a regular basis, this scheduling becomes difficult to manage manually. In fact, with manual test execution planning and scheduling, some robots may remain unoccupied for long periods of time and some test cases may not be executed. This paper introduces TC-Sched, a time-aware method for automated test case execution scheduling. TC-Sched uses Constraint Programming to schedule tests to run on multiple machines constrained by the tests' access to shared resources, such as measurement or networking devices. The CP model is written in SICStus Prolog and uses the Cumulatives global constraint. Given a set of test cases, a set of machines, and a set of shared resources, TC-Sched produces an execution schedule where each test is executed once with minimal time between when a source code change is committed and the test results are reported to the developer. Experiments reveal that TC-Sched can schedule 500 test cases over 100 machines in less than 4 minutes for 99.5% of the instances. In addition, TC-Sched largely outperforms simpler methods based on a greedy algorithm and is suitable for deployment on industrial robot testing.


Domain Constraint Approximation based Semi Supervision

arXiv.org Machine Learning

Deep learning for supervised learning has achieved astonishing performance in various machine learning applications. However, annotated data is expensive and rare. In practice, only a small portion of data samples are annotated. Pseudo-ensembling-based approaches have achieved state-of-the-art results in computer vision related tasks. However, it still relies on the quality of an initial model built by labeled data. Less labeled data may degrade model performance a lot. Domain constraint is another way regularize the posterior but has some limitation. In this paper, we proposed a fuzzy domain-constraint-based framework which loses the requirement of traditional constraint learning and enhances the model quality for semi supervision. Simulations results show the effectiveness of our design.


Solving Nurse Scheduling Problem Using Constraint Programming Technique

arXiv.org Artificial Intelligence

Staff scheduling is a universal problem that can be encountered in many organizations, such as call centers, educational institution, industry, hospital, and any other public services. It is one of the most important aspects of workforce management strategy and the one that is most prone to errors or issues as there are many entities should be considered, such as the staff turnover, employee availability, time between rotations, unusual periods of activity, and even the last-minute shift changes. The nurse scheduling problem is a variant of staff scheduling problems which appoints nurses to shifts as well as rooms per day taking both hard constraints, i.e., hospital requirements, and soft constraints, i.e., nurse preferences, into account. Most algorithms used for scheduling problems fall short when it comes to the number of inputs they can handle. In this paper, constraint programming was developed to solve the nurse scheduling problem. The developed constraint programming model was then implemented using python programming language.


SafeAI 2019 – AAAI's Workshop on Artificial Intelligence Safety

#artificialintelligence

You are invited to submit short position papers (2-4 pages), full technical papers (6-8 pages) or proposals for technical talks (one-page abstract). The workshop proceedings will be published on CEUR-WS.org. SafeAI will be a memorable event with two top keynote speakers and three great invited talks. The Program is now available! The DARPA Assured Autonomy program aims to advance the ways computing systems can learn and evolve with machine learning to better manage variations in the environment and enhance the predictability of autonomous systems like driverless vehicles.