New answers tagged constraint-satisfaction
1
vote
Encoding "all-except" constraints in CNF
Let $[b]$ to denote $1$ if $b$ is true, $0$ if $b$ is false.
We have
$$
\begin{align}
& \bigwedge_{b \in B \setminus B_i} b \\
\iff & \sum_{b \in B \setminus B_i} [\neg b] = 0 \\
\iff & \...
- 2,115
0
votes
Accepted
Algorithm for a modified worker-task assignment problem with groups of tasks and substitutability between tasks within groups
You can solve this problem as follows. Build a bipartite graph with one vertex per worker and one vertex per group of tasks (one vertex for the entire group; not one vertex per task). The cost of ...
D.W.♦
- 149k
Top 50 recent answers are included
Related Tags
constraint-satisfaction × 134algorithms × 33
satisfiability × 26
optimization × 24
constraint-programming × 21
linear-programming × 17
integer-programming × 12
graphs × 10
smt-solvers × 8
artificial-intelligence × 7
3-sat × 7
complexity-theory × 6
np-complete × 6
backtracking × 6
sat-solvers × 5
np-hard × 4
combinatorics × 4
heuristics × 4
genetic-algorithms × 4
data-structures × 3
reductions × 3
reference-request × 3
logic × 3
sorting × 3
polynomial-time × 3