[Scip] Eliminating model constraints following branching

[Gerald Gamrath]

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
>>