Questions tagged [constraint-programming]
For questions on modeling satisfaction or optimization problems in languages designed for expressing (often high-level) constraints on decision variables.
161
questions
1
vote
1
answer
129
views
Job Scheduling with Energy Consumption using Linear Programming
I'm looking for some advice for an optimization problem regarding scheduling jobs in a datacenter.
So I have a list of jobs and each job has a required time for finishing and a number of cores it has ...
- 11
0
votes
0
answers
53
views
Multilinear programming over the simplex
Let $\triangle_3 \in \mathbb{R}^3$ be the $3$-simplex. I am solving a series of multilinear programming problems that looks like this:
$$\text{Maximize}\sum_{0\leq i, j, k \leq 3} A_{i,j,k} x_i x_j ...
- 151
2
votes
0
answers
94
views
log-log regression as reward function in optimization problem
Consider the model $\hat{y}_t = e^{\text{trend} + \text{seasonality}} \prod_k^K x_{k, t}^{b_k}$
where $K$ denotes different investment alternatives. You can think that trend and seasonality are ...
- 21
1
vote
1
answer
317
views
Discrete point inside a polygon formed by set of vertices
I am working on a problem where I have a set of 2D vertices and a test point. I want to chek whether the test point lies inside ...
- 33
2
votes
2
answers
205
views
OR-Tools CP-SAT solver: is it possible to name a constraint like in GUROBI
I try to implement cp model with OR-tools CP-SAT solver. Please, is it possible to name constraints for being able to manage conflict later like for variables:
...
- 55
1
vote
2
answers
225
views
How to properly tackle a big model using weak constraints
I'm currently working on a model that has a large number of variables (around 200k), and I don't know what the proper way to handle such a big problem is.
One suggestion I got is to use lazy ...
- 11
2
votes
0
answers
58
views
System Stability constraints formulation
I am working with a system having a massless 2D plane and on that plane there is a rigid object with some mass placed on it. I want to support the plane with wooden sticks such that the system is ...
- 33
3
votes
1
answer
60
views
Finding a starting ellipsoid and a minimum volume to approximate a convex optimization problem
Suppose we have a convex optimizatiom program:
\begin{align}
\min &\quad f_0(x)\\
s.t. &\quad h_i(x) = 0 && i=1,\ldots, p\\
&\quad g_i(x) \leq 0 && i=1,\ldots, m\\
&\...
- 53
1
vote
1
answer
75
views
How to calculate the duration of a task in each shift?
I am solving a job scheduling problem with three shifts,
the duration of all shifts are assumed to be known (and might be equal):
The tasks can start from any shift
We know the duration of each task ...
- 1,277
0
votes
2
answers
35
views
Scheduling next shift such its not within X hours of previous shift
Hey i have this constraint that i am trying to code in python: "scheduling next shift such its not within X hours of previous shift"
Given that i have start, end time of each shift and the ...
1
vote
2
answers
46
views
Evaluation of linear expression with docplex based on a solution
For a CpModel using docplex, is there any function to evaluate a linear expression based on the variables values in the final solution?
For example, for ...
- 11
0
votes
1
answer
111
views
Using binary variable or integer variable in Constraint Programming (CP)?
I am trying to solve an assignment problem by Constraint Programming (CP). Let us consider a task assignment problem that have $|M|$ tasks and $|N|$ machines, each task has different processing time ...
- 712
2
votes
1
answer
91
views
Rearrange 'x' piles of items into eight possible locations/bins based on item colour and length
I have an optimisation problem that I believe is a variant of the 'bin packing problem with precedence', but I'm unsure of if that is the correct paradigm to work with and I'm not having a huge amount ...
- 21
2
votes
2
answers
360
views
Scheduling to minimize total "wait to start" time
I have a scheduling problem I am trying to work through. As I was outlining the problem, I realized it is probably of a known problem type, but I am unsure of what keywords to search for or what ...
- 273
1
vote
1
answer
93
views
Modelling Optimal Sorting Networks
I am trying to find sorting networks having the optimal depth or optimal number of comparators by generating $2^n$ binary sequences where $n$ is the channel size.
The main variables in my model are as ...
- 133
-1
votes
1
answer
56
views
How to set an objective to minimize the variance in ratio of allocation
I am trying to write a model where I have to distribute fractions of rent from properties to loans. The objective is to distribute the rents as equally as possible given the loan balance.
Say there ...
3
votes
2
answers
142
views
how to count the number of values that are greater than zero in OR-Tools
I am using OR-Tools for an employees scheduling problem. I have a dictionary that is defined as an IntVar, where such dictionary contains the number of hours that will be assigned to each employee, ...
- 31
3
votes
3
answers
135
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
862
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
500
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,277
-1
votes
1
answer
209
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
473
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
164
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?
- 19
1
vote
1
answer
77
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
497
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
148
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
74
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
582
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
184
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
446
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
128
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
345
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
138
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
95
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
239
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
99
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
173
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
461
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
64
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
271
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 ...
11
votes
4
answers
2k
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 ...
- 163
1
vote
1
answer
90
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
249
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
199
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
362
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
65
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
64
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
266
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
868
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
52
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,277