I'm working on a series of hard combinatorial optimization problems, the constraints of which can be described using Lazy Cuts (i.e. inequalities generated "on the fly" as needed). I also can generate user cuts based on specific combinatorial reasoning. At the end of the run I report how many of each (lazy or user) I generated, and cplex reports the number that it actually used. On the most challenging problems I find that it only uses a small fraction. For example on one run I generated 7565 user cuts, and 302 lazy cuts, but cplex only used 364 (I assume that it used all of the lazy cuts, since they're requirements of the problem, so this leaves only 62 out of 7565 that were useful). I know that cplex has some sort of scoring mechanism for cuts in the cut pool, and only uses the ones that score well enough. Does anyone know any more specifics about it? It would be really useful if I could get cplex to report which of the cuts it actually used, so that I might discern something about them and try to generate only those that are useful. Right now I do have any option in my code to generate only those cuts that are deep enough: if the potential cut has the form \(a^T \cdot x \le b\) I'll only generate it if \( ( a^T \cdot x^ * - b ) / \parallel a \parallel \gt \delta \) for some \(\delta \gt 0\) which is a parameter (and \(x^*\) is the current LP optimum). This sometimes helps a lot (e.g. it sped up one problem by a factor of 4), but sometimes it doesn't have much of an effect.

asked 16 Mar '15, 13:01

VictorSMiller's gravatar image

VictorSMiller
343215
accept rate: 0%

edited 16 Mar '15, 16:14

I am looking forward to answers from more insightful people here at OR-X. I have often ended up with (significantly) better run times if I generate and add the cuts in a pure cutting plane phase, and then afterwards change the variables to integers compared to a cut callback where cuts are added as user cuts.

(16 Mar '15, 14:10) Sune

I found the specific description of the cut pool functioning in SCIP in https://opus4.kobv.de/opus4-zib/files/1018/achterberg_tobias.pdf on pages 48 and 49. Does anyone know if this is pretty much the same thing that CPLEX does, or does CPLEX have its "secret sauce" that they don't want to reveal?

(19 Mar '15, 11:27) VictorSMiller

Are you employing a user cut callback? If not, perhaps you could add one, and use the node LP solution at the point the callback is called to guide your cut generator to a cut that is violated by the current node solution.

link

answered 16 Mar '15, 15:38

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

@PaulRubin: Yes, I am using a user cut callback. It really makes a huge difference. For example, on one problem it took about 400 seconds on my workstation with only lazy cuts, it then went down to 100 seconds with user cuts. I just found that if I changed the delta that I mentioned above to 0.15, then the problem solves in just 20 seconds. So I'll amend my comment about it not helping much.

(16 Mar '15, 16:12) VictorSMiller
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
×2

Asked: 16 Mar '15, 13:01

Seen: 1,750 times

Last updated: 19 Mar '15, 11:27

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