[Scip] Eliminating model constraints following branching

[Ambros Gleixner]

Hi Steve,

Am 18.02.2013 23:27, schrieb 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?

yes, you could catch the event SCIP_EVENTTYPE_ROWDELETEDLP, see 
http://scip.zib.de/doc/html/EVENT.shtml in the documentation.

> Also, if the rows are
> removed, will that affect column generation when a new column has a
> non-zero element in a removed row?

Since only non-tight rows are removed, their dual multipliers should be 
0, so the reduced costs remain unchanged.

Best regards,
Ambros


> 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
>>
>>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>

-- 
____________________________________________________________
Ambros M. Gleixner
Zuse Institute Berlin - Matheon - Berlin Mathematical School
http://www.zib.de/gleixner