[Coin-contest] Cut generators etc

Mon Feb 10 14:09:06 EST 2003

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

Two flavors of cuts come to mind: (1) established (to the point of being in
commercial solvers) and (2) promising cuts in the literature (that aren't
known to be used by commercial solvers).

For Category 1, the ISMP2000 presentation of Zonghau Gu which reported
experience on the impact of individual cuts on big test sets is a good
reference point. I don't have his presentation, but this is similiar:
http://faculty.smu.edu/barr/ip/01ipBixby.PDF.

Cut Family  Impact
----------  ------
Gomory       114%
Covers        56%,
MIR           56%
Flow Covers   41%
Disjunctive   17%
GUB covers    14%
Path           0%
Implied       -1%
Cliques       -3%

(Keep in mind this is the impact of _individual_ cuts. Computational
experience has shown that one type of cut can help another type of cut get
a toe-hold in the problem, and these results don't report on the impact of
cuts together.)

COIN-OR already has Gomory and Knapsack Covers. (The COIN-OR Knapsack Cover
Cuts aren't full-strenth. They need better lifting heurisitics, and they
need capability to exploit other problem structure like SOS sets).  Among
the other candidates, the only one that might be appearing in COIN-OR soon
are cliques. Marta Eso has implemented clique cuts and in the process of
contributing them to COIN-OR.

For Category 2:
A google search on "miplib" and "cutting plane" gives eight pages of
results (and that's only the tip of the iceberg). Here's are _some_
possibilities which interest me (insert here all possible caveats here
about this list :-).

Aggregation and Mixed Integer Rounding to Solve MIPs (1998)
http://citeseer.nj.nec.com/marchand98aggregation.html

The 0-1 knapsack problem with a single continous variable (1997)
http://citeseer.nj.nec.com/marchand97knapsack.html

Lift-and-project for mixed 0-1 programming: recent progress (1999)
http://citeseer.nj.nec.com/balas99liftproject.html

Cutting Planes for Integer Programs with General Integer Variables (1998)
http://citeseer.nj.nec.com/ceria98cutting.html

Additions and comments on this list are welcome.

Robin

PS: I came across these while I was surfing around. For your interst:

Personal Perspective on the Future of Integer Programming (INFORMS2002)
http://www.isye.gatech.edu/faculty/Martin_Savelsbergh/presentations/INFORMS111902.pdf

Progress in LP-based, B&B algorithms: an exposition (circa 1998)
http://www.isye.gatech.edu/faculty/Martin_Savelsbergh/publications/ijoc12a.pdf

Preprocesssing and probing techniques for MIP problems
http://www.isye.gatech.edu/faculty/Martin_Savelsbergh/publications/ojoc6.pdf

Cutting planes in integer and mixed-integer programming (1999: survey w/o
computatinal results)
http://citeseer.nj.nec.com/marchand99cutting.html

Cutting Plane Algorithms for Mixed Integer Programming
http://www.zib.de/Optimization/index.en/node3.html#SECTION00042200000000000000

----------------------------------------------------------------------------------

Robin Lougee-Heimer
IBM TJ Watson Research Center
ph: 914-945-3032   fax: 914-945-3434
robinlh at us.ibm.com
http://www.coin-or.org

John J Forrest/Watson/IBM at IBMUS@www-124.southbury.usf.ibm.com on 01/29/2003
08:55:55 AM

Sent by:    coin-contest-admin at www-124.southbury.usf.ibm.com

To:    coin-contest at www-124.southbury.usf.ibm.com
cc:
Subject:    [Coin-contest] Cut generators etc

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

_______________________________________________
Coin-contest mailing list
Coin-contest at www-124.ibm.com
 http://www-124.ibm.com/developerworks/oss/mailman/listinfo/coin-contest