Questions tagged [constraint-programming]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
38 views

How to write an OR constraint in MILP?

I want to write a constraint with ORs in a MILP. In particular, the following: $$x \ge c \lor x \le -c \lor x=0,$$ where $c$ is just a real number. Can anyone give me some hints?
0
votes
0answers
22 views

Stable matching with dynamic preference lists

I have a set $F$ of $n_1$ families, a set $C$ of $n_2$ children ($n_1<n_2$) and a set $M$ of feasible one-to-one matchings of the families with the children. All the children have the same ...
0
votes
0answers
18 views

ILP formulation question

How to formulate the following constraint in ILP? if i-1 <= x <= i+1 then y < 5 end if So basically if the x is ...
1
vote
0answers
19 views

Repair operator for evolutionary algorithm

I am working on a resource allocation problem using an SPEA 2 evolutionary algorithm. The problem involves decision variables where each variable has a different domain e.g. $E_i \le d_i$ where $E_i$ ...
0
votes
0answers
20 views

Coding a Binary Constraint in Python

I am working on a CSP solver in python, and am stuck how to code the constraints. According to my assignment, the constraints are given through an input file, and can contain operators such as <, >,...
0
votes
1answer
41 views

Why N-Queens Problem is not used as experiment in CSP thesis?

I am studying CSP for my master thesis. I found that many thesis based on CSP described N-Queens as an introductory and they actually do experiment on random CSP problems. If so,when I do master ...
0
votes
1answer
63 views

Integer Linear programming formulation if then condition

I want to create constraints such that I can implement the following condition: Let A be an integer variable >= 0 with an upper bound of 12 I want to introduce the following variable B also an ...
2
votes
2answers
60 views

Need recursive version of Conflict based backjumping

I am implementing conflict directed Backjumping algorithm of prosser in java. But, the algorithm is iterative approach. How can it be built with recursive approach? In AIMA they give the recursive ...
2
votes
1answer
64 views

How to know if a problem belongs to NP Class?

What I know (NOT strictly speaking): I know that there is an open question about the equality of P and NP Classes and as long as there is no known algorithm that solves NP problems in P time then we ...
1
vote
1answer
18 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 ...
1
vote
0answers
18 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 ...
2
votes
1answer
47 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
36 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
78 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 ...
1
vote
0answers
28 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
46 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
86 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}...
1
vote
1answer
354 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
19 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
55 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
80 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
1answer
125 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
45 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
48 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
101 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
95 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
162 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
416 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
1k 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
549 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
82 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
221 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
70 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
47 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
135 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
93 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
768 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
46 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
145 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
145 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
417 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
98 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
379 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
792 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
97 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
279 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 ...