[Scip] Transformed constraints

[Julio Rojas]

Thank you guys. I was just curious on the reformulation of the
problem. Now I understand a little bit better. As I told you before,
I'm not even close to a novice in integer optimization. I work with
fuzzy sets and was trying to solve a clustering problem with fuzzy
distances (edges values).

I would like to another question, is it possible to solve quadratic
problems with SCIP? Or do I have to reformulate it in a linear way?

And finally, a little of off topic question, do you know of any
standalone solver for multiobjective integer programming? I would like
to solve another problem in a multiobjective way?

Best regards to you all, keep the good work up.
-------------------------------------------------
Julio Rojas
jcredberry at gmail.com



On Fri, May 14, 2010 at 12:17 PM, Timo Berthold <berthold at zib.de> wrote:
> Hi Julio.
>
>> -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"?
>
> Well, in optimization as well as in real life, logic sometimes depends on the
> point of view. ;-)
> Maybe you noticed, that you x_1 and x_2 appear with the suffix _neg, which
> stands for negated. For a binary variable, the negation is defined as x_neg =
> 1-x. Hence, x_neg is "true", if x is "false" and vice versa.
>
> logicor(<t_y12>, <t_x1_neg>, <t_x2_neg>) now says that y_12 is true, or x1 or
> x2 is false, which is a (tighter) reformulation of
> -1<= 2*y12 - x1 - x2
>
>
>> On the setppc constraint:
>> [setppc] <both_x5x6_b_clq_0_0>: +<t_y56> +<t_x6_neg> <= 1;
>
> This comes from the clique partitioning of knapsack constraint. For a small
> example, see, e.g., http://scip.zib.de/doc/html/FAQ.html#Q16
>
> a knapsack is a constraint of the form \sum_{i} a_i x_ i \leq b, with a_i and
> b being positive integers and x_i binary variables.
> I guess that the right part of your constraint gets upgraded to a knapsack in
> the following way:
> 2*y12 - x1 - x2 <= 0
> <=> 2*y12 -(1-x1_neg) -(1-x2_neg) <= 0
> <=> 2*y12 +x1_neg+x2_neg <= 2
> which gives *exactly* the example linked above (with y12 playing the role of
> x3).
>
> Does all the presolving reformulation cause any hassles to you or are you just
> keen to understand what is happening?
> In the first case, we could give you some tips how to avoid them, in the later
> case I also recommend to have a look at Tobias Phd thesis:
> http://opus.kobv.de/tuberlin/volltexte/2007/1611/pdf/achterberg_tobias.pdf
>
>> 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 :)
>
> Just see it as an advantage, that solvers like SCIP or Cplex are often able to
> detect these information on their own. :-)
>
>> Again, thanks in advance.
>
> Always welcome.
>
> Cheers,
> Timo
>
>> 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/SCIPcre
>> >ateConsSetcover 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
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>>
>