Cut generators in CPModelProto

[TheCoolRob]

Hi

Following on from #666 - I found the reason why I wasn't using the CPModelProto. I've got some custom cutting planes I'm implementing over a SAT model and using the CutGenerator callbacks.

I wasn't able to find an interface on the CPModelProto that allows for adding a cut-callback. I would prefer to work at the CPModel level rather than SAT (as per Laurents' suggestion) but perhaps I'm just missing the part of the API that gives the appropriate functionality?

It could be that it's not available at that level - passing a pointer to a callback over the proto model seems like a bad idea and something that probably wouldn't be supported. I suppose this issue is simply then for confirmation that this is the case or not.

Thanks

[lperron]

I would like to know more. As we are looking at MIP cuts and presolve in the context of the CP-SAT solver, this is an interesting topic. Which cuts are you adding? Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00 Le mar. 30 oct. 2018 à 09:31, TheCoolRob <notifications@github.com> a écrit :

…

Hi Following on from #666 <#666> - I found the reason why I wasn't using the CPModelProto. I've got some custom cutting planes I'm implementing over a SAT model and using the CutGenerator callbacks. I wasn't able to find an interface on the CPModelProto that allows for adding a cut-callback. I would prefer to work at the CPModel level rather than SAT (as per Laurents' suggestion) but perhaps I'm just missing the part of the API that gives the appropriate functionality? It could be that it's not available at that level - passing a pointer to a callback over the proto model seems like a bad idea and something that probably wouldn't be supported. I suppose this issue is simply then for confirmation that this is the case or not. Thanks — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#912>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AKj17UMUx_8daiyrDs_wViLDfU7RHi5jks5uqA5ogaJpZM4YBaXJ> .

[TheCoolRob]

Hi Laurent.
So I was using the SAT cut generator layer that was available and extended your circuit cuts that were written.

1. The SAT cut gen only permitted cutting the root node once. It was relatively straight forward to modify your subtour elimination constraints (sec's) to run recursively until the min-cut returns cuts that already exist. This typically creates a tighter model for circuits - I got a nice improvement from that but forgot to push the change on the public repo (I wasn't sure how it would perform in all situations).
2. I added comb, blossom and connect cuts - but because of the representation issues in SAT (complete graph, directed edges) I moved to a two-commodity flow representation in MIP which gave me pretty tight bounds for the problem size I was tackling (mapping the undirected edge formulation cuts into the commodity flow representation).
3. I wanted to scale it up and use SAT for local search under the MIP but realised that without a cut-callback on the CPModelProto I wouldn't be able to generate cuts with a common definition of the cuts I'm using at the moment. It produced an itch that resulted in this github issue..
   Thanks

[lperron]

Nice! Do you use the two commodity flow as a relaxation of the TSP? The current flow with the cp_model API is that the constraint exists in the proto. When parsing and loading the model, we extract it in the CP-SAT layer, and in the LP. Thus, improvements to the circuit falls directly into this schema. Are comb, blossom, connect cuts related to the circuit constraint too? Do you have a reference for them? Thanks Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00 Le mar. 6 nov. 2018 à 09:27, TheCoolRob <notifications@github.com> a écrit :

…

Hi Laurent. So I was using the SAT cut generator layer that was available and extended your circuit cuts that were written. 1. The SAT cut gen only permitted cutting the root node once. It was relatively straight forward to modify your subtour elimination constraints (sec's) to run recursively until the min-cut returns cuts that already exist. This typically creates a tighter model for circuits - I got a nice improvement from that but forgot to push the change on the public repo (I wasn't sure how it would perform in all situations). 2. I added comb, blossom and connect cuts - but because of the representation issues in SAT (complete graph, directed edges) I moved to a two-commodity flow representation in MIP which gave me pretty tight bounds for the problem size I was tackling (mapping the undirected edge formulation cuts into the commodity flow representation). 3. I wanted to scale it up and use SAT for local search under the MIP but realised that without a cut-callback on the CPModelProto I wouldn't be able to generate cuts with a common definition of the cuts I'm using at the moment. It produced an itch that resulted in this github issue.. Thanks — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#912 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AKj17XFDC0Uol0UrS4UyVuxFWxeVGl5pks5usUfvgaJpZM4YBaXJ> .

[TheCoolRob]

This is a good reference for the cuts I've described related to the TSP:
https://www.math.uwaterloo.ca/~bico/papers/dfj_mathprog.pdf

