10 votes
Accepted

Is there an open-source equivalent to LocalSolver?

The simple answer is no. While I haven't used LocalSolver myself, I sell a solver that solves similar types of problems (Octeract Engine) so I get asked this type of question a lot for my own solver. ...
Nikos Kazazakis's user avatar
9 votes
Accepted

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/...
Stradivari's user avatar
  • 1,414
8 votes
Accepted

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

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 ...
Laurent Perron's user avatar
8 votes

Is there an open-source equivalent to LocalSolver?

To our knowledge, there is no equivalent of Hexaly (formerly LocalSolver) in open source and no equivalent of Hexaly in the market. Hexaly's uniqueness, and thus innovation, comes from the two key ...
Hexaly's user avatar
  • 2,976
7 votes

Help modeling grid placement problem

Let $x_{ij}^p$ be a binary variable that indicates if user $i\in I$ is assigned to access point $j \in J = \{1,...,M\}$ located in position $p\in P$, and let $z_{j}^p$ be a binary variable that ...
Kuifje's user avatar
  • 13.3k
7 votes

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

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 ...
prubin's user avatar
  • 39.1k
7 votes
Accepted

Constraint Programming OR-Tools finding Matrix Combinations

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: ...
Stradivari's user avatar
  • 1,414
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 ...
Laurent Perron's user avatar
6 votes

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

min, max, functions do not work in OR-Tools, you should use AddMinEquality instead: ...
Stradivari's user avatar
  • 1,414
6 votes
Accepted

Enforce Changeover Constraints in Production Scheduling

If you let $x_{ij} $ be a binary variable equalling 1 iff job $i$ comes just before job $j$, and continuous variables $u_i$ be the start time of job $i$, then you may model your constraints using MTZ ...
Sune's user avatar
  • 6,497
6 votes

Maximize the minimal distance between true variables in a list

You can maximize $z$ subject to linear big-M constraints $$z - (j-i) \le M_{ij} (2 - x_i - x_j),$$ where $M_{ij} = n-(j-i)$. Each such constraint enforces the logical implication $(x_i \land x_j) \...
RobPratt's user avatar
  • 32k
6 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()
Laurent Perron's user avatar
5 votes

Why most of constraint solvers do not support optional intervals?

I'm afraid that the answer is simply that not enough people use/request that feature from solver developers. The same is true in our company's case as well - in the 4 years since I started Octeract, ...
Nikos Kazazakis's user avatar
5 votes

How to tackle large nurse scheduling problem?

There are many approaches to formulate nurse scheduling model. In practice, MIPs and some heuristics have frequently been used. AFAIK, for large scale MIPs, column generation technique can be applied. ...
A.Omidi's user avatar
  • 8,882
5 votes
Accepted

Maximize the minimal distance between true variables in a list

I have no idea (i) whether the following can be encoded in a CP solver and (ii) how efficient it would be. On the pro side, it only requires a linear number of variables and constraints. Say you have $...
mtanneau's user avatar
  • 4,173
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 ...
Laurent Perron's user avatar
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 ...
ooo's user avatar
  • 119
4 votes
Accepted

How to know which constraint in CP-SAT did not meet the feasibility gap

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 ...
Stradivari's user avatar
  • 1,414
4 votes

ValidateModel or tools in c++ and proto problems

CpModelProto is a protobuf representation of your model in ortools. You create it by using the CpModelBuilder class (your ...
Stradivari's user avatar
  • 1,414
4 votes
Accepted

Why most of constraint solvers do not support optional intervals?

As you say, the specific modelling primitives you mention that CP Optimizer introduced are not very common in other solvers. A big reason for this is that the backing infrastructure that makes it work ...
Zayenz's user avatar
  • 196
4 votes
Accepted

Set value based on if other variable is in specific range

Please read https://github.com/google/or-tools/blob/stable/ortools/sat/doc/channeling.md OnlyEnforceIf() only accept one or more Boolean literals. So for the first ...
Laurent Perron's user avatar
4 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....
Laurent Perron's user avatar
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.
Laurent Perron's user avatar
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 ...
Zayenz's user avatar
  • 196
4 votes

CP-SAT: Workarounds for OnlyEnforceIf with Linear Expressions

This is a recurring question, and I have written a page of doc to solve it: https://github.com/google/or-tools/blob/stable/ortools/sat/docs/channeling.md The idea is to create a Boolean variable that ...
Laurent Perron's user avatar
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: ...
Laurent Perron's user avatar
3 votes
Accepted

Nurse Rostering Code with custom constraints Not Working

I didn't added lower bound for shift requirements so here's working code: ...
user3237357's user avatar
3 votes
Accepted

Solver Recommendation : Discrete Variables and Quadratic Constraints

This is by no means a complete list, but this is some of the best stuff for this mathematical structure: Open source: Couenne, SCIP Commercial and free: Octeract Engine (our own solver). Commercial ...
Nikos Kazazakis's user avatar
3 votes

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

Manually create groups, if you know which groups make more sense than others then you don't need to define every possible permutation. If you are less certain you can use a script to enumerate the ...
Rob's user avatar
  • 2,110
3 votes
Accepted

Multiple Knapsacks with splitting

This is not too big of a leap from the basic Knapsack problem and can be handled with only 3 constraints for the bin size, all-or-nothing, and the prohibited placements. Below is an example that I ...
AirSquid's user avatar
  • 252

Only top scored, non community-wiki answers of a minimum length are eligible