Questions tagged [constraint-programming]

The tag has no usage guidance.

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

Guarantee the solvability of conditional, but cyclic dependencies

I have a bunch of values, some that are given by an end user input and some that are calculated based on that input. The way that the values are calculated are input by a different group of users of ...
SourceOverflow's user avatar
1 vote
0 answers
14 views

Understanding Arc Consistency 4 in the context of Wave Function Collapse

Following this blog post about the Arc Consistency algorithms. Namely, the explanation on AC4. Consider the following example: If I understand AC problems correctly. Then: We have two known ...
bli00's user avatar
  • 111
3 votes
1 answer
28 views

How can I model this optimization problem?

We're looking to model the following problem as a standard optimization problem (or even a non-standard one). We can come close, but nothing seems to fit exactly. We have a working algorithm coded, ...
Ted Hopp's user avatar
  • 133
0 votes
0 answers
22 views

Placement of Tasks from Dataflow Graph on a Physical Graph

I have a dataflow graph where a set of different types of tasks are placed in corresponding types of nodes. Say the task types are called A, B, and C. A-type tasks are placed in all the leaf nodes of ...
bsha's user avatar
  • 1
0 votes
0 answers
18 views

Optimize clothing in RPG considering set bonuses

In role playing games, switching equipment for better is a common procedure. My question is to find an algorithm that can optimize linear combination of stats the equipped gear gives - this is exactly ...
Ferazhu's user avatar
0 votes
0 answers
79 views

Solving constrained optimization problem using PyTorch: Minimizing L1 norm of $\vec{x}$ subject to $\vec{x} = \mathbb{A^{-1}}\vec{y}$

My goal is to solve the above-constrained minimization problem where my vector to be optimized is x. The matrix A and the vector ...
Dixshant s's user avatar
1 vote
1 answer
58 views

Encoding "all-except" constraints in CNF

I am looking for an efficient CNF encoding of the following situation: I have sets of boolean literals $A = \{ a_1, \ldots, a_m \}$, $B = \{ b_1,\ldots, b_n \}$ and subsets $B_1, \ldots, B_m$, where ...
Markus's user avatar
  • 166
0 votes
0 answers
60 views

Constrained Horn Clauses vs. "ordinary" Horn Clauses

I see why ordinary Horn clauses (of the type Prolog might accept) are first order eg something like (with all variables universally quantified) $$ P(x) \leftarrow Q_1(x),Q_2(x,y).\\ P(x) \leftarrow ...
Motorhead's user avatar
  • 282
1 vote
1 answer
1k views

If greater than or equal to zero then binary variable equals 1: integer linear program

I have a variable $d_{i} \in \mathbb{Z}$ with an upper and lower bound. I also have a binary variable $v_{i}$ which I want to $=1$ if $d_{i} \geq 0$; else $v_{i} = 0$. How do I enforce this as a ...
Alex Pharaon's user avatar
0 votes
0 answers
2k views

Random team generator with constraints

I would like to create a tool to split a group of persons into multiple teams "randomly". Here is a mockup that shows the UI: https://ibb.co/jDHFkdH Inputs To generate the teams, the tool ...
Edwin ZAP's user avatar
  • 101
3 votes
1 answer
162 views

Is 2-SAT over Linear Real Arithmetic in P or NP?

The general boolean satisfiability problem (SAT) is NP-complete, and thus can't be solved in polynomial time (assuming $P \neq NP$). But the special case of 2-SAT is in P, and can be solved in linear ...
user3558515's user avatar
0 votes
1 answer
67 views

Encoding a binary sequence with shift in MILP

I would like to know if it's actually possible to encode a (binary) sequence with rotations in MILP/MIP. Given a binary sequence $(0,1,1,0,0,0,0,1)$ and variables $x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7$ I ...
DuckyQ's user avatar
  • 1
2 votes
2 answers
110 views

Constraint satisfaction problem: solve system, then evaluate whether many additional constraints are satisfied one at a time

I have a system that consists of binary inequality constraints between variables, plus some indicator variables that can assume only two values: ...
Evan Honnold's user avatar
4 votes
1 answer
353 views

Graph coloring with fixed-size color classes

I'm interested in coloring a graph, but with slightly different objectives than the standard problem. It seems like the focus of most graph-coloring algorithms (DSATUR etc) is to minimize the number ...
Raphie Palefsky-Smith's user avatar
0 votes
1 answer
157 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?
ali_ka's user avatar
  • 1
0 votes
0 answers
44 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 ...
Farah Mind's user avatar
1 vote
0 answers
26 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$ ...
user76646's user avatar
0 votes
1 answer
55 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 ...
Cecelia's user avatar
  • 53
-1 votes
1 answer
335 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 ...
Tobias Dekker's user avatar
2 votes
2 answers
236 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 ...
Cecelia's user avatar
  • 53
2 votes
1 answer
277 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 ...
entropyfeverone's user avatar
1 vote
1 answer
36 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 ...
jack malkovick's user avatar
1 vote
0 answers
19 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 ...
jack malkovick's user avatar
1 vote
1 answer
322 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.
Acc's user avatar
  • 19
0 votes
0 answers
53 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$ ...
OmG's user avatar
  • 3,572
0 votes
1 answer
340 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 ...
Adamos2468's user avatar
1 vote
0 answers
38 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 ...
FollowK's user avatar
  • 11
0 votes
1 answer
58 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 ...
Shinra_SGr's user avatar
1 vote
1 answer
265 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}...
WBM's user avatar
  • 113
2 votes
1 answer
969 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,...
Cecelia's user avatar
  • 53
1 vote
0 answers
67 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, ...
Alex Meiburg's user avatar
1 vote
1 answer
81 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 ...
hola's user avatar
  • 307
1 vote
1 answer
196 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 ...
Isitar's user avatar
  • 113
0 votes
2 answers
264 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 ...
SR89's user avatar
  • 1
1 vote
1 answer
144 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 ...
Kocur4d's user avatar
  • 113
1 vote
0 answers
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 ...
PraveenRB's user avatar
  • 123
1 vote
2 answers
56 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 ...
PraveenRB's user avatar
  • 123
0 votes
1 answer
168 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). ...
Isitar's user avatar
  • 113
1 vote
1 answer
151 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: ...
jminuscula's user avatar
2 votes
1 answer
176 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 ...
Jivan's user avatar
  • 203
1 vote
1 answer
49 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 ...
Andrei's user avatar
  • 362
2 votes
1 answer
820 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 ...
Johannes Heesterman's user avatar
3 votes
2 answers
3k 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 ...
Reinder Kas's user avatar
3 votes
0 answers
831 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 ...
Teodor Dyakov's user avatar
1 vote
0 answers
192 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-...
mohamed's user avatar
  • 41
0 votes
1 answer
253 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 ...
keithyip's user avatar
4 votes
0 answers
78 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 ...
ZakC's user avatar
  • 141
0 votes
0 answers
68 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 ...
Radical's user avatar
  • 101
3 votes
0 answers
167 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 ...
rnbguy's user avatar
  • 141
0 votes
2 answers
4k 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 ...
Michle Niaye's user avatar