Questions tagged [constraint-programming]
For questions on modeling satisfaction or optimization problems in languages designed for expressing (often high-level) constraints on decision variables.
140
questions
1
vote
1
answer
98
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
57
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
367
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 ...
- 165
3
votes
2
answers
136
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
62
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
404
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
99
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
379
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
103
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
213
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
74
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
86
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
159
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
87
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
113
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
420
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
48
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
216
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
908
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
77
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
144
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
170
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
202
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
60
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
59
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
202
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
839
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
46
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,076
3
votes
2
answers
484
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,076
2
votes
1
answer
135
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
103
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
83
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
59
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
351
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
167
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
900
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
1k
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
782
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
262
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
436
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
71
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
77
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
152
views
0
votes
0
answers
302
views
OR-Tools addElement constraint
I am just not able to grasp how can I use the addElement constraint of OR-Tools. I am trying to model the following constraint written in MiniZinc:
...
- 119
2
votes
1
answer
75
views
How to model a cumulative resource constraint with same family condition?
Assume that we have 3 tasks to schedule : $x_{a1}, x_{a2}, x_{b3}$. They all use the same cumulative resource : $r_1$. Each activity increases $r_1$ by $1$ at it starts time and decreases $r_1$ by $1$ ...
- 93
2
votes
1
answer
179
views
Scheduling when task duration longer than working interval
I'm trying to modify the job shop example for CP-SAT solver. (https://developers.google.com/optimization/scheduling/job_shop)
I'm limited to 8 hours working day,
So I defined a list of NewIntervalVar()...
- 65
2
votes
1
answer
479
views
Set value based on if other variable is in specific range
I have the following problem.
number_of_machines is controlled by other constraints. I need to set line variable to specific value based on "range" ...
- 65
2
votes
1
answer
52
views
ILOG CPOptimizer soft constraints (multiple solves reusing searched space)
I'm trying to feed information retrieved from my neural network to my CP model to help narrow down the search on big instances of my problem. However, I also want to remove the additional imposed ...
- 121