# Questions tagged [constraint-programming]

The tag has no usage guidance.

63 questions
Filter by
Sorted by
Tagged with
41 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?
23 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 ...
20 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 ...
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$ ...
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 <, >,...
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 ...
66 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 ...
64 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 ...
66 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 ...
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 ...
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 ...
48 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.
37 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$ ...
79 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 ...
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 ...
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 ...
88 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}...
361 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,...
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, ...
56 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 ...
81 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 ...
131 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 ...
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 ...
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 ...
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 ...
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). ...
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: ...
163 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 ...
40 views

223 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 ...
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 ...
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 ...
136 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 ...
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 ...
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 ...
792 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 ...
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 ...
150 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 ...
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 ...
422 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 ...
99 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 ...
391 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 ...
795 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 ...
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 ...