Questions tagged [constraint-programming]
The constraint-programming tag has no usage guidance.
71
questions
0
votes
0
answers
15
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 ...
- 1
0
votes
0
answers
27
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 ...
1
vote
1
answer
50
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 ...
- 166
0
votes
0
answers
52
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 ...
- 272
1
vote
1
answer
811
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 ...
- 23
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 ...
- 101
3
votes
1
answer
145
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 ...
- 133
0
votes
1
answer
61
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 ...
- 1
2
votes
2
answers
102
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:
...
- 23
4
votes
1
answer
298
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 ...
0
votes
1
answer
139
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?
- 1
0
votes
0
answers
43
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 ...
- 385
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$ ...
- 13
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 ...
- 43
-1
votes
1
answer
304
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
2
answers
205
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 ...
- 43
2
votes
1
answer
271
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 ...
- 256
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 ...
- 251
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 ...
- 251
1
vote
1
answer
291
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.
- 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$ ...
- 3,562
0
votes
1
answer
300
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 ...
- 41
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 ...
- 11
0
votes
1
answer
52
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
1
answer
244
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}...
- 113
1
vote
1
answer
915
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,...
- 43
1
vote
0
answers
64
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, ...
- 923
1
vote
1
answer
79
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 ...
- 307
1
vote
1
answer
181
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 ...
- 113
0
votes
2
answers
249
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
1
vote
1
answer
140
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 ...
- 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 ...
- 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 ...
- 123
0
votes
1
answer
164
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).
...
- 113
1
vote
1
answer
142
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:
...
- 121
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 ...
- 203
1
vote
1
answer
47
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 ...
- 362
2
votes
1
answer
754
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
2
answers
2k
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 ...
- 31
3
votes
0
answers
800
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,331
1
vote
0
answers
190
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-...
- 41
0
votes
1
answer
250
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 ...
- 9
4
votes
0
answers
77
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 ...
- 141
0
votes
0
answers
67
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 ...
- 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 ...
- 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 ...
4
votes
1
answer
105
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 ...
D.W.♦
- 156k
7
votes
2
answers
1k
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 ...
- 1,425
2
votes
1
answer
54
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 ...
- 21
3
votes
3
answers
202
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 ...
- 628