Questions tagged [constraint-programming]
For questions on modeling satisfaction or optimization problems in languages designed for expressing (often high-level) constraints on decision variables.
180 questions
2
votes
1
answer
47
views
CPLEX CP Optimizer's search phase doesn't support Restart SearchType
CPLEX CP Optimizer allows users to set search phases to specify the order in which variables are searched and the method for assigning values, thereby accelerating the search process.
However, when ...
- 111
4
votes
2
answers
781
views
Is it necessary to iterate the simulated annealing algorithm so many times in a production scenario?
I have recently been working on coding a solution for a assembly line balancing problem. My approach is to first use a greedy algorithm to generate an initial feasible solution, and then apply ...
- 163
2
votes
1
answer
393
views
Task assignment: Equitable and Fair work distribution
A set of workers: $w1, w2, w3, w4$ solve a set of arbitrary no. of tasks: $t_1, t_2, \ldots t_{37}$
Each task has a type, say there are total of 5 types of tasks: $q_1, q_2, q_3, q_4, q_5$ and the ...
5
votes
1
answer
237
views
Can this matrix problem be formulated as an ILP (or using constraint programming)?
Given an $n$ by $n$ binary matrix, I want to find the smallest number of bits that need to be flipped to reduce the rank of the matrix over the field of integers mod 2. I don't think there is a fast ...
- 181
4
votes
4
answers
460
views
Finding the longest snake on a grid
I'm trying to solve some variants of the following problem:
A 2D rectangular grid is given. Find the longest "snake" on it. Informally, a snake is a path that does not touch itself. In ...
- 221
0
votes
1
answer
147
views
Is it normal for the convergence curve of the simulated annealing results to look like this?
In a minimization problem I used the simulated annealing algorithm to search for an answer, my initial parameter settings were initial temperature T=100000, termination temperature Tf=1e-5, and ...
- 163
0
votes
0
answers
119
views
Flexible job shop scheduling with sequence dependent setup times - maximum problem size?
I have created a flexible job shop scheduling problem using
https://github.com/google/or-tools/blob/stable/examples/python/flexible_job_shop_sat.py as a basis. I have introduced some conditional ...
3
votes
2
answers
113
views
Constrained optimization with heuristic algorithm in actual production
In a real production problem, if you decide to use a heuristic algorithm (such as GA), what are the mainstream methods to deal with constraints in constraint optimization?
I mean, I knew that there ...
- 163
2
votes
1
answer
73
views
choose constraint from IIS to build penalty function
Suppose I have a single objective optimization model whose constraints are all composed of linear equations and linear inequalities, and now that it is proven to be infeasible in a calculation using ...
- 163
3
votes
2
answers
847
views
How to avoid similar solutions?
I have a problem like this
$x_1 +x_2 +x_3 =10$
let's assume $0 \leq x_i \leq 10$
It is obvious that this problem has more than one solution
For example :
Solution 1 : $x_1 =0 , x_2= 1 , x_3 =9$
...
- 1,378
2
votes
1
answer
149
views
Priority based demand fulfilment in Linear Constraint
Say I have 3 sources. D1, D2, D3. their capacity is 100, 200, 400. I want to create some constraints such that First D1 is depleted then D2 and then D3. But the catch is you cant use min or max ...
1
vote
1
answer
70
views
DOCPLEX Job Shop Scheduling In With Downtime
I am scheduling tasks (audits) to machines (auditors) with machine skills and planned downtime as considerations. I am using the docplex package in Python and ...
0
votes
3
answers
130
views
How do I convert Integer Programming to Constraint programming?
/*********************************************
OPL 12.10.0.0 Model
Author: Shahrukh
Creation Date: 10-Apr-2024 at 11:55:50 PM
The podrace tournament involves n competitors (where n is even) who all ...
0
votes
0
answers
82
views
Solving a multi depot multi vehicle capacitated routing problem using global constraints
I have built the model, but at this point, I am not sure how do I ensure that each fighter starts from the assigned depot and comes back to that depot. here is my code. The ...
0
votes
0
answers
111
views
Need Help for building two constraints in MIP model
Really need help for building two constraints with MIP model, I have written the required information and variable information on the diagram below.
The way I think of it now is to use two ...
- 163
1
vote
1
answer
145
views
Constraint Programming Interview
I'm new in CP. Want to start preparing for my upcoming interviews. What are the questions and topics should I study in CP to get my myself confident?
0
votes
1
answer
49
views
Circular queue modeling
Let
$P$ be a set of discretely interruptible processes/tasks;
$T_i \in \mathbb{N}$ be the running time of process $i \in P$; And
$\tau \in \mathbb{N}$ be the maximum amount of time a process can use ...
- 1,282
2
votes
2
answers
148
views
Differentiability of solution of optimization problem with respect to constraint (properties, conditions etc)
Assume you have the following simple constrained optimization problem:
$$
\begin{equation}
\begin{split}
&\min_x f(x) \\
& s.t \quad g(x) = c
\end{split}
\end{equation}
$$
where $f,g$ are both ...
- 23
1
vote
0
answers
57
views
Tents and trees constraints
I am trying to express the constraints for the 'Tents and trees' puzzle in minizinc but I am a bit stuck...
I can express that each tent must be attached to at least one tree
That a tree must be ...
- 11
1
vote
0
answers
75
views
Problems for which constraint programming is the state-of-the-art approach
What are examples of problems for which the state-of-the-art approach is constraint programming? Considering either heuristic or exact approaches.
I'm looking for specific problems, not just a class ...
- 2,728
5
votes
2
answers
244
views
How to combine MIP solver with a CP one?
I am working on the scheduling problem in the class of parallel resource scheduling models. When I have studied some papers regarding that, I see the method that combines an MIP with a CP. The ...
- 9,446
1
vote
1
answer
244
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
2
votes
0
answers
98
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
449
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
3
votes
2
answers
493
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:
...
- 67
1
vote
2
answers
308
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
62
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
81
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\\
&\...
- 73
1
vote
1
answer
90
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,378
0
votes
2
answers
37
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
89
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
224
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 ...
- 799
2
votes
2
answers
533
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 ...
- 343
1
vote
1
answer
102
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 ...
- 233
-1
votes
1
answer
84
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
373
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
168
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
2k
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 ...
- 221
4
votes
3
answers
510
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,378
-1
votes
1
answer
339
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
1k
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 ...
- 221
1
vote
1
answer
209
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
90
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
869
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 ...
- 221
3
votes
2
answers
159
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
3
answers
125
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 constraints:
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-...
- 121
6
votes
1
answer
1k
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
234
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, ...
- 409
2
votes
1
answer
567
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
147
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(...
user10750