12
See answer on https://github.com/google/or-tools/issues/1444
This is not implemented.
I welcome pull requests. :-)
You can have a look at the code in the gurobi or Scip interface files.
9
Thanks to @Laurent Perron for their answer - I've tried modifying the code as follows, and it appears to work fine:
from __future__ import print_function
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def create_data_model():
"""Stores the data for the problem."""
data = {}
data['...
9
Why quadratic?
just use a larger (linear) weight for tasks assigned to worker 1.
9
In addition to the answer from @Mehdi... I've recently started to work with OR-tools and find it very nice for prototyping. The Python interface allowed me to produce a first version of my model within one day. The times to obtain a first solution seem good - it performed very favorable in the MiniZinc Challenge 2018.
The main struggles/disadvantages that I'...
8
I used OR-tools for TSP and VRP. These are my observations:
1- It provides a good quality solution in reasonable time. However, it is not the optimal solution and in some cases you can find much better solutions easily.
2- The implantation in Python is straightforward.
3- It is not flexible. You can not add many extensions to the problem, just basic ...
8
What you want is:
AddLessOrEqual(LinearExpr(starts[j]).AddConstant(durations[j]), starts[succ[j][s]])
You might also want to take a look at the examples (ending with _sat.cc) to be more familiar with the c++ methods.
https://github.com/google/or-tools/tree/master/examples/cpp
8
Time to solve (to proven optimality) is certainly a good choice. I don't know that I would be excited about number of conflicts.
You could look at the ratio of objective value on that problem instance to the best known value for that problem instance (across all model variants), given a time limit. A similar ratio of best bounds to best overall bound (by ...
8
Introduce a binary variable $x_{d,s}$ and change the right hand side to $1+2x_{d,s}$.
7
CP-SAT ortools - Is there any complete list of possible/available StringParameters for the CpSolver?
As many things in Google, OR-Tools uses Protocol Buffers to serialize data.
Here's a list of all .proto files in OR-Tools: https://github.com/google/or-tools/search?l=Protocol+Buffer
The parameters for the CP-SAT solver are listed in the sat_parameters.proto file:
https://github.com/google/or-tools/blob/stable/ortools/sat/sat_parameters.proto
7
If you look at OR-Tools: CumulativeConstraint, AddCumulative takes a variable as argument, so if it is constant, create a variable with a fixed domain.
It returns a CumulativeConstraint with a method to add (IntervalVar, DemandVar) pairs to the constraint. See OR-Tools 7.4: C++ Reference (CumulativeConstraint).
Note that the rcpcp solver is implemented in ...
7
In many of its solvers, OR-Tools only accept integers (see Laurent Perron's comment below).
Something like that:
model.Maximize( int(round( sum(np.exp(-delta*s[j])*pro[j] for j in range(n)) )) )
will probably work (I haven't tried), but you might lose some precision. The usual solution is to multiply each value by a power of 10 and divide the result ...
7
Workforce scheduling describes many different problems.
The best technology for those is IMO CP-SAT (see the introduction, the reference manual in the CP-SAT sections and a set of recipes).
A popular concert is shift scheduling.
This example has gained a lot of traction in the past. It shows how to implement useful constraints on the problem that ...
7
You get the same result $2^{\operatorname{len}(y)}$ times because $y_i$ is not constrained.
You can see that by adding this to your callback:
print("y:", [self.Value(y) for y in self._y.values()])
x: 1 for x(1,0) and matrix value:5
x: 1 for x(0,1) and matrix value:1
x: 1 for x(1,2) and matrix value:1
y: [0, 0, 0]
x: 1 for x(1,0) and matrix value:5
x: 1 ...
6
(already answered on S.O. )
You should have a look at Jobshop scheduling example with transitions
In particular, it maintains a graph of direct successor between tasks on the same machine.
6
I notice you are using FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC. If this name does what it suggests, then it's probably a greedy strategy that chooses between distance 1, 1 and so on.
The clue is that you're using a strategy that does not guarantee optimal solutions. The structure also suggests that a certain random seed is used; there is an iteration ...
6
Crossposted from: Stack Overflow
The idea is to create another dimension ('visit') that is incremented by 1 on each visit.
Then use SetCumulVarSoftUpperBound on the cumul variable of that dimension at the end of each route.
5
There are some linear possibilities, depending on exactly what your goal is. They all require adding some binary variables to what is already a discrete optimization problem. One is to maximize the spread between the largest and smallest assigned loads (or maybe largest and smallest nonzero loads). That may result in one large load, one minimal (zero or one ...
5
To create an intermediate boolean that is true iff s[j] == t you just have to create 2 constraints:
cp_model.AddEquality(s[j], t).OnlyEnforceIf(b);
cp_model.AddNotEqual(s[j], t).OnlyEnforceIf(Not(b));
The problem with this line:
cp_model.AddEquality(b, starts[j]==actual_t);
is that starts[j]==actual_t "always" evaluates to false.
To learn more about ...
5
If I understand your problem correctly, you have a standard CVRP and a second (soft) objective.
You are therefore in the wonderful world of multi-objective optimization.
Typically what you do is try to turn this problem into a problem with a well defined optimal solution. There are some ways to do this: lexicographical ordering of objectives (Cplex calls ...
5
If your linear program does not have an optimal solution one of three things might be the case:
The solver didn't find the optimal solution, even though it exists. This might be due to runtime or storage space limitations. However this should rarely be the problem, unless you have huge LPs.
There is no optimal solution, because the problem is unbounded and ...
5
A TSP with a fixed starting point and no return to start, can be solved as an ordinary TSP with all the in-going arcs to the starting point having a cost of zero. That way the return to the starting point is "for free" and the TSP solver only focuses on the remaining part of the tour, giving you an optimal "open TSP".
4
CP solvers can find optimal solutions (given enough time and memory). Essentially, like the "bound" part of branch-and-bound, each time you find a feasible solution you redefine feasibility to include "better than the incumbent".
Whether you would be better off with a MIP approach or a CP approach depends a lot on the specific nature of your problem (and ...
4
CpModelProto is a protobuf representation of your model in ortools.
You create it by using the CpModelBuilder class (your cp_model), and calling its Build() method, the SolveCpModel function that you are using actually also takes a CpModelProto as its first argument.
4
In the Python API there is a pretty good docstring of what an OptionalIntervalVar is:
An optional interval variable is a constraint, that is itself used in other
constraints like NoOverlap. This constraint is protected by an is_present
literal that indicates if it is active or not.
Internally, it ensures that is_present implies start + size == ...
4
CP-SAT is a full fledged (non-mixed) integer programming solver (linear relaxation, presolve, cuts, branching heuristics). It is geared towards optimization, and is actually not very good at enumerating all feasible solution, compared to a tree search based CP solver.
It is also a CP solver, and a damn good one, and a SAT solver.
In our tests, it is on ...
4
The answer is yes. Is it worthwhile ? it depends.
If you just want to have two persons visit the same virtual place (2 duplicated nodes) at the same time, you can force the time cumul var to be equal when using the routing library.
This will probably more efficient than the CP-SAT VRP code as the routing library is highly tuned.
If you want more complex ...
4
min, max, functions do not work in OR-Tools, you should use AddMinEquality instead:
...
workload = []
for j in range(num_of_teacher):
tmp = model.NewIntVar(0, num_of_students, "")
model.Add(tmp == sum([x[i][j] for i in range(num_of_students)]))
workload.append(tmp)
...
obj = model.NewIntVar(0, num_of_students, "")
model....
4
There are no good answers to that question. It depends on the model, on the complexity of the problem. My gut reaction is that OR-Tools routinely solves to optimality bigger problems, but some much smaller problems can be impossible to prove, or even to find a feasible solution.
OR-Tools is a good CP solver (it won all 4 gold medals of the last 2 minizinc ...
4
Here's one way:
$$x\not=i \lor y\not=j \text{ for } k\in\{1,2,3,4\}, i\in S_k, j\in S_k$$
Here's another way, using ELEMENT constraints, as suggested by @prubin. The following is SAS code, but maybe OR-Tools has something similar.
proc optmodel;
set S {k in 1..4} =
if k = 1 then 1..249
else if k = 2 then 250..499
else if k = 3 ...
4
Not yet, see https://github.com/google/or-tools/issues/973
For debugging I would recommend you to divide your constraints into groups so you can activate/deactivate some of them to pin down the infeasibility
Only top voted, non community-wiki answers of a minimum length are eligible
