[Scip] Eliminating model constraints following branching

[Stephen J Maher]

Hi Gerald and Ambros,

Thanks a lot for your help. It has provided me with some ideas to pursue.

I would like to ask another question regarding the clean up of the LP. 
Is there a way to force the LP to clean up and remove the rows that are 
non-tight? I am just wondering whether it is possible to have any more 
control over this other than through the cleanuprows and cleanuprowsroot 
parameters.

Cheers,

Steve



On 19/02/13 21:08, Gerald Gamrath wrote:
> Hi Steve,
>
> On 19.02.2013 01:25, Ambros Gleixner wrote:
>>> 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.
>>
> That's right and if you ask for the dual multiplier of a row (or the
> corresponding constraint) which is not contained in the current LP, SCIP
> will return 0.0, so you don't need to change anything. However, you must
> add the newly created variable to the row/constraint, even if it is not
> in the LP, because it might be added to the LP later.
>
> Since you use linear constraints, you can handle these constraints just
> as if they would always be in the LP, i.e., getting dual solution
> values, adding variables, ... The constraints will automatically update
> the corresponding LP row (independent of whether it is in the LP at the
> moment). If you then use the removable rows concept of SCIP and set the
> cleanuprows parameters, SCIP automatically removes rows from the LP and
> will also add them to the LP again, if they are violated by the current
> LP solution. Nothing changes for you, you might only notice that the
> numbers in the column "rows" of the SCIP output changes.
>
> Best,
> Gerald
>
>
>>
>>> 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
>>>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>