Questions tagged [or-tools]
Questions related to or-tools, Google's open-source software suite for optimization
122
questions
1
vote
2
answers
40
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, ...
- 1,865
2
votes
3
answers
77
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,219
2
votes
1
answer
144
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 ...
- 2,219
3
votes
1
answer
753
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 ...
- 2,219
2
votes
1
answer
80
views
Control load per trip in multi trip VRP in ORTools
I have implemented multitrip VRP in ortools (To be specific, solved CVRPTW with virtual depots). Maximum number of trips per vehicle is limited to 2. I want to put a hard constraint that load carried ...
CommunityBot
- 1
-1
votes
1
answer
91
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 ...
- 3,121
1
vote
1
answer
143
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 ...
- 2,219
2
votes
1
answer
238
views
OR-Tools: Nonlinear constraints?
I have inherited a reasonably simple ortools-based optimizer (Python) with linear relationships that I need to non-linear-ize, and I have no idea how to do that.
The relevant part of my problem looks ...
CommunityBot
- 1
3
votes
1
answer
108
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".
...
- 2,219
1
vote
2
answers
92
views
Alternative Approaches to Assignment Problem
I have a real world use case where I aim to optimize the assignment of trucks to orders of different sizes over a time window by minimizing some cost function (e.g. total distance traveled).
The below ...
- 36.4k
4
votes
1
answer
217
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 ...
- 2,219
3
votes
1
answer
1k
views
Python, Google OR-Tools, OnlyEnforceIf() method
I am trying to solve a basic puzzle by using Google OR-Tools, this is my first try with OR-Tools and I am trying to learn. I completed almost everything and was ready to conclude the program until I ...
- 2,219
2
votes
2
answers
127
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. ...
- 2,219
9
votes
3
answers
2k
views
Open source MILP solver for quick “good enough” solution
I have a problem that I have already posted elsewhere in OR.stack, but the question is focused around a large binary MILP (about 1 million decision variables). Ultimately, I am more time constrained ...
- 2,219
1
vote
1
answer
63
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
...
- 1,865
2
votes
1
answer
153
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 ...
- 3,121
1
vote
1
answer
248
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 ...
- 2,219
3
votes
1
answer
145
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:
...
- 2,219
3
votes
0
answers
389
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,219
0
votes
1
answer
180
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 ...
- 2,219
1
vote
2
answers
211
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 ...
- 2,219
1
vote
1
answer
132
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 ...
- 2,219
3
votes
1
answer
219
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,219
2
votes
1
answer
257
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 ...
- 2,219
2
votes
1
answer
183
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,219
1
vote
1
answer
92
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 ...
- 2,219
3
votes
0
answers
141
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?
- 2,219
3
votes
1
answer
250
views
Minimum cost flow problem with multiple arcs between nodes in Python / Google OR
Is it possible to work with multiple arcs between 2 nodes within Google OR?
Or are there better modeling techniques?
I want to optimize flow from supply to demand areas, where supply and demand are ...
- 2,219
4
votes
0
answers
431
views
Google-OR tools vs Pyomo and other commercial Solvers for solving a simple maximum flow problem
I have implemented a Pyomo model for solving maximum flow problem as a subroutine of an algorithm. However, the approach does not scale very well because Pyomo does not provide a very good way to re-...
- 2,219
3
votes
2
answers
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 ...
4
votes
1
answer
446
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.).
- 28.2k
1
vote
1
answer
504
views
TypeError: unsupported operand type(s) for *: 'IntVar' and 'float' in ortools [closed]
I am trying to implement a constraint as follows:
...
- 181
2
votes
2
answers
110
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,121
1
vote
1
answer
148
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,...
- 3,121
2
votes
1
answer
119
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 ...
- 3,121
3
votes
0
answers
150
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
111
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 ...
- 1,865
5
votes
3
answers
430
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
0
answers
185
views
Fixed cost associated to SlackVar(waiting time cost) [CVRPTW]
I'm modeling a CVRPTW with some features:
Each type of vehicle has a cost per km and a fixed cost per trip. To calculate these costs, I am using these methods for this:
...
3
votes
2
answers
231
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 ...
- 89
2
votes
1
answer
79
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 ...
- 2,219
3
votes
1
answer
330
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 ...
- 2,219
2
votes
1
answer
235
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.
...
- 36.4k
6
votes
1
answer
362
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 ...
- 1,865
3
votes
0
answers
364
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
374
views
Best way to solve an allocation problem
I have the following problem: I have products with different attributes (price, weight, category) and I have a list of clients. Every client has an "affinity value" with every product, the ...
- 1,865
5
votes
1
answer
578
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 ...
- 91
9
votes
1
answer
569
views
TSP problem: traveller does not visit all nodes - Google OR-tools
Context:
I am dealing with a kind of scheduling problem, in which I have a set of tasks and machines. All tasks must be assigned to machines (not necessary all of them). In addition to that, I must ...
- 1,865
2
votes
1
answer
279
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, ...
- 8,483
3
votes
2
answers
759
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), ...
- 59