[Scip] 'Diving' Heuristic with Separating Constraints
Matthias Rost
mrost at zedat.fu-berlin.de
Thu Sep 5 23:28:42 MEST 2013
Dear SCIP-Community,
I have developed a MIP which uses a number of linear constraint as well
as a single constraint handler to separate an exponential number of
constraints.
While the MIP generally works great, I want to develop a simple
stand-alone heuristic apart from the B&B approach. The heuristic's
outline is as follows:
1. Solve LP relaxation
2. Separate exponential number of constraints (goto 1 if constraints
were added)
3. Try to construct a feasible solution and terminate if one was found
4. Fix few Variables
goto 1
While this prototypically resembles diving heuristics, I learnt that
diving heuristic's SCIPsolveDiveLP does not separate the constraints.
As the constraints modeled by the constraint handler are essential for
obtaining meaningful LP relaxations to guide the dive, my main question
boils down to:
How can I implement the above scheme without setting up and initializing
new SCIP copies after step 4? This is essential as the number of
separated inequalities is quite large and re-separating these just makes
no sense as they are still valid after fixing variables.
Secondly, during the diving process I'd like to change the RHS / LHS of
linear constraints to account for resource utilization. Is it possible
to adapt these values using SCIPchgLhsLinear (assuming that I stored the
SCIP_CONS pointer when calling SCIPcreateConsLinear(..))?
Note that I am not restricted to using the heuristic plugin interface
provided by SCIP as the heuristic shall be called only once (at the root).
With highest regards for you exceptional work,
Matthias Rost
More information about the Scip
mailing list