# Tag Info

7

You are looking for a maximum weight independent set in an interval graph, which can be solved in linear time (by a deterministic algorithm). By the way, the same is true also for a superclass of interval graphs, namely chordal graphs. One such algorithm is based on dynamic programming, you can see e.g., [1] for details and discussion. [1] Hsiao, Ju Yuan, ...

5

I'm not sure what you mean by CSP, but suppose that you mean the following: there are $n$ binary variables and $m$ constraints. Each constraint is associated with a $k$-tuple of (distinct) variables, for some $k$ depending on the constraint, along with a subset of $\{0,1\}^k$ which is the allowed assignments for the $k$-tuple of variables. For example, ...

4

Introduce a new variable $Q$, whose domain is $\{0000,0001,0010,\dots,1111\}$. It represents the value of $C1,C2,C3,P$. For instance, if $Q=0001$, that means that $C1=0$, $C2=0$, $C3=1$, $P=0$. Then, you add a constraint that the first bit of $Q$ is equal to $C1$ (that's a binary constraint), a constraint that the second bit of $Q$ is equal to $C2$ (...

4

It's hard to specify one approach because it depends on your needs. From my experience I can suggest the following: Precision Typical solvers report solutions as "optimal" using gap parameters specifying relative and absolute differences. Take this CPLEX parameter as an example: https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/...

4

I have a method for you that will help you find valid solutions (matrices) for many possible values of $m,n$. However, it is not a complete answer to your question. It can try to find a matrix for a particular value of $m,n$, but it might fail, and if it fails, you've learned nothing; my method cannot prove that no such matrix exists. The method is based ...

4

If you want to model an alldiff() constraint in SAT, there are several options. Here are two different options you can try: One way is to expand $\text{alldiff}(x_1,\dots,x_n)$ into $n(n-1)/2$ inequality constraints: $(x_1 \ne x_2) \land (x_1 \ne x_3) \land \cdots$. Now you can express each inequality constraint $x_i \ne x_j$ on $b$-bit values in turn as ...

4

The constraint satisfaction problem (CSP) is NP-complete. Identifying blobs is a question about graph connectivity which is in P. Therefore, yes, the question you're asking reduces to CSP but this doesn't tell you anything useful: it just says that CSP is at least as hard as this problem but it might be harder. (In fact, it is strictly harder if P$\neq$NP....

4

You can't. You can't express this without using quadratic constraints. Your requirement is about Euclidean distance. The Euclidean distance is inherently quadratic. To be more precise about that: the problem cannot be expressed using solely using linear constraints, as the Euclidean distance is non-linear. That said, you can solve your one-sentence ...

4

This problem is NP-hard: it is at least as hard as independent set. In particular, if you want to know whether there exists an independent set of size $N$, ask for a coloring with as many colors of size $N$; if you find any coloring where a single color occurs $N$ times, you know there's an independent set of size $N$. So, you should not expect any ...

4

You can express the fact that a variable $x_i$ is Boolean as follows: $$(0 \leq x_i \leq 1) \land ((x_i \leq 0) \lor (x_i \geq 1)).$$ You can express the condition $x_i \lor x_j \lor x_k$ as $$x_i + x_j + x_k \geq 1.$$ If some of the variables are negated, you can also accommodate that, by replacing $x_i$ with $1-x_i$. In total, we can express SAT as a ...

3

Let $\mathcal{C}(n,m)$ denote the set of sequences you are interested in, namely non-decreasing sequences of length $n$ consisting of integers from $\{0,\ldots,m\}$, and let $C(n,m) = |\mathcal C(n,m)|$ be the number of such sequences. It is not hard to verify the following recursion: \begin{align*} &C(0,m) = 1, \\ &C(n,m) = \sum_{k=0}^m C(n-1,k) \... 3 Using your graph theoretic formulation, this problem can be restated as the multi-cut problem. Given a graph G = (V, E) and a set of pairs (s_i, t_i) \in I find a set of edges E' \subseteq E such that there is no path s_i \leadsto t_i in the resulting graph G' = (V, E \setminus E') for each i. Since each inequality is unweighted you need to ... 3 If forward checking detects that the potential assignment of a variable x_1 leaves no valid assignments for the variable x_2, one simple strategy is to just make the assignment to x_1 and then queue x_2 as the next variable to be assigned. When the assignment of x_2 inevitably fails, your backjumping machinery will do what it always does and you ... 2 The obvious answer is: take a snapshot (checkpoint) of your state before applying the arc consistency inferences; recursively explore that option; and then if it is a failure, restore the state back to your snapshot. Whether this is efficient depends upon the size of the state and the amount of work done during the recursive call. For this particular ... 2 Below is an exact solutions for the case of 3 \leq n-1 \leq m . Thus, you would only need to manually check cases where m < n-1, (n>3). \mathbf{Theorem:} for 3 \leq n-1 \leq m there always exists a binary matrix X such that no (non-trivial) solution exists to the equation Xy=0. Furthermore, X has the form: X_{(m\ \times\ n)}=\...

2

Hardness Recovering the correct answers to the exam is NP-hard. I'll show how to reduce one-in-three 3SAT to it. Suppose we have a 3CNF formula $\varphi$ on $N$ variables $x_1,\dots,x_N$. The $i$th question on the exam is "Is $x_i$ true?" There is one answer sheet per clause of $\varphi$. If $\varphi$ contains a clause mentioning variables $x_i,x_j,x_k$...

2

The simplest approach (in terms of programming effort) might be to try using an existing graph layout tool. Those solve a related problem: given a graph with distances on the edges, try to find the best layout to draw the graph on the plane. You can treat your problem as an instance of the graph layout problem: we have one vertex per point, and for each ...

2

As you observe, restricting the domain of a variable has exactly the same effect as applying a unary constraint to it. One situation where you might prefer to use unary constraints rather than restricted domains is when you want to control very tightly the relations that are allowed to be used in constraints. For example, if you want to investigate the ...

2

If your system of constraints is expressed as a SAT instance, then this is known as the MAX-SAT problem. MAX-SAT is harder than SAT, but there are standard algorithms. The case of other discrete constraints can be reduced to Weighted MAX-SAT.

2

Make sure you use NP correctly. To say something belongs to NP doesn't really say anything, except that a right solution of the problem can be checked fast. From my experience, it's more about the type of problem than what specific constraints you give it. For example Indipendent-Set: Including a vertex at one end of the graph may inpact if you can take a ...

2

Use Cast to boolean, for integer linear programming, setting $x=a-b$ and $y=v$. This only works if you have a constant upper bound on $|a-b|$. Otherwise, I don't know how to express it in an ILP. See also Express boolean logic operations in zero-one integer linear programming (ILP), Boolean variable true iff equation is satisfied in ILP, Boolean variable ...

2

When a conflict is found during a recursive constraint satisfaction search there may be assignments and inferences in the call stack that have no connection to the conflict. Instead of backtracking through these ineffectual assignments at exponential cost it is better to jump backward over them in the call stack directly to the most recent assignment that ...

1

Your general approach is a good one. Use Boolean variable that captures whether an inequality holds to define $\delta_{i,j}^1$ and $\delta_{i,j}^2$. Then, use Express boolean logic operations in zero-one integer linear programming (ILP) to define $\delta_{i,j}$ in terms of $\delta_{i,j}^1$ and $\delta_{i,j}^2$ (via a logical-AND operation).

1

Use an algorithm to find a perfect matching in a graph. Build a graph where each vertex represents a person, and draw an edge between each two people who don't share any characteristic, then look for a perfect matching. If none exists, you can throw away that data and generate a new random sample, and repeat until you find a valid solution.

1

Turns out this problem is pretty hard to solve and is still under active research. This paper (2004) describes the state of the art.

1

Apparently, based on your comments, each condition is a linear inequality, you have a list of conditions, and you want to test whether an assignment satisfies all of the conditions, or find an assignment that satisfies all of the conditions. Testing whether an assignment satisfies all of the conditions is just a simple matter of programming. For each ...

1

Arc-Consistency algorithm only works on binary constraints.You have to use binary encoding and hidden variable encoding method.

1

Instead of forward checking, try arc consistency. You run arc consistency after every assignment to reduce backtracking. Another further improvement would be assigning a least constraining value (LCV) to a variable with minimum value in the domain (MRV).

1

You've misunderstood the book. It's not describing the AC-3 algorithm; it's describing some other algorithm. The book is describing an algorithm that combines both guess-and-backtrack together with arc consistency. The AC-3 algorithm doesn't do any guess-and-backtrack; it uses only arc consistency checks. Thus, AC-3 does terminate if there is some ...

1

the 2d case of "graph embedding" is also known simply as "graph drawing" and there is a very wide variety of techniques. the most common is probably force directed graph drawing. however heres a basic survey/ slide show that describes CSP, LP, ILP techniques in general. again there is large diversity and there does not really seem to be a unique or standard ...

Only top voted, non community-wiki answers of a minimum length are eligible