Or-tools: Which solver should be the fastest among open source ones for binary constraint programming?

[elmuz]

Hi everybody,
I am implementing an optimization algorithm which should solve a constraint programming in the field of multi view tracking. Specifically, this is the paper I am studying.

In this setup we have a graph similar to a min-cost flow graph. However, the problem is formulated as a binary constraint linear programming, in the sense that all the arcs/paths are the variables, which can be taken or not taken (hence a binary problem). We have a set of constraints (e.g. incoming flow must match outgoing one, incoming arcs must be no more than one per node, and so on...).

[Hofmann et al. 2013]

I am doing this in Python using a pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING solver. Then each variable is created as a BoolVar(). By doing the system works fine, I can get the solution I want and I am happy.

However, since in future we could have much bigger graphs I am wonder if I am using the right solver for the problem I am facing. In particular, I want to ask you if in your opinion:

• should GLPK be better/faster than CBC? Is there any other open source solver?
• is MIXED_INTEGER_PROGRAMMING the right solver? Since I only have boolean variables, there may be more reasonable solvers.

Thank you

[lperron]

I would use the CP-SAT solver, with scaling of the double coefficients to
integer (* 1000 for instance).
You can have a look at
https://github.com/google/or-tools/blob/stable/examples/python/bus_driver_scheduling_sat.py
which
gives some modeling tricks.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mar. 27 août 2019 à 13:53, elmuz [e-mail] a écrit :

Hi everybody,
I am implementing an optimization algorithm which should solve a
constraint programming in the field of multi view tracking. Specifically,
this
http://openaccess.thecvf.com/content_cvpr_2013/papers/Hofmann_Hypergraphs_for_Joint_2013_CVPR_paper.pdf
is the paper I am studying.

In this setup we have a graph similar to a min-cost flow graph. However,
the problem is formulated as a binary constraint linear programming, in the
sense that all the arcs/paths are the variables, which can be taken or not
taken (hence a binary problem). We have a set of constraints (e.g. incoming
flow must match outgoing one, incoming arcs must be no more than one per
node, and so on...).

I am doing this in Python using a
pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING solver. Then each variable
is created as a BoolVar(). By doing the system works fine, I can get the
solution I want and I am happy.

However, since in future we could have much bigger graphs I am wonder if I
am using the right solver for the problem I am facing. In particular, I
want to ask you if in your opinion:

• should GLPK be better/faster than CBC? Is there any other open
  source solver?
• is MIXED_INTEGER_PROGRAMMING the right solver? Since I only have
  boolean variables, there may be more reasonable solvers.

Thank you

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1522?email_source=notifications&email_token=ACUPL3J5FXYCFSEYVT4RTF3QGUIUVA5CNFSM4IQDRPS2YY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4HHUFE5Q,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3JL5ZXD6A3SW4NL5B3QGUIUVANCNFSM4IQDRPSQ
.

[lperron]

And GLPK is much work in terms of speed than CBC. But CBC sometimes is wrong.

Please switch to CP-SAT, especially with 8 threads.

[elmuz]

Ok, thank you Laurent. I will try to switch to CP-SAT by following the example you linked.

[elmuz]

I would use the CP-SAT solver, with scaling of the double coefficients to integer (* 1000 for instance).

I didn't get the need of the scaling... can you clarify a bit please?

[lperron]

Change 0.33 x + 0.5 y >= z into 33 x + 50 y >= 100z.

Le mar. 27 août 2019 à 18:04, elmuz [e-mail] a écrit :

I would use the CP-SAT solver, with scaling of the double coefficients to
integer (* 1000 for instance).
I didn't get the need of the scaling... can you clarify a bit please?

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1522?email_source=notifications&email_token=ACUPL3O3X5OHBEFMWVD52LDQGVF67A5CNFSM4IQDRPS2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD5IIELA#issuecomment-525369900,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3LUVGU3KBQRM7RH7Q3QGVF67ANCNFSM4IQDRPSQ
.

[elmuz]

Change 0.33 x + 0.5 y >= z into 33 x + 50 y >= 100z.

Ah ok. Actually I already do not have any fractional constraint... so I am fine.

[elmuz]

Hi @lperron,
in the end I profiled CBC, CLP, GLPK and CP-SAT in order to find which could be better in our scenario. If you are interested in this I can give you more details on the problem formulation. However, I give you here some excerpts of what I found. The test was to solve a graph of the kind of the paper above given the same input scene and same parameters set.

While CLP, GLPK and CBC are drop-in replaceable one of the other, CP-SAT has quite different APIs, therefore the syntax among the two tests unavoidable changed a bit.

