Questions tagged [constraint-satisfaction]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
56 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
2answers
48 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
0answers
42 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
1answer
30 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 ...
1
vote
1answer
48 views

Can an optimization algorithm be “universal”?

I am wondering if a Bayesian Optimization framework (e.g. Google's Vizier) can be used in lieu of a traditional solver like Gurobi or CPLEX. In trying to answer this question, I realized that I don'...
0
votes
1answer
60 views

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

I found this related question, but that's not quite it Is it possible to model this with integer programming: $$A = \begin{cases} 1 & \text{if } B \geq C \geq D \\ 0 & \text{otherwise}\end{...
3
votes
1answer
37 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 ...
1
vote
1answer
17 views

Constraint propagation using Projection rule

I've found this example of constraint propagation using projection rule We have C = { x1 ≠ x2, x1 ≥ x2 } < C; x1 ∈ {1,2,3}, x2 ∈ {1,2,3} > They say that ...
5
votes
1answer
355 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 ...
0
votes
0answers
52 views

How to apply AC-3(Arc-consistency 3) algorithm in N-Queen problem?

I am building N-Queen Solver with java. I confused with AC-3 algorithm. I heard that AC-3 can be applied with backtracking algorithm before processing and during the search.The latter is called MAC-3 ...
4
votes
0answers
87 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 ...
1
vote
1answer
27 views

How to put elements in allowed bags?

Let's say I have a list of "Items" I also have a list of "Bags". Each bag is a set of "Items" which gives what item can be placed in that bag. But only one item can go in each bag. I want to place ...
0
votes
0answers
38 views

Need some help implementing backjumping algorithm

I am extending aima csp solver in my project.I have read the AIMA book and the book says Backjumping algorithm can be implemented by with a little modification of Backtracking algorithm.But,I don't ...
0
votes
0answers
17 views

How to make schedules so that each team plays every game?

There are g games (checkers, chess, Monopoly, ...) and there are t teams. t is odd. Each ...
2
votes
1answer
37 views

What is the time complexity of FC_MRV algorithm?

I am studying CSP and read the papers on it.I wanted to know the time complexity of Forward checking with Minium Remaining Value algorithm.
0
votes
0answers
32 views

Channeling Constraints in Constraint Handling Rules (CHR)

Suppose we have a constraint satisfaction problem that can be defined as its constraints in two different viewpoints $V_1$ and $V_2$. Moreover, there are two variables $A$ and $B$ from $V_1$ and $V_2$ ...
1
vote
1answer
20 views

How to calculate the number of invalid strings given a constraint system on alphabet, word blacklist, and string length

If I have the following system, I am wondering how to calculate the number of valid strings it contains. The system is something like this, which can have arbitrary variations. Only consists of an ...
5
votes
3answers
453 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 ...
0
votes
0answers
35 views

Projection operator for constraints

I was looking at HM(X) framework, Hindley-Milner parameterized by a constraint system X, and I was struggling to understand what does the projection operator $\exists \alpha$ does for a constraint. ...
4
votes
1answer
73 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 ...
1
vote
0answers
12 views

How to build an execution graph of concurrency accesses

Sorry If I don't use the right vocabulary, maybe part of my question is due to the fact that I don't know the name of what I'm searching. I have a bounded set of operations that need to access a ...
3
votes
2answers
111 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 ...
0
votes
2answers
365 views

Solving a in/equality constraint problem with graph search

You are given a list of m constraints over n distinct variables x1, ..., xn. Each constraint is of one of the following two types. An equality constraint of the form xi = xj for some i!=j. An ...
4
votes
1answer
42 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'...
1
vote
1answer
54 views

Check a variable within a range with a binary variable [closed]

I have a value, a, it can be any value from 0 to 1. In an integer linear program, how can I formulate a constraint that uses a binary variable, y, to determine whether a is within a range of 0 and 1 ...
1
vote
1answer
19 views

Selection of dates respecting delay constraints

I encountered an issue at work that can be derived approximatively to this problem. Let say we have a machine that can be triggered to instantly do an action. There are several (between 10 to 15) ...
0
votes
0answers
140 views

Time complexity of well know constraint satisfaction problem algorithms with heuristics

I have know that complexity of csp algorithms as follow: Backtracking algorithm for constraint processing space:O(n) ,Time :O(expn) Backjumping algorithm for constraint satisfaction problem ...
1
vote
0answers
256 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 \...
3
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
0answers
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$ ...
3
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
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.
1
vote
0answers
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: ...
4
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
5
votes
1answer
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,...
1
vote
2answers
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-...
2
votes
1answer
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 ...
2
votes
1answer
350 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
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 ...
0
votes
1answer
63 views

Objective function and constraint satisfaction over a set of multi-attributes elements

I'm looking for an approach to solve a problem consisting of maximizing an objective function over a set of discrete elements, while respecting a set of constraints. To illustrate my point, I'll try ...