I'm using a relaxed version of the two-commodity flow, but with column generation for the edges (my comment about not needing a complete graph, makes the models much more compact). There several other cuts that are specific to the problem outside of the circuit feature (like capacity cuts and precedence cuts) as it's effectively a pickup and dropoff problem on top of the standard TSP. You can have both models side by side (flow variables which induce binary variables in the circuit representation). This gives you the best of both worlds, the tight bound from the DFJ representation and cumul dimension cuts from the flow model. Requires a bit of effort to keep them in sync but it's a good approach - as long as you have a cut callback at every node ;-)

Since we're on the topic of model representations - I saw you made a comment on the forums regarding upcoming changes to the routing library (re it's deprecation). I've seen some hints in the code that point to a more precise approach that you may be planning. How drastic are the changes you're planning and do you have provisional timeline for the release?

[Mizux]

For routing update, once we migrate our github source code to use the abseil-cpp third party dependency, then we will also be able to get in sync with our internal source code ~1 year ahead concerning the routing library.

You can follow advancement at #871 or looking at the Work In Progress abseil branch directly.
note: commit contains both abseil-cpp migration and backport of the "new" routing library

[lperron]

Hi, thanks for the pointers. So you are trying to solve a PDP with capacity (and maybe time windows) exactly using SAT. I like that. The routing library is not under maintenance, only the original CP code will only be extended to support the routing part. I strongly recommend persons not using the routing library to use the CP-SAT solver. The new API is visible in the abseil branch of or-tools on github: Here is the ported example: https://github.com/google/or-tools/blob/abseil/examples/cpp/tsp.cc 3 notable changes: - we do create an index manager that sync nodes in the routing graph and indices in the underlying model. - distance and capacity callbacks are registered on the routing model, and we use their index (returned by the register method) in dimension, costs... instead of the callback. - in non C++ languages, callbacks inherits from IntIntToLong instead of NodeEvaluator2 I ported all examples to the new API in very little time, and the benefits in term of code (no more mixing node and indices) are really worth it. Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00 Le mar. 6 nov. 2018 à 10:56, TheCoolRob <notifications@github.com> a écrit :

…

This is a good reference for the cuts I've described related to the TSP: https://www.math.uwaterloo.ca/~bico/papers/dfj_mathprog.pdf I'm using a relaxed version of the two-commodity flow, but with column generated for the edges (my comment about not needing a complete graph, makes the models much more compact). There several other cuts that are specific to the problem outside of the circuit feature (like capacity cuts and precedence cuts) as it's effectively a pickup and dropoff problem on top of the standard TSP. You can have both models side by side (flow variables which induce binary variables in the circuit representation). This gives you the best of both worlds, the tight bound from the DFJ representation and cumul dimension cuts from the flow model. Requires a bit of effort to keep them in sync but it's a good approach - as long as you have a cut callback at every node ;-) Since we're on the topic of model representations - I saw you made a comment on the forums regarding upcoming changes to the routing library (re it's deprecation). I've seen some hints in the code that point to a more precise approach that you may be planning. How drastic are the changes you're planning and do you have provisional timeline for the release? — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#912 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AKj17audFbuQnjuT-jFPVGyFjxlf7ByQks5usVzPgaJpZM4YBaXJ> .

[lperron]

Can you share the code? We will reimplement it, and as David works at Google, we can ask questions directly, but it will guide us. Thanks Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00 Le mar. 6 nov. 2018 à 11:08, Laurent Perron <lperron@google.com> a écrit :

…

