Questions tagged [constraint-programming]
The constraint-programming tag has no summary.
78 questions
0
votes
0
answers
56
views
suprisingly complicated optimization problem
I have the following constrained (global) optimization problem:
For a user defined sorted real values vector:
xi = [xi(1), ... , xi(N+1)]
I need to find an unknown vector:
x = [x(1), ..., x(L)]
where ...
1
vote
0
answers
54
views
Is it possible to modify the transportation problem to enforce that each destination is supplied by only one source?
Problem Description:
I have a standard transportation problem with:
m sources, each with a given supply capacity.
n destinations, each with a specific demand.
A cost associated with transporting ...
- 11
1
vote
1
answer
98
views
Encoding Universal Reachability in an NFA as a SAT Problem
I am working on encoding a reachability problem for a non-deterministic finite automaton (NFA) as a SAT problem. The NFA has multiple start states and a single final state. My goal is to find a ...
- 13
1
vote
2
answers
137
views
Is there a linear programming method that is polynomial in the number of variables, constraints and bitlength of numbers?
AFAIK, Interior Point method for solving a system of linear inequations is polynomial in the number of variables and constraints. Probably there are others. I don't need to optimize any function (...
- 165
2
votes
0
answers
87
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 ...
- 121
1
vote
0
answers
78
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 ...
- 111
3
votes
1
answer
57
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, ...
- 133
0
votes
0
answers
58
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 ...
- 1
0
votes
0
answers
163
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
2
answers
114
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
136
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 ...
- 301
1
vote
1
answer
2k
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
3k
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
214
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
119
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
202
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
5
votes
1
answer
561
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
249
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
69
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
44
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
77
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 ...
- 53
0
votes
1
answer
422
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 ...
- 101
2
votes
2
answers
321
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 ...
- 53
2
votes
1
answer
320
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
60
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 ...
- 271
1
vote
0
answers
33
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 ...
- 271
1
vote
1
answer
454
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
78
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,612
0
votes
1
answer
419
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
57
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
92
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
306
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
2
votes
1
answer
1k
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,...
- 53
1
vote
0
answers
131
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, ...
- 955
1
vote
1
answer
120
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 ...
- 317
1
vote
1
answer
238
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
342
views
Conditional milp formulation
I have two binary integer variables, $\alpha_{ts,it}$ and $\alpha_{ts,gshp} \in \{0,1\} $, and two real variables $T_{it}$ and $T_{ts}$ which have known upper and lower bounds. How can I model $\...
- 1
1
vote
1
answer
170
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
78
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
99
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
227
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
202
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
212
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
114
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
949
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
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 ...
- 31
4
votes
0
answers
897
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,351
1
vote
0
answers
229
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
298
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
96
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