[Scip] Eliminating model constraints following branching

Stephen J Maher stephen.maher at unsw.edu.au
Mon Feb 18 02:03:38 MET 2013


Hi Ambros,

Thanks for your email. I appreciate the fast reply.

You are right, I am adding the LP relaxation of the constraints to the 
problem. I am solving the LP at the root node using column-and-row 
generation, which involves adding model constraints throughout the 
solution process using a row generation procedure. Row generation also 
occurs during the branch-and-bound process, to ensure that the dual 
bound is correct.

What I would like to do is solve the root node to LP optimality using 
column-and-row generation, then remove all the added constraints and use 
column-and-row generation to solve each node in the branch-and-bound 
tree. So, deleting the constraints may not be required, but making them 
inactive in some way might work.

The removable flag won't help me in this case, since I would like to 
dictate when the constraints are removed and added to the problem.

Would it be possible to use the SCIPdisableCons() and SCIPenableCons() 
functions to achieve my desired result?

I appreciate your help.

Cheers,

Steve



On 16/02/13 02:19, Ambros Gleixner wrote:
> Hi Steve,
>
>   > During the solution process, some of these constraints are
>   > added to the problem.
>
> precisely speaking you probably mean "the LP relaxation of some of these
> constraints are added to the problem", right?
>
> You can use the SCIP method SCIPdelConsLocal() to disable the
> constraint's separation, enforcing, and propagation capabilities at the
> current node and all subnodes.
>
> I think you cannot directly force the corresponding rows to be removed
> from the LP.  If I understand you correctly, this is what you would want
> to do, right?  Can you tell us more about your motivation for this?  Are
> they redundant after the branching decision you make?
>
> If you declare the constraints as "removable" when creating them, their
> LP relaxation will be subject to ageing, i.e., they are removed if they
> are not tight for some time.  By playing with the advanced parameter
> lp/rowagelimit you can control how aggressively this is applied.  Maybe
> this can achieve the desired effect?
>
> Are the constraints from a specific constraint handler?
>
> Hope that helps, let us know!
>
> Ambros
>
>
>
>
> Am 15.02.2013 04:40, schrieb Stephen J Maher:
>> Hi all,
>>
>> I was just wondering whether it was possible to locally remove models
>> constraints from a node when the branching decisions are made. My goal
>> is to reduce the size of my problem by removing model constraints for
>> each subproblem that is created in the branch-and-bound tree.
>>
>> At the moment I start the model with only a subset of all constraints
>> initially included in the LP. This is done by setting the initial flag
>> to false. During the solution process, some of these constraints are
>> added to the problem. When branching is performed, I would like to
>> remove the constraints that were added and start the solving again.
>>
>> You help is appreciated.
>>
>> Cheers,
>>
>> Steve
>>
>


More information about the Scip mailing list