Questions tagged [or-tools]

Questions related to or-tools, Google's open-source software suite for optimization

Filter by
Sorted by
Tagged with
1 vote
1 answer
82 views

Applying weights to assignment problems for linear MIP solvers

In previous posts, A & B, I posed the Movie Theater Problem. In short, the movie theater problem encompasses assigning viewers to seats such that the distance between viewers is maximized, however,...
  • 347
2 votes
1 answer
52 views

Google OR Tools: Iterative Assignment Problem

This question is a Google OR-Tools specific implementation of recommendation from a previous question. In short, the movie theater problem encompasses assigning viewers to seats such that the distance ...
  • 347
2 votes
2 answers
72 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 ...
  • 347
3 votes
0 answers
44 views

Or-tools : CVRP multiple time window with multiple location

I am using or-tools to solve a CVRP with multiple time window, and multiple location. Meaning that a customer can move during the day. I can't achieve to add constraint like if i deliver the customer ...
  • 31
1 vote
1 answer
42 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
5 votes
3 answers
404 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
1 vote
1 answer
110 views

(OR-Tools) Custom Function to Evaluate Intermediate Solutons

I have a system with $k$ tasks, where each task is a state in a Markov chain. I am working on allocating agents to each task. I would like to achieve a specific distribution of the agents among these ...
2 votes
1 answer
66 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 ...
3 votes
1 answer
198 views

Google OR-Tools, algorithms under the hood?

Under the hood, what algorithms does Google OR-tools support? From adjacent questions, I saw someone as this question and the answer linked to this repo. However, these sources just show how to use ...
  • 347
2 votes
1 answer
199 views

Multiple Knapsack with Varying Values

