Questions tagged [constraint-programming]
For questions on modeling satisfaction or optimization problems in languages designed for expressing (often high-level) constraints on decision variables.
145
questions
1
vote
3
answers
62
views
Constraint programming problem with matrix of integers
I am trying to solve the following problem. Suppose $A$ is an $m \times n$ matrix of integers with entries in $\{1, \dots, k\}$. There are two kinds of constraints on the entries of this matrix:
For ...
2
votes
1
answer
139
views
What exactly does the AddHint() method in Google OR-Tools' CP-SAT solver do?
I have an optimization problem that I am solving with CP-SAT and I am using the Python interface. Moreover, I know a good feasible solution coming from a heuristic and I want the solver to start its ...
- 199
4
votes
3
answers
480
views
How can I formulate this 'if-then' constraint problem?
I have five integer variables, and I need to write some constraints on them:
$x_0$ , $[x_1, x_2, x_3, x_4 ]$. $1 \leq x_i \leq 3$
if $x_0 =1$ then no constraint on $[x_1, x_2, x_3, x_4 ]$
if $x_0 =...
- 1,120
-1
votes
1
answer
90
views
[OR-Tools][CP-SAT] Implement an indicator function in a constraint
Good morning ! I would like to implement this constraint using CP-SAT (see image below).
x_i,j is a boolean variable, a and b are given. The problem is that I don't know how to implement the ...
1
vote
1
answer
138
views
About circuit constraints in OR - tools
I am trying to implement a scheduling problem to solve with CP-SAT from OR-tools. There, in particular, for every machine I want to add a time transition constraint from every task that is performed ...
- 199
1
vote
1
answer
118
views
Linearize conditional constraint
Consider a variable c from the domain {-1,0,1}. I have the following constraint:
IF $c = 1 \Rightarrow x = 1 $ ELSE $x = 0$
How do I linearize this constraint?
- 21
1
vote
1
answer
63
views
Multiplicity-Constraint in Constraint Programming Solvers
I need to solve a CSP with a constraint imposing upper bounds on the multiplicity of variables in a list.
More precisely, I need a constraint of the form
...
- 113
3
votes
1
answer
407
views
Of what size should I expect to be able to solve an integer linear program with Pyomo?
So I am solving a purely integer linear optimization problem with Pyomo on a single computer (core i-5, 12 GB RAM). The problem has around 10000 variables and 300 constraints. For doing this, I am ...
- 199
3
votes
2
answers
139
views
Vehicle passenger assignment with capacity constraint
Problem Summary
To match passengers (the number of passengers) to capacitated vehicles such that the profit is increased. All the vehicles have the same capacity $c$. It is not important to track ...
- 33
1
vote
2
answers
64
views
If $x_1 \geq 4$ then **one** out of the following three constraints must hold: $x_2 \leq 3, x_3 \leq 4, x_4=5$
How does one linearize the following constaints:
If $x_1 \geq 4$ then one out of the following three constraints must hold: $x_2 \leq 3, x_3 \leq 4, x_4=5$.
$$x_1 \leq 4 + Mz_1$$
$$x_2 \leq 3 + M(1-...
- 119
6
votes
1
answer
447
views
Doubles Round Robin Sorting Algorithm
Background: I have a group of 6 guys that get together and play pickleball every week. We play 2v2 and 2 players sit each game. We play 2 sets of 6 games each week (12 total games) - in each set, ...
1
vote
2
answers
121
views
Does the cvxpy replace the max function by MIP formulation under the hood?
Does the cvxpy replace the max function, which is convex, by MIP formulation under the hood when shows up in the constraints (for example, $\max(x,y)\le z$) or in the objective function? In gurobipy, ...
- 391
2
votes
1
answer
390
views
If/then constraint formulation
Let's assume we have event $i=1,2,\cdots,k$, denoted as $\text{event}_i$. We know for a fact that $\text{event}_i$ is smaller then $\text{event}_{i+1}$ i.e., $\text{event}_i \leq \text{event}_{i+1}$. ...
2
votes
1
answer
118
views
Conditional constraint for binary
Could you please check where I might be wrong?
Task is:
If $z=1$, then either $x=1$ or $y=1$
My approach:
If $z=1$, then $x+y=1$
$\implies x+y\le1$
$\implies x+y\ge1$
If $z=0$, then $x+y\ge0 - M\cdot(...
5
votes
2
answers
238
views
Binary variable constraint
The task is to ensure that if $x_i = 1$ for at least $k$ of the possible indices $i$ in $\{1,...,n\}$ then $y = 1$, where $k$ and $n$ are parameters, $x$ is a binary variable vector with $n$ elements, ...
1
vote
1
answer
91
views
Simple Constraint Programming Problem: docplex works but equivalent ortools model is infeasible
I have a simple constraint programming model which can be solved using the docplex library, however I am struggling to implement the same model using ...
- 145
2
votes
1
answer
89
views
Modeling advice: scheduling problem with judged events and "blocks" of judging assignments
I am considering a scheduling problem in which the events are officiated, likely as a MILP problem. I'm getting hung up on how best to model a particular requirement of how the judged events are ...
- 123
3
votes
2
answers
183
views
Simple Integer Optimization Problem: docplex CP model works but equivalent PuLP+CBC model is infeasible?
I have an integer optimization problem with one constraint per decision variable and no objective function. It can be coded and solved using docplex, however I am ...
- 145
2
votes
1
answer
88
views
Modify the network model to accommodate multiple vehicles
Given a directed network (or graph) $G = (V,E)$ with each edge $e_{ij}$ having a non-negative cost as the travel time from $i$ to $j$. Each node has an associated demand $d_i$. If the demand is ...
- 145
1
vote
1
answer
127
views
Assignment problem with constrained number of unique tasks
I have an interesting assignment problem in which I have a cost matrix for workers and tasks, and need to assign each worker to exactly one task to minimize the cost.
However, this is all subject to ...
- 13
5
votes
3
answers
429
views
Maximize the minimal distance between true variables in a list
I'm using the OR-Tools CP-SAT solver on a list of $n$ boolean variables $x_i$. I'm trying to maximize the minimal distance between two true variables in this list, as illustrated by the following ...
- 235
2
votes
0
answers
52
views
Multi-objective optimization with known variable dependencies (via a graph) -- what is this called?
Suppose that I am trying to solve a standard multi-objective optimization problem:
$$
\min_{
\begin{array}{c}
\textbf{x} \in S
\end{array}
}
\left [ f_1(\textbf{x}),f_2(\...
- 121
3
votes
1
answer
240
views
Unexpected runtime error
I have a model that contains the sets (both ordered and Days also circular): Days and Personnel, and I'm trying to make a restriction run exaclty once per Day for every member of Personnel. I'm using ...
10
votes
4
answers
1k
views
Is there an open-source equivalent to LocalSolver?
I have a constraint programming problem that is easy to formulate and solve (with high solution quality) in LocalSolver. However, I would really prefer to use something open source for ...
- 153
1
vote
1
answer
85
views
Traversing a list data dynamically in Pyomo Abstract Model
In my PYOMO abstract model, I am reading my data file and storing some specific attributes in a list say demand=[].
I am reading the data file as follows:
...
- 69
4
votes
1
answer
175
views
Creating constraints dynamically in pyomo abstract model
I have a networkX graph with few nodes and these nodes have attributes such as "demand".
...
- 69
2
votes
1
answer
178
views
RAM overflow when scheduling 1000+ intervals
Due to the answers to this and this questions, I was able to find the optimal solution for scheduling problem. However, if there are many tasks that must be scheduled, e.g. 1000+, then the solver ...
- 75
2
votes
1
answer
250
views
CP-SAT solver doesn't use all space available for scheduling
This problem is a continuation of this problem. The issue here is the solver doesn't use the whole space available for the scheduling and thus some jobs are not being scheduled. For example: we need ...
- 75
2
votes
0
answers
61
views
Assignment/scheduling how to formulate considering job time and job cost
I have the following problem that I do not know how to formulate.
There are a fixed number of workers $w_i \in W$ for $i \in [1…N]$.
Also, there are a fixed number of jobs that must be assigned to ...
- 169
3
votes
2
answers
62
views
Constrained shift assignment problem using ilogcp solver can´t find an optimal solution
I´ve been trying to solve a contrained assignation problem given a set of constraints based in a real-world problem. I modeled the problem in AMPL as follows:
...
3
votes
1
answer
216
views
Force gaps between tasks, tasks are scheduled within their job's time windows in Jobshop problem
The problem I'm trying to solve is a modification of the original Jobshop problem. The additional constraints are:
There is only one machine for all jobs and their tasks.
Each job has a priority (...
- 75
7
votes
2
answers
845
views
Is there a better way of defining a constraint on positive integer variables such that no two variables are the same and are uniquely assigned a value
So suppose I have integer variables $x_1,x_2,\dots,x_N$ and I enforce that the integer variables are bounded i.e $1 \leq x_i \leq N$
I was interested in posing a constraint so that in the collection $...
- 205
2
votes
0
answers
49
views
How to add a cut to avoid previously found solution? [duplicate]
I do have a MILP problem. The decision variables are Integer ones. Let's call them $x_i$ and i $\in \{0,1,2,3,...,N \}$
I do want to find all distinct solutiuons for this problem.
The problem is ...
- 1,120
3
votes
2
answers
499
views
What is the difference bewteen CP and MILP approaches in Job Shop Scheduling?
My understanding is Constraint programming (CP) is a sub-set of MILP but in MILP we not only try to find a feasible solution (like CP) but also we should optimize an objective function.
I do have a ...
- 1,120
2
votes
1
answer
137
views
Software for Feasibility Problems
I face a feasibility problem of type
$$ c_i(\boldsymbol x) \leq 0, i = 1, \dots, \mathcal{I} \\ c_e(\boldsymbol x) = 0, e = 1, \dots, \mathcal{E} $$
where $\mathcal{I} + \mathcal{E} \gg \text{dim}(\...
- 297
2
votes
1
answer
109
views
Finding Diverse Paths using Constraint Programming
I am working on a graph problem and want to find some link-disjoint paths between given node pairs. I was wondering if there is an efficient way to achieve this in CP. I checked OR-Tools (routing and ...
- 21
6
votes
0
answers
86
views
Graph coloring problem while counting cliques
Let $G$ be a graph with a set of nodes $V$ and a set of edges $E$.
Let $G'$ be a graph with the same set of nodes $V$ but a second set of edges $E'$.
For a set of nodes $X\subset V$, we denote $f(X)$ ...
- 93
2
votes
0
answers
60
views
Good encoding for grid layout problem
How would you encode the problem given by https://oeis.org/A337663 with an off-the-shelf solver?
You need to lay out $n$ ones and $2, 3, ..., m$ on an infinite grid, for $m$ as large as possible. For ...
- 133
3
votes
0
answers
388
views
Circuit constraints in ortools
I am looking to assign tasks to people. Each successive task should be started after the first one is finished and should be started at the same location as the preceding task. While the time ...
4
votes
1
answer
144
views
Mathematically formulating formal problem of a cloud service scheduler
So, I have been tasked to create a formal mathematical description of problem statement on a cloud service scheduler for my team's university project, which is, honestly, a little weird of a thing to ...
- 79
2
votes
1
answer
183
views
opposite of no_overlap constraint in docplex for CP
I am using python for CP solving.
I would like to know if there is constraint that does the opposite of no_overlap.
This will be like
overlap(interval, arr, n)
interval - single interval variable
arr -...
- 173
5
votes
1
answer
97
views
Help modeling grid placement problem
I'm trying to model a grid placement problem to exercise in OR.
The problem is defined as:
a grid of some dimension (let's say 500x500)
N users that need connection. Every user has:
a defined ...
- 159
7
votes
4
answers
914
views
is prime? in Operations Research
Is there a way to linearize is prime? in Operations Research?
is prime(n) being true if $n$ is a prime number or false otherwise....
- 583
3
votes
1
answer
2k
views
SLSQP vs Trust Region Constrained Algorithms
I have gone through scipy constrained algos explanation, however, not much is mentioned about the differences, pros and cons of the 'trust-const' and 'slsqp' methods. I particularly wanted to know ...
- 139
4
votes
2
answers
879
views
What is the newest MIP and CP solver?
What is the newest MIP or CP solver (which is model based exact solver)?
I want to follow and wonder developments on solvers. But finding new developed solvers (experimental, academic, commercial etc.)...
- 746
7
votes
2
answers
290
views
Why most of constraint solvers do not support optional intervals?
Optional interval is a great idea of optional interval/task that can be active or inactive based on boolean variable. I found it very useful in complex scheduling problems.
It was introduced in IBM Cp ...
- 189
1
vote
1
answer
480
views
Custom lazy callback constraints using Google OR-Tools linear solver?
Is it possible to implement custom lazy callback constraints using OR-Tool's base linear solver?
Through Google's docs, I've seen their TSP examples using the constraint solver ...
- 138
3
votes
1
answer
72
views
Optimize parametric Log-Likelihood with a Tree
Suppose there are some objects with features, and the target is parametric density estimation. Density estimation is model-based. Parameters are obtained by maximizing log-likelihood.
$$\operatorname{...
- 31
1
vote
0
answers
85
views
Minimizing total number of banners used in the cover buildings problem modelled
I was watching a video about Google OR-Tools where they were solving this cover building problem from Codility challenges using constraint programming.
In short, you have a list of building heights, e....
- 111
2
votes
1
answer
158
views
