# Questions tagged [constraint-satisfaction]

The tag has no usage guidance.

91 questions
Filter by
Sorted by
Tagged with
33 views

### Why N-Queens Problem is not used as experiment in CSP thesis?

I am studying CSP for my master thesis. I found that many thesis based on CSP described N-Queens as an introductory and they actually do experiment on random CSP problems. If so,when I do master ...
19 views

### Find an algorithm to fully consume items with criteria and produce minimal result

So here are the prerequisites: There are items to be consumed. Consider an item is just an object with a bunch of properties (e.g. size, weight), and there are tens or hundreds of properties. Items ...
71 views
+50

### Selection over combinatorics that satisfies a distribution

I'm having an exciting problem that I could not manage to find an optimized solution. I actually have no idea if the problem is already known or not. Here is the problem : Consider a list of M ...
20 views

### Bin Packing variant

I am currently struggling with a bin packing variant, where we have fuel and compartments of a tank truck. Some industry constraints apply, but the whole picture is that you must fit the total volume ...
56 views

61 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 ...
31 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 ...
72 views

### Big M method for continuous variables

Is there any way to model the big M method for continuous variables? Something similar to this but $B, C \in \mathbb{R}_{\geq 0}$ and $A\in\{0,1\}$. Due to the precision problem, when the $B$ and $C$ ...
21 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 ...
22 views

### what does it mean to extend an assignment?

For a constraint satisfaction problem, what does it mean for an assignment x to extend an assignment a? Sorry if this is super trivial, I did not find an answer e.g here: No Small Linear ...
314 views

### A simple way to find the feasible region of a system with simple constraints

I'm coding something... weird, and I'm running into some constraint satisfaction and graph theory problems, which are fields I'm not too experienced in. Here's the problem: I start out with this ...
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.
344 views

### understanding constraint satisfaction problem: map coloring algorithm

I am trying to implement this recursive-backtracking function for a constraint satisfaction problem from the given algorithm: ...
1k 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 ...
43 views

### Algorithm to solve constraint satisfaction problems

I have group of people. Each person can be described by few characteristics: age, occupation, city, favorite_color I would like to generate 60 random people and ...
71 views

### Algorithm to Assign Values Based on Constraints

I have variables x y and z, and I have the values that they can be assigned to, I.E. x can be assigned 1,2, or 3, y can be 1, and z can be 2. The problem is a constraint that says once a value has ...
13 views

### Generating graph with complex structure

I want to generate a bunch of graphs of about 100 nodes, where each node is a categorial variable. I want the graphs to satisfy complex properties, like, "if a node of type A is connected to a node ...
97 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,...
42 views

### Does this constraint satisfaction problem have a name

I've been struggling with a particular constraint satisfaction problem, that appears like it should have an easy solution. In fact, I need a very fast solution. The problem is: I am making a card-...
157 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 ...