[Scip] 'Diving' Heuristic with Separating Constraints

[Matthias Rost]

Dear Gerald,

first, thank you for your detailed answer.

Following your idea to use a branching rule to guide the dive, I have
now implemented the stand-alone diving heuristic:
Each time the branching rule is called, it generates a single child.
Once no more candidate branchings exist, the branching rule tries to generate a
feasible solution.

As this heuristic works quite nice, I would now like to include the
heuristic into the main solver, such that it can be executed during the B&B process.

Reusing the exisiting code, I would need to create a subscip instance, which
contains a full copy of the current node's state (including the
constraint handler enforcing the separation procedures).

As I have never dealt with creating a subscip instance before and as I
guess, that the setup time to 'copy' rows and variables is quite large, I'd
still like to circumvent this by using SCIPstartProbing instead:

Is it possible to call SCIPaddCut on a probing node?
(Afer all, the generated cuts are globally valid)

If calling SCIPaddCut is not allowed, can I introduce further
constraints in some other way, such that these are included, when I call SCIPsolveProbingLP?

Best regards,
Matthias Rost

On 09/09/2013 06:54 PM, Gerald Gamrath wrote:
> 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