[Scip] 'Diving' Heuristic with Separating Constraints

[Gerald Gamrath]

Hi Matthias,

I thought about your application again and I fear that it would be much
more complicated to do it in the probing mode than I first thought.
There is no separation loop for a probing node, so adding the
constraints globally would not work, because the at the probing nodes,
no separation is performed and the rows corresponding to the new
constraints will not be separated into the LP. Also adding them locally
will not work directly, but you would need to create new probing nodes
after each seaparation to add the constraints to and I'm not even sure
this would work.

Thus, I strongly recommend that you use the copy functionality of SCIP
and run your heuristic as a sub-SCIP. Also there, you could try to
transfer the added constraints back to your original SCIP instance after
solving the sub-SCIP.

Alternatively, you could also use the diving mode of SCIP. This runs on
the LP only, you can modify it by adding rows and changing bounds,
re-optimize the LP, and iterate. You could even add the rows to the
global cut pool, such that they are automatically checked and added
during separation at "normal" branch-and-bound nodes.

Still, I would recommend creating a copy, because this would mean that
also other general heuristics are run, domain propagation is performed,
and much more, which is not done during diving.

Best,
Gerald

On 11.11.2013 17:30, Matthias Rost wrote:
> Dear Gerald,
>
> I think I will opt for adding linear constraints, as my separation
> procedures are already externally available
> for multi-threading purposes.
>
> As I would only generate constraints that globally hold, I think that
> including them via linear constraints might
> indeed amortize with respect to the time saved at later (non-probing)
> branch-and-bound nodes.
>
>
> Considering the parameters to create linear constraints, can you
> provide feedback, whether the
> following settings are correct:
>
> a)     simple ones:
>             initial, separate, enforce, check,propagate=TRUE
>             modifiable=FALSE
>
>
> b)     locality:
>             local=FALSE,
>             dynamic=TRUE
>             removable=FALSE
>             stickingatnode=FALSE
>
>
> Does setting dynamic with disabling removable make sense? How and when
> does SCIP decide to remove a constraint?
> What does age actually mean? Is it the number of consecutively LP
> iterations that a constraint is not tight?
>
> I guess that setting local=TRUE will only add the constraint to the
> node and all its children, such that cuts found during
> the probing will never be added to the 'main' LP?
>
> Thank you,
> Matthias
>
>
> On 11/11/2013 11:57 AM, Gerald Gamrath wrote:
>> 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
>>>
>