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
0 votes
0 answers
44 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 ...
0 votes
2 answers
53 views

How to request shifts when nurses _don't_ work

So I am working on a variation of the nurse scheduler. This includes then the ability to have nurses request when they are going to be on... However, I need to be able to support requests for when ...
0 votes
1 answer
37 views

Job Shop Scheduling with Multiple possible machines for a task in CP-SAT

I am trying to convert the job shop scheduling example of CP-SAT, which goes as; Below is a simple example of a job shop problem, in which each task is labeled by a pair of numbers (m, p) where m is ...
1 vote
2 answers
52 views

Convert sequence to succession matrix with CP-SAT

Say I have a sequence [3,1,0,2], where each element is a decision variable, i.e. I decide upon an optimal sequence of numbers. Is there an appropriate way to convert this sequence to a 2D succession ...
2 votes
1 answer
86 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 ...
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 ...
3 votes
1 answer
765 views

How to balance the workload of teachers in OR-Tools (maximization of the minimum)

I am very new to optimization and OR-Tools. I am trying to solve a very simple question. Let's assume that we have $n$ students. Each student needs to be assigned to only one teacher as a supervisor. ...
3 votes
1 answer
223 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 ...
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 ...
1 vote
1 answer
96 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 ...
1 vote
4 answers
574 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 ...
2 votes
1 answer
256 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 ...
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 ...
11 votes
1 answer
509 views

Modeling an assignment/scheduling problem to minimize total wait

I have an assignment type problem in which there is a set of students, $S$, and a set of training classes $T$. Each training has a fixed start and end day and can accommodate at most 1 student. In ...
6 votes
1 answer
1k views

Constraint Programming OR-Tools finding Matrix Combinations

As a similar post of mine Find all Combinations of a Matrix I am trying to find matrix combinations with entries $>0$ meaning for a matrix \begin{bmatrix} 0 & 1 & 3 \\ 5 & 2 & 1 \\ ...
3 votes
1 answer
127 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 ...
1 vote
0 answers
241 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 ...
6 votes
0 answers
166 views

Modelling issue with precedence constraint in OR-Tools

I'm trying to solve an RCPSPDc model It is infeasible, although Ilog Cplex solves it, so I think I have a modelling issue. I have more constraints but the precedence is the one that makes it ...
3 votes
1 answer
197 views

ValidateModel or tools in c++ and proto problems

I'm trying to validate my model, this is the relevant part of my code: ...
2 votes
1 answer
127 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 ...
8 votes
1 answer
204 views

Strategy for filling a table only slightly dependant on the number of columns

I'm using the OR-Tools CP-SAT solver to fill a table with integers, with various constraints, as illustrated by the x in the following figure. ...
2 votes
2 answers
182 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 ...
3 votes
2 answers
194 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 ...
4 votes
0 answers
107 views

Modelling issue with rcpsp and boolean expressions

I'm trying to solve an RCPSPDc problem in OR-Tools with CP-SAT solver. In my RCPSPDc model (with discount rate) i want to set this objective: $$\max_{s}\sum_{j\in J}\text{profit}_{j}\cdot \frac{1}{(1+...
2 votes
1 answer
293 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()...
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 ...
5 votes
3 answers
484 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 ...
2 votes
1 answer
685 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" ...
7 votes
1 answer
4k views

CP-SAT ortools - Is there any complete list of possible/available StringParameters for the CpSolver?

I wonder if there is any list of string parameters documented. So far, I only know max_time_in_seconds and num_search_workers. ...
2 votes
0 answers
223 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 ...
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? ...
8 votes
2 answers
3k views

CP-SAT over CBC for MIP, is it worthwhile?

I am working in an integer optimization problem. All of the decision variables are binary, and the objective is to minimize some cost function. I currently am implementing CBC, but I have been reading ...
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 ...
3 votes
2 answers
426 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. ...
6 votes
1 answer
448 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 ...
9 votes
1 answer
292 views

How to tackle large nurse scheduling problem?

I have a nurse-scheduling type of problem with a time span of a year and many employees. Formulation My main variables are: \begin{align}x_{e,t} &= \begin{cases}1 \text{ if employee } e \text{ ...
3 votes
1 answer
725 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 ...
7 votes
2 answers
459 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 ...
3 votes
2 answers
385 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: ...
1 vote
1 answer
166 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 ...
0 votes
2 answers
91 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 ...
0 votes
1 answer
169 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 ...
0 votes
1 answer
126 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 ...
3 votes
2 answers
265 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, ...
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 ...
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 ...
-1 votes
1 answer
301 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
803 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 ...
3 votes
1 answer
161 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". ...
4 votes
1 answer
392 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 ...