[Scip] Eliminating model constraints following branching

[Stephen J Maher]

Hi Gerald,

The constraints that I am adding are linear constraints. I do not want 
to remove all of the constraints, but only the ones that are not useful 
in the optimal solution. I would like to be able to remove the 
constraints and then add them back if necessary.

I will have a look at using the removable flag and see if I can achieve 
the desired result. I will also try setting the parameters 
lp/cleanuprows and lp/cleanuprowsroot to TRUE. In this regard, is it 
possible to know what rows SCIP has removed? Also, if the rows are 
removed, will that affect column generation when a new column has a 
non-zero element in a removed row?

Thanks a lot for your comments,

Steve



On 18/02/13 23:24, Gerald Gamrath wrote:
> Hey Steve,
>
> the constraints that you add during solving, are those linear
> constraints, some constraints of your own constraint handler, or just
> rows (added by your own constraint handler)?
>
> If it's constraints, you could use SCIPdisableCons() (which disables it
> at the current node and its subtree) or even SCIPdelCons(), which
> globally deletes the constraint (which you want to do, as you want to
> remove it at the root node). This should be more efficient, because the
> other variant cannot really delete the constraint, since it can be
> re-enabled later.
>
> However, I'm not so sure whether you really should remove all
> constraints, normally, you should keep tight ones and only throw away
> those that are "redundant" with respect to the current LP solution. Is
> there any specific reason why you want to remove all of them?
>
> If you just want to remove the rows (to keep your LP small), you should
> try to work with the removable concept of SCIP. As Ambros already
> mentioned, you can define the age limit after which a row leaves the LP
> and moreover, you can set lp/cleanuprows and lp/cleanuprowsroot to TRUE
> which means that all rows which are not tight are removed from the LP
> after the processing of the root / another node was finished.
>
> Best,
> Gerald
>
> Am 18.02.2013 02:03, schrieb Stephen J Maher:
>> 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
>>>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>
>