Questions tagged [constraint-programming]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
0answers
62 views

Choice of algorithm to use to produce an optimal solution based on a growing number of constraints [closed]

Background Information I am currently doing research for my final year project in college. I am planning on building an ambulance booking system that will ease the process of booking an ambulance for ...
4
votes
1answer
93 views

Extracting maximum information from a set of exam answers and their scores

Imagine we have a multiple-choice exam with N questions. Suppose we have a set of K answer sheets to the exam and their total scores (1 for a correct answer on a question, 0 for incorrect). How much ...
4
votes
1answer
220 views

transformation of constraint satisfaction to SAT

How can any Constraint satisfaction problem be converted to an instance of Satisfiability? I have a CSP and i know its NP hard to solve it, but i would like to convert to an instance of k-SAT, but im ...
1
vote
1answer
98 views
5
votes
2answers
278 views

Find a binary matrix so that no vector from {-1,0,1}^n is in its kernel

Given integers $n,m$, I want to find a $m \times n$ binary matrix $X$ such that there does not exist any non-zero vector $y \in \{-1,0,1\}^n$ with $Xy=0$ (all operations performed over $\mathbb{Z}$). ...
-2
votes
1answer
197 views

Alternative representations for the zebra puzzle?

All of the solutions for the zebra puzzle have a variable for each of the properties and a domain with the possible values. For instance A for Nationalities, B for pets, ... Ai with i = 1..5 and the ...
3
votes
0answers
76 views

Find sequence, given partial information about all pairs

Let $\Sigma$ be a small, finite alphabet. Suppose we are given ${n\choose 2}$ sets $S_{i,j}$, where $S_{i,j} \subseteq \Sigma \times\Sigma$. I'd like to determine whether there exists a sequence $...
-1
votes
1answer
2k views

How to minimize the sum of difference of element in sub-sequence of array of length k from given sequence of length n

How to minimize the sum of difference of element in sub-sequence of array of length k from given sequence of length n ? for example : for n=10 1 2 3 4 10 20 30 40 100 200 the sub-sequence of length ...
6
votes
1answer
375 views

In a CSP, what is an extensional constraint?

When talking about Constraint Satisfaction Problems (CSP), what does the term extensional constraint mean?
1
vote
0answers
90 views

Node-weighted CSP in Prim's algorithm?

I'm looking for an algorithm which would find a minimal spanning tree given certain constraints (CSP) about importance of some nodes, e.g. consider a graph with next distance matrix: $$ \left[ \begin{...
8
votes
1answer
219 views

Find subsequence of maximal length simultaneously satisfying two ordering constraints

We are given a set $F=\{f_1, f_2, f_3, …, f_N\}$ of $N$ Fruits. Each Fruit has price $P_i$ and vitamin content $V_i$; we associated fruit $f_i$ with the ordered pair $(P_i, V_i)$. Now we have to ...