Skip to main content

Questions tagged [cp-sat]

Questions relating to the Google CP-SAT solver, available through OR-Tools.

Filter by
Sorted by
Tagged with
2 votes
1 answer
78 views

Cumulative constraint with a window

I have a decision variable R, indexed by n over N, where R[n] is equal to some integer value. I want a constraint that, for a specific window size, e.g. 5, gives a maximum to the summed values inside ...
QuestioningPanda's user avatar
2 votes
1 answer
97 views

Assignment of colored boxes to groups

I am working on a problem that I think can be solved as an extension to the assignment problem, but am open to hear about other ways to solve. PROBLEM There are a lot of colored boxes. For each color ...
frellwan's user avatar
1 vote
1 answer
90 views

Information shared among workers in OR-tools CP-SAT

I stumbled upon this video while using OR-Tools CP-SAT solver https://www.youtube.com/watch?v=lmy1ddn4cyw At around 12:10, the part of multithreaded solvers starts. I understand these solvers are ...
QuestioningPanda's user avatar
2 votes
1 answer
223 views

CP-SAT: Workarounds for OnlyEnforceIf with Linear Expressions

Background I've written a solver that selects a subset of people from a larger pool such that the subset has at least X people per attribute (Gender/Job/Country etc. X differs per attribute). This ...
Riezz's user avatar
  • 41
1 vote
4 answers
562 views

Google-OR Tools: Assignment minimizing overlapping members

I'm rusty on constraint optimization and am looking for help in this particular use case. There are individuals who are each member to several teams. This is a fixed many-to-many relationship and is ...
James Kolpack's user avatar
3 votes
2 answers
368 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: ...
Issouf's user avatar
  • 65
1 vote
2 answers
70 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 ...
Nara's user avatar
  • 11
1 vote
1 answer
157 views

Non integer linear objective in or-tools CP-SAT

It seems that or-tools' CP-SAT solvers allows for non-integer coefficients in a linear objective expression. Am I correct, or is it just that the solver doesn't check for integrity and rounds the ...
E. Fischer's user avatar
0 votes
2 answers
90 views

Formulating assignment problem with people attributes that need to be balanced per assignment attribute in or-tools, CP-sat

I'm trying to do an assignment problem with the following characteristics: I have two sets that need to be matched with each other, set A (Students) and set B (Class combinations). Set A and B have ...
Riezz's user avatar
  • 41
0 votes
1 answer
165 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 ...
Penghui Guo's user avatar
0 votes
1 answer
122 views

Team Orienteering Problem with Time Windows infeasible using CP-SAT solver in Google OR-Tool

I am developing a TOPTW where there are a set of N nodes. Each node i is associated with a visit time, which is also the score Si. The starting point and the end point of each tour is fixed, which is ...
orman's user avatar
  • 33
3 votes
2 answers
248 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, ...
luca_dix's user avatar
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 ...
John D's user avatar
  • 199
-1 votes
1 answer
295 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 ...
Arthursbr's user avatar
1 vote
1 answer
768 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 ...
John D's user avatar
  • 199
3 votes
1 answer
159 views

CP-SAT's `NumBooleans()` parameter

The solver API for CP-SAT offers the attribute NumBooleans, which is documented as "Returns the number of boolean variables managed by the SAT solver". ...
Hanno's user avatar
  • 181
4 votes
1 answer
385 views

Relevance of order of model construction in CP-SAT

Question 1: Is ortool's CP-SAT sensitive to the order in which a model is constructed? In other words, does it matter which variables and constraints come first? I am seeing a high performance ...
Hanno's user avatar
  • 181
2 votes
2 answers
178 views

Mixed Integer Programming: Iterative assignment problem

I have a real world problem, which is analogous to the below toy problem, which I call 'The Movie Theater Problem' (TMTP.) In TMTP, movie viewers are assigned seats which principally balances two ...
jbuddy_13's user avatar
  • 551
1 vote
1 answer
174 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 ...
SlowLoris's user avatar
  • 145
5 votes
3 answers
483 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 ...
Blackhole's user avatar
  • 235
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 ...
Kathryn Twomey's user avatar
2 votes
1 answer
86 views

Circuit constraint leading to infeasibility if there are 0 jobs producable one a machine

