[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