New answers tagged

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 ...
  • 149k

Top 50 recent answers are included