Skip to content

CglProbing

Jump to bottom
Stefan Vigerske edited this page Mar 9, 2019 · 2 revisions

Contributor: John J. Forrest (@jjhforrest)

Maintainer: Lou Hafer (@LouHafer)

This is a simplification of probing ideas put into OSL about ten years ago. The only known documentation is a copy of a talk handout - Lou Hafer has one, and Robin Lougee might have one!

For selected integer variables (e.g. unsatisfied ones) the effect of setting them up or down is investigated. Setting a variable up may in turn set other variables (continuous as well as integer). There are various possible results:

  1. It is shown that the problem is infeasible (this may also be because the objective function or reduced costs show worse than best solution value). If the other way is feasible we can generate a column cut (and continue probing), otherwise we can say that the problem is infeasible.

  2. If both ways are feasible, it can happen that

    • 2.1) setting x to 0 implies that y must be set to 1 and
    • 2.2) setting x to 1 implies that y must be set to 1 yielding again a column cut. (2.2 is not done in this code as there is no mechanism for returning the information.)

    More common is that

    • 2.3) setting x to 0 implies that y must be set to 1 and
    • 2.4) setting x to 1 implies that y must be set to 0 so we can substitute for y which might lead later to more powerful cuts.

  3. When setting x to 1, a constraint went slack by c.
    We can tighten the constraint ax + .... <= b (where a may be zero) to (a+c)x + .... <= b. If this cut is violated then is generated.

  4. Similarly we can generate implied disaggregation cuts.

Note - differences to cuts in OSL:

  • OSL had structures intended to make this faster.
  • The "chaining" in 2) was done
  • Row cuts modified original constraint rather than adding cut
  • This code can cope with general integer variables.

Parameters: The mode options are:

    1. Only unsatisfied integer variables will be looked at. If no information exists for that variable then probing will be done so as a by-product you "may" get a fixing or infeasibility. This will be fast and is only available if a snapshot exists (otherwise as 1). The bounds in the snapshot are the ones used.
    1. Look at unsatisfied integer variables, using current bounds. Probing will be done on all looked at.
    1. Look at all integer variables, using current bounds. Probing will be done on all.

References:

  • Probing is more typically thought of as a pre-processing technique than a cut. For a short description of probing, see E. Johnson, G. Nemhauser, and M. Savelsbergh, Progress in Linear Programming Based Algorithms for Integer Programming: An Exposition, INFORMS Journal on Computing, 12(1), Winter 2000. (An early version can be found here.)
  • For a more complete exposition, see M. Savelsbergh, Preprocessing and Probing Techniques for Mixed Integer Programming Problems, ORSA Journal on Computing 6(4), Fall 1994. (An early version can be found here.)
Clone this wiki locally