Questions tagged [constraint-satisfaction]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
11
votes
2answers
17k views

What is Least-Constraining-Value?

In constraint satisfaction problems, heuristics can be used to improve the performance of a bactracking solver. Three commonly given heuristics for simple backtracking solvers are: Minimum-remaining-...
8
votes
2answers
300 views

Algorithm for solving planar constraint problem (“Pokemon Go monster finding”)

[Note: This problem was inspired by Pokemon Go. I will first explain the problem in mathematical terms, then explain the connection to Pokemon Go. My goal is not to cheat in the game. If I wanted to ...
7
votes
0answers
215 views

complexity of a Constraint Satisfaction Promise Problem

Due to curiosity regarding possible extensions of Schaefer's dichotomy theorem, I wound up considering the "promise constraint" with 3 boolean inputs that's given by $C(x,y,z) ​ ​ = \hspace{.1 in}\...
6
votes
2answers
2k views

Why don't modern SAT solvers use the notion of a “watched clause”, in the same way they use the notion of a “watched literal”?

Modern SAT solvers use the notion of "watched literals": when a value is chosen for a literal $l$, the solver only checks whether that falsifies clauses with $l$ in them if $l$ is one of the watched ...
6
votes
1answer
508 views

SAT algorithm for determining if a graph is disjoint

What are some good algorithms to have a SAT (CNF) solver determine if a given graph is fully-connected or disjoint? The best one I can think of is this: Number the nodes 1..N, where N is the number ...
6
votes
1answer
1k views

Algorithm to create dense style crossword puzzles

I am working on creating a program to generate dense American style crossword puzzles of grid sizes between 15x15 - 30x30. The database of words I'm using ranges between 20,000 and 100,000 words of ...
6
votes
1answer
58 views

Small world theorem for set constraints

Let $S_1,\dots,S_n$ be variables representing unknown sets. A set expression has the form $S_i$, $\overline{E}$ (the complement of $E$), or $E \cap E'$, where $E,E'$ are set expressions. A ...
5
votes
3answers
552 views

How do we place $8n$ objects in a grid of size $n \times n$?

How do we place $8n$ objects on a square of size $n\times n$ in a form of grid such that no 4 of them form a rectangle with sides parallel to those of square? Each object occupies exactly one cell in ...
5
votes
1answer
118 views

Subgraph isomorphism on star multi-graphs with labelled edges

My approach to the problem has been to reformulate it into something more recognizable, but I don't know the best way to solve the reformulated problems either. I list the original problem, an example,...
5
votes
0answers
480 views

Heuristic Repair and N-Queens Problem

Problem: I am trying to solve the $N$-Queens problem using Constraint Satisfaction and Heuristic Repair (also known as Min-Conflicts). I wrote a program to do this for any given $N$ queens and $N * N$...
4
votes
2answers
820 views

How could an SMT solver be implemented as simple as possible?

I'm trying to figure out how an SMT solver works as simple as possible. Let's assume we have a simple input program with symbolic values x and ...
4
votes
1answer
207 views

Efficient algorithm for simple constraint satisfaction problem

There are $k$ Boolean variables $x_1, x_2, \dots, x_k$. $m$ arbitrary subsets of these variables such that sum of each set equals to $1$ (i.e., only one variable is $1$, the others are $0$). E.g., ...
4
votes
1answer
3k views

Aren’t most constraining variable and least constraining value the exact opposite?

So aren’t MCV and LCV the exact opposite?MCV tries to choose the variable with the most constraints on remaining variables but LCV is opposite: it tries to rule out as least values for other variables ...
4
votes
1answer
121 views

Is this problem that's similar to integer linear programming also an NP-complete problem?

I've come across this problem while trying to work out a table-formatting algorithm. It's very similar to standard linear programming (though it uses $>$ instead of $<$; I'm not extremely ...
4
votes
1answer
65 views

Sorting strings with “before” and “after” constraints

I'm trying to solve a constraint-satisfaction problem for a project of mine that seems like it should have a well-known solution, but I can't for the life of me seem to find it described anywhere. I'...
4
votes
3answers
7k views

“Greater than” condition in integer linear program with a binary variable

How can one model the following condition in an integer linear program? $$A = \begin{cases} 1 & \text{if } B > C\\ 0 & \text{otherwise}\end{cases}$$ where $A \in \{0,1\}$ and $B, C \in \...
4
votes
2answers
1k views

Contraint with three variables into three binary constraints

I'm having a hard time tackling the following problem (perhaps some key data is missing). We have a constraint: $A+B= C$ One is supposed to represent this one constraint using three binary ...
4
votes
0answers
98 views

Answer Set Program to SAT translation

During the presentation (a talk) Answer Set Programming: Boolean Constraint Solving for Knowledge Representation and Reasoning Torsten Schaub (University of Postdam) stated around twenty-one minutes ...
4
votes
0answers
99 views

What is the generating algorithm for the “komb” instances found on satcompetition.org?

For the 2017 and 2018 Random SAT Tracks of the SAT Competition ran by the International Conference on Theory and Applications of Satisfiability Testing there are small, yet difficult, random 3-SAT ...
4
votes
0answers
72 views

(Historical perspective) CSP and SAT inter-fertilization

[Disclaimer: this is a rather specialized question] It is known that techniques like Conflict-Driven Clause Learning (CDCL) and back-jumping -- which improved the Satisfiability (SAT) strategies ...
3
votes
2answers
179 views

Is every X3SAT instance with no cycles satisfiable?

Exactly 1 in 3 SAT (X3SAT) is a variation of the Boolean Satisfiability problem. Given a set of clauses, where each clause has three literals, is there an assignment such that in each clause exactly ...
3
votes
1answer
78 views

existence of a permutation that satisfies order-constraints

I would like to know if there is a simple algorithm for checking the existence of a permutation that satisfies a number of order-constraints. For example, suppose we have a set (1, 2, 3, 4, 5) and a ...
3
votes
1answer
117 views

Sum of unique integers to cnf constraint

As a study project I try to solve the kakuro puzzle problem using SAT SOLVER. I can't really find an efficient way to convert the sum of k unique integers (1...9) to a CNF constraint. What I had in ...
3
votes
1answer
26 views

General structure of solutions to 3-SAT circuits

Certain special forms of the SAT problem have solution sets of a special form. For example, given any three solutions to a 2-SAT circuit, their bitwise median is also a solution. Likewise, given any ...
3
votes
1answer
83 views

Theoretical CSPs where (in)equality constraints can be expressed as a single constraint?

I'm designing puzzles by running a MAX-CSP solver, and it works nicely in practice. For concreteness, my problems have the following form (in a pseudo-modeling language): ...
3
votes
3answers
155 views

Isn't Domain of a variable nothing but a constraint?

In Constraint programming we have Variables and their Domains and then all the constraints, but if you at the concept of a domain of a variable it is nothing but another type of constraint, you are ...
3
votes
2answers
2k views

CSP Forward checking with n-ary (and binary) constraints

I have implemented my own CSP solver using a Backtracking algorithm. Within the Backtracking algorithm I apply a Forward Checking algorithm (reducing domains of connected, unnasigned variables) that ...
3
votes
1answer
422 views

Linear optimization or Constraint Satisfaction Problem with food

I was hoping someone could point me in the right direction in terms of what type of problem I am describing here so I can research it. My initial thought is that it is some form of Constraint ...
3
votes
1answer
69 views

Proving NP hardness about graph creation problem with triangle number

I have graph creation problem. Given a set of nodes of graph, and node constraints such as given every node's number of neighbors (degree). I am also provided with the total number of triangles in ...
3
votes
0answers
86 views

Given two arrays of length n and n - 1, order the first array such that no partial sum is in the second array

Two arrays of natural numbers are given of length $n$ and $n - 1$: e.g. $A: [a_0, a_1,..., a_{n-1}, a_n]$ $B: [b_0, b_1, ..., b_{n-2}, b_{n-1}]$ All elements of $A$ are unique (can be in $B$), all ...
3
votes
0answers
49 views

Knowing if I have an optimal ordering for a OBDD

I'm learning about OBDD and I have learned that the size of a reduced OBDD (ROBDD) is dependent on the ordering of the variables, and that finding an optimal ordering is an NP hard problem. Say I ...
2
votes
1answer
166 views

Constraint Satisfaction: maximizing total value with no overlaps

Suppose we have a bunch of bars, which can represent anything (time slots, paths, physical items...) and each of them has a start point, an end point, and an associated value. Out of all the bars ...
2
votes
1answer
90 views

Linear programming over a finite field

I have a system of equations $Ax = b$ over some finite field $\mathbb{Z}_p$ and want to find a feasible solution. I'm sure this problem is NP-hard, but I'm struggling to find any literature on the ...
2
votes
1answer
467 views

Binarization of Constraints

I am trying to solve a Constraint Satisfaction Problem that involves lots of n-ary constraints. But the solver I have implemented only works with algorithms for binary constraints. I've been reading ...
2
votes
1answer
188 views

Are finite-domain binary constraint satisfaction problems solvable in polynomial time?

Suppose a CSP has $n$ variables with finite domains of maximal size $d$. Furthermore, all constraints on the variables are binary. Can such a CSP be solved in polynomial time in $n$ and $d$? This was ...
2
votes
2answers
107 views

Need recursive version of Conflict based backjumping

I am implementing conflict directed Backjumping algorithm of prosser in java. But, the algorithm is iterative approach. How can it be built with recursive approach? In AIMA they give the recursive ...
2
votes
1answer
40 views

IA network that is path-consistent, but not consistent

I'm studying continuous CSP from the slides of my professor and i got that with the PATH-CONSISTENCY algorithm you can check consistency for PA (Point Algebra), SIA and ORD-Horn; however it cannot be ...
2
votes
1answer
29 views

Is there a “well known” example of a constraint satisfaction problem on a 3-element set which is polynomial-time solvable?

I'm basically looking for an example (in maybe graph theory) of a constraint satisfaction problem which has a 3-element set as a domain and the problem is known to be polynomial-time solvable.
2
votes
1answer
226 views

Mimimum spanning tree with a constraint on number of certain types of edges

I have the the following problem. Say we have a graph $G = (V,E)$ where all $e \in E$ have positive weight, and $E$ can be separated in to two disjoint sets $E = A \cup B$. We have to find a spanning ...
2
votes
1answer
530 views

Parameter sharing / weight constraints in Neural Networks

I would like to train a neural network whose parameters (alternatively, weights) are subject to linear constraints such as $w_{i,j} = w_{i',j'}$, where $w_{i,j}$ denotes the weight from input node $...
2
votes
1answer
23 views

Is there an optimization algorithm that could help match the maximum number clients to servers with constraints?

How do you go about solving the following problem that tries to match the greatest number of clients with servers with constraints? I'm trying to identify an algorithm or simulation that could help me ...
2
votes
2answers
69 views

Constraint satisfaction problem: solve system, then evaluate whether many additional constraints are satisfied one at a time

I have a system that consists of binary inequality constraints between variables, plus some indicator variables that can assume only two values: ...
2
votes
1answer
38 views

CSP heuristics to help avoid redundancy while checking values for constraint inconsistency?

I'm a complete beginner. Please forgive my ignorance.Trying to learn about CSP online, I noticed a lot of the focus on search methods and heuristics which tell you which variable to expand next (e.g. ...
2
votes
1answer
59 views

How to represent sums of piecewise quadratic functions for efficient optimisation?

I'm trying to implement a decision procedure for finding solutions to a scheduling problem; this involves computing the point in time which is under the most contention. Each task to be scheduled has ...
2
votes
1answer
49 views

Non-Boolean SAT

I was wondering about the complexity of SAT tests with variables $x_i = 0 \lor 1 \lor 2 \dots \lor n$, with clauses being of the form $x_i = a \implies x_j \neq b$. When $n=2$, we have 2SAT, which has ...
2
votes
1answer
94 views

Mutli-Path Collision Avoidance

I need an algorithm which can do the following: Given some finite number of particles (circles) each with the same radius, and a list of prescribed points for each particle, find paths in $\mathbb{...
2
votes
0answers
178 views

Least constraining value heuristic in Sudoku [closed]

I was trying to implement Least Constraining Value Heuristic in Sudoku but wasn't getting the idea on how to do it. Can someone share their idea for the same ?
2
votes
0answers
785 views

“Greater than 0” condition in integer linear program with a binary variable [duplicate]

How can one model the following condition in an integer linear program? $$ y = \begin{cases} 1 & \text{if } x > 0\\ 0 & \text{otherwise}\end{cases} $$ Where $y \in \{0,1\}$ and $x \in \...
2
votes
1answer
21 views

Is $\Gamma = Inv(Pol(\Gamma))$?

I'm reading A Rendezvous of Logic, Complexity and Algebra, my first introduction to the world of CSP. Let $\Gamma$ be a finite constraint language. It says in Pg. 9 that $Pol(\Gamma)$ is used to ...
2
votes
0answers
33 views

State-of-the-art for Set Constraints?

I've recently stumbled across the field of Set constraints for program analysis, that is, solving equations of the form $exp_1 \subseteq exp_2$, where (depending on the particular variant of the ...