[Scip] Eliminating model constraints following branching

Wed Feb 20 19:30:07 MET 2013

Dear Steve,

no, I fear there is no way to force the cleanup yourself. Another thing
worth noticing is that only those rows can be removed, which were
previously added at this node. Other rows cannot be removed, since they
are already contained in some basis information of other nodes.

Best,
Gerald

On 20.02.2013 02:22, Stephen J Maher wrote:
> 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
>>