Using the CP-SAT Solver: My Model turns infeasible whenever there is no job available for a machine. Not every job can be built on every machine. Example Situtations: Less jobs than machines No jobs ...
cl_cookie's user avatar
2 votes
1 answer
217 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 ...
Artem Popov's user avatar
2 votes
1 answer
476 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 ...
Artem Popov's user avatar
3 votes
1 answer
356 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 (...
Artem Popov's user avatar
3 votes
0 answers
199 views

Can Pyomo be linked with Google's GLOP or CP-SAT solvers?

Pyomo can be linked with several solvers Open source and commercial ones. I was wondering if Pyomo can be linked with Google's GLOP or CP-SAT solvers?
Optimization team's user avatar
2 votes
1 answer
195 views

Scheduling optimization, Adding 4 day same shift and 3 day off weekly constraint

Am writing a small scheduling program in C# for a group of 7 staff who will be working in three shifts daily for 4 weeks. Am using the google OR-Tools Template, but i have modified it abit This is the ...
indago's user avatar
  • 121
1 vote
1 answer
183 views

Modeling Multi-Agent Collision in Google CP-SAT Solver

I would like to implement a solution for Multi-Agent Pathfinding Problem using Google's CP-SAT Solver. How do I implement the constraint that prohibits 2 or more agents from occupying the same cell at ...
Raghav Thakar's user avatar
1 vote
2 answers
263 views

Google CP-SAT Infeasible ILP for Large Problem Area

I am trying to generate a shortest path between source and sink in a square grid of cells. I am using the Google CP-SAT solver ...
Raghav Thakar's user avatar
2 votes
0 answers
77 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 ...
user1502040's user avatar
2 votes
0 answers
222 views

CP sat solver approach for task assignment with pre defined task start end times

I spent some time trying to clarify the problem more succinctly. I has a set of fixed tasks which are of a certain type/category and which can be allocated to a set of workers. The tasks have ...
ana's user avatar
  • 21
0 votes
1 answer
233 views

or-tools: job shop problem never exists not finding additional solutions

I am trying to solve a flexible job shop problem variant using or-tools. And in some input configuration, in general after one month of scheduling time, I am facing a weird behavior. I am aware that ...
Joel's user avatar
  • 9
3 votes
0 answers
463 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 ...
Srikanth Shastry's user avatar
3 votes
2 answers
421 views

Enforce Changeover Constraints in Production Scheduling

I'm building a production scheduling optimization model (but not exactly a jobshop, so I can't just use OR tools). I have decision variables for both the start time of each job, and the duration. ...
Ralph Asher's user avatar
6 votes
1 answer
116 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 ...
rsella's user avatar
  • 169
3 votes
1 answer
158 views

"Complex" scheduling problem model structure

So, I'm modelling a job assigning problem in OR-Tools CP-SAT. I want to maximize rescheduled jobs based on some constraints. Right now jobs in my model look like this: ...
Gleb S's user avatar
  • 51
7 votes
2 answers
447 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 ...
gregy4's user avatar
  • 189
1 vote
1 answer
346 views

Circuit constraint respecting the order of the next n jobs / jobs on each machine starting at 0

I am working on a scheduling problem in OR-Tools using the CP-SAT solver. I'm working with python but I managed to rebuild this solution as starting point: Optimal way to ensure optional intervals are ...
cl_cookie's user avatar
2 votes
1 answer
290 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()...
Shkvarka's user avatar
2 votes
1 answer
678 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" ...
Shkvarka's user avatar
3 votes
1 answer
126 views

Nurse Rostering Code with custom constraints Not Working

Could someone please check this code. I modified constraints as : No. of nurses - 10 Max No. of nurses in Morning/Afternoon/Evening Shifts - 3/4/2 Max no. of shifts in a week per nurse - 5 ...
user3237357's user avatar
6 votes
1 answer
444 views

Solver Recommendation : Discrete Variables and Quadratic Constraints

I would like some solver recommendations to solve a problem with boolean/integer variables, mostly linear constraints but also some quadratic constraints. I also have an objective to minimize which is ...
Shinra_SGr's user avatar
1 vote
0 answers
237 views

Modified bus scheduling problem question in ortools

Has been crossposted in stackoverflow. I want to solve the bus scheduling problem using ortools with some minor modifications. In my case, the max number of drivers is known. The modifications I would ...
azal's user avatar
  • 153
3 votes
1 answer
2k views

CP-SAT _ Summing variables under conditions

I have been working lately on scheduling optimization using CP-SAT in OR-TOOLS and now I'm at the point where I need to start considering due dates in my model. I didn't want to put them as ...
ooo's user avatar
  • 119
3 votes
2 answers
193 views

Google OR returning different values depending on language

Lately, I have been working on a CP-SAT model for solving multi-resource flexible job shop problems. I used the code (1) as an inspiration for building code (2) in Python which works well. Then I had ...
ooo's user avatar
  • 119
2 votes
2 answers
217 views

Parallel scheduling with precedence constraints and variable job length

I have $N$ jobs and $M$ machines and want to minimize the makespan, i.e. the total time to finish all jobs. Some jobs have precedence constraints and can only be started once other jobs are finished. ...
tphillips's user avatar
  • 145
2 votes
1 answer
2k views

How to know which constraint in CP-SAT did not meet the feasibility gap

Is there any systematic way to retrieve some information on the constraint that caused infeasibility in Or.Tools CP-SAT? ...
Mahmoud's user avatar
  • 127
2 votes
1 answer
126 views

How to model a set of integer variables getting assigned different values than another set of integer variables

Assume we have variables $x_1, x_2, x_3, x_4$ that each can belong to $\{1,2,...,10\}$. How can we model a constraint that variables $x_1, x_2$ get assigned different values than $x_3, x_4$? Because ...
Mahmoud's user avatar
  • 127
3 votes
1 answer
222 views

Best known results on the flexible jobshop benchmarks

Is there a website that compiles the best known results on the flexible jobshop problem ? I know there was a blog post/article by Quintiq, a (deleted) blog post on CP Optimizer, some more recent ...
Laurent Perron's user avatar
3 votes
1 answer
715 views

Multiple Knapsacks with splitting

I am trying to solve a problem that I believe is a variation of the multiple knapsacks. Like the classical multiple knapsacks problem, I have a set of items, each one with a weight and a value and I ...
Cesar Canassa's user avatar