[Scip] Transformed constraints

[michael.winkler@zib.de]

Hi,

> -1<= 2*y12 - x1 - x2 <= 0
> [logicor] <both_x1x2_a>: logicor(<t_y12>, <t_x1_neg>, <t_x2_neg>)
>
> I guess that logicor stands for "logic or", but my constraint is more
> of a "logic and" in the sense that if y12 is in the solution then both
> x1 and x2 are also part of the solution. Why an "or"?

There are many presolving steps so, it's difficult to say which one leads
to the new form of the constraint(s). But here it looks like that your
ranged row is split up in two parts, the first one -1<= 2*y12 - x1 - x2
and the second one 2*y12 - x1 - x2 <= 0. Now only consider the first part;
x1 and x2 will be replaced by their negated variable (x1_neg = 1 - x1).
Now you have 1 <= 2*y12 + x1_neg + x2_neg and you see that you can reduce
the first coefficent from two to one so the "last" form is 1 <= y12 +
x1_neg + x2_neg which is a logicor(/set cover).


> On the setppc constraint:
> [setppc] <both_x5x6_b_clq_0_0>: +<t_y56> +<t_x6_neg> <= 1;
>
> Is this derived from the same original constraint as the logicor? Why
> both? I actually included the setppc constraint in my model when I was
> starting to define it, but I dropped it later on its development as I
> thought it was redundant. I guess not :)

The constraint above is a clique - constraint, it was created out of
knapsack constraint and related to your formulation it was extracted out
of your "both_x5x6_b" constraint (as you can see by the created name).
This constraint may still be redundant as you thought(, but it's not easy
to check for redundancy).

Hope it helps you again.


Best,
Michael


> Thank you very much for your explanation Michael. I'm not programming
> with SCIP, as my rudimentary C knowledge wouldn't let me go very far
> and I'm already behind my schedule. I create an lp file and pass it to
> the standalone solver. Would you care to explain a little bit more the
> logicor constraint? In my problem, I have the following constraint
> from which I believe it comes:
>
> -1<= 2*y12 - x1 - x2 <= 0
> [logicor] <both_x1x2_a>: logicor(<t_y12>, <t_x1_neg>, <t_x2_neg>)
>
> I guess that logicor stands for "logic or", but my constraint is more
> of a "logic and" in the sense that if y12 is in the solution then both
> x1 and x2 are also part of the solution. Why an "or"?
>
> On the setppc constraint:
> [setppc] <both_x5x6_b_clq_0_0>: +<t_y56> +<t_x6_neg> <= 1;
>
> Is this derived from the same original constraint as the logicor? Why
> both? I actually included the setppc constraint in my model when I was
> starting to define it, but I dropped it later on its development as I
> thought it was redundant. I guess not :)
>
> Again, thanks in advance. I don't know where I would be in my thesis
> if not for you guys and SCIP. I was fed up by my CPLEX friends (PhD in
> OR) laughing at me for using lpsolve. ;)
>
> -------------------------------------------------
> Julio Rojas
> jcredberry at gmail.com
>
>
>
> On Fri, May 14, 2010 at 2:03 AM,  <michael.winkler at zib.de> wrote:
>> Hi Julio,
>>
>>> [logicor] <both_x1x2_a>: logicor(<t_y12>, <t_x1_neg>, <t_x2_neg>);
>>> [setppc] <both_x5x6_b_clq_0_0>: +<t_y56> +<t_x6_neg> <= 1;
>>>
>>> The second one, I think the presolver took it by decomposing another
>>> constraint in two. But the first one, I don't have a clue of what it
>>> means.
>>
>> Yes, the presolver extracted the second constraint out of another. The
>> first one is an upgraded special linear constraint.
>>
>>> Can somebody care to explain what "logicor" and "setppc" mean?
>>
>> "setppc" and "logicor" constraints are a special type of linear
>> constraints containing only binary variables and as coefficients and
>> right
>> hand side and/or left hand side only ones.
>>
>> "setppc" comprises three subtypes,
>>
>> set partitioning: sum_i^n x_i = 1
>>
>> set packing: sum_i^n x_i <= 1
>>
>> set cover: sum_i^n x_i >= 1
>>
>> "logicor" constraints looks like set cover constraints, but are handled
>> differently inside SCIP.
>>
>>> Is there a way to directly include this kind of constraints using the
>>> standalone solver?
>>
>> Do you mean that if the standalone solver is able to read these kind of
>> constraints in the format above? Then now, SCIP is not able to read this
>> format (CIP format) directly, but we are working on it and hopefully it
>> will be possible to read this format after our next release. But you can
>> easily write these kinds of constraints as (normal) linear constraints
>> (e.g. in lp format) and SCIP will recognize and upgrade them to their
>> special linear contraint types.
>> ( If you are programming with SCIP, you can call
>> SCIPcreateConsLogicor/SCIPcreateConsSetpart/SCIPcreateConsSetpack/SCIPcreateConsSetcover
>> to directly create these special types of constraints. See more at
>> http://scip.zib.de/doc/html/index.html )
>>
>> Hope that helps you a little bit, have fun.
>>
>> Best regards,
>>
>> Michael
>>
>>
>>> Dear all, I'm really new to linear optimization in general and binary
>>> integer programming in particular. I mostly use very simple models for
>>> clustering and bundling problems. In one of them I see that there are
>>> some transformed constraints after the presolver passes by:
>>>
>>> [logicor] <both_x1x2_a>: logicor(<t_y12>, <t_x1_neg>, <t_x2_neg>);
>>> [setppc] <both_x5x6_b_clq_0_0>: +<t_y56> +<t_x6_neg> <= 1;
>>>
>>> The second one, I think the presolver took it by decomposing another
>>> constraint in two. But the first one, I don't have a clue of what it
>>> means. Can somebody care to explain what "logicor" and "setppc" mean?
>>> Is there a way to directly include this kind of constraints using the
>>> standalone solver?
>>>
>>> Thanks in advance for your help. Best regards.
>>> -------------------------------------------------
>>> Julio Rojas
>>> jcredberry at gmail.com
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de
>>> http://listserv.zib.de/mailman/listinfo/scip
>>>
>>
>>
>