[Scip] 'Diving' Heuristic with Separating Constraints

Mon Nov 11 11:57:38 CET 2013

Hi Matthias,

I'm happy to hear that the heuristic works well.

Unfortunately, it is currently not possible to call separation at a
probing node, but we are working on that. What you can do is add new
constraints to a probing node (or also gobally). But for this, you would
have to make the separation method available by an external interface
which you can call during probing and which then adds the cuts as linear
constraints instead of rows.

On the other hand, I would recommend to try the sub-SCIP approach. You
just need to implement the copy callbacks for your constraint handler
(if you didn't already). Have a look at heur_rens.c to see how a
heuristic creates a sub-SCIP and get the solution out of it in the end.
The copy is normally not too expensive. SCIP actually measures the time
for copying and prints it at the beginning of the statistics together
with he number of copies and maximum copy time, e.g.,
>   copying          :       0.21 (20 #copies) (minimal 0.01, maximal
> 0.02, average 0.01)
Of course, the time depends on how large your problem is and how many
cuts need to be copied, and of course also how often you want to run
your heuristic, but if you solve LPs and separate cuts in your
heuristic, the copy time should normally not make a big difference.
By the way: in debug mode, there are a lot more memory checks, which
slow down in particular the freeing of the sub-SCIP, so you should check
the copy time in optimized mode.

Best,
Gerald

On 06.11.2013 16:26, Matthias Rost wrote:
> 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
>
>