I wish to assign customers to their nearest distribution hubs. These hubs have maximum capacities however, and if these are breached I would like to assign customers to the next most appropriate hub. ...
2 votes
1 answer
145 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 ...
2 votes
1 answer
132 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 ...
3 votes
1 answer
165 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 (...
2 votes
0 answers
89 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 ...
  • 121
1 vote
1 answer
96 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 ...
1 vote
2 answers
158 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 ...
6 votes
1 answer
349 views

How to Model Path Being Only Through Adjacent Cells

I am trying to develop a MILP for a path planning problem. I am operating on a grid of cells that represents a map. The arrangement of cells in the grid represents the placement of the cells in real ...
0 votes
1 answer
137 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 ...
  • 9
3 votes
0 answers
229 views

Incorporating OR-Tools in a CMake Project

I'm trying to incorporate or-tools into my cmake project. I've tried some of the suggestions given by the project maintainers, who give a few different ways to integrate or-tools in the readme and in ...
  • 431
5 votes
1 answer
364 views

How does OR-Tools improve on an initial solution to CVRP?

I have an initial solution to a CVRP instance which I am setting as input to the solver. The solver as expected returns an improved solution. I have a few questions regarding the solver. How does the ...
3 votes
0 answers
265 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 ...
2 votes
1 answer
198 views

Mathematical Formulations for Google-OR tools

I recently started looking into Google-OR tools. However, I do not see mathematical formulations of any of the problems the OR-tools can solve. Without looking at the model (set, objective, ...
  • 571
1 vote
1 answer
103 views

OR-Tools Cost Function Integration

I am modeling a problem similar to the job shop problem (tasks with start times, duration, and predecessors) and my objective is to minimize the makespan, with Python and OR-Tools. start[i] is an ...
  • 11
3 votes
2 answers
635 views

Simple example of finding Hamiltonian path using Google OR-Tools?

I'd like to test how good/fast OR-Tools is in finding hamiltonian paths on some (big) directed graphs. But I can't find simple enough (for me) examples. Something like these ones (or even simpler), ...
3 votes
1 answer
125 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: ...
  • 51
2 votes
2 answers
321 views

Modeling Refueling in Vehicle Routing Problem in OR-Tools

As the title suggests, I am working on a problem that pertains to single-vehicle routing, where certain vertices in V are not mandatory to be visited, but are ...
2 votes
0 answers
243 views

Can I print the linear programming sensitivity analysis report using google or-tools?

One can solve the linear programs using google or-tools with GLOP solver. I wonder if there is a way to print the sensitivity report (like shadow prices etc.).
1 vote
1 answer
180 views

How to stop the vehicle from reaching the depot in between the trip

Requirement overview: The trip route can have the following type of task Delivery only Pickup only Pickup from one location and deliver to another location Condition: Once a trip starts from depot, ...
2 votes
1 answer
272 views

Minimize capacity of vehicles in VRP with OR Tools

I'm using Google's OR tools in Python to do some optimization in routing in a model where I need to pick just the bare minimum to satisfy a demand. The situation is, let's say I need 100 units of the ...
1 vote
1 answer
382 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 ...
1 vote
1 answer
168 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 ...
1 vote
0 answers
70 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
0 votes
0 answers
239 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
4 votes
1 answer
360 views

Is Google's OR-tools for professional work? Specially VRP module [closed]

So I've been given at work a project which consist on finding optimal pathing for trucks in certain custom scenarios. When I discovered this tool I thought it worked wonders for what I understood the ...
6 votes
1 answer
498 views

Python "Coffee Shop Scheduling Problem" - Scheduling Lunches/Breaks

I'm working on an employee scheduling program in python. Having never done this before, I've been researching different libraries that can be used to accomplish the task. Unfortunately, none of the ...
  • 63
2 votes
1 answer
431 views

Using OR-Tools with .NET and GUROBI

We want to model our MILP problem with Google OR-Tools in .NET, and solve it using GUROBI (solver may change in the next 1-2 years). However, we couldn't find the correct syntax to call GUROBI. https:/...
2 votes
1 answer
140 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
1 answer
412 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" ...
1 vote
0 answers
219 views

Set Covering and Column Generation

I need some set covering and column generation examples in OR-Tools python. If anyone can provide or direct me to some resources that would be great..!
2 votes
1 answer
178 views

A specific case of a resource constrained project scheduling problem with partially renewable resources (RCPSP/$\pi$) - OR-Tools

I've been trying solve a specific case of the resource constrained project scheduling problem with partially renewable resources (RCPSP/$\pi$ in the literature e.g. this paper). These resources are ...
1 vote
1 answer
70 views

Print Intermediate Solutions of Scheduling Problem and tackling FLAGS in jupyter notebook

I tried this code and it goes on and I'm clueless when it'll end so I manually interrupt it. Is there any way we can see intermediate solutions that are feasible solutions and can we limit time or ...
2 votes
0 answers
122 views

Multiple Depot/Crew Office Bus Driver Scheduling Modelling

I'm working on Bus Driver Schedule with multiple add-on constraints that are complex and hence trying to figure out how this can be achieved. Reference of Bus Driver Scheduling using OR-Tools:- https:/...
3 votes
2 answers
196 views

Extracting CNF representation of my problem from SAT solver

As I know, any SAT solver such as or-tools or cplex cp optimizer converts a given problem to CNF form in the first place. Is it possible to extract the resulting CNF representation from or-tools or ...
2 votes
1 answer
176 views

OR-Tools, How to avoid dividing by zero

Problem: There is an order to fabricate some products of total number, let's say 200 (all products are the same). We have some number of factories, let's say 5. Every factory has different number of ...
4 votes
1 answer
608 views

Using VRPy and OR-tools in Python to solve the DCVRP

This question is a follow-up to this one. Since I understand the complexity of the problem I have been underestimating, I turned my attention to off-the-shelf solvers, like VRPy and OR-tools. I would ...
  • 1,239
4 votes
2 answers
289 views

OR-Tools: Partial Solution ignored due to "unknown rate is too large"

With SetHint() from the OR-tools linear solver I am trying to pass a feasible solution to my problem. But I receive the following warning: ...
  • 93
1 vote
1 answer
2k views

Travelling salesman problem variant without returning to the starting point

I tried the code provided on the link : https://developers.google.com/optimization/routing/tsp The actual requirement is to traverse all paths without returning to the start point with minimum ...
  • 111
4 votes
2 answers
2k views

find suboptimal solution, if no optimal solution exists?

I am using or-tools linear solver. and my problem ends up having no optimal solution. how can I tell the solver to find a suboptimal solution?
1 vote
0 answers
122 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 ...
  • 153
0 votes
0 answers
120 views

Mixed Integer Programming - Model Formulation for A Resource Allocation Problem

There are a number of orders, which needs to be shipped. For each order, there may be 1 to 3 route options. The problem here is to find out the best allocation (combination) of orders among these ...
  • 137