These are the general steps:
1) Create variables
2) Create constraints
3) Solve the graph

1) VARIABLES CREATION

In CBC/CLP/GLPK approach I did something like:

...
var = self.solver.BoolVar(name=name)
self._or_variables['reconstruction_cost'][reco_id] = var
self._objective.SetCoefficient(var, coeff)
...

CP-SAT counterpart is a little bit different (note the integer rounding)

...
var = self.model.NewBoolVar(name=name)
self._or_variables['reconstruction_cost'][reco_id] = var
self._objective_vars.append(var)
self._objective_coeff.append(int(coeff * 1e4))
self.model.Minimize(cp_model.LinearExpr.ScalProd(self._objective_vars, self._objective_coeff))
...

Profiling this function brings the following results

• CBC/CLP/GLPK: 73568 0.018 0.000 0.191 0.000 pywraplp.py:173(BoolVar)
• CBC/CLP/GLPK: 73568 0.020 0.000 0.059 0.000 pywraplp.py:362(SetCoefficient)
• CP-SAT: 73568 0.140 0.000 2.549 0.000 cp_model.py:729(NewBoolVar)
• CP-SAT: 1 0.001 0.001 0.950 0.950 cp_model.py:1466(Minimize)

2) CONSTRAINTS CREATION

In CBC/CLP/GLPK I created them more or less like:

...
constraint_out = self.solver.Constraint(0, 0)
for many times:
    var = get_variable(...)
    constraint_out.SetCoefficient(var, 1)
...

while in CP-SAT is something like:

...
self.model.Add(R_node - exit_edge - sum(out_link_edges) == 0)
... # or sometimes
self.model.AddLinearConstraint(sum(related_nodes), 0, 1)
...

Profiling these functions I get the following results:

• CBC/CLP/GLPK: 1931 0.001 0.000 0.008 0.000 pywraplp.py:185(Constraint)
• CBC/CLP/GLPK: 147854 0.033 0.000 0.089 0.000 pywraplp.py:486(SetCoefficient)
• CP-SAT: 1810 0.006 0.000 2.593 0.001 cp_model.py:769(Add)
• CP-SAT: 121 0.000 0.000 0.051 0.000 cp_model.py:739(AddLinearConstraint)

3) GRAPH SOLUTION

Here is quite similar. In CBC/CLP/GLPK:

self.solver.Solve()

while in CP-SAT:

self.solver.parameters.num_search_workers = 8
status = self.solver.Solve(self.model)

And also here performances respect the same trend:

• CLP: 1 0.000 0.000 0.720 0.720 pywraplp.py:197(Solve)
• CBC: 1 0.000 0.000 2.739 2.739 graph.py:660(solve)
• GLPK: 1 0.000 0.000 6.697 6.697 pywraplp.py:197(Solve)
• CP-SAT: 1 0.000 0.000 9.958 9.958 cp_model.py:1575(Solve)

I am pretty sure that results are the same, regardless the solver I used. In fact I checked the objective value, which is -502.118878 for CLP, GLPK and CBC, while -5021190 for CP-SAT (there is a subtle difference due to the 1e4 scaling and rounding).

Do you think that these results make sense? Do you feel I can add some parameters to CP-SAT to make it faster the way you suggested? Do you think I built it from sources in a bad way?

Thank you

[elmuz]

UPDATE: it turned out that moving away from constraint programming solvers in favor of linear programming solvers improved a lot my results in terms of speed.
Even inside the same family GLPK_MIXED_INTEGERS is slower than GLPK_LINEAR (same story for CBC vs CLP)
So I can say that finally GLOP is the fastest for my scenario, which takes only 0.456 seconds for the same graph solution.

[lperron]

But GLPK linear, CLP and GLOP are not solving the same problem as CBC/GLPK
MIP, or CP-SAT.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le lun. 2 sept. 2019 à 15:42, elmuz [e-mail] a écrit :

UPDATE: it turned out that moving away from constraint programming solvers
in favor of linear programming solvers improved a lot my results in terms
of speed.
Even inside the same family GLPK_MIXED_INTEGERS is slower than GLPK_LINEAR
(same story for CBC vs CLP)
So I can say that finally GLOP is the fastest for my scenario, which takes
only 0.456 seconds for the same graph solution.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1522?email_source=notifications&email_token=ACUPL3LNWNWD2VCUST5FFF3QHUJ2ZA5CNFSM4IQDRPS2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD5V3LYY#issuecomment-527152611,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3MXOQNIQRONCQ4BH7TQHUJ2ZANCNFSM4IQDRPSQ
.

