Questions tagged [constraint-satisfaction]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
21 views

Is minimum interval hitting problem NP-HARD?

Consider this problem: We want to mark some integer numbers such that we mark the minimum number of the numbers and satisfy some constraints. Each constraint wants that at least $k$ numbers in ...
Soroush Vahidi's user avatar
0 votes
1 answer
26 views

Bipartite matching with constraints on one part

We have a bipartite graph with parts $A$ and $B$, and it is edge weighted. We have some constraints for part $B$. Each constraint is in this format: Between vertices $b_1$ and $b_2$ both from part $B$,...
Soroush Vahidi's user avatar
2 votes
1 answer
60 views

Minimal set of elements needed to satisfy property counts

I have a friend who works in education. Sometimes, they need to create customized "word lists" to help students practice reading. These lists are limited in length, and must contain ...
Aderyn Thomas's user avatar
0 votes
0 answers
24 views

Solving the constraint portion of the input-encoding problem

The "input-encoding problem" is where the binary representations of symbolic input variables to a Boolean function are chosen to minimize the decode logic complexity. The "Espresso-MV&...
MattyZ's user avatar
  • 101
1 vote
1 answer
40 views

Efficient way to calculate many Dutch auctions?

I have 4,500 ($N$) unique items, and I want to auction each one off to the highest bidder (break ties arbitrarily). Each item has $T$ binary traits. Since it is too complex for the $B$ bidders to ...
Neel's user avatar
  • 131
0 votes
0 answers
9 views

Relating the number of solutions to a CSP to the size of the domain and the width of its constraint hypergraph

Let $P$ be a constraint satisfaction problem with $n$ variables, each with the same finite domain $D$, and with $m$ > 0 constraints, where each constraint is an $AllDifferent$ constraint of arity $...
SVMteamsTool's user avatar
2 votes
2 answers
89 views

what is the background theory that Z3 uses to prove constraints unsat

The method to get the sat result is kind of straightforward, you can use some search algorithms like heuristic search to get a solution. But how does z3 get the unsat result like x < 2 && x ...
qingyang's user avatar
0 votes
0 answers
27 views

Constraint Satisfaction Problem 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
1 answer
29 views

How to solve boolean SAT with equality constraints

Say I have boolean formula in form of a CNF(x1,x2,...) with $x_i$ being boolean variables. Testing the satisfiability of the CNF is the SAT problem, i.e. determine ...
Andreas H.'s user avatar
1 vote
1 answer
60 views

Encoding SAT EqualsK Constraint with Two Possible Values

I am wondering about a way to CNF encode an EqualsK constraint with two possible values. In other words, I want to solve for the equation: $$ (\sum_{i=1}^n x_i = A) \lor (\sum_{i=1}^n x_i = B) $$ ...
Tim Bersama's user avatar
1 vote
1 answer
48 views

Encoding "all-except" constraints in CNF

I am looking for an efficient CNF encoding of the following situation: I have sets of boolean literals $A = \{ a_1, \ldots, a_m \}$, $B = \{ b_1,\ldots, b_n \}$ and subsets $B_1, \ldots, B_m$, where ...
Markus's user avatar
  • 166
1 vote
0 answers
56 views

New Knapsack Problem solution with neural network approach

