[Scip] Non-binding inequalities

[Gerald Gamrath]

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.

> 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