Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [constraint-satisfaction]

The tag has no usage guidance.

1
vote
0answers
22 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$ ...
0
votes
0answers
22 views

Comparison between SAT, SMT, LP and CSP

How to know which method is better for modelling and solving a problem. I am generally asking about solving a problem as a satisfiability problem (SAT or SMT) vs. Solving as a linear programming ...
0
votes
0answers
15 views

If I have two variables, x and y, which are constrained to only be {0, 1}, is there any way to multiply/AND them using only addition/subtraction

Basically I want to add and subtract x and y using some linear operations to AND/multiply the values. The use case is a linear program, which is why I don't want to introduce new variables/can't ...
2
votes
1answer
12 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
14 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
50 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
21 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
22 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: ...
0
votes
1answer
66 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
35 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
34 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
12 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 ...
4
votes
1answer
47 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
40 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
43 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 ...
1
vote
1answer
31 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
19 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
52 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 ...
-1
votes
1answer
40 views

Possible orderings with constraints

Given variables {A, B, ,,,,,Z} We want to sort these varibles according to given constraints. The constrains are in below format: X Y Z meaning the third variable (Z) is not in the range ...
3
votes
1answer
136 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 ...
1
vote
1answer
85 views

I have n boys and n girls. I need to pair as much of them as possible for a dance in O(nlogn). Reduce this to a standard problem?

There are n girls and n boys. Each girl i has an objective attractiveness constant Pi (a natural number). The bigger the number, the more attractive. Each boy has a range in which he is comfortable ...
3
votes
0answers
72 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
30 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 ...
1
vote
1answer
37 views

Checking large number of configurations with multiple constraints

I have a very large number of constraints such as: $ A1 \land B1 \land C1 \land D1 \land E1 \land F1$ $ A2 \land B2 \land C2 \land D2 \land E2 \land F2$ $ A3 \land B3 \land C3 \land D3 \land E3 \land ...
4
votes
2answers
221 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 ...
1
vote
0answers
32 views

Constraint-based layouts for GUIs

The VPRI institut founded by Alan Kay has some papers on constraint-based layouts for GUIs based on constraint solving. For instance: Wallingford: Toward a Constraint Reactive Programming Language ...
2
votes
1answer
118 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 ...
3
votes
1answer
450 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 ...
2
votes
0answers
377 views

Finding multi word anagrams from a set of words

Finding all anagrams for a word $w$ from a set of words is a problem with many well-known solutions (for example make a hash table mapping from the bag of letters of a word to the word). But what ...
6
votes
1answer
53 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 ...
0
votes
0answers
34 views

Handling eqaulity constraints in genetic algorithms

I am trying to solve an optimization problem with strength pareto algorithm (SPEA2). My decision variable have lower and upper bounds as well as an equality constraint (sum(dp) = 1). I am unable to ...
4
votes
1answer
145 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., ...
0
votes
2answers
130 views

Modeling tiling problems as SAT problems

I read that tiling problems can be modeled as satisfiability problems (2-SAT?), but the author did not explain how. Is this true? What would be an example? By a "tiling problem" I mean you have a ...
1
vote
1answer
49 views

“strongly relational m-consistency when the domains contain at most m elements implies satisfiability” plain wrong?

Wikipedia states A constraint satisfaction problem may be relationally consistent, have no empty domain or unsatisfiable constraint, and yet be unsatisfiable. There are however some cases in ...
5
votes
0answers
367 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
0answers
54 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 ...
1
vote
0answers
80 views

Any reason to use the least-constrained variable heuristic when searching the solution of a CSP?

Is there any (kind of) (well-known) problem which can be expressed as a CSP in which the least constrained variable heuristic seems to give the best results, when employing backtracking with ...
2
votes
3answers
3k 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 \...
3
votes
1answer
140 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 ...
0
votes
2answers
226 views

It's necessary to replace all the population each generation in a genetic algorithm?

I'm creating a timetable generator using GA's, and I'm stuck in the crossover part. Each generation, I just basically copy the best individuals (the 50% fittest individuals inside the population), ...
0
votes
0answers
42 views

Using Genetic Algorithms for volatile problems

Suppose I am looking at an optimization problem with a large number of interconnected constraints, but the solution is - in some regions - extremely volatile (With volatile I mean: small mutations ...
1
vote
1answer
24 views

Do approximation results for CSPs hold even when domains are of finite but different size?

We need to have a precise definition for what a constraint satisfaction problem (CSP) is to study it formally. Looking at a survey by Libor Barto, titled "The Constraint Satisfaction Problem and ...
3
votes
1answer
75 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
1answer
74 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 ...
1
vote
1answer
45 views

Can a $k$-ary relation have polymorphisms of arity greater than $k$?

To quote Hubie Chen's A Rendezvous of Logic, Complexity, and Algebra (2009) on constraint satisfaction and complexity, An operation $f : D^m \to D$ is a polymorphism of a relation $R \subseteq D^k$ ...
8
votes
2answers
246 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 ...
2
votes
1answer
29 views

Similarity between Min-Conflicts and Coordinate Descent in CSPs?

I'm currently writing a library that solves a specific type of problem that involves mainly constraint satisfaction. I have came across the Min-Conflicts Algorithm which proved to be rather ...
0
votes
2answers
1k views

AC-3 Algorithms on CSP problem, What is happened when enocunter to an empty domain variable?

Suppose We Applying Arc-Consistency (AC3) algorithms on one Constraint Satisfaction Problem, if domain of one variable be empty, what is the next step of this algorithm? According to This Link and to ...
3
votes
0answers
33 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 ...
4
votes
1answer
221 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 ...