[Scip] 'Diving' Heuristic with Separating Constraints

[Gerald Gamrath]

Dear Matthias,

should your heuristic at the end be included into the solving process or
do you really want to either run a complete B&B or run the diving heuristic?

Whichever you want to do, I would suggest you write a branching rule,
which does the "diving". This means, in the copy of your problem (or the
original problem, if you just want to run the heuristic), you start the
solving process, SCIP solves the LP relaxation and your constraint
handler separates constraints until no more constraints are added. SCIP
will automatically check whether the LP solution is feasible. You can
also add a heuristic plugin to the subscip which tries to construct a
feasible solution by modifying the LP solution. If the LP solution is
feasible, SCIP will automatically stop, because the problem was solved
to optimality. If not, your heuristic can stop the solving process by
calling SCIPinterruptSolve().
If no feasible solution was constructed, SCIP calls the branching rules.
If your own branching rule has the highest priority, if will be called
first, and you can branch by creating one child node in which you fix a
few variables, like for diving. After that, SCIP will select this node
as the next node to be processed, because only one node was created.
Your branching rule is incomplete, because you loose feasible (or even
optimal) solutions. Therefore, you get a wrong dual bound during solving
and SCIP will probably wrongly state that the solution that you
construct is optimal, so you cannot rely on the dual bound. But except
for that, you get the behavior that you are looking for.

Within your branching rule, you can create the child node using
SCIPcreateChild() and fix the variables at that node via
SCIPchgVarLbNode() and SCIPchgVarUbNode().
http://scip.zib.de/doc/html/scip_8h.shtml#ad2acad3baa29cfaa154e00f24ce7ed76
http://scip.zib.de/doc/html/scip_8h.shtml#abf19e0473a2fe31118fad33b48ba45ea
http://scip.zib.de/doc/html/scip_8h.shtml#a47046aeb6c243f2e1399c9bccd51c174

You could also implement the branching within your constraint handler,
if you do not want to implement a branching rule. Your constraint
handler should then perform branching within the ENFOLP callback in case
there are fractional variables. Note that your constraint handler needs
to have a positive ENFOPRIORITY in order to be called before the
branching rules. And you have to disable this during the B&B search.

Concerning your second question: If a variable is fixed, SCIP will
automatically update RHS and LHS of all constraints this variable
appears in or add the value of this variable times its coefficient as a
constant to the activity of the constraint. Therefore, it would be wrong
if you would reduce the RHS of "x + 4y <= 9" to 5 after fixing y to 1.
Is that what you wanted to do or do you want to change LHS and RHS based
on decisions taken on variables which are not present in the constraint?
In the latter case, you should definitely not weaken LHS and RHS during
the solving, because this can invalidate presolving steps taken and dual
bounds computed. Tightening them should probably work, but you should
run your code in debug mode to check that no assert comes up.

Best,
Gerald

On 05.09.2013 23:28, Matthias Rost wrote:
> 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
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip