Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

Questions tagged [constraint-satisfaction]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
36 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 ...
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 ...
user avatar
0 votes
1 answer
69 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 ...
user avatar
2 votes
1 answer
66 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 ...
user avatar
  • 1
3 votes
1 answer
98 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 ...
user avatar
0 votes
0 answers
15 views

Constraint Satisfaction Constraints Transformation

In constraint Satisfaction, there are implicit constraints which is a single variable and explicit constraints which are multiple variables. I have found a way to transform an explicit constraint into ...
user avatar
0 votes
0 answers
29 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 ...
user avatar
  • 113
0 votes
0 answers
18 views

Method for minimizing relays in a switching/steering network - combinatorics/CSP algorithm exists?

This question is borne from the electrical engineering world, so I first asked it there, but it's really more of an algorithm optimization problem that everyone here might be better suited to help ...
user avatar
0 votes
0 answers
24 views

Finding all k-partitions with additional constraints

The partition problem is a very well known one. To partition an integer array into k equal sum partitions. My problem is I want to partition them in such a way that the sum of their partitions equals ...
user avatar
0 votes
0 answers
19 views

the convergence of the iterative algorithm has a major problem

In order to solve an optimization problem, I divided the main problem into two sub-problems. The two sub-problems require to be solved iteratively until the algorithm converges. I use the bi-section ...
user avatar
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 ...
user avatar
0 votes
0 answers
43 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 ...
user avatar
  • 1
2 votes
2 answers
70 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$ ...
user avatar
  • 123
1 vote
1 answer
84 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 ...
user avatar
0 votes
1 answer
71 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 ...
user avatar
0 votes
2 answers
39 views

Is the following problem NP-Complete? [closed]

3SAT with the additional condition that exactly 1 or 3 literals must evaluate to 1.
user avatar
0 votes
1 answer
57 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 ...
user avatar
1 vote
2 answers
33 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 ...
user avatar
  • 131
2 votes
1 answer
36 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 ...
user avatar
1 vote
0 answers
54 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 ...
user avatar
0 votes
1 answer
27 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?
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 ...
user avatar
  • 215
1 vote
0 answers
110 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 ...
user avatar
1 vote
0 answers
33 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 ...
user avatar
  • 11
2 votes
2 answers
86 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: ...
user avatar
0 votes
1 answer
40 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 ...
user avatar
  • 101
4 votes
0 answers
122 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 ...
user avatar
  • 883
1 vote
2 answers
201 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 ...
user avatar
0 votes
0 answers
36 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 ...
user avatar
2 votes
1 answer
45 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. ...
user avatar
2 votes
1 answer
166 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 ...
user avatar
1 vote
3 answers
196 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 ...
user avatar
2 votes
1 answer
71 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 ...
user avatar
1 vote
2 answers
65 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 ...
user avatar
  • 123
1 vote
2 answers
48 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$, ...
user avatar
  • 131
0 votes
0 answers
76 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, ...
user avatar
0 votes
0 answers
27 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 ...
user avatar
  • 103
2 votes
1 answer
166 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 ...
user avatar
  • 121
9 votes
1 answer
2k 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 ...
user avatar
  • 91
1 vote
1 answer
22 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 ...
user avatar
  • 168
1 vote
0 answers
25 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$ ...
user avatar
1 vote
1 answer
59 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 ...
user avatar
0 votes
1 answer
51 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 ...
user avatar
  • 43
1 vote
0 answers
31 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 ...
user avatar
  • 111
1 vote
1 answer
85 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 ...
user avatar
0 votes
1 answer
25 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 ...
user avatar
2 votes
1 answer
115 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{...
user avatar
2 votes
2 answers
179 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 ...
user avatar
  • 43
2 votes
0 answers
248 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 ?
user avatar
2 votes
1 answer
70 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 ...
user avatar