While I was learning the Constraint Satisfaction Problems, I analyzed the Knapsack problem(https://www.csplib.org/Problems/prob133/) and I saw the approach with the neural network was not the best ...
ILIRKI's user avatar
  • 11
0 votes
0 answers
49 views

Constraint satisfaction problems in Natural language processing

I have just started learning about CSP and NLP, for which I have to write a review paper of some research articles. The problem is that when a searched for research articles on some trusted digital ...
Yllka's user avatar
  • 1
1 vote
1 answer
145 views

Algorithm for a modified worker-task assignment problem with groups of tasks and substitutability between tasks within groups

I'm looking for an algorithm to solve a modified version of the assignment problem. It differs from the standard assignment problem in that the modified version has groups of tasks instead of just ...
DOS's user avatar
  • 13
0 votes
0 answers
20 views

Constraint Satisfaction Problem on 8-puzzle

In the 8-puzzle problem, how can I put constraints on the movement of the blank? If zijk represents in the (i, j)th cell, number k is present. Domain, i, j E {1,2,3}, k E {1,2,...,8} Constraint(s) are:...
0jas's user avatar
  • 26
3 votes
1 answer
86 views

Finding a minimal set of package versions in a dependency graph with constraints

Suppose you have a dependency graph of "packages" registered in the ecosystem of a given programming language. We can model each package as a tuple ...
tom's user avatar
  • 133
1 vote
1 answer
34 views

Efficiently finding/ sampling from all solutions to a constrained linear problem

Start with $N>3$ vectors $\vec{v}_I$ in $\mathbb{R}^3_+$, any $3$ of which are linearly independent. $I$ here ranges from $0$ to $N-1$. Let $v_{\left[abc\right]}$ be a matrix in $\mathbb{R}^{3 \...
kram1032's user avatar
  • 113
1 vote
2 answers
341 views

How does the SMT solver Z3 handle conditional statements in a constraint?

I have a constraint system which I seek to find solutions for. The constraints consist of lesser/equal inequalities which have a difference of two minimum expressions on their right side, for example: ...
MvB's user avatar
  • 33
1 vote
7 answers
202 views

How to design a faster sort algorithm? Is there sort of meta-algoritm for it? Or we do not understand how better sort algorithms were discovered?

I know that Quicksort or MergeSort are faster than, say, Bubblesort or Selection sort. And I know why (complexity metrics) but I never been able to find out how could someone start with, for example ...
Luxspes's user avatar
  • 113
0 votes
0 answers
33 views

How to read and interpret these expressions?

I am reading a research paper in which following equation is given: $\underset{\small{X}\\\text{s.t}\sum_{(i,k)\in \mathcal{A}}x_{ik}=1, \forall i\in \mathcal{M}}{\operatorname{max}} u$ where $\small{...
chaaru's user avatar
  • 1
2 votes
1 answer
64 views

Complexity of a restricted SAT problem

I am wondering about the complexity of the following SAT related problem: Given a CNF with $n$ clauses containing exactly $k$ literals with the following properties: The intersection of any pair of ...
PhPanda's user avatar
  • 23
1 vote
1 answer
36 views

Choose combinations of similar value, without repeating first or second coordinate

Motivation In a particular board game, players start the game with a country and a special ability. Two players cannot have the same country or the same special ability. Analysis has shown that ...
redmoncoreyl's user avatar
1 vote
1 answer
673 views

If greater than or equal to zero then binary variable equals 1: integer linear program

I have a variable $d_{i} \in \mathbb{Z}$ with an upper and lower bound. I also have a binary variable $v_{i}$ which I want to $=1$ if $d_{i} \geq 0$; else $v_{i} = 0$. How do I enforce this as a ...
Alex Pharaon's user avatar
2 votes
1 answer
247 views

What is the maximal length of a CNF formula?

The question is quite short. Let $k$ be a given number. What is the maximal length of $k$-CNF formulae can we compute, over the set of binary variables $\left\{ x_1 ,\ldots, x_n \right\}$? The way I ...
Eric_'s user avatar
  • 435
3 votes
1 answer
140 views

Is 2-SAT over Linear Real Arithmetic in P or NP?

The general boolean satisfiability problem (SAT) is NP-complete, and thus can't be solved in polynomial time (assuming $P \neq NP$). But the special case of 2-SAT is in P, and can be solved in linear ...
user3558515's user avatar
0 votes
0 answers
34 views

Specific quantifier elimination for real algebraic numbers

It is well-known that the theory of (first-order) real arithmetic, $\mathcal{T}_{\mathbb{R}}$, is decidable, both on its linear and non-linear (a.k.a field) fragments, since Tarski-Seindenberg proved ...
Theo Deep's user avatar
  • 113
1 vote
0 answers
22 views

Software/library to generate Ising models for random $k$-sat problems

Could someone point me to a software/library which lets one to generate the Ising model/spin model for random $k$-sat problems or $k$-sat problem of a given structure? I understand that it will be ...
Omar Shehab's user avatar
0 votes
0 answers
118 views

Routing with constraints

The following is the statement of the problem: There are 40 packets to be delivered in a day. Each packet needs to be delivered to a particular location. Apart from this, there are constraints also ...
shivam's user avatar
  • 1
2 votes
2 answers
102 views

Efficient Algorithm to Find the Closest Integer Representation, in the Form $A\times\frac{N}{D}$ for a Value

The Problem I am working on a problem that boils down to finding the closest representation of an arbitrary number ($x$) in the form: $$x = A\times\frac{N}{D}$$ Where $A$ is a 32-bit integer, and $N$ ...
Mark Omo's user avatar
  • 123
1 vote
1 answer
127 views

Are there any solvers that can handle non-linearity?

I need a way to solve linear and non-linear inequalities over the natural numbers. So equations like this should be solveable: $\forall n, p, q \in \mathbb{N}. q \cdot (1 + n^p) \leq q$ From what I ...
John Smith's user avatar
0 votes
1 answer
143 views

Non-convex linear program optimisation with infinite number of OR constraints

I am aware that when we have a linear problem subject to OR constraints, the LP would be a non-convex optimisation problem. For example, ${x = 0}$ OR ${1<=x<=2}$. My question is in such a ...
Amal Sailendran's user avatar
0 votes
2 answers
42 views

Is the following problem NP-Complete? [closed]

3SAT with the additional condition that exactly 1 or 3 literals must evaluate to 1.
user136946's user avatar
-1 votes
1 answer
89 views

Solving a CSP using AC-3

Peter (P), Mary (M), Otto (O) and Dicky (D) would like to rent an apartment house. The house has three floors: G/F, 1/F, 2/F. Every floor has only one apartment. P, M, O and D must be assigned to ...
user136632's user avatar
1 vote
2 answers
40 views

Are joins/pullbacks of bloom filters possible?

An interesting advantage of bloom filters over hash tables, that they share with bitarrays, is that they support taking unions & intersections of sets by simply doing bitwise or & bitwise and ...
saolof's user avatar
  • 131
2 votes
1 answer
41 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 ...
imagineerThat's user avatar
1 vote
0 answers
100 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 ...
Abhishek Choudhary's user avatar
0 votes
1 answer
28 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?
yupbank's user avatar
  • 215
1 vote
0 answers
29 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 ...
yupbank's user avatar
  • 215
1 vote
0 answers
125 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 ...
The Pointer's user avatar
1 vote
0 answers
35 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 ...
Sina's user avatar
  • 11
2 votes
2 answers
99 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: ...
Evan Honnold's user avatar
-1 votes
1 answer
50 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 ...
Jack Feng's user avatar
4 votes
0 answers
160 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 ...
Pushpa's user avatar
  • 933
1 vote
2 answers
208 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 ...
Velvet Ghost's user avatar
0 votes
0 answers
40 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 ...
Matthieu's user avatar
2 votes
1 answer
48 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. ...
Matthieu's user avatar
2 votes
1 answer
270 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 ...
Richard Ding's user avatar
1 vote
3 answers
236 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 ...
Rikard Olsson's user avatar
2 votes
1 answer
87 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 ...
Sam Derbyshire's user avatar
1 vote
2 answers
69 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 ...
Sam's user avatar
  • 123