Hi, thanks for the pointers. So you are trying to solve a PDP with capacity (and maybe time windows) exactly using SAT. I like that. The routing library is not under maintenance, only the original CP code will only be extended to support the routing part. I strongly recommend persons not using the routing library to use the CP-SAT solver. The new API is visible in the abseil branch of or-tools on github: Here is the ported example: https://github.com/google/or-tools/blob/abseil/examples/cpp/tsp.cc 3 notable changes: - we do create an index manager that sync nodes in the routing graph and indices in the underlying model. - distance and capacity callbacks are registered on the routing model, and we use their index (returned by the register method) in dimension, costs... instead of the callback. - in non C++ languages, callbacks inherits from IntIntToLong instead of NodeEvaluator2 I ported all examples to the new API in very little time, and the benefits in term of code (no more mixing node and indices) are really worth it. Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le mar. 6 nov. 2018 à 10:56, TheCoolRob ***@***.***> a écrit : > This is a good reference for the cuts I've described related to the TSP: > https://www.math.uwaterloo.ca/~bico/papers/dfj_mathprog.pdf > > I'm using a relaxed version of the two-commodity flow, but with column > generated for the edges (my comment about not needing a complete graph, > makes the models much more compact). There several other cuts that are > specific to the problem outside of the circuit feature (like capacity cuts > and precedence cuts) as it's effectively a pickup and dropoff problem on > top of the standard TSP. You can have both models side by side (flow > variables which induce binary variables in the circuit representation). > This gives you the best of both worlds, the tight bound from the DFJ > representation and cumul dimension cuts from the flow model. Requires a bit > of effort to keep them in sync but it's a good approach - as long as you > have a cut callback at every node ;-) > > Since we're on the topic of model representations - I saw you made a > comment on the forums regarding upcoming changes to the routing library (re > it's deprecation). I've seen some hints in the code that point to a more > precise approach that you may be planning. How drastic are the changes > you're planning and do you have provisional timeline for the release? > > — > You are receiving this because you commented. > Reply to this email directly, view it on GitHub > <#912 (comment)>, > or mute the thread > <https://github.com/notifications/unsubscribe-auth/AKj17audFbuQnjuT-jFPVGyFjxlf7ByQks5usVzPgaJpZM4YBaXJ> > . >

[TheCoolRob]

@Mizux thanks for the heads up on the branch - does that mean that branch is currently up to date with the internal state of the routing solver or that it be updated once the abseil move is complete?

@lperron thanks for the link to the sample. Moving away from those two layers of indexes will mean a 50% reduction in questions on the forum 🥇 . I suppose my question was more about the structure of the way in which the solver works - specifically, pickup and dropoff models (from my testing at any rate) don't seem to produce good solutions. Some of the seeding mechanisms just aren't designed to handle the dependencies between orders and the local search heuristics chain together in a really inefficient way (mostly O(n^2) local search operators for pairs). This isn't a fair complaint, because the routing layer does a lot really well, but it felt like perhaps if you were tackling some restructuring of the design then I was hoping this would be on the list?

Lastly on the code - I can't share my implementation unfortunately (its a commercial implementation) - but luck is on your side because you can ask David if you can port the concorde procedures (the canonical implementation referenced in that paper) into the open source world (currently it's only available under for academic usage). If he would prefer that you re-write them I'd be happy to help contribute in this regard if/when you get around to it as there is no publicly available unrestricted-use license for those cut procedures (not to my knowledge, happy to be corrected if wrong).

[Mizux]

@TheCoolRob Should be in sync modulo 2 weeks I would say....

[lperron]

A lot of work has been done on the routing library to improve performance of the local search, and the first solution heuristics w.r.t. extra constraints like PDP. I would expect this version to be much better. About code sharing, I understand. If there are anything you can share, please send it to me. Thanks Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00 Le mar. 6 nov. 2018 à 12:45, Mizux <notifications@github.com> a écrit :

…

@TheCoolRob <https://github.com/TheCoolRob> Should be in sync modulo 2 weeks I would say.... — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#912 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AKj17bGwMYKEI1vh1JGsvhSrrJI2MkyLks5usXY9gaJpZM4YBaXJ> .

[TheCoolRob]

Thanks @lperron. Looking forward to testing the new release when it's available with these changes.

Looping back to the original topic - a cut-call back that can be specified through the CPModelProto layer - does this idea make sense in your design for the CP-SAT layer or is this a different kind of animal?

[lperron]

Interesting idea. We need to think of the architecture. In the meantime, you could build from source and modify the source locally. If you have code you can share, we can integrate it/reimplement it, or add an API for callbacks.

…

--Laurent Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00 Le mar. 6 nov. 2018 à 14:57, TheCoolRob <notifications@github.com> a écrit :

Thanks @lperron <https://github.com/lperron>. Looking forward to testing the new release when it's available with these changes. Looping back to the original topic - a cut-call back that can be specified through the CPModelProto layer - does this idea make sense in your design for the CP-SAT layer or is this a different kind of animal? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#912 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AKj17bVwwiPmXarVyYNVh0SCOrogULzUks5usZVWgaJpZM4YBaXJ> .

[TheCoolRob]

I suspect callback for the api would be quite simple since a cut is only a function of an incumbent. So a solution vector in, vector of inequalities out. That way you're also decoupled from my situation of having 2 different representations of the same model (i.e. the user is responsible for the translation).

I agree that some working code is a sensible way forward. I'll put together a use-case and perhaps it will be clearer how to extract it out into something that can be used generically.