[Coin-contest] Cut generators etc

[John J Forrest]

As working with cut generators is an obvious way to enter this contest,  I
thought I would make some remarks on the current state of the generators
and point out some of their defects.  Fixing defects will definitely get
bonus points from me.

In this area it is very easy to make mistakes - normally a plus is used
instead of a minus or some such.  This has one of two results:
1) Illegal cuts are generated - often leading to better run times!  The way
to find these is to switch on the cut debugging tool in OsiRowCutDebugger
which can recognize a problem, plug in an optimal solution and then
complain if any cuts cut off this solution when they should not do so.  I
will try and increase the number of problems for which
OsiRowCutDebugger.cpp knows the solution - if anyone has solutions already
please send them to me.

2) Much harder to find are the cases where the cuts are weakened.
Personally, I would think that fixing such a bug in existing generators can
be as useful  and challenging (and should recieve as much credit in the
contest) as creating a new (and possibly buggy) cut generator.  One good
way of tracking down such bugs is to see if two equivalent problems give
same cuts e.g. turn a <= row into a >= row and switch signs.

The existing cut generators are:

CglGomory

This is fairly well tested.  There can be problems of accuracy with long
cuts, but that is the nature of the beast.  There may still be negative
bugs and I may put in one minor improvement to do with implicit integer
slacks.

CglKnapsackCover

Again this is fairly well tested.  It currently contains alternate methods
for finding covers (greedy, heuristic, exact) and alternate methods for
lifting (sequential, simulataneous).  Additional cover finding and lifting
ideas could be put in, especially those that take advantage of other
problem information such as  cliques  would be a good area for coding.

CglLiftAndProject

There are a whole cadre of lift-and-project cuts using different norms
This cut generator is an implementation of only one, the most basic one,
what is called "Norm1" in the lift-and-project literature and does not make
use of all the published lifting results.  It assumes that the user only
invokes it when appropriate. Much could be done here.  This is not very
well tested and should be made to fail gracefully when such cuts are not
applicable.

CglOddHole

This works - sort of.  I don't think it has any bugs which create false
cuts but I am fairly sure it has bugs which prevent it from creating cuts,
I found a stupid one just yesterday.  A complete re-write could be the best
way forward.

CglProbing

Probing (changing a bound on an integer variable and seeing what happens is
normally thought of as preprocessing, and not as a cut generator, however
if a continuous variable goes to a bound then you may be able to get a
disaggregation cut and if a constraint goes slack when a variable is fixed
you may be able to strengthen a coefficient in that constraint, This is
fairly solid.  It may not do as much as it should.  It can fix variables
and with the correct options do coefficient strengthening and
disaggregation. If there's any preprocessing capability/information that
would be useful for you to have for your own work, I would be glad to hear
requests. For coefficient strengthening it produces a new cut with the
strengthened coefficient (as opposed to actually changing the coefficient
in the matrix).   At the root node it might be useful to allow it to
replace the constraint -.  I may re-work cuts to make that easier.

CglSimpleRounding

This was designed as an example and I think will always be dominated by
other cuts.  It would be interesting to switch it on and see if it does
produce any cuts not generated by other generators. The  question of how to
avoid duplication of cuts and so on  is also interesting.

I will be working on making these generators faster by preselecting
promising rows and by decreasing the frequency of trying some generators.
.There is some crude coding in Simple Branch and Bound, but it needs
improvement. - this should be done as modifications to SbbCutGenerator.

Is there any extra functionality you would like to have..?

Now over to you Robin to discuss possible new cut generators.

John Forrest