[Scip] Non-binding inequalities

[Stefan Lörwald]

Hi Michael and Gerald,

thank you for answering so fast. I have no further questions regarding this.

Thanks again,
Stefan

2014-02-05 Michael Winkler <michael.winkler at zib.de>:
> 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
>