Questions tagged [constraint-satisfaction-problems]

For questions about constraint satisfaction problems (CSPs), which are usually described by a set of variables, a set of domains, and a set of constraints. For more details, see, for example, chapter 6 of the book "Artificial Intelligence: A Modern Approach" (3rd Edition) by Stuart Russell and Peter Norvig.

Filter by
Sorted by
Tagged with
0 votes
0 answers
31 views

Inquiry about utilising AI in CNC machining path generation

I will begin by describing a situation. I work in laser machining control company. The essence of the problem, to which I would like to try to apply AI based tool is this: Say I have a analytically ...
Donatas Šimeliūnas's user avatar
0 votes
0 answers
24 views

Is there a chess engine whose architecture is composed purely of ranked/weighted constraints that then generate candidate moves for search?

Chess can be seen as a search for a move with many constraints on it. In the human way of searching for a move, we think to ourselves something like "I need to find a move that both moves the ...
smnc's user avatar
  • 1
0 votes
0 answers
9 views

Constraints Satisfaction for Perfect Matchings

Consider the problem of finding a perfect matching for a graph $G$ as a constraint satisfaction problem where the variables are the vertices and there is just one global constraint (which does not ...
SVMteamsTool's user avatar
0 votes
0 answers
25 views

How to prove that, for any graph $G$, the tree width of $G$ is $1$, if and only if $G$ is acyclic?

I am studying about CSPs, tree decomposition of a graph and tree width ($\text{TW}(G)$) of a graph - the smallest tree width of a tree decomposition. I encountered the following problem: Prove that ...
Daniel's user avatar
  • 131
0 votes
0 answers
133 views

Constraint Satisfaction Problem for 8-puzzle

My question is more related to the fundamentals of the constraint satisfaction problem. In 8-puzzle, we have a 3X3 board with 8 numbers on it and a blank space. The initial state of the puzzle might ...
0jas's user avatar
  • 83
2 votes
0 answers
28 views

How to create a loss function that penalizes duplicate indices in the output tensor?

We're working on a sequence-to-sequence problem using pytorch, and are using cross-entropy to calculate the loss when comparing the output sequence to the target sequence. This works fine and ...
vgoklani's user avatar
  • 121
1 vote
0 answers
145 views

What is my mistake in applying the AC-3 algorithm on this problem?

I want to apply AC-3 algorithm to the following CSP: There are two variables $A$ and $B$. Domain of $A: \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\} $ Domain of $B: \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\} $ The ...
user153245's user avatar
2 votes
0 answers
206 views

Understanding conflict set generation for conflict directed backjumping

I was reading Constraint Satisfaction Problem chapter from Artificial Intelligence 3rd ed book by Peter Norvig et al. On page 219, section 6.3 it explains computation of conflict set for conflict ...
Rnj's user avatar
  • 221
1 vote
1 answer
44 views

How to handle equality constraints in the mutation operation of evolutionary algorithms?

I am new in evolutionary algorithms field. I have a chromosome of 6 variables (real variable), where the sum of these variables is equal to 1. I am looking for mutation formulas that can generate a ...
Rahim Brahimi's user avatar
1 vote
0 answers
29 views

CSP heuristic to simultaneously reduce conflicts and find near optimal assignment

I am trying to design a good heuristic to solve a constraint satisfaction problem (CSP). I think that a possible heuristic to use is $$h_1(\text{state}) = \text{number of conflicts in state}$$ However,...
bobby brown's user avatar
1 vote
1 answer
154 views

What's wrong with my answer to this constraint satisfaction problem, which needs to be solved the AC-3 algorithm?

I was watching the video Constraint Satisfaction: the AC-3 algorithm, and I tried to solve this question: Given the variables A, B, C and D, with domain {1, 2, 3, 4} in each of them and restrictions ...
Rodrigo Franco's user avatar
5 votes
1 answer
877 views

What are the differences between constraint satisfaction problems and linear programming?

I have taken an algorithms course where we talked about LP significantly, and also many reductions to LPs. As I recall, normal LP is not NP-Hard. Integer LP is NP-Hard. I am currently taking an ...
Prabh Dhali's user avatar
1 vote
0 answers
22 views

How can I design a system that suggests physical exercises to a person while keeping into account the fatigue?

I want to create an exercise suggester. Each day either has a routine or is a rest day. A routine has 4 slots. For each slot we select an exercise. We constrain the legal exercises, only do upper-body ...
Just_Alex's user avatar
  • 151
1 vote
0 answers
34 views

How do I decide which norm to use for placing a constraint on my adversarial perturbation?

I am performing an adversarial machine learning attack on a neural network for network traffic classification. For adding adversarial perturbations in features such as packet interarrival times and ...
boomselector's user avatar
1 vote
0 answers
42 views

Where can I find example data for Nonogram solver?

