Questions tagged [constraint-satisfaction]
The constraint-satisfaction tag has no usage guidance.
112
questions
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 ...
1
vote
0answers
39 views
QuickSort when the range of data is known
In QuickSort Algorithm, the pivot is chosen as the first element or a randomised element. However, if the range of data to be sorted is known, For example, from 1 to 100, and they are mostly equally ...
0
votes
1answer
24 views
would complexity of constraint satisfaction problem bound the constrained optimization problem?
If a constraint satisfaction problem $x \in Y$ is NP-Complete.
Can I conclude that the optimization problem $𝑥^* =\text{argmax}_x 𝑓(x)$ s.t. $x \in Y$ is also NP-Complete?
1
vote
0answers
26 views
would complexity of constrained optimization problem bound the constraint satisfaction problem?
For an optimization problem $x^* =\text{argmax}_xf(x)$ s.t. $x \in Y$ satisfy to some constraint $Y$.
Can I argue that if there is a polynomial algorithm for this optimization problem. Then there must ...
1
vote
0answers
105 views
Constraint based analysis: understanding the program $[[ \text{fn} \ x => [x]^1]^2 [ \text{fn} \ y => [y]^3]^4]^5$
I am currently studying the textbook Principles of Program Analysis by Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Chapter 1.4 Constraint Based Analysis says the following:
1.4 Constraint ...
1
vote
0answers
28 views
IP Programming - objective function ist not a function BUT a table
Here is a short description of my problem:
Part of my objective function is not a regular function. Instead it's a table.
You can see a short extract here:
So if the height is smaller or equal to 300 ...
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:
...
0
votes
0answers
61 views
How AC-3 (Arc Consistency) with backtracking works
I'm trying to understand the AC-3 algorithm with backtracking to implement a Rat in Maze algorithm via C++. So far I've base on these links I have a basic idea in terms of AC-3 and how to implement ...
0
votes
1answer
31 views
Generating topological sequence from DAG with additional “not appearing before” constraints
DAG specifies the relationship of one node must appear after another. What if I add an additional constraint where one node cannot appear before another on top of the DAG?
Is there an algorithm for ...
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 ...
0
votes
0answers
12 views
Are arc inconsistencies predictable?
Are arc consistency algorithms such as AC-3 inevitable for CSP to be solved more efficiently through pruning of inconsistent values? Can't we use the constraints that we have and predict arc ...
1
vote
2answers
193 views
Automated reasoning with real numbers
I have a large number of equivalences which look like:
$(a \leq 0.54 \wedge b \geq 0.12) \vee (c \gt 0.98)$ $\Leftrightarrow$ $(x \leq 0.25) \vee (x \gt 0.91 \wedge y \geq 0.01)$
This is just an ...
0
votes
0answers
30 views
Can arc consistency checks be avoided if constraints are formulated properly?
While solving a few CSPs by hand, I noticed that I don't actually need to check for arc consistency after each assignment.
All I needed to do was to formulate the CSP in such a way that I'm adding ...
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. ...
0
votes
0answers
70 views
How can we formulate an anti-knight Sudoku as an exact cover problem?
Formulating standard Sudoku as an exact cover problem is easy and well documented. All of the constrained groups contain every digit which makes it natural to express the problem this way. Wikipedia ...
1
vote
3answers
172 views
Counting the number of satisfied models - given mathematical constraints
Question
There are plenty of algorithms for solving the #SAT problem, with one being the DPLL algorithm and is implemented for all kinds of programming languages. As far as I've seen, they all take a ...
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 ...
1
vote
2answers
56 views
Algorithm for optimal rule-based arrangements?
I am trying to plant a row in a garden. Certain plants are good for some plants and bad for others, and I am trying to find the best order of plants: most adjacent friends and no adjacent foes, as ...
1
vote
2answers
30 views
Algebra for min/max bounds
I am trying to model some set operations which are only well-defined if one is a subset of the other. The way the sets are constructed, I'll have a series of constraints of the form $x \subseteq y$, ...
0
votes
0answers
65 views
Special case of stable marriage
I have an instance of the stable marriage problem in which the first side $S_1$ has $n_1$ agents and the second side $S_2$ has $n_2$ agents with $n_2$ is very big in comparison to $n_1$. In addition, ...
0
votes
0answers
18 views
How to change the constraint's arity from n to 3?
How to change the constraint's arity from n to 3?
I know how to perform binarization of constraints, explained here: https://cw.fel.cvut.cz/b172/_media/courses/b4b36zui/binarization.pdf, but I don't ...
2
votes
1answer
93 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 ...
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 ...
1
vote
1answer
17 views
Equivalence between MIN UNCUT and MIN-CSP_XOR
In this paper
Agarwal, Amit, et al. "O (√ log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems." Proceedings of the thirty-seventh annual ACM symposium on ...
1
vote
0answers
22 views
Repair operator for evolutionary algorithm
I am working on a resource allocation problem using an SPEA 2 evolutionary algorithm. The problem involves decision variables where each variable has a different domain e.g. $E_i \le d_i$ where $E_i$ ...
1
vote
1answer
42 views
Multi-Path Length Minimization
I've been thinking about path planning and am trying to make good heuristics for cases with multiple agents.
Suppose there are sets $S_i$ of coordinates in $\mathbb R^2$ or $\mathbb R^3$, each of the ...
0
votes
1answer
45 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
25 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
84 views
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
22 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 ...
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
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
0answers
180 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
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 ...
1
vote
1answer
62 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
146 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
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 ...
1
vote
1answer
20 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 ...
6
votes
1answer
510 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 ...
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 ...
1
vote
1answer
28 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 ...
1
vote
1answer
80 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
38 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
27 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
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 ...
4
votes
1answer
124 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
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 ...
0
votes
2answers
644 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
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'...
