[Coin-discuss] Implementation Issues in a SDP Cutting Plane Scheme

[Lou Hafer]

Joseph,

	At present there is no generic `cut management' capability in the
COIN or OSI libraries. I believe BCP might provide better facilities ---
hopefully one of the BCP developers will answer. Bookkeeping is a nontrivial 
problem, but perhaps you've already dealt with it.

	For constraint system and basis modification, your best bet for
sample `how to do it' code using COIN/OSI capabilities is to look in sbb.
Check SbbModel.cpp::addCuts, ::takeOffCuts.  Very roughly, there are two
issues: adding/deleting constraints from the constraint system, and
maintaining the lp basis. CoinWarmStartBasis routines are unadorned below; 
OsiSolverInterface routines are prefaced with OSI.

To add constraints:
    * Get a starting basis big enough to hold your cuts: create an empty
      basis of the appropriate capacity with a constructor and setSize(), or
      use OSI::getWarmStartBasis() and resize()
    * Add the constraints: use OSI::addRows() to place the constraints in the
      constraint system, and setArtifStatus() to augment the basis with a
      logical (slack) variable.
If you know how to build a less generic basis, consider rolling up the
structural and artificial status arrays from scratch. Various approaches are
possible, depending on how much you want to penetrate the veil around
CoinWarmStartBasis.

To delete loose constraints:
    * Use OSI::getWarmStartBasis() to grab the current basis
    * Scan the status of artificials (getArtifStatus()). Compress in place
      to remove basis entries for loose constraints. (Various possibilities,
      check the CoinWarmStartBasis routines.)
    * Delete constraints from constraint system with OSI::deleteRows().
    * Install the altered basis with OSI::setWarmStartBasis().
This sequence for deletion should work with any OSIxxx. Some OSI's (OsiClp now, 
OsiDylp within a week) maintain a notion of current basis and will update the 
basis when OSI::deleteRows() is called to remove loose constraints. (The code in 
SbbModel::takeOffCuts() works in this fashion.) This is a grey area for OSI 
behaviour.

	If this is unclear (:-) feel free to ask for clarification.
	
							Lou