Questions tagged [constraint-programming]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
14 views

Constraint propagation using Projection rule

I've found this example of constraint propagation using projection rule We have C = { x1 ≠ x2, x1 ≥ x2 } < C; x1 ∈ {1,2,3}, x2 ∈ {1,2,3} > They say that ...
0
votes
0answers
11 views

How to apply AC-3(Arc-consistency 3) algorithm in N-Queen problem?

I am building N-Queen Solver with java. I confused with AC-3 algorithm. I heard that AC-3 can be applied with backtracking algorithm before processing and during the search.The latter is called MAC-3 ...
1
vote
0answers
15 views

Constraint headers format in CHR

I'm new to CHR and I was wondering if it makes sense to have have functions as arguments for constraint heads in a rule. I know that in the body of the rule this is possible. E.g. Is ...
0
votes
0answers
12 views

How to calculate constraint check in BT of 4-Queens problem?

I have seen number of constraint check in paper of CSPs. The constraint checking is counted as followed: when a value of a variable x is checked against a value of variable y, this is counted as ...
0
votes
0answers
19 views

What is the time complexity of FC_MRV algorithm?

I am studying CSP and read the papers on it.I wanted to know the time complexity of Forward checking with Minium Remaining Value algorithm.
0
votes
0answers
21 views

Channeling Constraints in Constraint Handling Rules (CHR)

Suppose we have a constraint satisfaction problem that can be defined as its constraints in two different viewpoints $V_1$ and $V_2$. Moreover, there are two variables $A$ and $B$ from $V_1$ and $V_2$ ...
0
votes
1answer
33 views

How to model equality in Integer Linear Programming

How to implement v=(a==b) using Linear Programming? $$ v= \begin{cases} True, a=b\\ False, a≠b\\ \end{cases} $$ Until now I tried the big M-Method. To show a≤b: $$a-b+Mv≤M$$ $$-a+b-Mv≤-1$$ To show ...
0
votes
0answers
35 views

Projection operator for constraints

I was looking at HM(X) framework, Hindley-Milner parameterized by a constraint system X, and I was struggling to understand what does the projection operator $\exists \alpha$ does for a constraint. ...
1
vote
0answers
26 views

What approach to solve an open shop problem with following constraints

