We’re rewarding the question askers & reputations are being recalculated! Read more.

# Tag Info

13

To solve a problem with Prolog, as with any programming language, be it declarative or imperative, you have to think about the representation of the solution and the input. Since this is a programming question, it would've been popular on StackOverflow.com where programmers solve programming problems. Here I would attempt to be more scientific. To solve ...

10

As spotted by svick, the first issue with the code in the OP is that names beginning with upper-case letters are variables in Prolog. So admit(CP) :- admit(AD) is equivalent to attend(X) :- attend(Y), which results in Prolog immediately entering an infinite loop trying to demonstrate that attend holds for some term by finding some term for which attend holds....

8

I think this is a very good question. You could also ask: when to use a SMT solver? I have a feeling it might be hard to determine before modeling the problem and actually running the CSP/SAT/SMT solvers and finding out. It is well known that even different solvers perform very differently on the same instances! My intuition also comes from the fact that ...

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.,  for details and discussion.  Hsiao, Ju Yuan, ...

6

Problem 1 The case of $(x\rightarrow y \vee \overline y)$ should be a "non conditional variable" with respect to $x$ (ie. that $\overline x$ should now be inserted into $W$). If this is not true, then your algorithm needs an extra step to infer this. Assuming $(x\rightarrow y \vee \overline y)$ is a "non conditional variable", we continue. Problem 2 NOTE: ...

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, ...

5

A dynamic programming solution would work here, if the vitamin contents come from a finite set (for instance, bounded integers). First, sort the fruits on price ascending and in the cases were two or more fruit have the same price, sort them on vitamin content (descending). Now, define $M[f, v]$ to be the maximal number of fruits in a sublist, containing ...

5

Let $X$ be a finite set of variables, where each variable $x \in X$ has a domain of values. Let $D(x)$ denote the domain of the variable $x$. Let $C$ be a finite set of constraints on the variables. Each constraint $c \in C$ has a scope, which is a subset of the Cartesian product $D(x_i) \times \cdots \times D(x_j)$. In other words, the scope of the ...

4

I found the following paper on SAT solving using prolog: A Pearl on SAT Solving in Prolog by Jacob M. Howe and Andy King An implementation of the solver can be found here. See this stackoverflow answer for details on the code and how to use it.

4

It sounds like you want a cost-sensitive (cost-aware, budgeted) optimization technique. Minimizing two values (e.g. the solution of your objective and the cost of operations on $x$ and $y$) is a multicriteria optimization problem, and those tend to be very hard to solve. A common approach is to specify a budget for the maximum allowable costs and then ...

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

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

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 ...

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 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 ... 3 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/... 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

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 ...

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

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 ...

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 ...

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