I made CSP nonogram solver and I wanna test it on some bigger data. Where can I find such data to test my program? I've been looking on the internet but I couldn't find anything.
Karol's user avatar
  • 161
3 votes
0 answers
295 views

How can I formulate a nonogram problem as a constraint satisfaction problem?

I've just started learning CSP and I find it quite exciting. Now I'm facing a nonogram solving problem and I want to solve it using backtracking with CSP. The first problem that I face is that I ...
Karol's user avatar
  • 161
3 votes
0 answers
1k views

Can the degree and minimum remaining values heuristics be used in conjunction?

I am currently studying constraint satisfaction problems and have come across two heuristics for variable selection. The minimum remaining values(MRV) heuristic and the degree heuristic. The MRV ...
calveeen's user avatar
  • 1,251
2 votes
1 answer
445 views

How can I develop a genetic algorithm with a constraint on the sum of alleles?

I'm working on a genetic algorithm with a constraint on the sum of the alleles, e.g. if we use regular binary coding and a chromosome is 5-bits long I'd like to constrain it so that the sum of the ...
Mark's user avatar
  • 21
1 vote
1 answer
267 views

What is exactly the role of commutative property in a Constraint Satisfaction Problem?

I have been looking into the backtracking search for CSPs, and understand that if we just plainly do a typical depth-limited search we have a vast tree with leaves size $n!d^n$ where $n$ is the number ...
MuneshSingh's user avatar
2 votes
1 answer
3k views

How can I formulate the k-knights problem as a constraint satisfaction problem?

There are three things in every constraint satisfaction problem (CSP): Variables Domain Constraints In the given scenario, I know how to identify the constraints, but I don't know how to identify ...
Sheri's user avatar
  • 123
2 votes
1 answer
106 views

Which algorithm can I use to solve a problem with multiple objectives and constraints?

Consider a problem with many objectives. In my case, these are school grades for different courses (or subjects). To be more concrete, suppose that my current grade for the math course is $12/20$ and ...
YLM's user avatar
  • 121
2 votes
0 answers
119 views

How can I assign agents to tasks based on time and affinity?

I am working on an assignment problem. Consider $K$ agents $A_1, \dots A_K$ and $N$ tasks $T_1, \dots T_N$. Each task has a certain time $t(T_i)$ to be completed and each agent has a matching (or ...
Tariq Kavish Arain's user avatar
1 vote
0 answers
36 views

Write Constraint Satisfaction Formulation for problem

Given $F_1,F_2,..,F_n$ as set of final exams of subjects taken by students $S_1,..,S_k$ in h slots such that no student takes two exams in a single slot.Here the objective is to maximize the number of ...
ten do's user avatar
  • 145
6 votes
1 answer
2k views

What is local consistency in constraint satisfaction problems?

In the Constraint Propagation in CSP, it is often stated that pre-processing can solve the whole problem, so no search is required at all. And the key idea is local consistency. What does this ...
Lexi's user avatar
  • 109
0 votes
1 answer
212 views

What is the goal of a constraint solver?

What is the goal of a constraint solver? How are constraints propagated in a constraint satisfaction search? Any references are also appreciated.
Lexi's user avatar
  • 109
2 votes
1 answer
285 views

What are daily life examples of SAT problems?

What are (good) daily life examples of SAT problems? I've thought about this one. The problem of placing a bunch of different kinds of glasses in a shared cabinet in such a way that some constraints ...
Jay Critch's user avatar
1 vote
0 answers
3k views

How to improve the efficiency of the backtracking search in CSPs?

Backtracking search is the basic uninformed search algorithm for constraint satisfaction problems (CSPs). How could we improve the efficiency of the backtracking search in CSPs?
Abbas Ali's user avatar
  • 566
2 votes
1 answer
7k views

What is a successor function (in CSPs)?

In Constraint Satisfaction Problems (CSPs), a state is any data structure that supports a successor function, a heuristic function, and a goal test. In this context, what is a successor function?
Abbas Ali's user avatar
  • 566
4 votes
1 answer
138 views

What AI technique should I use to assign a person to a task?

I'm trying to learn AI and thinking to apply it to our system. We have an application for the translation industry. What we are doing now is the coordinator $C$ assigns a file to a translator $T$. The ...
Jaime Sangcap's user avatar
6 votes
1 answer
3k views

How to turn a ternary constraint into three binary constraints?

I'm trying to solve problem 6.6 from the book Artificial Intelligence: A Modern Approach, by Peter Norvig and Stuart Russell. This is in the context of Constraint Satisfaction Problem and how you can ...
Cristóbal Alcázar's user avatar
2 votes
1 answer
260 views

Have evolutionary algorithms been used for engineering design?

Recently, I've been looking recently into what uses AI - specifically evolutionary algorithms - may have in automating engineering design. For a long time, there have been algorithms that solve ...
QuadraticOne's user avatar