[Scip] Non-binding inequalities

[Michael Winkler]

On 05/02/14 15:30, Gerald Gamrath wrote:
> Hi Stefan,
>> thanks for your reply. I think you already answered the main part of
>> my question, which is - given a redundancy free system of constraints
>> - those parallel to the objective function are ignored. This is a
>> thing in the presolving phase which is on by default, right?
> yes, removing constraints parallel to the objective function is turned
> on by default.

To be more precise, parallel constraints are detected and they will not
enter the LP but provide SCIP with a upper or lower bound. Such
constraint will be propagated and a solution must also fulfill such
constraint.

Best, Michael

>> Basically I'm curious if, as a general rule of thumb, I can use the
>> following for creating a B&C solver with SCIP:
>>
>> 1. SCIPincludeConshdlrLinear(scip)
>> 2. Add all model constraints (without redundancies) with
>> SCIPcreateConsLinear(...) (I only have linear constraints)
>> 3. Add constrainthandlers for facets (I used SCIPincludeConshdlrBasic
>> and implemented a routine for SCIPsetConshdlrSepa)
>>
>> This is what I extracted from the TSP / LOP example code and
>> experimenting a bit to get the best performance I can get.
>> In my mind this looks like the straightforward approach, but may be a
>> misuse of what SCIP actually was designed for.
> This approach is totally fine. In the TSP example, the subtour
> constraint handler creates model constraints during separation and it
> needs to be a constraint handler because the "nosubtour" property needs
> to be checked for solution candidates.
>
> However, if you use 3. only in order to tighten the LP relaxation and
> the constraints added in 2. suffice to decide whether a given integer
> solution is feasible or not, you could also use a separator instead of a
> constraint handler. A constraint handler is more complex and can do a
> lot of things which other specialized plugins can do as well
> (separation, propagation, presolving). Originally, the idea was that the
> constraint handler can do some structure-specific things for its type of
> constraints (e.g., cover inequalities for knapsack constraints). Since
> you do not have any constraints of your new constraint handler, I would
> prefer to implement this as a separator, but I wouldn't call it a misuse
> of SCIP if you implement it as a constraint handler (and it might allow
> you to extend the constraint handler later and add some problem-specific
> propagation, for example).
>
> Best,
> Gerald
>
>> Yours,
>> Stefan
>>
>>
>> 2014-02-05 Gerald Gamrath <gamrath at zib.de>:
>>> Hi Stefan,
>>>
>>> what do you mean with "non-binding" and what do you mean with "allow to
>>> ignore"?
>>>
>>> SCIP does a presolving phase before the actual solving process and will
>>> remove some redundant constraints there. However, already doing a
>>> pairwise comparison of constraints is quite expensive, so SCIP will not
>>> detect if a constraint is implicitly fullfilled due to two or more other
>>> constraints. However, all constraints lead to tightening of variable
>>> bounds and those are of course also taken into account when computing
>>> activity bounds while looking for redundant constraints. Moreover,
>>> constraints which are parallel to the objective function are removed
>>> from the problem and added as a cutoff or lower bound.
>>>
>>> There is a lot more, if you tell us what exactly you mean are looking
>>> for, we can tell you whether this is automatically done or if you can
>>> turn it on with a parameter.
>>>
>>> Best,
>>> Gerald
>>>
>>> On 05.02.2014 13:43, Stefan Lörwald wrote:
>>>> Hi,
>>>>
>>>> I'd like to know if there is an option to ignore non-binding
>>>> inequalities provided with "SCIPcreateConsLinear" /
>>>> "SCIPincludeConshdlrLinear(scip)". That is, does SCIP allow to ignore
>>>> inequalities that are provably non-binding because of the objective
>>>> function? Is it perhaps enabled by default?
>>>>
>>>> yours,
>>>> Stefan
>>>> _______________________________________________
>>>> 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