Hello World,

I am currently programming a MILP containing routing constraints in C++ solving the problems in CPLEX via Concert Technology, meaning that I have to deal with subtour elimination in the most effective way possible. I have thought of using a Callback to separate the integer subtours and another one for the fractional ones.

The former is just an O(n) check of the elements of the solution to determine the connected components of the solution imposing (global) cuts to prevent any subtour (based on the connected components of the solution) from being regenerated. I am externalizing (lol) the latter one as far more complex using the CVRPSEP library of Pr. Lysgaard, by far the best possibility there is.

My question is, which should be the type of callbacks I should be using for each type of separation?

Intuitively, I think of using a Lazy Constraint Callback for the integer and a User Cut Callback for the interface with the CVRPSEP i.e. the fractional. Is this correct? Could you please elaborate and give the general rationale I should use to determine which callback to use as I find IBM's documentation on this respect rather vague or incomplete.

asked 15 Jun '16, 11:33

Jackobian's gravatar image

Jackobian
235
accept rate: 0%


I'll supplement Ehsan's answer, while agreeing with it. Assuming you do not plan to list them all as ordinary constraints, subtour elimination constraints must be added as lazy constraints. If you use only a user cut callback, CPLEX will incorrectly infer that none of your cuts will ever cut off a feasible integer solution, and as a consequence may do some dual reductions and other modifications to the problem that can lead to an incorrect answer. Also, as Ehsan points out, you can't always be sure a user cut will be checked, so adding only user cuts could result in a solution with subtours slipping past the cuts and being accepted. (I think. Actual workings of CPLEX internals are both really complicated and proprietary information.)

On the other hand, the lazy constraint callback is called only when an integer feasible candidate is found (again, as Ehsan said), so if you only use the lazy constraint callback, you'll miss out on adding some if not all of the fractional cuts. Thus putting them in a user cut callback makes more sense.

There's one more wrinkle. My understanding is that the cuts added in the lazy constraint callback may not be checked during the cut phases of nodes. You're guaranteed they'll block any solution with subtours, but if they have any benefit in tightening the best bound, you may not get that benefit. There's nothing stopping you from adding those cuts both places (lazy constraint callback and user cut callback). It's not really redundant because they end up in separate pools. I'm not sure if it's beneficial, though. Not too long ago, I tried this on a symmetric TSP with random distances, just to see if adding the cuts twice made a difference. (I only used regular subtour cuts, not fractional ones.) In very minimal testing, I didn't see any performance difference. Barring a bug in my code (which I checked fairly carefully), this suggests that the integer subtour constraints didn't tighten the LP relaxations enough to get CPLEX's attention ... or else, contrary to what I've been told by IBMers, globally valid lazy constraints actually do get considered during the cut loop.

link

answered 15 Jun '16, 16:34

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Thank you so much for your answers within a few hours only of my post. Ehsan my main source of inspiration was indeed the Benders' example. I based my first version of the Lazy Constraint Callback on theirs and then modified it to meet my purpose. My intuition was right is just that I needed expert confirmation of that I now I have it. One more time thank you so much to Ehsan and Paul Rubin for your expertise and time!

(15 Jun '16, 16:43) Jackobian

A final question related with the same subject. What about adding valid inequalities...? Would it be better to add them within a User Cut Callback rather than using the addUserCut(), right? Also, would it be a problem if I use a couple of User Cut Callbacks or should I have to make both the fractional separation (via a CVRPSEP linkage) AND the adding of valid inequalities within the same User Cut Callback?

(15 Jun '16, 16:47) Jackobian

I'm not sure about user cut callback v. addUserCut(). If you know all the valid inequalities up front, I'd be tempted to use addUserCut. They'll go in a pool (and be activated only when needed). I would use a cut callback only if there are a large number of valid inequalities and most of them will never be helpful (but you don't know which).

(15 Jun '16, 17:09) Paul Rubin ♦♦
1

As to the last question, you can have only one callback of each type. If you add a user cut callback and then add a second user cut callback, the second one replaces the first. The same holds for adding a second lazy constraint callback, a second heuristic callback, etc. So if you want to add multiple types of user cuts, add them all in a single callback. Note that you do not have to add them all at once. At any given node, your user cut callback will be called repeatedly until it stops coughing up new cuts, at which point CPLEX will move on.

(15 Jun '16, 17:09) Paul Rubin ♦♦

Many KUDOS for your help I have learned a lot today thanks to both of you. Is difficult to find all this specifics so important to our works on the web. CPLEX documentation is vast and generic, narrowing down the info to fit our needs is extremely complex. Thanks for the help, hope the post could also help others facing the same issues I have had.

(15 Jun '16, 20:23) Jackobian

You should use lazy constraint callbacks only if your model is incomplete without them (i.e., a solution not satisfying any of the lazy constraints is not a feasible solution to the original problem). On the other hand, you should use user cut callback only if you want to omit part of the LP relaxation feasible region (i.e., fractional solutions). In this case, your model is still correct even if the you don't apply the user cuts.

Based on your description, you should definitely use the lazy constraint callback for the SECs. Regarding the second set of cuts, I'm not sure what you are exactly separating, but based on your description, it seems that you need the user cut callback.

Source: See here.

link

answered 15 Jun '16, 12:14

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

I know, I read the documentation is just that according to your description and that of the IBM Knowledge Center is like if they were intended to:

Lazy Constraint: Adding on-the-fly some model constraints that weren't added a priori e.g. as there is an exponential number or they are hard to verify. Hence, only the violated ones will be added during the Branch-and-Cut process as a mean to alleviate the CPU burden of enumerating/verifying them all a priori. User Cuts: Valid Inequalities that are meant to reinforce the model bounds but that wouldn't exclude any feasible solution

(15 Jun '16, 12:49) Jackobian

But I have been said that Lazy Constraints are meant to be verified on pure integer solutions versus User Cut Callbacks on fractional solutions (as you mentioned). At the end, which one of these two versions, 1st and/or 2nd comment, is correct?

(15 Jun '16, 12:54) Jackobian
1

Lazy constraint callbacks are invoked only when an integer feasible solution is found. However, according to the documentation, user cut callbacks may be invoked at any part of the solution process (with no guarantee of being invoked when an integer feasible solution is found). So, both answers are correct.

(15 Jun '16, 14:24) Ehsan ♦

You might want to check the bendersatsp example in the example folder of CPLEX. It adds lazy cuts for integer solutions and user cuts for the fractional ones.

(15 Jun '16, 15:48) Ehsan ♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×191
×30
×22
×16
×8

Asked: 15 Jun '16, 11:33

Seen: 1,782 times

Last updated: 15 Jun '16, 20:23

OR-Exchange! Your site for questions, answers, and announcements about operations research.