Say we have an open shop scheduling problem with following constraints : No wait-time between operations of a job Multiple job types (meaning each job type has different set of operations eventhough ...
0
votes
1answer
39 views

Modelling of minimal NOR-circuit problem with CP

I'm currently working on a Constraint Programming problem which I find difficult to model. Here 's the definition of the problem : " Given a specification of a Boolean function f(x1, ..., xn) in the ...
1
vote
1answer
41 views

How to model a logical indicator when two inequalities hold in Integer Programming?

I have an IP program where $\forall i \in I, j \in J$ my decision variables are $x_{i,j}$. I have two sets of inequalities (one inequality for every $i,j$ pair) that are of interest which are $$a_{i,j}...
0
votes
0answers
41 views

Time complexity of well know constraint satisfaction problem algorithms with heuristics

I have know that complexity of csp algorithms as follow: Backtracking algorithm for constraint processing space:O(n) ,Time :O(expn) Backjumping algorithm for constraint satisfaction problem ...
0
votes
1answer
49 views

Which BackJumping Algorithm is being used here?

This is the illustration of the Backjumping algorithm for four queens exhaustive study of essential constraint satisfaction problem techniques based on N-Queens problem .I am confused whether this is ...
1
vote
1answer
97 views

Which AC-3 algorithm is being used here?

This is the illustration of the AC-3 algorithm for four queens from exhaustive study of essential constraint satisfaction problem techniques based on N-Queens problem by Md. Ahsan Ayub, Kazi A Kalpoma,...
1
vote
0answers
15 views

Does Quadratically-Constrainted Quadratic Programming get easier if all constraints are equalities?

A Quadratically-Constrainted Quadratic Program consists of optimizing a quadratic objective function while imposing quadratic constraints, which can be inequalities or equalities. Obviously, ...
1
vote
1answer
50 views

Finding infeasible sets of constraints (CSP)

Given a set of constraints, I want to check whether the constraints are feasible. What I am trying now, is to feed the constraints to a solver and check if the solver returns infeasible. I am using ...
1
vote
1answer
62 views

(M)ILP overlap of two intervals

I got an ILP Model where $c_i$ represents the starting time for a visit$_i$. $c_i$ is already constraint by a number of constraints, one is $c_i > 0$. I have now outside of my model 0 or multiple ...
0
votes
0answers
4 views

Looking for a specific type of ADMM iterates

For a $k-$dimensional optimization variable $b \in \mathbb{R}^k$ say the objective is given as, $$f(b) = \langle b, v \rangle + \langle b , Ab \rangle + \lambda \Vert b \Vert_1$$ for some parameter ...
0
votes
1answer
86 views

Conditional milp formulation

I have two binaries, $\alpha_{ts,it}$ and $\alpha_{ts,gshp} \in \{0,1\} $, and two reals $T_{it}$ and $T_{ts}$ which have upper and lower bounds. How can I model $\alpha_{ts,it}=1$ if the following ...
1
vote
1answer
39 views

Algorithm to solve constraint satisfaction problems

I have group of people. Each person can be described by few characteristics: age, occupation, city, favorite_color I would like to generate 60 random people and ...
1
vote
0answers
59 views

Can somebody suggest what is wrong with these constraint? [closed]

I have written two constraints for Mixed integer linear problem. I am working on the scheduling problem i.e., Scheduling of hybrid appliances. For example, the washing machine is appliance indicated ...
1
vote
2answers
46 views

How to create constraints for Mixed integer linear problem?

i am a beginner to Discrete optimization domain. I am working on the real world problem, i.e., Scheduling of hybrid appliances. I have hybrid appliances which can ...
0
votes
1answer
75 views

How do you proceed if your milp is not solvable

We are currently developing an ilp/milp model to fit the best routes with given resources (people) in a given timeframe and given visits and costs to travel from one visit to another (asymetrical). ...
1
vote
1answer
77 views

Shift Organization algorithms (Constraint Programming + Marriage problem)

I want to assign people to cover shifts considering a set of constraints and preferences. Here's the problem definition: Daily shifts must be covered by workers, who are divided in three groups: ...
2
votes
1answer
158 views

Constraint Satisfaction: maximizing total value with no overlaps

Suppose we have a bunch of bars, which can represent anything (time slots, paths, physical items...) and each of them has a start point, an end point, and an associated value. Out of all the bars ...
1
vote
1answer
40 views

Checking large number of configurations with multiple constraints

I have a very large number of constraints such as: $ A1 \land B1 \land C1 \land D1 \land E1 \land F1$ $ A2 \land B2 \land C2 \land D2 \land E2 \land F2$ $ A3 \land B3 \land C3 \land D3 \land E3 \land ...
2
votes
1answer
264 views

Binarization of Constraints

I am trying to solve a Constraint Satisfaction Problem that involves lots of n-ary constraints. But the solver I have implemented only works with algorithms for binary constraints. I've been reading ...
3
votes
2answers
962 views

CSP Forward checking with n-ary (and binary) constraints

I have implemented my own CSP solver using a Backtracking algorithm. Within the Backtracking algorithm I apply a Forward Checking algorithm (reducing domains of connected, unnasigned variables) that ...
2
votes
0answers
480 views

Finding multi word anagrams from a set of words

Finding all anagrams for a word $w$ from a set of words is a problem with many well-known solutions (for example make a hash table mapping from the bag of letters of a word to the word). But what ...
1
vote
0answers
54 views

How to model the constraint of a circle placement problem mathematically?

I have a circle with radius $R$ and $N$ points on a 2D plane with known locations $(x_i,y_i), i=1,2,..N$. I want to place the circle such that it maximizes the number of covered points. Let $d_i=(x_i-...
0
votes
1answer
200 views

How to encode a sequence of non-decreasing integers with an integer without redundancy, loops, and recursions

How to encode a sequence of n non-decreasing integer of [0, ..., m] fulfilling the following conditions: no or minimal redundancy only use 1 integer variable or k independent integer variables with a ...
4
votes
0answers
63 views

(Historical perspective) CSP and SAT inter-fertilization

[Disclaimer: this is a rather specialized question] It is known that techniques like Conflict-Driven Clause Learning (CDCL) and back-jumping -- which improved the Satisfiability (SAT) strategies ...
0
votes
0answers
44 views

Using Genetic Algorithms for volatile problems

Suppose I am looking at an optimization problem with a large number of interconnected constraints, but the solution is - in some regions - extremely volatile (With volatile I mean: small mutations ...
2
votes
0answers
120 views

n-queen puzzle with no 3 queens on same line

I am trying to solve n-queen puzzle with an additional stronger condition that no 3 queens can be on the same line. Right now my algorithm is, Generate a random permutation of ...
0
votes
2answers
2k views

AC-3 Algorithms on CSP problem, What is happened when enocunter to an empty domain variable?

Suppose We Applying Arc-Consistency (AC3) algorithms on one Constraint Satisfaction Problem, if domain of one variable be empty, what is the next step of this algorithm? According to This Link and to ...
4
votes
1answer
82 views

Maximum set of equalities, subject to some inequalities

I have $n$ variables $x_1,\dots,x_n$. I'm given a set $E$ of equalities (each of the form $x_i=x_j$ for some $i,j$) and a set $I$ of inequalities (each of the form $x_i \ne x_j$ for some $i,j$). I ...
6
votes
2answers
517 views

How to impose Euclidean distance constraint in a constraint satisfaction problem without quadratic constraints?

Best reference I could find is this one. However, I could not quite understand this one since there is no numerical example. What I am trying to achieve with one sentence How can I answer the ...
2
votes
1answer
45 views

Help Understanding the Type and Complexity of my Programming Task [closed]

I'm working on a programming task that I, without good evidence, have a sneaking suspicion is NP-Complete. With that said, I would like confirmation on this if possible, as well as some suggestion for ...
3
votes
3answers
142 views

Isn't Domain of a variable nothing but a constraint?

In Constraint programming we have Variables and their Domains and then all the constraints, but if you at the concept of a domain of a variable it is nothing but another type of constraint, you are ...
1
vote
1answer
136 views

Requiring at least one alldiff constraint to be satisfied converted to SAT

For generating certain hard puzzles, I am trying to model a problem (ultimately) in SAT. I don't know how to do that, so I am starting with CSP because it's more expressive. In CSP, there is a global ...
3
votes
1answer
364 views

Efficient algorithm to fulfil a set of coordinate constraints

I have a set of labelled points and a set of distance constraints between pairs of points, consisting of a lower and upper distance bound. There is definitely an arrangement of the points in 3D space ...
2
votes
1answer
94 views

How to decide if CSP is ambiguous?

When you pick up some reading about CSP the main focus is how to solve it. My goal is to compute/decide if CSP is ambiguous (has 2 or more solutions) or not (has 1 solution). Of course brute-force ...
0
votes
1answer
328 views

Blob detection as Constraint satisfaction problem?

In image processing I have a black and white image which is represented by matrix {0,1}, I have to find blob (a region of connected pixels) in it. I'm confused, can this problem be reduced to ...
0
votes
1answer
738 views

Forward checking with conflict directed backjumping [closed]

Can somebody explain me how can I join forward checking with conflict directed backjumping in my CSP solver? I understand that when the consistency fails when I add a value to a variable, I should ...
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 ...
3
votes
0answers
214 views

Steiner tree wiring problem

I’m trying to find an algorithm that can give me an approximate solution for a wiring problem that I have been asked to look at. I believe this is closely related to finding a node weighted Steiner ...
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}$). ...