[elmuz]

But GLPK linear, CLP and GLOP are not solving the same problem as CBC/GLPK
MIP, or CP-SAT.

Sure, but I think that maybe I don't need CP family and linear is fine since according to the doc I satisfy the three requirements:

1. A linear objective function. In fact the objective here is a sum over _i_ of _cost_i_ * _var_i_, where variables are binary (take or not take the path).
2. Linear constraints that can be equalities or inequalities. And in fact they are... constraints like incoming flow must match outgoing flow is in the form of sum(in_vars) == sum(out_vars).
3. Bounds on variables that can be positive, negative, finite or infinite. Specifically, they are all binary.

For what I understood the other solvers can solve a broader family of problems (so they produce same optimal results also here) but they are slower. Right?

[lperron]

But with glop, and other linear solvers, the binary will take any value
between 0 and 1, not just 0 or 1.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le lun. 2 sept. 2019 à 16:49, elmuz [e-mail] a écrit :

But GLPK linear, CLP and GLOP are not solving the same problem as CBC/GLPK
MIP, or CP-SAT.

Sure, but I think that maybe I don't need CP family and linear is fine
since according to the doc
https://developers.google.com/optimization/reference/linear_solver/linear_solver/
I satisfy the three requirements:

1. A linear objective function. In fact the objective here is a sum
   over i of cost_i * var_i, where variables are binary (take or
   not take the path).
2. Linear constraints that can be equalities or inequalities. And in
   fact they are... constraints like incoming flow must match outgoing flow is
   in the form of sum(in_vars) == sum(out_vars).
3. Bounds on variables that can be positive, negative, finite or
   infinite. Specifically, they are all binary.

For what I understood the other solvers can solve a broader family of
problems (so they produce same optimal results also here) but they are
slower. Right?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1522?email_source=notifications&email_token=ACUPL3JF3EG7PVTLW6V2CFLQHURWDA5CNFSM4IQDRPS2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD5WAQUQ#issuecomment-527173714,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3PGWBR3AHSOOEQWHODQHURWDANCNFSM4IQDRPSQ
.

[elmuz]

But with glop, and other linear solvers, the binary will take any value
between 0 and 1, not just 0 or 1.

...so you are saying they do not take into account that I specify their boolean nature with var = self.model.NewBoolVar(name=name)?

[lperron]

yes, they are linear programming solvers, not mixed integer programming
solvers.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le lun. 2 sept. 2019 à 18:02, elmuz [e-mail] a écrit :

But with glop, and other linear solvers, the binary will take any value
between 0 and 1, not just 0 or 1.

...so you are saying they do not take into account that I specify their
boolean nature with var = self.model.NewBoolVar(name=name)?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1522?email_source=notifications&email_token=ACUPL3K67L4G6LU73VAGXQ3QHU2HTA5CNFSM4IQDRPS2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD5WFNUQ#issuecomment-527193810,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3IODXAMJ5D5CWIEAATQHU2HTANCNFSM4IQDRPSQ
.

[elmuz]

Ok, got it. Now I know that I have to stick on CBC, GLPK (MIP) or CP-SAT. Among the 3 solvers, CBC is the one which performs better.

Last question (I promise). Do you have some idea on why CP-SAT is so slower than CBC in variables creation, constraint creation and graph resolution? We're talking about 5 times slower than CBC. Do you think there some tweaks I can apply? Do you have some guidelines to follow (even when compiling maybe)?
Thank you

[lperron]

Modeling is indeed slower for the CP-SAT, especially since the modeling
part is pure python, instead of a quick SWIG interface on top of C++.
But it is rarely a problem in my opinion.

To improve solving speed, you can add a new parameter:
num_search_workers:8, usually it helps a lot.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mar. 3 sept. 2019 à 15:34, elmuz [e-mail] a écrit :

Ok, got it. Now I know that I have to stick on CBC, GLPK (MIP) or CP-SAT.
Among the 3 solvers, CBC is the one which performs better.

Last question (I promise). Do you have some idea on why CP-SAT is so
slower than CBC in variables creation, constraint creation and graph
resolution? We're talking about 5 times slower than CBC. Do you think there
some tweaks I can apply? Do you have some guidelines to follow (even when
compiling maybe)?
Thank you

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1522?email_source=notifications&email_token=ACUPL3KS2GFKPAWFZ46BC6LQHZRWXA5CNFSM4IQDRPS2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD5YGS5I#issuecomment-527460725,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3KLONV2SU2ORTULFEDQHZRWXANCNFSM4IQDRPSQ
.