CSPs as learning problems:

1.
Multiple constriant acquisition
(2017)
Constraint programming is a powerful paradigm for modeling and solving combinatorial problems.
However it has long been recognized that expressing a combinatorial problem as a constraint network requires expertise in CP.
The system asks the user to provide one of the constraints of the target problem each time the system proposes an incorrect solution.
Based on examples of solutions and non-solutions provided by the user, the system learns a set of constraints that correctly classifies all the examples given so far.
The system always converge on the target set of constraints in a polynomial nmumber of queries.
However even that good theoretical bound can be hard to put in practice.
A constraint network agrees with given set of examples if the network accepts all the examples labelled as positive in the example set and does not accept those labelled as negative.

2.
Explaining Ourselves: Human Aware Constraint Reasoning
(2017)
Constraint reasoning or Constraint programming involves finding values for problem varibles that satisfy constriants on which combinations of values are allowed.
Constraints may be soft, representing preferences or probabilities or costs, introducing the element of optimization.
ML may reduce the burden on the user- by appyling Bolztmann Machines and Constraint acquisition.
Articulating one's constraints becomes challenging issue when soft constraints are involved.
There exists systems that learns preferences over constraints from preferences over solutions.
Various challenges and Issues are raised: 
Multiple interaction modalities: Natural language, examples, analogies, stories, histories
Efficient Intereaction: reducing user effort, multiple users: cooperative and adversarial, Maintainability: as needs and context change, 
Extracting constraints and CSP models from Big Data and the web and Using Deep learning, Learning and improving models by observing or interacting with human domain experts,
Leraning from the experience with users, User interfaces for interactive problem solving, for real-time, dynamic problems,
Explaining implications of choices or changes in problem specification, Providing appropriate insight and guidance for human-machine collboration,
Acquiring, improving and utilizing background knowledge of user and problem domain constraints to facilitate future problem solving,
Specialized methods for different classes of constraints, Specialized tools for specific application domains,
Specialized tools for specific application domains, Measuring and improving explanation quality.

3.
Learning based abstractions for Non-linear Constraint solving
Constraints that arise for real-world systems are often nonconvex, nonlinear and lack structure that can be exploited, making these problems computationally expensive.
If the constraints contain only polynomial arithmetic, then the constraint-solving problem is decidable, while the algortihms ar doubly exponential.
If the constraints contain functions like exponentials or trigonometics, then the constraint solving problem is undecidable.
Several approaches have been proposed to improve performance for discrete constraint Satisfiability problems using decompositions.
One problem decomposition approach where the original non-convex optimization problem is decomposed into subproblems that are approx independent.
In the approach from the paper the problem is decomposed and then uses a learning procedure to find simpler abstractions of the problem that are more tractable to solve.
The main problem with finding these interpolants-which serve as simplifications through syntactic manipulations is that they are slower and difficult to scale.
A concern with using learning based approaches for constraint solving problems is finding provable relaxations or restirctions of the original problem.
The approach in paper decomposes a set of non-linear arithmetic constraints into subsets and learns simpler relaxations and restrictions for them.
To learn these simplifications, we begin by computing a large number of satisfying and falsifying instances for each subset of constraints using sampling procedure.
Semi soft Support vector machine(SVM) can be used for a given set of samples to learn asymmetric classfiers as candidate antecedants and consequents.
The simpler learned antecedents can be used to find a satisfying instance and the learned consequents can be used to demonstrate that no satisfying instance exists.
 

Not so useful:
1.
Satisfiablity as Classification Problem:
(2008)
SAT was the first problem proved to be NP-Complete, a breakthrough in Computational Complexity. 
SAT problems occur in a variety of domains such as Hardware verification, security protocol analysis, theorem proving, scheduling problems, routing, planning, digital circuit design and AI.
All systematic search algortihms have exponential worst-case running times, which has the scalability of systematic search methods based on backtracking, local search or even resolution.
If a SAT problem is unsatisfiable, local search algorithms, while scalable, cannot prove that to be the case.
A k-SAT is polynomial for k < 3 while k-SAT is NP-Complete for k = 3 and higher. All k-SAT instances with k > 3 can be transformed into k = 3 in time polynomial in the size of k-SAT instance.

SAT is defined as: Given a propositional formula, over a set of variables decide whether or not there exists a truth assignment to the varibles such that the propositional formula evaluates to true.
SAT problems are usually expressed in a standard form, called Conjunctive Normal Form(CNF). A SAT problem is expressed as a conjunction of clauses, where each clause is a disjunction of literals; a literal being either a variable or its negation, 

The paper discusses following classifiers: Random forest of decision trees, Decision trees, Mulilayer perceptrons, Nearest neighbour and Naive Bayes.
The SAT instances were pre-classified as satisfiable or unsatisfiable with 48 features about the instance. The training set having an equal distribution of Satisfiable and unsatisfiable instances.
The results of their experiment was to evaluate the accuracy with which standard classification algorithms could determine whether a SAT instance was satisfiable or not.
The classification accuracies are high as in excess of 90%.

2.
Constraint satisfaction problems: Convexity makes AllDifferent constraints tractable
CSPs with All different constraints naturally model a wide-range of real-world and combinatorial problems like scheduling, frequency allocations and graph coloring problems.
The crucial property that makes the problem achieve fixed parameter tractability is convexity of the variable constraints. The convexity of the domain does not make the problem easier.
Much research has been devoted to finding restricted classes of CSPs that admit polynomial time algortihms.
First direction is investigating structural properties of relations between variables and constraints of a CSP instance. 
The second direction investigates limitations on the types of constraints in CSP constraint language, so-called tractable constraint languages.