7
votes
Accepted
Relevance of order of model construction in CP-SAT
This is a well know behavior of all MIP/CP solvers. Presolve and search are heavily heuristics based (to limit the complexity of the underlying algorithms), and thus are dependent on variables and ...
- 2,597
5
votes
Accepted
OR-Tools CP-SAT solver: is it possible to name a constraint like in GUROBI
Setter:
ct = model.Add(x == 2).WithName("my_ct")
Getter:
ct_name = ct.Name()
- 2,597
5
votes
CP-SAT's `NumBooleans()` parameter
This does not count Boolean variables in the model. It counts Boolean variables in the SAT solver. This is vastly different. Presolve is happening, some constraints are expanded, search and conflicts ...
- 2,597
4
votes
Accepted
CP-SAT _ Summing variables under conditions
A few hours after posting my question here I found a concept I was not familiar with called channelling : https://github.com/google/or-tools/blob/stable/ortools/sat/docs/channeling.md
I used it for my ...
- 119
4
votes
how to count the number of values that are greater than zero in OR-Tools
You can a look at this doc.
You will create one Boolean variable per integer variable, and sum them.
- 2,597
4
votes
Google-OR Tools: Assignment minimizing overlapping members
The MIP model by Erwin Kalvelagen is a good way to solve the problem, and is probably quite efficient.
As an alternative, the following MiniZinc model is a fairly straight-forward model based on the ...
- 196
3
votes
Accepted
Google-OR Tools: Assignment minimizing overlapping members
It is often a good idea to split this task into two parts:
Developing a mathematical model
Implement the model (coding)
Often, if you do a good job on (1), (2) becomes a breeze.
Here is my attempt.
...
- 2,586
3
votes
Non integer linear objective in or-tools CP-SAT
CP-SAT accepts floating point coefficients in the objective. It applies the necessary scaling to do all computation with integers, and report the unscaled objective.
It also displays in the log some ...
- 2,597
3
votes
Accepted
Using binary variable or integer variable in Constraint Programming (CP)?
For the CP-SAT solver, the rule of thumb is the following:
if you need to check if a variable ==/!= value, then you should use an array of Boolean variables instead
the start, end, size of interval ...
- 2,597
3
votes
Accepted
About circuit constraints in OR - tools
The graph is defined by the arcs you pass.
An arc is (start node, end node, literal)
If the literal is true, the arc is selected....
- 2,597
3
votes
Accepted
Force gaps between tasks, tasks are scheduled within their job's time windows in Jobshop problem
Here is a working version of your code:
You need to change the objective. The obvious optimal is not to schedule any job.
You need to add a 0 -> 0 arc to ...
- 2,597
3
votes
Accepted
Simple Constraint Programming Problem: docplex works but equivalent ortools model is infeasible
Please read this doc section
cp-sat prefers Boolean variables. Here is a c++ version.
- 2,597
3
votes
Accepted
Circuit constraint leading to infeasibility if there are 0 jobs producable one a machine
you need to add a self arc 0 -> 0 with a Boolean variable indicating if the circuit is empty.
For for all tasks, add the implication (circuit is empty => task is not performed).
...
- 2,597
3
votes
Google CP-SAT Infeasible ILP for Large Problem Area
With 256, I get the optimal solution quite fast.
With > 256, I get the following error:
...
- 2,597
3
votes
Accepted
Modeling Multi-Agent Collision in Google CP-SAT Solver
Here is my proposal:
for each arc: (one vertical or horizontal segment of an path)
create a start variable
compute a min duration
create a end variable
create an variable interval with those 3 ...
- 2,597
2
votes
Accepted
Parallel scheduling with precedence constraints and variable job length
If you search for literature on job shop scheduling with sequence-dependent setups, I think you will find what you want. As the phrase suggests, sequence-dependent setups refer to lost time and/or ...
- 37.9k
2
votes
Accepted
"Complex" scheduling problem model structure
So, with a great help of Mr. Perron I understood my own assignment!
Basically I was linking my OptionalIntervals to the particular points in time, making it time and memory consuming. I really thought ...
- 51
2
votes
RAM overflow when scheduling 1000+ intervals
A stack overflow does not necessarily mean that you ran out of RAM usually being out of RAM throws a java.lang.OutOfMemoryError: Java heap space. To verify this, ...
- 3,975
2
votes
Accepted
CP-SAT solver doesn't use all space available for scheduling
Once again, the objective does not incentive scheduling tasks. So you rely on the randomness of the multi threaded search
- 2,597
2
votes
Accepted
Team Orienteering Problem with Time Windows infeasible using CP-SAT solver in Google OR-Tool
I enabled logging:
solver.parameters.log_search_progress = True
Unfortunately, nothing jumps out. The model is proven infeasible during presolve.
You should look ...
- 2,597
2
votes
Accepted
What exactly does the AddHint() method in Google OR-Tools' CP-SAT solver do?
The hints are actually wrong and infeasible. A good way to check it is to add the parameter fix_variables_to_their_hinted_value:true to the solver before solving.
...
- 2,597
1
vote
Google-OR Tools: Assignment minimizing overlapping members
The original data mises the team 9,16 (these two do not belong to any team)
The code in OR-TOOLS
Data
...
- 1,275
1
vote
Accepted
Formulating assignment problem with people attributes that need to be balanced per assignment attribute in or-tools, CP-sat
You'd need two optimization variables
Binary $ x_{s,r} = 1$ if student $s$ from set A is matched with row $r$ from set B
Binary $ y_{s,c} = 1$ of student is matched to a class $c$
Derived sets/matrix ...
- 3,343
1
vote
Scheduling optimization, Adding 4 day same shift and 3 day off weekly constraint
Not sure why this question was abandoned but I'll give it a try:
Two vars: binary $x_{e,s,d}=1$ if employee $e$ alloted to shift $s$ on day $d$ & another binary $o_{e,d} = 1$ if off for day $d$ ...
- 3,343
1
vote
Accepted
Google CP-SAT Infeasible ILP for Large Problem Area
So the issue here is that I have overconstrained the model. I am constraining the relationship between out_degree and in_degree while simultaneously constraining the actual value of ...
- 325
1
vote
or-tools: job shop problem never exists not finding additional solutions
Proving optimality is where the NP-Hard part is. A lot of small job-shops are still open (meaning not proven). In your case, you have a maximization objective. You have found a feasible value with ...
- 2,597
1
vote
Accepted
Circuit constraint respecting the order of the next n jobs / jobs on each machine starting at 0
for 1) Look at this literal in the jobshop with setup times. You just need to add:
model.Add(start_of_job == 0).OnlyEnforceIf(start_lit)
For 2) For each color, add ...
- 2,597
1
vote
Parallel scheduling with precedence constraints and variable job length
First of all, if in the problem there is a specific precedence constraint for each job, let's say each job has its specific route, your problem sounds like (...
- 8,450
Only top scored, non community-wiki answers of a minimum length are eligible