wiki:CglProbing

Version 2 (modified by anonymous, 13 years ago) (diff)

--

CglProbing

Contributor: John J. Forrest
Maintainer: John J. Forrest, jjforre@…

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 - we think Robin Lougee-Heimer has a copy!

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 it is

generated.

  • 4) Similarly we can generate implied disaggregation cuts

Note - differences to cuts in OSL.

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

The mode options are:

  • 0) 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.

  • 2) Look at all integer variables, using current bounds.

Probing will be done on all